P14806 [CCPC 2024 Harbin Site] 1D Galaxy

In a magical one-dimensional space, there are $n$ planets numbered from $1$ to $n$. Initially ($t=0$), the planet numbered $i$ is located at position $x_i$ with weight $w_i$ (which can be negative). In the real world, planets move under the influence of gravity, and similarly, in this one-dimensional galaxy, planets move due to attraction. However, the movement in this galaxy does not follow conventional physical laws. Specifically, for any planet in this one-dimensional galaxy, if the total weight of planets to its left is greater than the total weight of planets to its right, it moves one unit to the left at the next time step. Conversely, if the total weight on the right is greater than that on the left, it moves one unit to the right. If both sides are equal, it remains in the same position. You can assume that the planets do not physically collide, meaning they can pass through each other. Formally, let the position of the planet numbered $i$ at time $t$ ($t = 0, 1, 2, \ldots$) be $x_{i,t}$. The total weight of the planets to its left at this time is $w_{i,t}^l = \sum_{j\ :\ x_{j,t} < x_{i,t}} w_j$, and the total weight of the planets to its right is $w_{i,t}^r = \sum_{j\ :\ x_{j,t} > x_{i,t}} w_j$. The position of the planet at the next time step, $x_{i, t+1}$, is given by: $$ x_{i, t+1} = \begin{cases} x_{i,t} - 1, & w_{i,t}^l > w_{i,t}^r \\ x_{i,t} + 1, & w_{i,t}^l < w_{i,t}^r \\ x_{i,t}, & w_{i,t}^l = w_{i,t}^r \end{cases} $$ There are $q$ queries, each asking for the position of the planet numbered $i$ at a specific time $t$. Please answer these queries.

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 10^5$), representing the number of planets and the number of queries, respectively. The $i$-th of the next $n$ lines contains two integers $x_i, w_i$ ($-10^9 \le x_i, w_i \le 10^9$), representing the initial position and weight of the planet numbered $i$. The following $q$ lines each contain two integers $t$ and $i$ ($0 \le t \le 10^9$, $1 \le i \le n$), representing a query.

Output $q$ lines, each representing the answer to the corresponding query.