給定一張有 $n$ 個頂點的無向圖,初始時圖中沒有任何邊。請維護 $q$ 次以下兩種類型的操作:
- $+\ u\ v\ w$:加入一條連接頂點 $u$ 與 $v$、權重為 $w$ 的邊。
- $?\ u\ v$:定義一條路徑的權重為該路徑上所有邊之權重的按位與(bitwise-and)。請計算從頂點 $u$ 出發並於頂點 $v$ 結束的路徑之最大可能權重。若不存在連接頂點 $u$ 與 $v$ 的路徑,則答案應為 $-1$。
輸入格式
輸入包含多組測試資料。輸入的第一行包含一個整數 $T$($1 \le T \le 100$),代表測試資料的組數。對於每組測試資料:
第一行包含兩個整數 $n$ 與 $q$($2 \le n \le 10^3$,$1 \le q \le 10^6$),分別代表頂點數量與操作數量。
接下來的 $q$ 行中,第 $i$ 行首先包含一個字元 $op$($op \in \{+, ?\}$),代表第 $i$ 次操作的類型。
- 若 $op = +$,接著會有三個整數 $u$、$v$ 與 $w$($1 \le u, v \le n$,$0 \le w < 2^{12}$),代表第一種類型的操作。
- 若 $op = ?$,接著會有兩個整數 $u$ 與 $v$($1 \le u, v \le n$,$u \ne v$),代表第二種類型的操作。
保證每組測試資料至少有一次第二種類型的操作。此外,所有測試資料的 $n$ 總和不超過 $10^3$,且所有測試資料的 $q$ 總和不超過 $10^6$。
輸出格式
為了減少輸出量,對於每組測試資料,只需輸出一行一個整數,代表所有第二種類型操作之答案的總和。
範例
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
說明
對於第一組範例測試資料,第二種類型操作的答案依序為 $2$、$3$、$4$、$2$ 與 $6$。
對於第二組範例測試資料,第二種類型操作的答案依序為 $64$ 與 $-1$。