$n$ 個の頂点を持つ無向グラフが与えられます。初期状態ではグラフに辺はありません。以下の 2 種類の操作を $q$ 回処理してください。
- $+\ u\ v\ w$: 頂点 $u$ と頂点 $v$ を結ぶ重み $w$ の辺を追加する。
- $?\ u\ v$: パスの重みを、そのパスに含まれるすべての辺の重みのビット毎論理積(bitwise-and)として定義する。頂点 $u$ から始まり頂点 $v$ で終わるパスの重みとしてあり得る最大値を求める。頂点 $u$ と頂点 $v$ を結ぶパスが存在しない場合、答えは $-1$ とする。
入力
複数のテストケースが与えられます。入力の 1 行目にはテストケースの個数を表す整数 $T$($1 \le T \le 100$)が与えられます。各テストケースについて:
1 行目には頂点数と操作数を表す 2 つの整数 $n$ と $q$($2 \le n \le 10^3$、$1 \le q \le 10^6$)が与えられます。
続く $q$ 行のうち $i$ 行目には、まず $i$ 番目のクエリの種類を表す文字 $op$($op \in \{+, ?\}$)が与えられます。
- $op = +$ の場合、続いて 3 つの整数 $u$、$v$、$w$($1 \le u, v \le n$、$0 \le w < 2^{12}$)が与えられ、1 種類目の操作を表します。
- $op = ?$ の場合、続いて 2 つの整数 $u$ と $v$($1 \le u, v \le n$、$u \ne v$)が与えられ、2 種類目の操作を表します。
各テストケースには 2 種類目の操作が少なくとも 1 つ含まれることが保証されます。また、すべてのテストケースにおける $n$ の総和は $10^3$ を超えず、$q$ の総和は $10^6$ を超えません。
出力
出力サイズを削減するため、各テストケースについて 1 行に 1 つの整数を出力してください。これは 2 種類目の操作すべてに対する答えの総和を表します。
入出力例
2
4 11
+ 1 3 6
+ 3 4 2
? 1 4
+ 1 4 3
? 4 1
+ 4 3 4
? 1 4
+ 3 2 3
? 1 2
+ 1 1 4
? 1 3
4 4
+ 1 2 64
+ 3 4 32
? 1 2
? 3 1
17
63
注記
1 つ目のサンプルテストケースでは、2 種類目の操作に対する答えは順に $2$、$3$、$4$、$2$、$6$ です。
2 つ目のサンプルテストケースでは、2 種類目の操作に対する答えは順に $64$ と $-1$ です。