Gitt en urettet graf med $n$ noder, som i utgangspunktet ikke har noen kanter. Håndter $q$ operasjoner av følgende to typer:
- $+\ u\ v\ w$: Legg til en kant som forbinder nodene $u$ og $v$, med vekt $w$.
- $?\ u\ v$: Definer vekten av en sti som bitvis OG (bitwise-and) av vektene til alle kantene på stien. Beregn den største mulige vekten av en sti som starter i node $u$ og slutter i node $v$. Hvis det ikke finnes noen sti som forbinder nodene $u$ og $v$, skal svaret være $-1$.
Inndata
Det er flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 100$) som angir antall testtilfeller. For hvert testtilfelle:
Den første linjen inneholder to heltall $n$ og $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) som angir antall noder og antall operasjoner.
I de påfølgende $q$ linjene inneholder den $i$-te linjen først et tegn $op$ ($op \in \{+, ?\}$) som angir typen til den $i$-te spørringen.
- Hvis $op = +$, følger tre heltall $u$, $v$ og $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$), som angir en operasjon av den første typen.
- Hvis $op = ?$, følger to heltall $u$ og $v$ ($1 \le u, v \le n$, $u \ne v$), som angir en operasjon av den andre typen.
Det er garantert at det finnes minst én operasjon av den andre typen for hvert testtilfelle. I tillegg overstiger ikke summen av $n$ over alle testtilfeller $10^3$, og summen av $q$ over alle testtilfeller overstiger ikke $10^6$.
Utdata
For å redusere størrelsen på utdataene skal du for hvert testtilfelle bare skrive ut én linje som inneholder ett heltall, som angir summen av svarene på alle operasjonene av den andre typen.
Eksempler
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
Forklaring
For det første eksempeltesttilfellet er svarene på operasjonene av den andre typen $2$, $3$, $4$, $2$ og $6$.
For det andre eksempeltesttilfellet er svarene på operasjonene av den andre typen $64$ og $-1$.