È dato un grafo non orientato con $n$ vertici; inizialmente il grafo non ha archi. Gestisci $q$ operazioni dei seguenti due tipi:
- $+\ u\ v\ w$: Aggiungi un arco che collega i vertici $u$ e $v$, con peso $w$.
- $?\ u\ v$: Definisci il peso di un cammino come l'AND bit a bit (bitwise-and) dei pesi di tutti gli archi nel cammino. Calcola il massimo peso possibile di un cammino che inizia dal vertice $u$ e termina nel vertice $v$. Se non esiste alcun cammino che collega i vertici $u$ e $v$, la risposta deve essere $-1$.
Dati di ingresso
Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 100$) che indica il numero di casi di test. Per ciascun caso di test:
La prima riga contiene due interi $n$ e $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) che indicano il numero di vertici e il numero di operazioni.
Per le successive $q$ righe, la $i$-esima riga contiene innanzitutto un carattere $op$ ($op \in \{+, ?\}$) che indica il tipo della $i$-esima query.
- Se $op = +$, seguono tre interi $u$, $v$ e $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$), che indicano un'operazione del primo tipo.
- Se $op = ?$, seguono due interi $u$ e $v$ ($1 \le u, v \le n$, $u \ne v$), che indicano un'operazione del secondo tipo.
È garantito che ci sia almeno un'operazione del secondo tipo per ogni caso di test. Inoltre, la somma di $n$ su tutti i casi di test non supera $10^3$, e la somma di $q$ su tutti i casi di test non supera $10^6$.
Dati di uscita
Per ridurre la dimensione dell'output, per ciascun caso di test stampa semplicemente una riga contenente un solo intero, che indica la somma delle risposte a tutte le operazioni del secondo tipo.
Esempi
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
Note
Per il primo caso di test di esempio, le risposte alle operazioni del secondo tipo sono $2$, $3$, $4$, $2$ e $6$.
Per il secondo caso di test di esempio, le risposte alle operazioni del secondo tipo sono $64$ e $-1$.