Finding a Hitting Set in a Huge Metal Grid

You are given a huge metal grid with dimensions (10^9\times10^9). Each cell is identified by its coordinates ((x,y)) where (1 \le x,y \le 10^9), with (x) counting columns from left to right and (y) counting rows from top to bottom. There are (N) burger pieces placed on the grid. The (i)th burger piece covers a rectangular area with its bottom‐left corner at ((L_i, D_i)) and top‐right corner at ((R_i, U_i)) (that is, it covers all grid cells ((x,y)) with (L_i \le x \le R_i) and (D_i \le y \le U_i)). Note that burger pieces may overlap.\n\nTo check whether every burger piece is properly cooked, you must stick bamboo skewers vertically at the center of some grid cells. Formally, you are allowed to choose exactly (K) grid cells ((x_1,y_1), \dots, (x_K,y_K)) (with (1 \le x_j,y_j \le 10^9)) such that for every burger piece (i) ((1 \le i \le N)), there is at least one skewer ((x_j,y_j)) satisfying (L_i \le x_j \le R_i) and (D_i \le y_j \le U_i). You are guaranteed that a solution exists.\n\nYour task is to output any valid set of (K) grid cells that meets the above condition.

inputFormat

The input is given in the following format:\ The first line contains two integers (N) and (K) (the number of burger pieces and the number of skewers to place).\ Each of the following (N) lines contains four integers: (L_i), (D_i), (R_i), and (U_i), describing the rectangular region covered by the (i)th burger piece.\ It is guaranteed that (1 \le L_i, D_i \le R_i, U_i \le 10^9) and that a valid set of (K) grid cells exists.

outputFormat

Output exactly (K) lines. On the (j)th line, output two integers (x_j) and (y_j) ((1 \le x_j, y_j \le 10^9)), representing the grid cell where you place a skewer. The set of (K) points must satisfy that for every burger piece (i), there exists at least one (j) with (L_i \le x_j \le R_i) and (D_i \le y_j \le U_i).

sample

2 2
1 1 5 5
4 4 10 10

5 5
1 1