P6602 "EZEC-2" Number Line

X drew a number line. He will perform $n$ operations. In each operation, he first adds $a_i$ marks at position $x_i$ on the number line. Then he needs to choose a pair $(l,r)$, where $l,r$ are integers, $0\le l\le r \le m$, and the number of marks on the interval $[l,r]$ on the number line is **less than or equal to** $k$. For each operation, you need to find the maximum value of $r-l$ among all pairs $(l,r)$ that satisfy the condition.

The first line contains three integers, $n$, $m$, and $k$. The next $n$ lines each contain two integers $x_i$ and $a_i$.

Output $n$ lines, where the $i$-th line is the answer after the $i$-th operation. If there is no valid pair $(l,r)$, output `-1`.

**[Sample Explanation #2]** After each operation, the chosen pairs are $(0,15),(4,15),(4,15),(8,15),(9,15)$. --- **[Constraints and Notes]** | Test Point ID | $n=$ | $m=$ | $k=$ | | :----------: | :----------: | :----------: | :----------: | | $1,2$ | $100$ | $100$ | $3$ | | $3,4$ | $100$ | $10^3$ | $3$ | | $5,6$ | $100$ | $10^4$ | $3$ | | $7,8$ | $500$ | $10^4$ | $3$ | | $9,10$ | $10^3$ | $10^4$ | $3$ | | $11,12$ | $10^4$ | $10^5$ | $3$ | | $13\sim 16$ | $10^5$ | $10^6$ | $0$ | | $17\sim 21$ | $10^5$ | $10^6$ | $3$ | | $22,23$ | $10^5$ | $10^9$ | $100$ | | $24,25$ | $10^6$ | $10^9$ | $100$ | It is guaranteed that for test points $13\sim 16$, $x_i$ is generated randomly. For test points $24,25$, the time limit is $3\text s$, and for all other test points, the time limit is $2\text s$. For $100\%$ of the data, $1\le n\le 10^6$, $0\le m\le 10^9$, $0\le x_i\le m$, $0\le k\le 100$, and $1\le a_i\le 100$. **Note: Marks may be added multiple times at the same position on the number line.** **$\text{O2}$ optimization is enabled automatically. It is guaranteed that the time and memory limits are both more than twice those of $\text{std}$ with $\text{O2}$ enabled.** Translated by ChatGPT 5