18840번 - Hamburg Steak 서브태스크스페셜 저지다국어

Have you ever heard of Just Odd Inventions, Ltd.? This company is known for their “just odd inventions.” We call it JOI, Ltd. in this problem.

A new year party is being held in JOI, Ltd. The staff is baking N hamburg steaks on a huge wire mesh. We consider the wire mesh as a 1 000 000 000 × 1 000 000 000 grid. We denote by (x, y) the cell in the x-th column from the left and the y-th row from the bottom (1 ≤ x ≤ 1 000 000 000, 1 ≤ y ≤ 1 000 000 000)

Hamburg steaks are numbered from 1 to N. The Hamburg steak i (1 ≤ i ≤ N) is place on the rectangular area whose left-bottom vertex is (L_i, D_i) and right-top vertex is (R_i, U_i). It is possible that the Hamburg steaks overlaps.

You are a new employee of JOI, Ltd. Your task is to choose K cells on the wire mesh and stick bamboo skewers at the center of the cells perpendicularly to the wire mesh. For each hamburg steak, you can confirm how it is cooked by sticking at least one bamboo skewer at a cell on it. You need to confirm all the hamburg steaks. You are allowed to stick more than one bamboo skewer at a cell. You are also allowed to stick a bamboo skewer at a cell where no hamburg steak exists.

Formally, your task is to find a tuple of (not necessarily distinct) K pairs of integers (x₁, y₁), . . . , (x_K, y_K) satisfying the following condition:

• For every i (1 ≤ i ≤ N), there exists j (1 ≤ j ≤ K) such that both L_i ≤ x_j ≤ R_i and D_i ≤ y_j ≤ U_i hold.
• For every j (1 ≤ j ≤ K), both 1 ≤ x_j ≤ 1 000 000 000 and 1 ≤ y_j ≤ 1 000 000 000 hold.

Write a program which, given the positions of the hamburg steaks and the number of bamboo skewers, calculates one way to stick the bamboo skewers. For the input data given for this task, it is guaranteed that there exists a tuple of cells satisfying the above conditions.

Read the following data from the standard input. All the values in the input are integers.

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

Write K lines to the standard output. In the j-th line (1 ≤ j ≤ K), output x_j and y_j, separating them by a space.

If there are more than one way to stick the bamboo skewers satisfying the conditions, output any of them.

• 1 ≤ N ≤ 200 000.
• 1 ≤ K ≤ 4.
• 1 ≤ L_i ≤ R_i ≤ 1 000 000 000 (1 ≤ i ≤ N).
• 1 ≤ D_i ≤ U_i ≤ 1 000 000 000 (1 ≤ i ≤ N).
• There exists a tuple of K cells satisfying the conditions in the problem statement.