問題文

インコ11、インコ22、・・・、インコNNNN匹からなるインコの群れがあります。
はじめ、インコppの序列はpp番目です。

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

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

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

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

制約

  • 2N3×1042≤N≤3×10^4
  • 1D,Q3×1041≤D,Q≤3×10^4
  • 1Xd,Yd,Rd,PqN1≤X_d,Y_d,R_d,P_q≤N
  • XdYdX_d≠Y_d
  • 1FqD1≤F_q≤D
  • 入力はすべて整数

入力

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

NN DD QQ
X1X_1 Y1Y_1 R1R_1
\vdots
XDX_D YDY_D RDR_D
P1P_1 F1F_1
\vdots
PQP_Q FQF_Q

出力

QQ行出力せよ。
qq行目には、インコPqP_qFqF_q回目の食事をするのが何日目か、整数で出力せよ。
DD日間での食事回数の合計がFqF_q回未満である場合、1-1を出力せよ。

入力例1
3 2 4
2 3 2
1 3 1
1 1
2 1
3 1
3 2
出力例1
1
-1
1
2

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

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

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

入力例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
2
3
-1
1
3
-1

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

入力例3
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
3
-1
4
1
5

Submit


Go (1.21)