Dany jest graf nieskierowany o $n$ wierzchołkach, który początkowo nie zawiera żadnych krawędzi. Obsłuż $q$ operacji następujących dwóch typów:
- $+\ u\ v\ w$: Dodaj krawędź łączącą wierzchołki $u$ i $v$ o wadze $w$.
- $?\ u\ v$: Zdefiniujmy wagę ścieżki jako bitową koniunkcję (bitwise-and) wag wszystkich krawędzi na tej ścieżce. Oblicz największą możliwą wagę ścieżki zaczynającej się w wierzchołku $u$ i kończącej w wierzchołku $v$. Jeśli nie istnieje żadna ścieżka łącząca wierzchołki $u$ i $v$, odpowiedzią powinno być $-1$.
Wejście
Wejście składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 100$) oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:
Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) oznaczające liczbę wierzchołków oraz liczbę operacji.
W kolejnych $q$ wierszach $i$-ty wiersz zaczyna się od znaku $op$ ($op \in \{+, ?\}$) określającego typ $i$-tego zapytania.
- Jeśli $op = +$, to dalej następują trzy liczby całkowite $u$, $v$ oraz $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$), oznaczające operację pierwszego typu.
- Jeśli $op = ?$, to dalej następują dwie liczby całkowite $u$ oraz $v$ ($1 \le u, v \le n$, $u \ne v$), oznaczające operację drugiego typu.
Gwarantuje się, że w każdym przypadku testowym występuje co najmniej jedna operacja drugiego typu. Ponadto suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $10^3$, a suma wartości $q$ po wszystkich przypadkach testowych nie przekracza $10^6$.
Wyjście
Aby zmniejszyć rozmiar wyjścia, dla każdego przypadku testowego wypisz tylko jeden wiersz zawierający jedną liczbę całkowitą, oznaczającą sumę odpowiedzi na wszystkie operacje drugiego typu.
Przykład
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
Uwagi
Dla pierwszego przykładowego przypadku testowego odpowiedzi na operacje drugiego typu wynoszą kolejno $2$, $3$, $4$, $2$ oraz $6$.
Dla drugiego przykładowego przypadku testowego odpowiedzi na operacje drugiego typu wynoszą kolejno $64$ oraz $-1$.