RT，我的最坏能被卡到 $O(nk)$ 的假做法跑得还挺快。

hack 生成器：

#include<bits/stdc++.h>
using namespace std;
int n=2000000,k=500000;
int main(){
	cout<<n<<" "<<k<<endl;
	for(int i=1;i<=400000;++i)
		cout<<1<<" "<<i*2<<" "<<i*2<<" "<<100000<<endl;
	for(int i=1;i<=100000;++i)
		cout<<2<<" "<<1<<" "<<800000<<" "<<100000-i<<endl;
	return 0;
}