問題文

インコ$1$、インコ$2$、･･･、インコ$N$の$N$匹からなるインコの群れがあります。
はじめ、インコ$p$の序列は$p$番目です。

この群れを$D$日間観察すると、毎日$2$つのイベントが起きていました。
$d$日目のイベントは以下の通りです。

• まずケンカが起き、インコ$X_d$とインコ$Y_d$の序列が入れ替わる。
  それ以外の$N-2$匹の序列は変わらない。
• 次に、群れで集めた$R_d$匹ぶんの食事を序列順に食べる。
  すなわち、序列が$1$番目から$R_d$番目までの$R_d$匹のインコだけが食事をする。

$Q$個の質問に答えてください。
$q$個目の質問は以下の通りです。

• インコ$P_q$が$F_q$回目の食事をするのは何日目か答えよ。
  $D$日間での食事回数の合計が$F_q$回未満である場合、$-1$を出力せよ。

制約

• $2≤N≤3×10^4$
• $1≤D,Q≤3×10^4$
• $1≤X_d,Y_d,R_d,P_q≤N$
• $X_d≠Y_d$
• $1≤F_q≤D$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $D$ $Q$
$X_1$ $Y_1$ $R_1$
$\vdots$
$X_D$ $Y_D$ $R_D$
$P_1$ $F_1$
$\vdots$
$P_Q$ $F_Q$

出力

$Q$行出力せよ。
$q$行目には、インコ$P_q$が$F_q$回目の食事をするのが何日目か、整数で出力せよ。
$D$日間での食事回数の合計が$F_q$回未満である場合、$-1$を出力せよ。

3 2 4
2 3 2
1 3 1
1 1
2 1
3 1
3 2

1
-1
1
2

はじめの序列は、インコ$1$から順に$1,2,3$番目です。

• $1$日目、インコ$2$とインコ$3$の序列が入れ替わり、$3$匹の序列は順に$1,3,2$番目になります。
  その後、序列が$1$番目から$2$番目のインコ$1$とインコ$3$が食事をします。
• $2$日目、インコ$1$とインコ$3$の序列が入れ替わり、$3$匹の序列は順に$2,3,1$番目となります。
  その後、序列が$1$番目のインコ$3$だけが食事をします。

この例では、インコ$2$は一度も食事ができませんでした。

3 3 6
1 3 1
1 3 2
1 3 3
2 1
2 2
2 3
3 1
3 2
3 3

2
3
-1
1
3
-1

一度も序列が変化しないインコが居るかもしれません。

5 5 5
1 3 5
5 2 4
5 1 3
1 3 3
5 3 2
1 3
2 2
3 4
4 1
5 5

3
-1
4
1
5