Рамазан は本格的な事業としてキャベツの栽培を始めることにしました。
キャベツを育てる畑は、無限に広がる格子状の畑です。各マスにはキャベツを 1 玉植えることができます。
Рамазан は畑の一部だけにキャベツを植えました。複数の長方形の区画を使う予定を立てたところ、一部の区画は重なることが分かりました。少なくとも 1 つの長方形に含まれるマスを、栽培領域に属するマスとします。
形式的には、Рамазан は $n$ 個の長方形の区画 $(x_i^L,y_i^L,x_i^R,y_i^R)$（$x_i^L\le x_i^R$、$y_i^L\le y_i^R$、$1\le i\le n$）を選びました。マス $(x,y)$ にキャベツがあるのは、$x_i^L\le x\le x_i^R$ かつ $y_i^L\le y\le y_i^R$ を満たす選ばれた長方形 $i$（$1\le i\le n$）が少なくとも 1 つ存在するときです。
Рамазан は以前プログラマー（そして優勝者）だったので、栽培領域を定期的に手入れするために人工知能を搭載したロボットを使うことにしました。1 台のロボットは任意の水平なマスの区間 $(x_1^{robot},x_2^{robot},y^{robot})$、つまり $x_1^{robot}\le x\le x_2^{robot}$ かつ $y=y^{robot}$ を満たすすべてのマス $(x,y)$ を担当できます。
ロボットが栽培領域だけを走ることが重要です。ロボットの台数を最小化するには、これ以上広げられない水平区間を使うことが重要だと彼は気付きました。Рамазан は、以下を満たすマスの区間 $(x_1^{robot},x_2^{robot},y^{robot})$ にロボットを配置します。
- $x_1^{robot}\le x\le x_2^{robot}$ かつ $y=y^{robot}$ を満たすすべてのマス $(x,y)$ が栽培領域に属する。
- マス $(x_1^{robot}-1,y^{robot})$ が栽培領域に属さない。
- マス $(x_2^{robot}+1,y^{robot})$ が栽培領域に属さない。
あなたの仕事は、農園で働くロボットについて重要な統計を集めることです。区間 $(x_1,x_2,y)$ をちょうど担当するロボットが存在するとき、組 $(x_1,x_2)$ は行 $y$ で担当されると言います。
- いずれかの行で担当されるすべての組 $(x_1,x_2)$ を求めてください。
- そのような各組 $(x_1,x_2)$ について、担当される行の数を求めてください。
- そのような各組 $(x_1,x_2)$ について、担当される連続した行の数の最大値を求めてください。言い換えると、$k$ 個の連続する行の区間 $[y_1,y_2]$（$y_2-y_1+1=k$）が存在し、$y_1\le y\le y_2$ を満たす任意の行 $y$ で組 $(x_1,x_2)$ が担当されるような、最大の $k$ を求めてください。
入力
各テストは複数のテストケースからなります。最初の行にはテストケース数を表す整数 $t$（$1\le t\le 200\,000$）が 1 つ与えられます。その後、各テストケースの説明が続きます。
各テストケースの最初の行には、選ばれた長方形の区画の数を表す整数 $n$（$1\le n\le 200\,000$）が 1 つ与えられます。
続く $n$ 行にはそれぞれ、選ばれた長方形の区画を表す 4 つの整数 $x_i^L,y_i^L,x_i^R,y_i^R$（$1\le x_i^L\le x_i^R\le 10^9$、$1\le y_i^L\le y_i^R\le 10^9$）が与えられます。
1 つのテストに含まれるすべてのテストケースの $n$ の総和を $N$ とします。$N\le 200\,000$ が保証されます。
出力
各テストケースについて、まず、いずれかの行で担当される組 $(x_1,x_2)$ の数を表す整数 $p$（$p\ge 1$）を 1 つ出力してください。
続く $p$ 行にはそれぞれ 4 つの整数 $x_1,x_2,cnt,k$（$1\le x_1\le x_2\le 10^9$、$0\le cnt,k\le 10^9$）を出力してください。$cnt$ は組 $(x_1,x_2)$ が担当される行の数と等しくなければなりません。$k$ は組 $(x_1,x_2)$ が担当される連続した行の数の最大値と等しくなければなりません。
すべての組 $(x_1,x_2)$ は互いに異なる必要があります。いずれかの行で担当される各組を、ちょうど 1 回ずつ出力してください。組は任意の順序で出力できます。
小課題
各テストケースについて、畑の幅を $w$、すなわち $w=\max_{i=1}^{n}x_i^R$、畑の高さを $h$、すなわち $h=\max_{i=1}^{n}y_i^R$ とします。
| 小課題 | 配点 | 制約：$n,N$ | 制約：$w,h$ | 追加の制約 | 必要な小課題 |
|---|---|---|---|---|---|
| 1 | 4 | $n=1$ | |||
| 2 | 8 | $h=1$ | |||
| 3 | 8 | $n\le 30$, $N\le 3000$ | $w,h\le 10$ | $t\le 100$ | 入出力例 |
| 4 | 4 | $w,h\le 5000$, $\sum wh\le 25\cdot 10^6$ | 入出力例, 3 | ||
| 5 | 8 | $N\le 3000$ | 入出力例, 3 | ||
| 6 | 4 | $N\le 10\,000$ | 入出力例, 3, 5 | ||
| 7 | 8 | すべての $[x_i^L,x_i^R]$ が交わる | 1 | ||
| 8 | 8 | $y_i^L=1$ | 2 | ||
| 9 | 8 | 長方形が互いに重ならない | 1 | ||
| 10 | 8 | 任意の $1\le i,j\le n$ と任意の $y\in[y_i^L,y_i^R]\cap[y_j^L,y_j^R]$ に対して $[x_i^L,x_i^R]\nsubseteq[x_j^L,x_j^R]$ が成り立つ | 1, 9 | ||
| 11 | 8 | すべての区間 $[x_i^L,x_i^R+1]$ は、一方が他方に含まれるか、互いに交わらない | 1 | ||
| 12 | 8 | $N\le 50\,000$ | 入出力例, 3, 5–6 | ||
| 13 | 8 | $N\le 100\,000$ | 入出力例, 3, 5–6, 12 | ||
| 14 | 8 | $N\le 200\,000$ | 入出力例, 1–13 |
- あるテストにおいて、いずれかの行で担当される組 $(x_1,x_2)$ の集合を誤って求めた場合、解答は「不正解」の判定を受けます。
小課題および必要な小課題のすべてのテストで、解答が以下を満たす場合、それぞれの配点を得ます。
- 集合を正しく求めているが、すべての $cnt$ が正しいわけではない場合、小課題の配点の $50\%$ を得ます。
- 集合とすべての $cnt$ を正しく求めているが、すべての $k$ が正しいわけではない場合、小課題の配点の $75\%$ を得ます。
- 集合、すべての $cnt$、すべての $k$ を正しく求めている場合、小課題の配点の $100\%$ を得ます。
小課題の部分点を得る場合も、各組 $(x_1,x_2)$ に対して何らかの $cnt$ と $k$ の値を出力する必要があります。ただし、これらは正しくなくても構いません。
入出力例
入力 1
4 2 2 2 3 3 3 3 4 4 2 2 1 2 3 1 2 3 2 4 2 2 4 5 3 4 9 7 2 9 9 10 7 1 9 7 7 2 1 2 9 5 1 6 8 4 5 7 6 1 8 4 10 1 6 3 6 1 2 7 3 4 1 7 1
出力 1
3 2 3 1 1 2 4 1 1 3 4 1 1 2 1 3 1 1 2 2 2 1 4 2 4 2 2 2 9 4 2 3 9 2 2 7 9 3 3 6 1 4 2 2 1 6 1 1 1 7 3 2 2 2 4 2 4 7 2 1 5 6 2 1
注記
問題文中のテストの 1 番目と 2 番目のテストケース
1 番目のテストケースでは、区間 $(2,3,2)$、$(2,4,3)$、$(3,4,4)$ にロボットを配置します。したがって、組 $(2,3)$、$(2,4)$、$(3,4)$ がいずれかの行で担当され、各組はちょうど 1 つの行で担当されます。
2 番目のテストケースでは、区間 $(2,2,1)$、$(2,4,2)$、$(2,2,3)$ にロボットを配置します。したがって、組 $(2,2)$、$(2,4)$ がいずれかの行で担当されます。組 $(2,2)$ は行 $1,3$ で担当され、組 $(2,4)$ は行 $2$ で担当されます。
問題文中のテストの 3 番目と 4 番目のテストケース