C. Упрощенное скрещивание
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Биоинформатик Федот решил заняться скрещиванием двух организмов. Последовательности ДНК этих организмов — это две строки $$$s_0$$$ и $$$t_0$$$, состоящие из символов 'A', 'C', 'G' и 'T'.

Поскольку Федоту всего лишь 5 лет, он не очень знает, как происходит скрещивание, но абсолютно уверен, что если у него есть последовательности $$$s_i$$$ и $$$t_i$$$, это происходит следующим образом:

  • Строка $$$s_i$$$ делится на две строки (возможно нулевой длины) $$$s_i^p$$$ и $$$s_i^s$$$ такие, что их конкатенация $$$s_i^p + s_i^s$$$ равна $$$s_i$$$ (то есть $$$s_i^p$$$ — префикс строки $$$s$$$, а $$$s_i^s$$$ — оставшийся суффикс)
  • Аналогичным образом $$$t_i$$$ делится на $$$t_i^p$$$ и $$$t_i^s$$$
  • Исходные последовательности (строки) заменяются на $$$s_{i+1} = s_i^p + t_i^s$$$ и $$$t_{i+1} = t_i^p + s_i^s$$$

Федот хочет произвести скрещивание несколько раз, чтобы в конце получить две последовательности ДНК $$$s_k$$$ и $$$t_k$$$ такие, что $$$s_k$$$ состоит только из аденина ('A'), а $$$t_k$$$ — не содержит аденин вообще. Помогите ему добиться этого за минимальное число скрещиваний.

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

Ввод состоит из двух строк — $$$s_0$$$ и $$$t_0$$$ — последовательностей ДНК двух исходных организмов ($$$1 \leqslant |s_0|, |t_0| \leqslant 10^6$$$).

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

В первой строке выведите число $$$k$$$ — минимальное количество шагов скрещивания, которое необходимо для переноса всего аденина в первый организм.

В $$$i$$$-й (нумеруя с нуля) из следующих $$$k$$$ строк выведите через пробел $$$|s_i^p|$$$ и $$$|t_i^p|$$$ — длины выбранных префиксов последовательностей на $$$i$$$-м шагу скрещивания.

Пример
Входные данные
ACAT
GAA
Выходные данные
3
3 1
2 0
1 0
Примечание

В примере из условия скрещивания происходят следующим образом:

  1. «ACAT» делится на «ACA» и «T», и «GAA» делится на «G» и «AA». После обмены суффиксами получаются «ACAAA» и «GT».
  2. Затем «ACAAA» делится на «AC» и «AAA», тогда как «GT» делится на пустой префикс «» и суффикс «GT». После обмена получаются «ACGT» и «AAA».
  3. Последним шагом отделяются префиксы длин $$$1$$$ («A») и $$$0$$$ («»), и в результате строки оказываются равны «AAAA» и «CGT».

Можно доказать, что за два скрещивания желаемого результата добиться нельзя.