Particles#8722

Particles

2 seconds

256 megabytes

Hard

Two linear particle accelerators **A** and **B**, placed opposite to each other at a distance $L$ apart, are propelling elementary particles. **A** is shooting **x-particles**, while **B** is shooting **y-particles.** The two kinds of particles are flying one opposing the other, and when an **x-particle** meets a **y-particle**, they collide and annihilate. One should be aware that an x particle could overtake other x-particles, as well as a y-particle could overtake other y-particles without any consequences for the particles.

Like so, in a given moment of time, which we assume to be zero, a shooting of $N$ **x-particles** and $N$ **y-particles** starts from the two accelerators. Each particle moves with its own constant speed. The particles are numbered in the order of their shooting from $1$ to $N$ , this holds true for both the x-particles and the y-particles.

Remark: For time $t$ , a particle with speed $v$ travels distance $s = v t$ s = vt.

The shooting time moments for the **x-particles** are $0 = t_{x_{1}} < t_{x_{2}} < t_{x_{3}} < \dots < t_{x_{N}}$ 0 = t_{x_1} < t_{x_2} < t_{x_3} < \ldots < t_{x_N}, and their speeds are $v_{x_{1}}$ v_{x_1}, $v_{x_{2}}$ v_{x_2}, $v_{x_{3}}$ v_{x_3}, ..., $v_{x_{N}}$ v_{x_N}.

Correspondingly, for the y-particles the moments are denoted by $0 = t_{y_{1}} < t_{y_{2}} < t_{y_{3}} < \dots < t_{y_{N}}$ 0 = t_{y_1} < t_{y_2} < t_{y_3} < \ldots < t_{y_N}, and their speeds by $v_{y_{1}}$ v_{y_1}, $v_{y_{2}}$ v_{y_2}, $v_{y_{3}}$ v_{y_3}, ..., $v_{y_{N}}$ v_{y_N}.

The shooting is executed in a way to guarantee the fulfillment of the following conditions:

- Each particle will collide a particle of the opposite type; - When two particles collide, all other particles will be at a distance greater than or equal to $1$ from the collision point. This is guarantee for the first $K$ collisions.

Write a program particles to determine the first $K$ collisions between particles of the two kinds.

Input

The three space separated positive integers $N$ ( $1 \leq N \leq 50000$ 1 \le N \le 50000), $L$ ( $1 \leq L \leq 1 0^{9}$ 1 \le L \le 10^9), and $K$ ( $1 \leq K \leq 100$ 1 \le K \le 100) are read from the first line of the standard input.

The following $N$ lines contain two space separated non-negative integers $t_{x_{i}}$ t_{x_i} ( $0 \leq t_{x_{i}} \leq 1 0^{9}$ 0 \le t_{x_i} \le 10^9) and $v_{x_{i}}$ v_{x_i} ( $1 \leq v_{x_{i}} \leq 1 0^{9}$ 1 \le v_{x_i} \le 10^9) each: the shooting moment and the speed of the corresponding x-particle.

The last $N$ input lines contain, respectively, each the shooting moment $t_{y_{i}}$ t_{y_i} ( $0 \leq t_{y_{i}} \leq 1 0^{9}$ 0 \le t_{y_i} \le 10^9) and the speed $v_{y_{i}}$ v_{y_i} ( $1 \leq v_{y_{i}} \leq 1 0^{9}$ 1 \le v_{y_i} \le 10^9) of the corresponding y-particle in the same format.

Output

The program must print to the standard output $K$ lines, each containing two space separated positive integers: the numbers of the **x-particle** and **y-particle**, which are involved in the corresponding collision.

Lines are output increasingly by the order of collisions – from the first one to the $K$ th.

Examples

Example 1