Cho một đồ thị vô hướng gồm $n$ đỉnh, ban đầu đồ thị không có cạnh nào. Hãy thực hiện $q$ thao tác thuộc hai loại sau:
- $+\ u\ v\ w$: Thêm một cạnh nối hai đỉnh $u$ và $v$ với trọng số là $w$.
- $?\ u\ v$: Định nghĩa trọng số của một đường đi là phép AND theo bit (bitwise-and) của trọng số tất cả các cạnh trên đường đi đó. Hãy tính trọng số lớn nhất có thể của một đường đi bắt đầu từ đỉnh $u$ và kết thúc tại đỉnh $v$. Nếu không có đường đi nào nối hai đỉnh $u$ và $v$, câu trả lời sẽ là $-1$.
Dữ liệu vào
Có nhiều bộ dữ liệu. Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 100$) biểu thị số lượng bộ dữ liệu. Với mỗi bộ dữ liệu:
Dòng đầu tiên chứa hai số nguyên $n$ và $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) lần lượt biểu thị số lượng đỉnh và số lượng thao tác.
Trong $q$ dòng tiếp theo, dòng thứ $i$ trước hết chứa một ký tự $op$ ($op \in \{+, ?\}$) biểu thị loại truy vấn thứ $i$.
- Nếu $op = +$, theo sau là ba số nguyên $u$, $v$ và $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$), biểu thị một thao tác loại một.
- Nếu $op = ?$, theo sau là hai số nguyên $u$ và $v$ ($1 \le u, v \le n$, $u \ne v$), biểu thị một thao tác loại hai.
Dữ liệu đảm bảo có ít nhất một thao tác loại hai trong mỗi bộ dữ liệu. Ngoài ra, tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $10^3$, và tổng của $q$ trong tất cả các bộ dữ liệu không vượt quá $10^6$.
Dữ liệu ra
Để giảm kích thước dữ liệu ra, với mỗi bộ dữ liệu chỉ cần in ra một dòng chứa một số nguyên là tổng các câu trả lời cho tất cả các thao tác loại hai.
Ví dụ
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
Ghi chú
Ở bộ dữ liệu mẫu đầu tiên, câu trả lời cho các thao tác loại hai lần lượt là $2$, $3$, $4$, $2$ và $6$.
Ở bộ dữ liệu mẫu thứ hai, câu trả lời cho các thao tác loại hai lần lượt là $64$ và $-1$.