給定 n 組成對(duì)的數(shù) a_i , b_i，每組數(shù)表示一個(gè) a_i 行 a_i 列的如圖所示的三角形：

其中 b_i 為 0 時(shí)左邊較低，為 1 時(shí)右邊較低。 

將每組數(shù)對(duì)應(yīng)的三角按數(shù)的順序從左到右拼接起來。 

現(xiàn)給出 m 組詢問 l_i ,r_i , v_i，對(duì)每組詢問求最低高度 h_i 使得 l_i 到 r_i 列之間的高度在 h_i 以內(nèi)的 o 的數(shù)量大于等于 v_i。 

輸入的第一行包含兩個(gè)整數(shù) n, m，用一個(gè)空格分隔。

接下來 n 行，每行包含兩個(gè)整數(shù) a_i , b_i，用一個(gè)空格分隔。

接下來 m 行，每行包含三個(gè)整數(shù) l_i ,r_i , vi，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔。

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

第一個(gè)詢問對(duì)應(yīng)的范圍如圖所示：

對(duì)于 30% 的評(píng)測(cè)用例，1 ≤ n, m, a_i ≤ 500； 

對(duì)于 50% 的評(píng)測(cè)用例，1 ≤ n, m, a_i ≤ 5000； 

對(duì)于所有評(píng)測(cè)用例，1 ≤ n, m ≤ 200000 ，1 ≤ a_i ≤ 10⁶ ，0 ≤ b_i ≤ 1 ， 1 ≤ l_i ≤ r_i ≤ ∑ a_i ，1 ≤ v_i ≤ 10¹⁸。