Problem C
Conveyor Belt Sushi

After a successful contest, all the team members from your university have gathered at your local Sushi Shop to celebrate!

At the Sushi Shop, you and your teammates sit around a long, circular conveyor belt. The chef also has a designated location on the conveyor belt. When they see you enter (at time $t=0$), the chef will begin putting sushi plates on the conveyor belt. Each second, the chef will attempt to place a new plate onto the belt in front of them. At the same time, a subset of the team members can take a sushi plate off of the belt in front of them. After that, the conveyor belt will advance all plates clockwise one seat. If a plate passes everyone without being taken, it returns to the chef the next second and makes another pass around the circle. The number of seats around the belt is one greater than the number of team members, as the chef has their own seat.

The conveyor belt is initially empty, but at time $t=0$ seconds, the chef will place the first menu plate onto the belt. At time $t=1$ second, the chef will place the second menu plate onto the belt. Each second, the chef will place the next menu plate if there is not already a plate in front of them. Once they have placed all menu plates onto the belt, they will start back at the first menu plate. If at any point there is already a plate in front of them, the chef will wait until the next opening on the belt to place the current plate.

Sample Input 1 after person 3 takes the $7 sushi plate at time $t = 6$.

The Sushi Shop has developed a smart billing system that is meant to automatically track who takes which sushi and bill them properly. However, their system is down! Can you help them figure out how to split the bill?

Input

The first line of input contains an integer, $M$ ($2 \le M \le 100$), the number of plates on the menu. The next line contains $M$ integers, each detailing the cost, $c_i$ ($1 \le c_i \le 100$), of the $i$-th plate in dollars.

The next line contains two integers, $N$ ($1 \le N \le 100$) and $E$ ($1 \le E \le 10\, 000$), the number of team members and the number of events to process.

Each of the next $E$ lines describes an event. Each event is described with two integers, $t_j$ ($1 \le t_j \le 10\, 000$) and $p_j$ ($1 \le p_j \le N$), indicating that the person $p_j$ seats clockwise from the chef takes the sushi plate in front of them off of the belt at time $t = t_j$ seconds. It is guaranteed that there is a sushi plate in front of person $p_j$.

Events are given in non-decreasing chronological order.

Output

Output $N$ lines, detailing the bill for each team member. The first line should be the person one seat clockwise from the chef. From there, work clockwise around the conveyor belt to each team member.

Explanation for Sample Input 1

At time $t=0$, the chef places a $2 plate in front of them.

At time $t=1$, the $2 plate has rotated to be in front of person 1. The chef then places the $3 plate.

At time $t=2$, persons 1 and 2 take the $3 and $2 plates from in front of them. At the same time, the chef places a $5 plate.

At time $t=3$, the chef places the $7 plate. The $5 plate is now in front of person 1.

At time $t=4$, the chef places a second $2 plate. Persons 1 and 2 have $7 and $5 plates in front of them, respectively.

At time $t=5$, the chef places a second $3 plate. Persons 1, 2, and 3 have $2, $7, and $5 plates in front of them.

At time $t=6$, the $5 plate has traveled fully around the conveyor belt. Because of this, the chef will wait for an open spot to place the next $5 plate. However, person 3 will take the $7 plate in front of them.

4
2 3 5 7
3 3
2 2
2 1
6 3

3
2
7

4
2 3 5 7
4 6
3 2
4 1
6 4
8 3
8 2
15 1

9
6
2
5