세 순열과 쿼리

길이 $N$의 세 순열 $p,q,r$이 주어진다. 세 순열은 모두 $1,2,\cdots,N$을 한 번씩 포함한다.

길이 $N$의 순열 $a$가 다음 조건을 만족하면 $a$를 좋은 순열이라고 하자.

• 서로 다른 두 정수 $x,y$에 대하여, $a$에서 $x$가 $y$보다 앞에 나온다면 $p,q,r$ 중 적어도 두 순열에서도 $x$가 $y$보다 앞에 나온다.

$M$개의 쿼리가 주어진다. 각 쿼리는 세 순열 중 하나에서 서로 인접한 두 원소를 서로 바꾼다. 앞선 쿼리의 결과는 다음 쿼리에도 유지된다.

각 쿼리를 수행한 직후, 현재의 $p,q,r$에 대하여 좋은 순열이 존재하는지 판별하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N\ M$ $p_1\ p_2\ \cdots\ p_N$ $q_1\ q_2\ \cdots\ q_N$ $r_1\ r_2\ \cdots\ r_N$ $s_1\ i_1$ $s_2\ i_2$ $\vdots$ $s_M\ i_M$

$j$번 쿼리에서는 $s_j=1$이면 $p$, $s_j=2$이면 $q$, $s_j=3$이면 $r$에서 $i_j$번째 원소와 $(i_j+1)$번째 원소를 서로 바꾼다.

각 테스트 케이스의 각 쿼리에 대하여, 쿼리를 수행한 직후 좋은 순열이 존재하면 YES, 존재하지 않으면 NO를 한 줄에 하나씩 출력한다.

• $1 \le T \le 100\,000$.
• $2 \le N \le 200\,000$.
• $1 \le M \le 200\,000$.
• $p,q,r$은 각각 $1,2,\cdots,N$의 순열이다.
• $1 \le s_j \le 3$ ($1 \le j \le M$).
• $1 \le i_j < N$ ($1 \le j \le M$).
• 모든 테스트 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.
• 모든 테스트 케이스에 대한 $M$의 합은 $200\,000$ 이하이다.