Se da un grafo no dirigido con $n$ vértices; inicialmente el grafo no tiene aristas. Mantén $q$ operaciones de los siguientes dos tipos:
- $+\ u\ v\ w$: Añade una arista que conecte los vértices $u$ y $v$, con un peso de $w$.
- $?\ u\ v$: Define el peso de un camino como el AND bit a bit (bitwise-and) de los pesos de todas las aristas en el camino. Calcula el mayor peso posible de un camino que comience en el vértice $u$ y termine en el vértice $v$. Si no existe ningún camino que conecte los vértices $u$ y $v$, la respuesta debe ser $-1$.
Entrada
Hay múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 100$) que indica el número de casos de prueba. Para cada caso de prueba:
La primera línea contiene dos enteros $n$ y $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) que indican el número de vértices y el número de operaciones.
En las siguientes $q$ líneas, la $i$-ésima línea contiene primero un carácter $op$ ($op \in \{+, ?\}$) que indica el tipo de la $i$-ésima consulta.
- Si $op = +$, siguen tres enteros $u$, $v$ y $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$), indicando una operación del primer tipo.
- Si $op = ?$, siguen dos enteros $u$ y $v$ ($1 \le u, v \le n$, $u \ne v$), indicando una operación del segundo tipo.
Se garantiza que hay al menos una operación del segundo tipo en cada caso de prueba. Además, la suma de $n$ en todos los casos de prueba no supera $10^3$, y la suma de $q$ en todos los casos de prueba no supera $10^6$.
Salida
Para reducir el tamaño de la salida, para cada caso de prueba imprime únicamente una línea con un entero, indicando la suma de las respuestas a todas las operaciones del segundo tipo.
Ejemplos
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
Nota
Para el primer caso de prueba de ejemplo, las respuestas a las operaciones del segundo tipo son $2$, $3$, $4$, $2$ y $6$.
Para el segundo caso de prueba de ejemplo, las respuestas a las operaciones del segundo tipo son $64$ y $-1$.