長さ \(N-1\) の正整数列 \(A = (A_1, A_2, \ldots, A_{N-1})\) と、\(Q\) 個のクエリが与えられます。\(q\) 番目のクエリでは正整数の組 \((L_q, R_q, X_q)\) が与えられるので、以下の問題を解いてください。
合計でちょうど \(X_q\) 個のたまねぎが召喚されるように魔法を使うことが可能であるか判定し、もし可能であるならば最後に使う魔法の時刻としてあり得る最小値を求めてください。
なお、各クエリにおいて魔法は一度も使われていない状態から始まります。
入力は以下の形式で標準入力から与えられます。
| \(N\) | |
| \(A_1\) \(A_2\) \(\ldots\) \(A_{N-1}\) | |
| \(Q\) | |
| \(L_1\) \(R_1\) \(X_1\) | |
| \(\vdots\) | |
| \(L_Q\) \(R_Q\) \(X_Q\) |
入力は以下の制約をすべて満たします。
\(Q\) 行出力してください。
\(q\) \((1 \leq q \leq Q)\) 行目には、\(q\) 番目のクエリに対する答えを以下のように出力してください。
合計でちょうど \(X_q\) 個のたまねぎが召喚されるように魔法を使うことが可能である場合、最後に使う魔法の時刻としてあり得る最小値を出力してください。
合計でちょうど \(X_q\) 個のたまねぎが召喚されるように魔法を使うことが不可能である場合、 \(-1\) を出力してください。
以下の追加制約を満たすデータセットに正解した場合、部分点が与えられます。
41 2 341 10 104 10 105 10 1011 11 10
5 6 10 -1
210000000011 1 1
1