Annettuna on suuntaamaton verkko, jossa on $n$ solmua ja jossa ei aluksi ole yhtään kaarta. Käsittele $q$ operaatiota, jotka ovat seuraavaa kahta tyyppiä:
- $+\ u\ v\ w$: Lisää solmut $u$ ja $v$ yhdistävä kaari, jonka paino on $w$.
- $?\ u\ v$: Määritellään polun painoksi polun kaikkien kaarten painojen bittittäinen JA (bitwise-and). Laske suurin mahdollinen paino polulle, joka alkaa solmusta $u$ ja päättyy solmuun $v$. Jos solmujen $u$ ja $v$ välillä ei ole polkua, vastauksen tulee olla $-1$.
Syöte
Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 100$), joka ilmaisee testitapausten määrän. Jokaisessa testitapauksessa:
Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$), jotka ilmaisevat solmujen määrän ja operaatioiden määrän.
Seuraavilla $q$ rivillä $i$:s rivi sisältää ensin merkin $op$ ($op \in \{+, ?\}$), joka ilmaisee $i$:nnen kyselyn tyypin.
- Jos $op = +$, sen perässä on kolme kokonaislukua $u$, $v$ ja $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$), jotka ilmaisevat ensimmäisen tyypin operaation.
- Jos $op = ?$, sen perässä on kaksi kokonaislukua $u$ ja $v$ ($1 \le u, v \le n$, $u \ne v$), jotka ilmaisevat toisen tyypin operaation.
On taattu, että jokaisessa testitapauksessa on vähintään yksi toisen tyypin operaatio. Lisäksi lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^3$, eikä lukujen $q$ summa yli kaikkien testitapausten ylitä arvoa $10^6$.
Tuloste
Tulosteen koon pienentämiseksi tulosta jokaiselle testitapaukselle vain yksi rivi, joka sisältää yhden kokonaisluvun: kaikkien toisen tyypin operaatioiden vastausten summan.
Esimerkit
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
Huomautus
Ensimmäisessä esimerkkitestitapauksessa vastaukset toisen tyypin operaatioihin ovat $2$, $3$, $4$, $2$ ja $6$.
Toisessa esimerkkitestitapauksessa vastaukset toisen tyypin operaatioihin ovat $64$ ja $-1$.