Gefið er óstefnt net með $n$ hnútum og í upphafi hefur netið enga leggi. Framkvæmið $q$ aðgerðir af eftirfarandi tveimur gerðum:
- $+\ u\ v\ w$: Bætið við legg sem tengir hnútana $u$ og $v$ með þyngd $w$.
- $?\ u\ v$: Skilgreinum þyngd vegar sem bitbundið OG (bitwise-and) af þyngdum allra leggja á veginum. Reiknið mestu mögulegu þyngd vegar sem byrjar í hnúti $u$ og endar í hnúti $v$. Ef enginn vegur tengir hnútana $u$ og $v$ á svarið að vera $-1$.
Inntak
Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 100$) sem gefur til kynna fjölda prófunartilvika. Fyrir hvert prófunartilvik:
Fyrsta línan inniheldur tvær heiltölur $n$ og $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) sem gefa til kynna fjölda hnúta og fjölda aðgerða.
Í næstu $q$ línum inniheldur $i$-ta línan fyrst tákn $op$ ($op \in \{+, ?\}$) sem gefur til kynna gerð $i$-tu fyrirspurnarinnar.
- Ef $op = +$, þá fylgja þrjár heiltölur $u$, $v$ og $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$), sem tákna aðgerð af fyrri gerðinni.
- Ef $op = ?$, þá fylgja tvær heiltölur $u$ og $v$ ($1 \le u, v \le n$, $u \ne v$), sem tákna aðgerð af seinni gerðinni.
Það er tryggt að það sé að minnsta kosti ein aðgerð af seinni gerðinni í hverju prófunartilviki. Einnig er summa $n$ yfir öll prófunartilvik ekki meiri en $10^3$, og summa $q$ yfir öll prófunartilvik er ekki meiri en $10^6$.
Úttak
Til að minnka stærð úttaksins skal fyrir hvert prófunartilvik aðeins prenta eina línu sem inniheldur eina heiltölu, sem táknar summu svaranna við öllum aðgerðum af seinni gerðinni.
Dæmi
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
Athugasemd
Fyrir fyrra prófunartilvikið í dæminu eru svörin við aðgerðunum af seinni gerðinni $2$, $3$, $4$, $2$ og $6$.
Fyrir seinna prófunartilvikið í dæminu eru svörin við aðgerðunum af seinni gerðinni $64$ og $-1$.