問題

hitsujiくんはあるゲームに参加することにしました。
このゲームには $N$ 人が参加しており、スペードのA、スペードの2、ハートのA、ハートの2のうち参加者ごとにどれか1枚が配られます。
hitsujiくんは $M$ 個の参加者 $A_i$ と $B_i$ が持っているカードの関係が $C_i$ であると分かりました。 $C_i$ は次の4種類のいずれかです。
なお、絵柄とはスペードとハートを、番号とはAと2を指します。

• 1: $A_i$ と $B_i$ のカードは絵柄も番号も同じである。
• 2: $A_i$ と $B_i$ のカードは絵柄が同じであるが、番号が異なる。
• 3: $A_i$ と $B_i$ のカードは番号が同じであるが、絵柄が異なる。
• 4: $A_i$ と $B_i$ のカードは絵柄も番号も異なる。

このとき、以下の $Q$ 個の質問に答えてください。

• 参加者 $X_i$ のカードが $Y_i$ であるとしたとき、参加者 $Z_i$ のカードはなにか。
  カード $Y_i$ について、スペードのAを 1 、スペードの2を 2 、ハートのAを 3 、ハートの2を 4 と表す。

制約

• $1 \le N \le 10^5$
• $0 \le M \le \min(\frac{N(N-1)}{2}, 10^5)$
• $1 \le A_i < B_i \le N$
• $i \ne j$ ならば $(A_i, B_i) \ne (A_j, B_j)$
• $1 \le C_i \le 4$
• $A_i, B_i, C_i$ に矛盾はない
• $1 \le Q \le 10^5$
• $1 \le X_i, Z_i \le N$
• $1 \le Y_i \le 4$
• 入力はすべて整数

入力

出力

$Q$ 行出力せよ。
$i$ 行目には参加者 $Z_i$ のカードを、スペードのAを 1 、スペードの2を 2 、ハートのAを 3 、ハートの2を 4 と出力せよ。
一意に定まらない場合は -1 と出力せよ。

入力例1

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

出力例1

1
4
4
-1

1. 参加者1のカードはスペードのAであり、参加者2のカードとは「絵柄も番号も同じである」であるため、参加者2のカードはスペードのAになります。
2. 参加者1のカードはハートのAであり、参加者3のカードとは「絵柄が同じであるが、番号が異なる」であるため、参加者2のカードはハートの2になります。
3. 参加者3のカードはスペードの2であり、参加者4のカードとは「番号が同じであるが、絵柄が異なる」であるため、参加者2のカードはハートの2になります。
4. 参加者3からのカードから参加者5のカードを知ることはできません。

入力例2

8 7
1 2 1
1 3 2
1 4 3
5 6 3 
5 7 4
6 7 2
7 8 1
6
1 1 2
4 2 3
2 3 8
7 4 6
5 1 8
7 2 3

出力例2

1
3
-1
3
4
-1