給定 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 , v_i，相鄰兩個整數之間用一個空格分隔。

輸出 m 行，每行包含一個整數 h_i ，依次表示每次詢問對應的答案。如果不存在這樣的 h_i，請輸出 ?1。 

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¹⁸。