까다로운 연산

시간 제한1초메모리 제한2048 MB

요약

배열에 접두사 XOR, 접미사 XOR, 그리고 각각의 역연산을 순서대로 적용한 뒤 최종 배열을 출력합니다.

문제

Svetozar에게 정수 $n$ 개로 이루어진 배열 $a$ 가 있다. 그는 이 배열에 다음 연산들을 생각해 냈다.

1: 배열 $a$ 를 $a$ 의 접두사 XOR 배열로 바꾼다. 즉, 연산 후 $i$ 번째 원소는 $a_1 \oplus a_2 \oplus \ldots \oplus a_i$ 가 된다.
2: 배열 $a$ 를 접미사 XOR 배열로 바꾼다. 즉, 연산 후 $i$ 번째 원소는 $a_i \oplus a_{i+1} \oplus \ldots \oplus a_n$ 이 된다.
-1: 연산 1의 역연산이다. 연산 -1을 수행한 뒤 연산 1을 적용하면, 그 결과는 -1을 적용하기 전의 배열과 같아진다.
-2: 연산 2의 역연산이다. 연산 -2를 수행한 뒤 연산 2를 적용하면, 그 결과는 -2를 적용하기 전의 배열과 같아진다.

Svetozar는 여러 연산을 차례로 수행했고, 이 계산이 맞는지 확인하려고 한다. 첫 번째 연산은 항상 양수로 표시되며, 연속된 두 연산의 부호는 서로 다르다.

첫 줄에 테스트 케이스의 수 $T$ ( $1 \leq T \leq 10^5$ )가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다.

첫 줄에는 배열의 크기 $n$ 과 연산의 수 $q$ ( $1 \leq n, q \leq 10^5$ )가 주어진다.

둘째 줄에는 배열의 원소 $a_1, a_2, \ldots, a_n$ ( $0 \leq a_i \leq 10^9$ )이 주어진다.

셋째 줄에는 실행 순서대로 연산 $op_1, op_2, \ldots, op_q$ ( $-2 \leq op_i \leq 2$ , $op_i \neq 0$ , $op_1 > 0$ , $op_i \cdot op_{i+1} < 0$ )가 주어진다.

모든 테스트 케이스에서 $n$ 의 합은 $10^5$ 를 넘지 않고, $q$ 의 합도 $10^5$ 를 넘지 않는다.

각 테스트 케이스마다 모든 연산을 적용한 뒤의 배열을 한 줄에 $n$ 개의 정수로 출력한다.

예제 1

입력

3
5 1
0 1 2 4 8
1
7 2
25 2 20 23 998 244 353
2 -2
9 9
9 9 8 2 4 4 3 5 3
2 -1 2 -1 2 -1 2 -1 2

예상 출력

0 1 3 7 15
25 2 20 23 998 244 353
4 7 2 1 14 7 14 6 4