Дано неорієнтований граф із $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$.