Three Permutations and Queries

Three permutations $p,q,r$ of length $N$ are given. Each permutation contains every integer from $1$ to $N$ exactly once.

A permutation $a$ of length $N$ is called good if it satisfies the following condition.

• For every pair of distinct integers $x,y$, if $x$ appears before $y$ in $a$, then $x$ also appears before $y$ in at least two of $p,q,r$.

There are $M$ queries. Each query swaps two adjacent elements in one of the three permutations. The changes made by previous queries remain in effect.

Immediately after each query, determine whether a good permutation exists for the current $p,q,r$.

The input is given from Standard Input in the following format:

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

Each case is given in the following format:

$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$

In the $j$-th query, if $s_j=1$ swap the $i_j$-th and $(i_j+1)$-th elements of $p$; if $s_j=2$, do the same in $q$; if $s_j=3$, do the same in $r$.

For each query of each test case, print YES if a good permutation exists immediately after the query, and print NO otherwise. Print one answer per line.

• $1 \le T \le 100\,000$.
• $2 \le N \le 200\,000$.
• $1 \le M \le 200\,000$.
• Each of $p,q,r$ is a permutation of $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$).
• The sum of $N$ over all test cases does not exceed $200\,000$.
• The sum of $M$ over all test cases does not exceed $200\,000$.