On vous donne un graphe non orienté à $n$ sommets, qui ne contient initialement aucune arête. Vous devez traiter $q$ opérations des deux types suivants :
- $+\ u\ v\ w$ : Ajouter une arête reliant les sommets $u$ et $v$, de poids $w$.
- $?\ u\ v$ : On définit le poids d'un chemin comme le ET bit à bit (bitwise-and) des poids de toutes les arêtes du chemin. Calculez le poids maximal possible d'un chemin partant du sommet $u$ et se terminant au sommet $v$. S'il n'existe aucun chemin reliant les sommets $u$ et $v$, la réponse doit être $-1$.
Entrée
Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 100$) indiquant le nombre de cas de test. Pour chaque cas de test :
La première ligne contient deux entiers $n$ et $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) indiquant le nombre de sommets et le nombre d'opérations.
Pour les $q$ lignes suivantes, la $i$-ème ligne commence par un caractère $op$ ($op \in \{+, ?\}$) indiquant le type de la $i$-ème requête.
- Si $op = +$, trois entiers $u$, $v$ et $w$ suivent ($1 \le u, v \le n$, $0 \le w < 2^{12}$), indiquant une opération du premier type.
- Si $op = ?$, deux entiers $u$ et $v$ suivent ($1 \le u, v \le n$, $u \ne v$), indiquant une opération du second type.
Il est garanti qu'il y a au moins une opération du second type pour chaque cas de test. De plus, la somme de $n$ sur tous les cas de test ne dépasse pas $10^3$, et la somme de $q$ sur tous les cas de test ne dépasse pas $10^6$.
Sortie
Pour réduire la taille de la sortie, affichez simplement pour chaque cas de test une ligne contenant un seul entier, indiquant la somme des réponses à toutes les opérations du second type.
Exemples
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
Remarque
Pour le premier cas de test de l'exemple, les réponses aux opérations du second type sont $2$, $3$, $4$, $2$ et $6$.
Pour le second cas de test de l'exemple, les réponses aux opérations du second type sont $64$ et $-1$.