Ants on a Circle

Taekhee has a circle and keeps $M$ ants that crawl around its circumference at a constant speed. Each ant is so small that its size can be ignored.

One day Taekhee marked the points that divide the circumference into $N$ ($\ge M$) equal parts and numbered them 1, 2, 3, $\ldots$, $N$ in clockwise order. Reading the point numbers clockwise gives 1, 2, 3, $\ldots$, $N$, and after point $N$ comes point 1. Then he placed the ants so that every ant stands on a different point. Each ant faces either clockwise or counterclockwise, and when Taekhee shouts "start," every ant moves in the direction it faces. The start time is 0, and from then on, exactly every 1 second, the ants arrive at the next point.

All ants move at the same speed, and when two ants meet each other, they immediately reverse direction and go back. The ants move forever, stepping on the $N$ points Taekhee marked.

Taekhee thought that, depending on the ants' initial positions and directions, some points would be stepped on relatively more often over the same amount of time. But since the ants never stop, he could not check whether such points actually exist.

At time 0, each ant is standing on its point, so every point where an ant initially stands has been stepped on 1 time at time 0, and every other point has been stepped on 0 times. Also, when two ants step on a point at the same time, that point counts as being stepped on twice at that time.

Taekhee decided he needs a program to test his hypothesis. Specifically, he became curious about the earliest time at which a point $P$ gets stepped on at least $X$ times, for several queries. For Taekhee, let us write a program that answers these queries quickly.

The first line gives the number of points on the circumference $N$ ($2 \le N \le 10^5$), the number of ants $M$ ($1 \le M \le N$), and the number of queries Taekhee is curious about $Q$ ($1 \le Q \le 10^5$).

The next $M$ lines give each ant's initial position $P_i$ and direction $d_i$. ($1 \le P_i \le N$, $d_i = 0$ or $1$)

All $P_i$ are distinct.

If $d_i = 0$, the ant moves clockwise, and if $d_i = 1$, it moves counterclockwise.

The next $Q$ lines give the queries $P$ $X$ that Taekhee is curious about. ($1 \le P \le N$, $1 \le X \le 10^9$)

This means he wants to know the earliest time at which point $P$ gets stepped on at least $X$ times.

Over $Q$ lines, output the answer to each query. The start time is 0.