Description

You have two strings $s, t$, and they contain only the letters a and b. You may perform the following operation multiple times: choose a prefix of $s$ and a prefix of $t$, and swap them. (Note that the prefix can be empty or the entire string.)

Your task is to find a sequence of operations such that after performing them, one string contains only the character a, and the other contains only the character b.

You should use as few operations as possible, but a non-optimal solution may still get partial points. For details, see the “Constraints and Hint” section.

Input Format

The input consists of two lines, containing the two strings $s, t$.

Output Format

Output an integer $n$ ($0\leq n\leq 5\times 10^5$) on the first line, representing the total number of operations.

In the next $n$ lines, each line contains two integers $a_i, b_i$, which are the prefix lengths of $s$ and $t$ to be swapped in this operation, respectively.

If there are multiple valid solutions, you may output any of them.

bab
bb

2
1 0
1 3

bbbb
aaa

0

Hint

Explanation for Sample $1$:

In this sample, first swap the prefix of length $1$ of the first string with the prefix of length $0$ of the second string, i.e. insert b at the beginning of the second string. The two strings become ab and bbb. Next, swap the prefix of length $1$ of the first string with the prefix of length $3$ of the second string, i.e. swap a and bbb. The two strings become bbbb and a, achieving the goal.

Explanation for Sample $2$:

It is already in the required final state.

Scoring Policy

Let $n$ be the number of operations you output, and $m$ be the number in the official answer. This problem uses SPJ.

• If for all test cases $n=m$, you will get $100\%$ of the score.

• If for all test cases $n\leq m+2$, you will get $70\%$ of the score. (Rounded to the nearest integer.)

• If for all test cases $n\leq 2m+2$, you will get $50\%$ of the score. (Rounded to the nearest integer.)

• If for all test cases $n\leq 5\times 10^5$, you will get $30\%$ of the score. (Rounded to the nearest integer.)

• If for at least one test case $n > 5\times 10^5$, you will get $0\%$ of the score.

For $100\%$ of the testdata, it is guaranteed that $1\leq \lvert s\rvert,\lvert t\rvert \leq 2\times 10^5$, where $\lvert s\rvert,\lvert t\rvert$ denote the lengths of $s, t$, respectively. It is also guaranteed that at least one string contains at least one character a, and at least one string contains at least one character b.

Constraints

Translated by ChatGPT 5