23763번 - 괄호 문자열 이동하기 스페셜 저지

문제

올바른 괄호 문자열(VPS)은 다음과 같이 정의한다.

1. 빈 문자열은 VPS이다.
2. S가 VPS라면 (S)도 VPS이다.
3. S와 T가 VPS라면 ST도 VPS이다.
4. 모든 VPS는 위 세 가지 규칙으로만 만들 수 있다.

예를 들어 "(())()", "()()()", "(()())” 등은 VPS이고, "())(()", "(", "(()()()" 등은 VPS가 아니다.

VPS를 좋아하는 태수는 길이가 $N$인 VPS $S$를 선물 받았다. 하지만 태수의 위시리스트에 담겨있던 VPS는 $T$였기에, $S$의 두 문자를 바꾸는 작업을 최대 $N$번 해서 $T$로 만들고 싶었다. 하지만 VPS를 좋아하는 태수는 다음과 같은 조건들을 만족할 때만 두 원소를 바꾸기로 했다.

• 1ドル \leq L < R \leq N$을 만족하는 $L,ドル $R$에 대해 $S[L]$과 $S[R]$을 바꾼다고 할 때, 두 문자 사이에 있는 문자열도 VPS여야한다. 즉, $R-L=1$을 만족하거나 $S[L+1 ... R-1]$이 VPS여야한다. 또한, 두 문자를 바꾼 뒤에도 $S$는 VPS여야 한다.

태수를 위해 $S$를 $T$로 바꾸는 방법을 알려주자. 답이 반드시 존재함을 증명할 수 있다.

입력

첫째 줄에 테스트케이스의 개수 $C$가 주어진다. $(1 \leq C \leq 5 \times 10^5)$

각 테스트케이스 별로 입력은 다음과 같이 주어진다.

첫째 줄에 정수 $N$이 주어진다. $(1 \leq N \leq 10^6)$

둘째 줄에 길이가 $N$인 VPS $S$가 주어진다.

셋째 줄에 길이가 $N$인 VPS $T$가 주어진다.

모든 테스트케이스의 $N$의 합은 10ドル^6$을 넘지 않는다.

출력

각 테스트케이스 별로 다음과 같이 출력한다.

첫째 줄에 작업 횟수 $X$ $(0 \leq X \leq N)$를 출력한다.

둘째 줄부터 $X$줄에 걸쳐, 바꾸는 두 원소의 인덱스 $L$ $R$ 을 작업 순서에 맞춰 출력한다.

반드시 작업 횟수가 최소가 될 필요는 없다.

제한

힌트