VK often holds hackathons where programmers solve various problems. VK is now preparing a new hackathon in which anyone can try their hand at developing a unique and useful application or service for one of several tracks including Fintech, Culture, Media, and others.

As with any well-organized hackathon, to allow participants to fully dedicate themselves to solving the task at hand they are provided with a carefully organized venue. Pleasant bonuses often include food and drinks, which can be enjoyed over the several days that participants spend at the venue.

This time VK is organizing a new hackathon, and $m$ participants have gathered at the venue. For these $m$ participants the organizers have ordered $n$ pizzas which are arranged in a row and numbered from $1$ to $n$. It is known that:

• each pizza consists of an infinite number of slices;
• the first slice of the $i$-th pizza has a dough thickness of $a_i$, and each subsequent one is $1$ thicker than the previous (i.e., $a_i + 1$, $a_i + 2$, and so on);
• the slices with the least dough thickness seem most attractive to participants;
• any participant can approach the row of pizzas at any point, but afterwards can only move left (towards the pizzas with smaller numbers) to avoid collisions with other participants.

Periodically, participants get up from their places and approach the row of pizzas to take a slice. Participant number $i$ approaches the pizza numbered $s_i$ at time $t_i$, after which they immediately find the slice of pizza with the least dough thickness among pizzas from $1$ to $s_i$ and start moving towards it. It takes each participant the same amount of time to move between two adjacent pizzas — exactly $v$ seconds. Several participants can be near the same pizza at the same time.

As soon as a participant reaches the pizza they have chosen, they take the slice and return to their seat. If several participants have chosen the same slice and reach it simultaneously, the participant with the lower number takes the slice. If the slice a participant was counting on is taken by someone else, that participant immediately chooses a new target using the same algorithm: they look at all the pizzas from the first to their current position, select the minimum among them, and start moving towards it.

Formally, this process can be described as follows. At every whole number of seconds $t$:

1. all participants who were already in the row at time $t - 1$ move by $\frac{1}{v}$ to the left;
2. all participants with $t_i = t$ approach the pizza number $s_i$;
3. time "stops";
4. all participants standing at whole positions $p$ such that $a_p = \min(a_1, a_2, \ldots, a_p)$ are identified;
5. for each such $p$, the participant with the minimum number standing at position $p$ takes the slice of pizza with thickness $a_p$ and leaves; $a_p$ is increased by $1$;
6. after some slices of pizza are taken, it may happen that the minimum thickness of the slice that some participants can still get has changed, in which case the process repeats from step 4;
7. otherwise, time "starts again" and the process moves to the next second.

Based on the information about participants' approaches to the pizzas, determine for each participant the thickness of the pizza slice they received and how much time they spent in the row.

Scoring

Points for each subtask are awarded only if all tests of that subtask and the required subtasks are successfully passed.