Note: If your judgment is correct, but you output an invalid sequence of operations (other than a sequence with $M=0$), you may receive a Wrong Answer result and $0$ points. Please be aware of this.

Given a string $S$ of length $N$ consisting only of characters A and B, you can perform the following operation:

• Choose $2$ or $3$ consecutive elements such that all chosen elements have the same value. Then, remove these elements from the string.

You want to determine if it is possible to empty the entire string. If it is possible, you must also output a valid sequence of operations.

Input

The first line of input contains an integer $N$.

The next line contains a string $S$ of length $N$ consisting only of characters A and B.

Output

If there is no valid sequence of operations to empty $S$, output a single line containing No.

Otherwise, output Yes on the first line.

Then, output an integer $M$ on the next line, representing the number of operations in your sequence.

The following $M$ lines should each contain two integers $i$ and $j$, representing the removal of $j$ elements starting from index $i$ to $i+j-1$. You must ensure $j \in \{2, 3\}$ and $1 \le i \le n-j+1$. The elements in the string are indexed starting from $1$, and the indices of subsequent elements are updated after each removal. See the sample data and its explanation for details.

Please note that if you can only determine whether a solution exists but cannot construct a correct sequence, you can still obtain partial points. In this case, do not output the sequence, or output a sequence with $M=0$; otherwise, you may fail to receive these points.

Examples

Input 1

9
AABBBBAAA

Output 1

Yes
4
3 2
3 2
1 3
1 2

Note 1

• Initially, $S = \texttt{AABBBBAAA}$. Remove $2$ consecutive $\texttt{B}$s starting from the $3$rd character. The string becomes $S = \texttt{AABBAAA}$.
• Then, $S = \texttt{AABBAAA}$. Remove $2$ consecutive $\texttt{B}$s starting from the $3$rd character. The string becomes $S = \texttt{AAAAA}$.
• Then, $S = \texttt{AAAAA}$. Remove $3$ consecutive $\texttt{A}$s starting from the $1$st character. The string becomes $S = \texttt{AA}$.
• Then, $S = \texttt{AA}$. Remove $2$ consecutive $\texttt{A}$s starting from the $1$st character. The string becomes empty.

The following output can earn $60\%$ of the points:

Yes

Input 2

2
AB

Output 2

No

Subtasks

For all test cases, $1 \le N = |S| \le 10^6$.

For a test case, if you can only determine whether a solution exists but cannot provide the specific construction, you can obtain $60\%$ of the points.