畀定一個有 $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$。