There are two strings $*s*$ and $*t*$, consisting only of letters a and b. You can make the following operation several times: choose a prefix of $*s*$, a prefix of $*t*$ and swap them. Prefixes can be empty, also a prefix can coincide with a whole string.

Your task is to find a sequence of operations after which one of the strings consists only of a letters and the other consists only of b letters. The number of operations should be minimized.

Input

The first line contains a string $*s*$ ($1 ≤ |*s*| ≤ 2·10^{5}$).

The second line contains a string $*t*$ ($1 ≤ |*t*| ≤ 2·10^{5}$).

Here $|*s*|$ and $|*t*|$ denote the lengths of $*s*$ and $*t*$, respectively. It is guaranteed that at least one of the strings contains at least one a letter and at least one of the strings contains at least one b letter.

Output

The first line should contain a single integer $*n*$ ($0 ≤ *n* ≤ 5·10^{5}$) — the number of operations.

Each of the next $*n*$ lines should contain two space-separated integers $*a*_{*i*}$, $*b*_{*i*}$ — the lengths of prefixes of $*s*$ and $*t*$ to swap, respectively.

If there are multiple possible solutions, you can print any of them. It's guaranteed that a solution with given constraints exists.

Note

In the first example, you can solve the problem in two operations:

1. Swap the prefix of the first string with length $1$ and the prefix of the second string with length $0$. After this swap, you'll have strings ab and bbb.
2. Swap the prefix of the first string with length $1$ and the prefix of the second string with length $3$. After this swap, you'll have strings bbbb and a.

In the second example, the strings are already appropriate, so no operations are needed.