Concatenated Triangular Grids Query

You are given n pairs of numbers \(a_i\) and \(b_i\). Each pair represents a triangle drawn on an \(a_i \times a_i\) grid as shown in the figure. The triangle is drawn in one of two variants:

• If \(b_i=0\), the triangle is a left-lower (right angle at the bottom left) triangle. In this triangle, if we number the rows from bottom to top (i.e. row 1 is the bottom row and row \(a_i\) is the top), then the filled cells (marked with an o) in row \(r\) are the leftmost \(r\) columns of that triangle.
• If \(b_i=1\), the triangle is a right-lower (right angle at the bottom right) triangle. In row \(r\) (numbered from bottom to top), the filled cells are the rightmost \(r\) columns of the \(a_i \times a_i\) grid.

The triangles are then concatenated horizontally in the given order. That is, the first triangle occupies columns \(1 \ldots a_1\), the second occupies columns \(a_1+1 \ldots a_1+a_2\), and so on. Note that the overall grid has its bottom rows aligned. Let \(H\) be the maximum value among all \(a_i\); then the overall grid has \(H\) rows, and a triangle of height \(a_i (< H)\) is aligned so that its bottom row coincides with the overall grid's bottom row.

Next, you are given m queries. Each query is described by three integers \(l_i, r_i, v_i\). For a given query, consider the vertical subgrid consisting of columns \(l_i\) to \(r_i\) (inclusive) and the bottom \(h\) rows of the overall grid (i.e. rows \(H-h+1\) to \(H\)). Your task is to find the minimum value \(h_i\) (with \(1 \le h_i \le H\)) such that the total number of o characters in the specified subgrid is at least \(v_i\). It is guaranteed that a solution exists.

Note: All formulas are formatted in \(\LaTeX\).

inputFormat

The first line contains two integers (n) and (m) separated by a space. The next (n) lines each contain two integers (a_i) and (b_i) (with (b_i) being either 0 or 1) representing a triangle. The following (m) lines each contain three integers (l_i), (r_i), and (v_i), describing a query.

outputFormat

For each query, output a single integer on its own line representing the minimum height (h_i) (starting from the bottom) such that the total number of o characters in columns (l_i) to (r_i) is at least (v_i).

sample

2 3
3 0
2 1
1 3 3
4 5 2
1 5 6

2
2
2