Description

Let’s assume we are on a 1D map with coordinates ranging from 0 to 1e9.
There are $N$ portals and $M$ people who want to travel from one coordinate to another using the portals.

Each person begins at a specific starting coordinate and wants to travel to a specific destination.
For each person, you must find the nearest portal to their starting location and the nearest portal to their destination.

• If there are two portals equally close, choose the one with the smaller coordinate.
• If the nearest start and destination portals are the same, or if the total walking distance to reach the portals is greater than or equal to the direct walking distance from the start to the destination, the person will walk instead.
• Once a portal is used by person i, it is no longer available to any person after them.

Input

The first line contains two integers $N$ and $M$, representing the number of portals and the number of people.

The second line contains $N$ distinct integers $c_1, c_2, \dots, c_N$, where each $c_i$ is the coordinate of a portal.
It is guaranteed that all portals are located at distinct coordinates.

The next $M$ lines each contain two integers $s_i$ and $d_i$, representing the starting and destination coordinates of the $i$-th person.

Constraints
$1 \leq M \leq N \leq 2 \times 10^5$
$1 \leq c_i \leq 10^9$
$1 \leq s_i \leq d_i \leq 10^9$

Subtask

1. (Test cases 1–3) $1 \leq N, M \leq 1000$
2. (Test cases 4–6) No additional constraints.

Output

Output $M$ lines. For each person, output one of the following:

"walk", if walking is better or the start and the destination portals are the same.

Two integers — the coordinates of the nearest portal to the starting location and the nearest portal to the destination.

Sample Input  Download

Sample Output  Download

Tags

Discuss