C. Texas-Sized Nuggets
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Everything is bigger in Texas, so of course you want your chicken nuggets to be as big as it can be — but it still has to fit on your plate.

Your chicken nugget is described by $$$n$$$ points in the plane. The $$$i$$$-th point is at integer coordinates $$$(x_i, y_i)$$$ with $$$0 \le x_i, y_i \le 10^9$$$.

You are given an integer scaling factor $$$k$$$. Scaling the chicken nugget by $$$k$$$ moves every point $$$(x_i, y_i)$$$ to $$$(k \cdot x_i,\ k \cdot y_i)$$$. You may translate the chicken nugget after it is scaled, but you may not rotate it.

The plate is an axis-aligned square whose corners are $$$(0, 0)$$$ and $$$(m, m)$$$. The scaled chicken nugget fits on the plate if it is possible to translate it in such a way that every point lies inside the square or on its boundary.

Warning: you may need to use 64 bit integers for this problem!

Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 10^{18}$$$; $$$1 \le k \le 10^9$$$).

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^9$$$) — the coordinates of the $$$i$$$-th point. Points are not necessarily distinct.

Output

If the scaled chicken nuggy does not fit on the plate, print a single line containing -1.

Otherwise print the $$$n$$$ final points of the chicken nugget after scaling and possibly translating, one per line, each as two integers $$$k \cdot x_i$$$ and $$$k \cdot y_i$$$. The points may be printed in any order.

Examples
Input
3 10 2
5 5
6 7
5 8
Output
0 0
2 4
0 6
Input
2 5 3
0 0
2 2
Output
-1
Note

In the first sample, $$$k = 2$$$, so the points scale to $$$(10, 10)$$$, $$$(12, 14)$$$, and $$$(10, 16)$$$. As they stand they poke off the $$$10 \times 10$$$ billboard, but the scaled logo is only $$$2$$$ wide and $$$6$$$ tall, so shifting it by $$$(-10, -10)$$$ places it at $$$(0, 0)$$$, $$$(2, 4)$$$, $$$(0, 6)$$$ — entirely on the billboard.

In the second sample, $$$k = 3$$$ scales the logo to a $$$6 \times 6$$$ span, which is wider than the side length $$$5$$$, so no translation can make it fit and the answer is -1.