Bob the Builder loves building perfect crosses in 2-D planes — two lines where the counterclockwise angles of each line to the ~OX~-axis are exactly ~45^{\circ}~ and ~135^{\circ}~. There are ~N~ points ~(x_i, y_i)~ in the plane, and Bob would like to pick two pairs of points to draw a perfect cross. However, real-life is harsh, and it may be impossible to construct a perfect cross from the ~N~ points given. Furthermore, Bob can only access points that are within ~S~ steps from his camp location, each step one unit in an axis-aligned direction.

Let the distance between two lines be defined as the minimal absolute degree measure you need to rotate one of the lines such that both lines share the same slope. For ~Q~ queries of camp locations ~(X_j, Y_j)~, help Bob find two pairs of accessible points that are as close to a perfect cross as possible — one pair should be as close to a ~45^{\circ}~ line as possible, and the other pair closest to a ~135^{\circ}~ line. Each pair of points should consist of two distinct points, although it is allowed to use the same points for different pairs.

Constraints

~2 \le N \le 2 \times 10^5~

~1 \le Q \le 2 \times 10^5~

~1 \le S \le 10^9~

~-10^9 \le x_i, y_i, X_j, Y_j \le 10^9~

All ~N~ points are pairwise distinct.

There are at least two accessible points in each query.

Subtask 1 [20%]

~2 \le N \le 2 \times 10^3~

~1 \le Q \le 2 \times 10^3~

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains ~3~ integers ~N~, ~Q~, and ~S~.

The next ~N~ lines each contain ~2~ integers ~x_i~ and ~y_i~.

The next ~Q~ lines each contain ~2~ integers ~X_j~ and ~Y_j~.

Output Specification

For each query, output ~4~ integers on a single line: ~a, b, c, d~ ~(1 \le a, b, c, d \le N)~. These should satisfy ~a \neq b~ and ~c \neq d~.

The ~a~-th, ~b~-th, ~c~-th, and ~d~-th points must all be within ~S~ axis-aligned steps from the query location.

Furthermore, over all accessible points, the line connecting the ~a~-th and ~b~-th point should be as close to a ~45^{\circ}~ line as possible, and the line connecting the ~c~-th and ~d~-th point should be as close to a ~135^{\circ}~ line as possible.

If there are multiple such choices of points satisfying all of the properties above, any one of them will be accepted.

Sample Input

5 3 5
3 1
1 -3
1 -2
-1 2
-3 0
3 1
-1 1
5 -1

Sample Output

1 3 4 3
5 4 3 5
3 1 1 3

Explanation

Below is a diagram of the cross chosen in the first query:

Then, a diagram of the second cross. Here, an equally correct choice for the second line is marked in blue:

Finally, a diagram of the cross chosen in the third query. Since there are only two accessible points, we must choose them for both lines of the cross: