問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
クライアント 0, 1, ..., n を直線状につなぐネットワークがあり、各クライアントは n 個の通信ケーブルによって接続されています。
paiza 君は、このネットワークで発生した通信障害を調査することになりました。
i 番目の通信ケーブル (ケーブル i) は、クライアント (i - 1) とクライアント i の間をつないでおり、時刻 0 における通信速度は s_i です。
また、時刻 1 から t までの各時刻 j において、ケーブル c_j の通信速度が d_j だけ低下したことがわかっています。
以下の q 個のクエリに答えてください。
i 番目のクエリでは、a_i, b_i, x_i が与えられるので、クライアント a_i とクライアント b_i の間の通信速度が x_i 以下になった最初の時刻を求めてください。
ただし、クライアント a_i とクライアント b_i の間の通信速度は、通信ケーブル a_i + 1, a_i + 2, ..., b_i の通信速度の最小値とします。
n t q
s_1 s_2 ... s_n
c_1 d_1
c_2 d_2
...
c_t d_t
a_1 b_1 x_1
a_2 b_2 x_2
...
a_q b_q x_q
q 行出力してください。
i 行目には、i 番目のクエリの答えを整数で出力してください。
ただし、クライアント a_i とクライアント b_i の間の通信速度が時刻 0 の時点で x_i 以下である場合は、0 を出力してください。
また、クライアント a_i とクライアント b_i の間の通信速度が x_i 以下になる時刻が存在しない場合は、-1 を出力してください。
末尾に改行を入れ、余計な文字を含んではいけません。
・ 2 ≦ n ≦ 1000 = 10^3
・ 1 ≦ t ≦ 1000 = 10^3
・ 1 ≦ q ≦ 100000 = 10^5
・ 1 ≦ s_i, d_i, x_i ≦ 1000000000 = 10^9
・ 1 ≦ c_j ≦ n
・ 0 ≦ a_i < b_i ≦ n
・ 通信速度の低下量の合計はそれぞれ s_i 未満である
・ 入力はすべて整数
4 4 4
5 5 5 5
1 3
3 2
4 4
2 1
0 4 5
2 3 3
1 4 1
0 1 1
0
2
3
-1