409104: GYM103438 J ABC Legacy

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. ABC Legacytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a string $$$S$$$ of length $$$2n$$$, consisting of the characters A, B and C. Determine if $$$S$$$ can be split into $$$n$$$ non-intersecting subsequences, each of which forms one of the strings "AB", "AC", "BC". If it is possible, find such a splitting.

Input

The first line of input contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line of input contains a string $$$S$$$ of length $$$2n$$$, consisting of the characters A, B and C.

Output

If the splitting is not possible, print "NO" (without quotes).

If the splitting is possible, print "YES" (without quotes), followed by $$$n$$$ lines, each describing two indices for the $$$i$$$-th subsequence ($$$1 \le l_i < r_i \le 2n$$$).

ExamplesInput
3
BABBCC
Output
YES
3 5
1 6
2 4
Input
2
CBAC
Output
NO
Input
1
AA
Output
NO
Input
3
ABCACB
Output
YES
2 3
4 6
1 5

加入题单

上一题 下一题 算法标签: