Dọn phòng bừa bộn

Cho một dãy ngoặc $s=s_1{s}_2\dots s_n$ độ dài $n$ chẵn, gồm đúng $\frac{n}{2}$ ký tự ( và $\frac{n}{2}$ ký tự ).

Trong một thao tác, bạn chọn một đoạn con liên tiếp $s[l\dots r]$ và đảo ngược nó, tức là đoạn $s_l,s_{l+1},\dots ,s_r$ trở thành $s_r,s_{r-1},\dots ,s_l$. Ví dụ, đảo ngược đoạn $s[2\dots 4]$ của $s=$ ((())) ta được ()(()).

Ta gọi dãy $s$ là gọn gàng nếu:

• toàn bộ $s$ là một dãy ngoặc đúng;
• có đúng $k$ tiền tố của $s$ là dãy ngoặc đúng (tính cả chính $s$).

Ví dụ, với $k=2$, dãy (())() là gọn gàng (hai tiền tố đúng là (()) và (())()).

Hãy dùng không quá $n$ thao tác để biến $s$ thành một dãy gọn gàng. Các thao tác được thực hiện lần lượt. Bạn không cần tối thiểu hóa số thao tác. Dữ liệu đảm bảo luôn có đáp án; nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $t$, số bộ dữ liệu.

Mỗi bộ dữ liệu gồm:

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• Dòng thứ hai chứa xâu $s$ độ dài $n$, chỉ gồm các ký tự ( và ).

Dữ liệu ra

Với mỗi bộ dữ liệu:

• Dòng đầu in số nguyên $m$ ($0\le m\le n$), số thao tác.
• $m$ dòng tiếp theo, mỗi dòng in hai số nguyên $l,r$ ($1\le l\le r\le n$) mô tả thao tác đảo ngược đoạn $s[l\dots r]$.

Sau khi thực hiện tất cả thao tác, $s$ phải là dãy ngoặc đúng và có đúng $k$ tiền tố là dãy ngoặc đúng.

Ràng buộc

• $1\le t\le 100$
• $2\le n\le 2000$, $n$ chẵn
• $1\le k\le \frac{n}{2}$
• $s$ có đúng $\frac{n}{2}$ ký tự ( và $\frac{n}{2}$ ký tự )
• Tổng $n$ của tất cả bộ dữ liệu không vượt quá $2000$

Ví dụ