Рамазан은 본격적인 사업으로 양배추 재배를 시작하기로 했다.
양배추를 재배할 밭은 무한한 격자이다. 각 칸에는 양배추 한 포기를 심을 수 있다.
Рамазан은 밭의 일부에만 양배추를 심었다. 여러 직사각형 구역을 사용할 계획을 세웠는데, 일부 구역은 서로 겹칠 수 있다. 밭의 칸이 직사각형 중 하나 이상에 들어 있으면 재배 구역에 속한다.
정확히 말하면, Рамазан은 $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_i^L\le x\le x_i^R$ 및 $y_i^L\le y\le y_i^R$를 만족하는 선택된 직사각형 $i$ ($1\le i\le n$)가 하나 이상 존재하면 칸 $(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},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$에서 쌍 $(x_1,x_2)$가 관리되도록 하는 최대 $k$를 구하라.
입력
각 테스트는 여러 테스트 케이스로 이루어진다. 첫 번째 줄에는 테스트 케이스 수를 나타내는 정수 $t$ ($1\le t\le200\,000$)가 주어진다. 이어서 각 테스트 케이스의 설명이 주어진다.
각 테스트 케이스의 첫 번째 줄에는 선택한 직사각형 구역 수를 나타내는 정수 $n$ ($1\le n\le200\,000$)이 주어진다.
다음 $n$개의 줄에는 선택한 직사각형 구역을 나타내는 네 정수 $x_i^L,y_i^L,x_i^R,y_i^R$가 주어진다 ($1\le x_i^L\le x_i^R\le10^9$, $1\le y_i^L\le y_i^R\le10^9$).
한 테스트의 모든 테스트 케이스에 대한 $n$의 합을 $N$이라고 하자. $N\le200\,000$임이 보장된다.
출력
각 테스트 케이스에 대해, 먼저 어떤 행에서든 관리되는 쌍 $(x_1,x_2)$의 수를 나타내는 정수 $p$ ($p\ge1$)를 출력하라.
다음 $p$개의 줄에는 네 정수 $x_1,x_2,cnt,k$를 출력하라 ($1\le x_1\le x_2\le10^9$, $0\le cnt,k\le10^9$). $cnt$는 쌍 $(x_1,x_2)$가 관리되는 행의 수이다. $k$는 쌍 $(x_1,x_2)$가 관리되는 연속한 행의 최대 개수이다.
모든 쌍 $(x_1,x_2)$는 서로 달라야 한다. 어떤 행에서든 관리되는 각 쌍을 정확히 한 번 출력해야 한다. 쌍은 임의의 순서로 출력해도 된다.
서브태스크
테스트 케이스의 밭 너비를 $w=\max_{i=1}^{n}x_i^R$, 높이를 $h=\max_{i=1}^{n}y_i^R$라고 하자.
| 서브태스크 | 점수 | 제한: $n,N$ | 제한: $w,h$ | 추가 제한 | 필요한 서브태스크 |
|---|---|---|---|---|---|
| 1 | 4 | $n=1$ | |||
| 2 | 8 | $h=1$ | |||
| 3 | 8 | $n\le30$, $N\le3000$ | $w,h\le10$ | $t\le100$ | 예제 |
| 4 | 4 | $w,h\le5000$, $\sum wh\le25\cdot10^6$ | 예제, 3 | ||
| 5 | 8 | $N\le3000$ | 예제, 3 | ||
| 6 | 4 | $N\le10\,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\le50\,000$ | 예제, 3, 5–6 | ||
| 13 | 8 | $N\le100\,000$ | 예제, 3, 5–6, 12 | ||
| 14 | 8 | $N\le200\,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
참고
예제의 첫 번째와 두 번째 테스트 케이스.
첫 번째 테스트 케이스에서는 구간 $(2,3,2)$, $(2,4,3)$, $(3,4,4)$에서 로봇을 사용한다. 따라서 쌍 $(2,3)$, $(2,4)$, $(3,4)$가 어떤 행에서든 관리되며, 각 쌍은 정확히 한 행에서 관리된다.
두 번째 테스트 케이스에서는 구간 $(2,2,1)$, $(2,4,2)$, $(2,2,3)$에서 로봇을 사용한다. 따라서 쌍 $(2,2)$와 $(2,4)$가 어떤 행에서든 관리된다. 쌍 $(2,2)$는 행 $1,3$에서 관리되며, 쌍 $(2,4)$는 행 $2$에서 관리된다.
예제의 세 번째와 네 번째 테스트 케이스.