给定 n 组成对的数 a_i , b_i，每组数表示一个 a_i 行 a_i 列的如图所示的三角形：

其中 b_i 为 0 时左边较低，为 1 时右边较低。 

将每组数对应的三角按数的顺序从左到右拼接起来。 

现给出 m 组询问 l_i ,r_i , v_i，对每组询问求最低高度 h_i 使得 l_i 到 r_i 列之间的高度在 h_i 以内的 o 的数量大于等于 v_i。 

输入的第一行包含两个整数 n, m，用一个空格分隔。

接下来 n 行，每行包含两个整数 a_i , b_i，用一个空格分隔。

接下来 m 行，每行包含三个整数 l_i ,r_i , vi，相邻两个整数之间用一个空格分隔。

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

第一个询问对应的范围如图所示：

对于 30% 的评测用例，1 ≤ n, m, a_i ≤ 500； 

对于 50% 的评测用例，1 ≤ n, m, a_i ≤ 5000； 

对于所有评测用例，1 ≤ n, m ≤ 200000 ，1 ≤ a_i ≤ 10⁶ ，0 ≤ b_i ≤ 1 ， 1 ≤ l_i ≤ r_i ≤ ∑ a_i ，1 ≤ v_i ≤ 10¹⁸。