$n$개의 정점으로 이루어진 무방향 그래프가 주어지며, 처음에 그래프에는 간선이 없습니다. 다음 두 가지 유형의 연산 $q$개를 처리하세요.
- $+\ u\ v\ w$: 정점 $u$와 정점 $v$를 연결하고 가중치가 $w$인 간선을 추가합니다.
- $?\ u\ v$: 경로의 가중치를 경로에 포함된 모든 간선의 가중치들의 비트 AND(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$번째 줄에는 먼저 $i$번째 질의의 유형을 나타내는 문자 $op$ ($op \in \{+, ?\}$)가 주어집니다.
- $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$입니다.