У Марии есть строка \(s\) длины \(n\), состоящая из букв «A» и «B». Она хочет сделать так, чтобы строка \(s\) содержала ровно \(k\) символов «B». Для этого она может использовать следующую операцию.
- Выбрать целое число \(i\) (\(1 \leq i \leq n\)) и букву \(c\) (\(c\) должна быть равна «A» или «B»).
- После этого заменить каждую из первых \(i\) букв строки \(s\) (то есть, буквы \(s_1, s_2, \ldots, s_i\)) на \(c\).
Мария просит вас найти минимальное количество операций, которое необходимо выполнить для того, чтобы строка \(s\) содержала ровно \(k\) символов «B». Также она просит вас найти сами эти операции (то есть, число \(i\) и букву \(c\) в каждой операции).
Выходные данные
Для каждого набора входных данных в первой строке выведите число \(m\) — минимальное количество операций, которое нужно выполнить Марии.
В \(j\)-й из следующих \(m\) строк выведите число \(i\) (\(1 \le i \le n\)) и букву \(c\) (\(c\) должна быть равна «A» или «B») — параметры \(j\)-й операции.
Если существует несколько решений с минимальным возможным количеством операций, вы можете вывести любое из них.
Примечание
В первом наборе входных данных в строке \(s\) уже \(2\) символа «B», поэтому Марии не нужно выполнять ни одной операции.
Во втором наборе входных данных единственный способ добиться того, чтобы строка \(s\) содержала \(3\) символа «B» после одной операции — заменить первый символ строки \(s\) на «B»: «AABAB» \(\rightarrow\) «BABAB».
В третьем наборе входных данных единственный способ добиться того, чтобы строка \(s\) содержала \(0\) символов «B» после одной операции — заменить первые \(5\) символов строки \(s\) на «A»: «BBBBB» \(\rightarrow\) «AAAAA».
В четвёртом наборе входных один из способов добиться того, чтобы строка \(s\) содержала \(0\) символов «B» после одной операции — заменить первые \(2\) символа строки \(s\) на «A»: «BAA» \(\rightarrow\) «AAA». Обратите внимание, что «1 A» и «3 A» тоже являются правильными решениями в одну операцию.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 2
AAABB
5 3
AABAB
5 0
BBBBB
3 0
BAA
10 3
BBBABBBBAB
|
0
1
1 B
1
5 A
1
2 A
1
6 A
|