P8077 [WC2022] Sequence Transformation (No data for now)

2s 512M -O2. There is currently no data for this problem. You can submit on [UOJ](https://uoj.ac/problem/989).

You have two valid bracket sequences $s_1, s_2$, both of length $2n$. In your eyes, different bracket sequences bring different visual aesthetics. Therefore, you especially like bracket sequences with a certain kind of structure, and dislike some other structures. You want to apply some transformations to $s_1$ to eliminate some structures you dislike. Specifically, a structure of the form $\texttt{((A)B)(C)}$ (where $\texttt{A,B,C}$ are all valid bracket sequences; the same applies below) is what you like, while the following structures are what you dislike: $\texttt{(((A)B)C)}$, $\texttt{((A)(B)C)}$, $\texttt{(A)((B)C)}$, and $\texttt{(A)(B)(C)}$. Accordingly, you have $4$ kinds of transformation operations: each takes one disliked substring from the original bracket sequence, transforms it into the liked structure, and puts it back to the original position. Formally, these $4$ operations are: - Operation $1$: transform a string of the form $\texttt{p(((A)B)C)q}$ into $\texttt{p((A)B)(C)q}$ (where $\texttt{p,q}$ are any strings, possibly empty, and they do not necessarily have to be valid bracket sequences; the same applies below). - Operation $2$: transform a string of the form $\texttt{p((A)(B)C)q}$ into $\texttt{p((A)B)(C)q}$. - Operation $3$: transform a string of the form $\texttt{p(A)((B)C)q}$ into $\texttt{p((A)B)(C)q}$. - Operation $4$: transform a string of the form $\texttt{p(A)(B)(C)q}$ into $\texttt{p((A)B)(C)q}$. In addition, you also want some operations that can change the length of the string. So you want to be able to insert a pair of brackets $\texttt{()}$ at any position in the string, or delete a pair of brackets $\texttt{()}$ at any position, formally described as follows: - Operation $5$: transform a string of the form $\texttt{pq}$ into $\texttt{p()q}$. - Operation $6$: transform a string of the form $\texttt{p()q}$ into $\texttt{pq}$. However, due to some constraints, the numbers of times you perform the above two operations are **at most $2$ times each** (this constraint does not apply in some subtasks; see the Constraints section for details). It is easy to prove that applying any one of the $6$ operations above to any valid bracket sequence will still result in a valid bracket sequence. Now you want to know: with the operations above, can you transform $s_1$ into $s_2$? If it is possible, you want to find a transformation plan that does not use too many operations.

Each test point consists of multiple test cases. The first line contains two positive integers $\mathit{id}, T$, representing the test point ID and the number of test cases. The test point ID can help you determine special conditions of that test point. For each test case: The first line contains two positive integers $n, k$, where $k$ is the upper limit on the number of operations you are allowed to use. The second line contains a bracket sequence $s_1$ of length $2n$. The third line contains a bracket sequence $s_2$ of length $2n$.

For each test case, output several lines: The first line of each test case is an integer $m$, representing the number of operations. You must ensure that $m \leq k$. In the next $m$ lines, output two non-negative integers $\mathit{op}\ x$ describing an operation. Here $\mathit{op}$ is the operation ID and must satisfy $1 \leq \mathit{op} \leq 6$. The value $x$ describes the position of this operation; for convenience, it is defined uniformly as the length of $p$ in the formal description. You must ensure that the output $\mathit{op}\ x$ indeed describes a valid operation as required. Under this condition, it can be proven that every valid operation can be uniquely determined by $\mathit{op}\ x$. You must also ensure that, in each test case, the numbers of uses of operations $5$ and $6$ do not exceed $2$ each, except for subtasks with special statements. If there are multiple valid transformation plans, output any one. In particular, if this test case cannot be transformed within $k$ steps, you only need to output $-1$ for this test case.

**[Sample Explanation #1]** In all sample files, $\mathit{id}$ is $0$. The transformation process for this test case is: $\texttt{(())()} \rightarrow \texttt{(())()()} \rightarrow \texttt{((()))()} \rightarrow \texttt{((()))}$ **[Constraints]** | Test point ID | $n \le$ | $k =$ | Special conditions | |:-:|:-:|:-:|:-:| | $1 \sim 3$ | $10$ | ${10}^5$ | None | | $4 \sim 6$ | $100$ | ${10}^4$ | None | | $7 \sim 8$ | $500$ | ${10}^5$ | Operations $5$ and $6$ can be used any number of times | | $9 \sim 11$ | $1000$ | ${10}^4$ | None | | $12 \sim 13$ | $5000$ | $2 \times {10}^4$ | None | | $14 \sim 16$ | ${10}^5$ | $3 \times {10}^5$ | Operations $5$ and $6$ can be used any number of times | | $17 \sim 20$ | ${10}^5$ | $3 \times {10}^5$ | None | For $100\%$ of the data, $1 \le T \le 3$, $1 \le n \le {10}^5$, $1 \le k \le 3 \times {10}^5$. [image]:  **[Hint]** A string $s$ is called a valid bracket sequence if and only if $s$ consists only of an equal number of characters $\texttt{(}$ and $\texttt{)}$, and for every prefix of $s$, the number of $\texttt{(}$ is at least the number of $\texttt{)}$. In particular, the empty string is also a valid bracket sequence. Translated by ChatGPT 5