Givet en oriktad graf med $n$ hörn, som från början saknar kanter. Hantera $q$ operationer av följande två typer:
- $+\ u\ v\ w$: Lägg till en kant som förbinder hörnen $u$ och $v$, med vikten $w$.
- $?\ u\ v$: Definiera vikten av en väg som det bitvisa OCH-värdet (bitwise-and) av vikterna för alla kanter längs vägen. Beräkna den största möjliga vikten för en väg som startar i hörn $u$ och slutar i hörn $v$. Om det inte finns någon väg som förbinder hörnen $u$ och $v$ ska svaret vara $-1$.
Indata
Det finns flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 100$) som anger antalet testfall. För varje testfall:
Den första raden innehåller två heltal $n$ och $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) som anger antalet hörn och antalet operationer.
För de följande $q$ raderna innehåller den $i$-te raden först ett tecken $op$ ($op \in \{+, ?\}$) som anger typen för den $i$-te frågan.
- Om $op = +$ följer tre heltal $u$, $v$ och $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$), vilket anger en operation av den första typen.
- Om $op = ?$ följer två heltal $u$ och $v$ ($1 \le u, v \le n$, $u \ne v$), vilket anger en operation av den andra typen.
Det garanteras att det finns minst en operation av den andra typen i varje testfall. Dessutom överstiger summan av $n$ över alla testfall inte $10^3$, och summan av $q$ över alla testfall överstiger inte $10^6$.
Utdata
För att minska storleken på utdatan ska du för varje testfall bara skriva ut en rad med ett enda heltal, som anger summan av svaren på alla operationer av den andra typen.
Exempel
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
Förklaring
För det första exempeltestfallet är svaren på operationerna av den andra typen $2$, $3$, $4$, $2$ och $6$.
För det andra exempeltestfallet är svaren på operationerna av den andra typen $64$ och $-1$.