You have two valid bracket sequences $s_1$ and $s_2$, both of length $2n$.

In your view, different bracket sequences have different aesthetic qualities. Therefore, you particularly like bracket sequences with a certain structure, while you dislike those with other structures. You wish to perform some transformations on $s_1$ to eliminate the structures you dislike.

Specifically, a structure of the form $((A)B)(C)$ (where $A, B, C$ are all valid bracket sequences, same below) is one you like, while the following structures are ones you dislike: $(((A)B)C)$, $((A)(B)C)$, $(A)((B)C)$, and $(A)(B)(C)$. Accordingly, you have 4 transformation operations, each representing taking a substring of the original bracket sequence that you dislike and transforming it into a structure you like before placing it back in its original position.

Formally, these 4 transformation operations are as follows: Operation 1: Transform a string of the form $p(((A)B)C)q$ into $p((A)B)(C)q$ (where $p, q$ are arbitrary strings, which can be empty, and are not necessarily valid bracket sequences, same below); Operation 2: Transform a string of the form $p((A)(B)C)q$ into $p((A)B)(C)q$; Operation 3: Transform a string of the form $p(A)((B)C)q$ into $p((A)B)(C)q$; Operation 4: Transform a string of the form $p(A)(B)(C)q$ into $p((A)B)(C)q$;

Additionally, you wish to have some operations that can change the length of the string, so you want to be able to insert a pair of brackets $()$ at any position in the string, or delete a pair of brackets $()$ at any position. Formally described as follows: Operation 5: Transform a string of the form $pq$ into $p()q$; Operation 6: Transform a string of the form $p()q$ into $pq$;

However, due to some constraints, the number of times you perform the above two operations must not exceed 2 times each (some subtasks do not have this restriction, see the Constraints section for details).

It is easy to prove that for any valid bracket sequence, performing one of the above 6 operations results in a valid bracket sequence.

You now want to know: using the above operations, can $s_1$ be transformed into $s_2$? If so, you hope to find a transformation plan with a reasonable number of operations.

Input

Each test case consists of multiple data groups. The first line contains 2 positive integers $id, T$, representing the test case ID and the number of data groups, respectively. The test case ID can help you determine special conditions for the test case.

For each data group: The first line contains two positive integers $n, k$, where $k$ represents the upper limit of your operation steps. The second line contains a bracket sequence $s_1$ of length $2n$. The third line contains a bracket sequence $s_2$ of length $2n$.

Output

For each data group, output several lines: The first line of each data group contains an integer $m$, representing the number of your operations. You must ensure $m \le k$. The next $m$ lines each output 2 non-negative integers $op\ x$, describing an operation. Here $op$ is the current operation number, satisfying $1 \le op \le 6$; $x$ describes the position of this operation, defined for convenience as the length of $p$ in the formal description.

You need to ensure that the given $op\ x$ correctly describes a valid operation; on this basis, it can be proven that all valid operations are uniquely determined by $op\ x$. At the same time, you must ensure that the number of times operations 5 and 6 are used in each data group does not exceed 2, except for subtasks with special instructions. If there are multiple transformation plans that meet the requirements, output any one of them. In particular, if this group of data cannot be transformed within $k$ steps, you only need to output $-1$ for this group of data.

Constraints

For 100% of the data, $T \le 3, n \le 10^5, k \le 3 \times 10^5$.

Examples

Input 1

0 1
3 6
(())()
((()))

Output 1

3
5 6
4 0
6 6

Note

In all example files, $id$ is $0$. The transformation process for this data group is as follows: 1. (())() 2. (())()() 3. ((()))() 4. ((()))

Input 2

0 2
3 10
(()())
(())()
4 20
((()))()
(()())()

Output 2

1
2 0
2
6 2
5 1

Note

A string $s$ is called a valid bracket sequence if and only if $s$ consists only of an equal number of characters '(' and ')', and for every prefix of $s$, the number of '(' is not less than the number of ')'. In particular, the empty string is also a valid bracket sequence.