Дан неориентированный граф с $n$ вершинами, изначально не содержащий рёбер. Обработайте $q$ операций следующих двух типов:
- $+\ u\ v\ w$: Добавить ребро, соединяющее вершины $u$ и $v$, с весом $w$.
- $?\ u\ v$: Определим вес пути как побитовое И (bitwise-and) весов всех рёбер на этом пути. Найдите наибольший возможный вес пути, начинающегося в вершине $u$ и заканчивающегося в вершине $v$. Если пути между вершинами $u$ и $v$ не существует, ответом должно быть $-1$.
Входные данные
Входные данные состоят из нескольких наборов входных данных. Первая строка содержит целое число $T$ ($1 \le T \le 100$) — количество наборов входных данных. Для каждого набора входных данных:
Первая строка содержит два целых числа $n$ и $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) — количество вершин и количество операций.
В следующих $q$ строках $i$-я строка сначала содержит символ $op$ ($op \in \{+, ?\}$), указывающий тип $i$-го запроса.
- Если $op = +$, то далее следуют три целых числа $u$, $v$ и $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$), описывающие операцию первого типа.
- Если $op = ?$, то далее следуют два целых числа $u$ и $v$ ($1 \le u, v \le n$, $u \ne v$), описывающие операцию второго типа.
Гарантируется, что в каждом наборе входных данных есть хотя бы одна операция второго типа. Также сумма $n$ по всем наборам входных данных не превышает $10^3$, а сумма $q$ по всем наборам входных данных не превышает $10^6$.
Выходные данные
Чтобы уменьшить объём вывода, для каждого набора входных данных выведите одну строку, содержащую одно целое число — сумму ответов на все операции второго типа.
Примеры
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
Примечание
В первом примере ответы на операции второго типа равны $2$, $3$, $4$, $2$ и $6$.
Во втором примере ответы на операции второго типа равны $64$ и $-1$.