Background

Thanks to Lotuses for providing the testdata.

Problem Description

Given $n$ pairs of numbers $a_i, b_i$, each pair represents a triangle with $a_i$ rows and $a_i$ columns as shown in the figure:

When $b_i = 0$, the left side is lower; when $b_i = 1$, the right side is lower.

Concatenate the triangles corresponding to each pair from left to right in the given order.

Now there are $m$ queries $l_i, r_i, v_i$. For each query, find the minimum height $h_i$ such that, between columns $l_i$ and $r_i$, the number of $o$ whose height is within $h_i$ is at least $v_i$.

Input Format

The first line contains two integers $n, m$, separated by a space.

The next $n$ lines each contain two integers $a_i, b_i$, separated by a space.

The next $m$ lines each contain three integers $l_i, r_i, v_i$, where adjacent integers are separated by a space.

Output Format

Output one line containing a string representing the answer.

6 6
3 0
4 0
2 1
3 1
5 0
1 1
3 9 12
3 9 13
3 4 4
14 16 7
9 15 12
1 18 42

2
3
3
3
3
-1

Hint

Sample Explanation

The range corresponding to the first query is shown in the figure:

Constraints

• For $30\%$ of the test cases, $1 \leq n, m, a_i \leq 500$.
• For $50\%$ of the test cases, $1 \leq n, m, a_i \leq 5000$.
• For all test cases, $1 \leq n, m \leq 2\times10^5$, $1 \leq a_i \leq 10^6$, $0 \leq b_i \leq 1$, $1 \leq l_i \leq r_i \leq \sum a_i$, $1 \leq v_i \leq 10^{18}$.

Lanqiao Cup 2022 National Contest A Group, Problem I.

Translated by ChatGPT 5