Даны две строки s и t, состоящие только из букв a и b. Вы можете несколько раз совершить следующую операцию: выбрать префикс строки s, префикс строки t и поменять их местами. Префиксы могут быть пустыми, также префикс может совпадать со всей строкой.
Ваша задача — найти последовательность операций, после которой одна из строк будет состоять только из букв a, а другая — только из букв b. Число операций нужно минимизировать.
Выходные данные
Первая строка вывода должна содержать число n (0 ≤ n ≤ 5·105) — количество операций.
Каждая из последующих n строк должна содержать два числа ai, bi, разделённых пробелом — длины префиксов s и t для обмена, соответственно.
Если существует несколько возможных решений, вы можете вывести любое. Гарантируется, что решение с заданными ограничениями существует.
Примечание
В первом примере вы можете решить задачу в две операции:
- Обменять префикс первой строки длины 1 и префикс второй строки длины 0. После этого обмена вы получите ab и bbb.
- Обменять префикс первой строки длины 1 и префикс второй строки длины 3. После этого обмена вы получите bbbb и a.
Во втором примере строки уже подходящие, поэтому операции не нужны.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
bab
bb
|
2
1 0
1 3
|
|
2
|
bbbb
aaa
|
0
|