Robots

Robotics builder Daumilas has constructed $M$ robots and wants to test them in a circular arena. The arena is divided into $N$ sections, numbered $1$ to $N$ clockwise: for $1 \le i \le N-1$ section $i$ borders section $i+1$, and section $N$ additionally borders section $1$.

Each section may be left empty, or hold a single robot or a single wall (never both). Daumilas gives robot $i$ a command $a_i$. Then every robot starts moving at the same instant. Robot $i$ travels clockwise at a constant speed of one section per second for $a_i$ seconds. If stationary robots lie in its path, it pushes them forward without slowing down. A robot stops before its command is finished (before all $a_i$ seconds pass) only when it, or a robot it is pushing, comes up against a wall. Only one robot fits in a section, and robots can never pass through one another.

Determine which section each robot occupies once the simulation ends.

The first line contains three integers $N$, $M$, and $K$ — the number of sections, the number of robots, and the number of walls.

Each of the next $M$ lines contains two integers $x_i$ and $a_i$ — the starting section of robot $i$ and its command.

The last line contains $K$ integers $y_i$ — the section of each wall (this line is empty when $K = 0$).

Robots and walls are each listed in increasing order of section, and all listed sections are distinct.

Output $M$ integers separated by single spaces on one line. The $i$-th integer is the section occupied by the $i$-th robot (in the input order) when the simulation ends.

• $3 \le N \le 10^9$
• $1 \le M \le 2 \cdot 10^5$
• $0 \le K \le 2 \cdot 10^5$
• $M + K \le N$
• $0 \le a_i \le N - 1$
• $1 \le x_i, y_i \le N$
• Robots are given in increasing order of their starting section.
• Walls are given in increasing order of their section.
• No section holds more than one object (a wall or a robot).