햄버그 스테이크

Just Odd Inventions, Ltd.라는 회사를 들어 본 적이 있나요? 이 회사는 "just odd inventions"로 유명합니다. 이 문제에서는 이 회사를 JOI, Ltd.라고 부릅니다.

JOI, Ltd.에서 새해 파티가 열립니다. 직원들은 거대한 철망 위에서 햄버그 스테이크 N개를 굽고 있습니다. 철망은 1 000 000 000 × 1 000 000 000 격자로 봅니다. 칸 $(x, y)$는 왼쪽에서 $x$번째 열, 아래에서 $y$번째 행을 뜻하며, $1 \le x \le 1\,000\,000\,000$, $1 \le y \le 1\,000\,000\,000$입니다.

햄버그 스테이크는 1번부터 N번까지 번호가 붙어 있습니다. 햄버그 스테이크 $i$ ($1 \le i \le N$)는 왼쪽 아래 꼭짓점이 $(L_i, D_i)$, 오른쪽 위 꼭짓점이 $(R_i, U_i)$인 직사각형 영역에 놓여 있습니다. 햄버그 스테이크끼리 겹칠 수 있습니다.

당신은 JOI, Ltd.의 신입 사원입니다. 철망에서 K개의 칸을 골라, 각 칸의 중심에 대나무 꼬치를 철망에 수직으로 꽂으세요. 햄버그 스테이크 영역 안의 칸에 꼬치를 하나 이상 꽂으면 그 스테이크가 어떻게 익었는지 확인할 수 있습니다. 모든 스테이크를 확인해야 합니다. 한 칸에 꼬치를 여러 개 꽂아도 되고, 스테이크가 없는 칸에 꽂아도 됩니다.

형식적으로 말하면, 다음 조건을 만족하는 정수 쌍 K개 $(x_1, y_1), \dots, (x_K, y_K)$ (서로 같을 수도 있음)를 찾으세요.

• 모든 $i$ ($1 \le i \le N$)에 대해 $L_i \le x_j \le R_i$이고 $D_i \le y_j \le U_i$인 $j$ ($1 \le j \le K$)가 존재한다.
• 모든 $j$ ($1 \le j \le K$)에 대해 $1 \le x_j \le 1\,000\,000\,000$이고 $1 \le y_j \le 1\,000\,000\,000$이다.

입력은 다음 형식으로 주어집니다.

N K
L1 D1 R1 U1
L2 D2 R2 U2
...
LN DN RN UN

K줄을 출력하세요. $j$번째 줄에는 $x_j$와 $y_j$를 공백으로 구분해 출력합니다. 조건을 만족하는 방법이 여럿이면 그중 아무거나 출력해도 됩니다.

• $1 \le N \le 200\,000$
• $1 \le K \le 4$
• $1 \le L_i \le R_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
• $1 \le D_i \le U_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
• 문제 조건을 만족하는 K개 칸의 조합이 존재합니다.