D. AB-Строки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны две строки s и t, состоящие только из букв a и b. Вы можете несколько раз совершить следующую операцию: выбрать префикс строки s, префикс строки t и поменять их местами. Префиксы могут быть пустыми, также префикс может совпадать со всей строкой.

Ваша задача — найти последовательность операций, после которой одна из строк будет состоять только из букв a, а другая — только из букв b. Число операций нужно минимизировать.

Входные данные

Первая строка содержит строку s (1 ≤ |s| ≤ 2·105).

Вторая строка содержит строку t (1 ≤ |t| ≤ 2·105).

Здесь |s| и |t| означают длины строк s and t, соответственно. Гарантируется, что хотя бы в одной строке есть хотя бы один символ a и хотя бы в одной строке есть хотя бы один символ b.

Выходные данные

Первая строка вывода должна содержать число n (0 ≤ n ≤ 5·105) — количество операций.

Каждая из последующих n строк должна содержать два числа ai, bi, разделённых пробелом — длины префиксов s и t для обмена, соответственно.

Если существует несколько возможных решений, вы можете вывести любое. Гарантируется, что решение с заданными ограничениями существует.

Примеры
Входные данные
bab
bb
Выходные данные
2
1 0
1 3
Входные данные
bbbb
aaa
Выходные данные
0
Примечание

В первом примере вы можете решить задачу в две операции:

  1. Обменять префикс первой строки длины 1 и префикс второй строки длины 0. После этого обмена вы получите ab и bbb.
  2. Обменять префикс первой строки длины 1 и префикс второй строки длины 3. После этого обмена вы получите bbbb и a.

Во втором примере строки уже подходящие, поэтому операции не нужны.