#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vpdd = vector<pdd>;
using vvpdd = vector<vpdd>;
template <typename T>
void ckmin(T& a, const T& b) {
  a = min(a, b);
}
template <typename T>
void ckmax(T& a, const T& b) {
  a = max(a, b);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace __input {
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
template <class Arg, class... Args>
void re(Arg& first, Args&... rest) {
  re(first);
  re(rest...);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = 0; i < (int((a).size())); i++) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = 0; i < (SZ); i++) re(a[i]);
}
}  // namespace __input
using namespace __input;
namespace __output {
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T, size_t SZ>
void pr(const array<T, SZ>& x);
template <class T>
void pr(const vector<T>& x);
template <class T>
void pr(const deque<T>& x);
template <class T>
void pr(const set<T>& x);
template <class T1, class T2>
void pr(const map<T1, T2>& x);
template <class T>
void pr(const T& x) {
  cout << x;
}
template <class Arg, class... Args>
void pr(const Arg& first, const Args&... rest) {
  pr(first);
  pr(rest...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T, bool pretty = true>
void prContain(const T& x) {
  if (pretty) pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? pretty ? ", " : " " : "", a), fst = 0;
  if (pretty) pr("}");
}
template <class T>
void pc(const T& x) {
  prContain<T, false>(x);
  pr("\n");
}
template <class T, size_t SZ>
void pr(const array<T, SZ>& x) {
  prContain(x);
}
template <class T>
void pr(const vector<T>& x) {
  prContain(x);
}
template <class T>
void pr(const deque<T>& x) {
  prContain(x);
}
template <class T>
void pr(const set<T>& x) {
  prContain(x);
}
template <class T1, class T2>
void pr(const map<T1, T2>& x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg>
void ps(const Arg& first) {
  pr(first);
  ps();
}
template <class Arg, class... Args>
void ps(const Arg& first, const Args&... rest) {
  pr(first, " ");
  ps(rest...);
}
}  // namespace __output
using namespace __output;
namespace __algorithm {
template <typename T>
void dedup(vector<T>& v) {
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
}
template <typename T>
typename vector<T>::iterator find(vector<T>& v, const T& x) {
  auto it = lower_bound((v).begin(), (v).end(), x);
  return it != v.end() && *it == x ? it : v.end();
}
template <typename T>
size_t index(vector<T>& v, const T& x) {
  auto it = find(v, x);
  assert(it != v.end() && *it == x);
  return it - v.begin();
}
template <typename C, typename T, typename OP>
vector<T> prefixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = 0; i < (int((v).size())); i++) r[i + 1] = op(r[i], v[i]);
  return r;
}
template <typename C, typename T, typename OP>
vector<T> suffixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = (int((v).size())) - 1; i >= 0; i--) r[i] = op(v[i], r[i + 1]);
  return r;
}
}  // namespace __algorithm
using namespace __algorithm;
struct monostate {
  friend istream& operator>>(istream& is,
                             const __attribute__((unused)) monostate& ms) {
    return is;
  }
  friend ostream& operator<<(ostream& os,
                             const __attribute__((unused)) monostate& ms) {
    return os;
  }
} ms;
template <typename W = monostate>
struct wedge {
  int u, v, i;
  W w;
  wedge<W>(int _u = -1, int _v = -1, int _i = -1) : u(_u), v(_v), i(_i) {}
  int operator[](int loc) const { return u ^ v ^ loc; }
  friend void re(wedge& e) {
    re(e.u, e.v, e.w);
    --e.u, --e.v;
  }
  friend void pr(const wedge& e) { pr(e.u, "<-", e.w, "->", e.v); }
};
namespace __io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.precision(15);
  if (int((second).size())) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace __io
using namespace __io;
using dpii = deque<pii>;
dpii split(string str) {
  dpii res;
  for (int i = 0, j; i < int((str).size()); i = j) {
    j = i;
    while (j < int((str).size()) && str[j] == str[i]) j++;
    res.push_back({str[i] - 'a', j - i});
  }
  return res;
}
int main() {
  setIO();
  string _s, _t;
  re(_s, _t);
  dpii second = split(_s), t = split(_t);
  auto sim_swap = [&](int si, int ti) {
    assert(0 <= si && si <= int((second).size()));
    assert(0 <= ti && ti <= int((t).size()));
    int tsz = int((t).size()) - ti + si, tf = 0;
    if (tsz) {
      if (si > 0 && ti < int((t).size()) && second[si - 1].first == t[ti].first)
        tsz--;
      tf = si ? second.front().first : t[ti].first;
    }
    int ssz = int((second).size()) - si + ti, sf = 0;
    if (ssz) {
      if (ti > 0 && si < int((second).size()) &&
          t[ti - 1].first == second[si].first)
        ssz--;
      sf = ti ? t.front().first : second[si].first;
    }
    int ops = (si > 0 || ti > 0) + max(tsz - 1, 0) + max(ssz - 1, 0);
    if (tf == sf) {
      if (tsz > ssz)
        tsz--;
      else
        ssz--;
    }
    ops -= max(0, min(tsz, ssz) - 1);
    return ops;
  };
  vpii ops;
  auto do_swap = [&](int si, int ti) {
    if (si == 0 && ti == 0) return;
    ops.push_back({0, 0});
    stack<pii> st, ts;
    for (int i = 0; i < (si); i++) {
      pii p = second.front();
      second.pop_front();
      ops.back().first += p.second;
      st.push(p);
    }
    for (int i = 0; i < (ti); i++) {
      pii p = t.front();
      t.pop_front();
      ops.back().second += p.second;
      ts.push(p);
    }
    if (!ts.empty() && !second.empty() &&
        ts.top().first == second.front().first) {
      second.front().second += ts.top().second;
      ts.pop();
    }
    while (!ts.empty()) {
      second.push_front(ts.top());
      ts.pop();
    }
    if (!st.empty() && !t.empty() && st.top().first == t.front().first) {
      t.front().second += st.top().second;
      st.pop();
    }
    while (!st.empty()) {
      t.push_front(st.top());
      st.pop();
    }
  };
  array<int, 3> ans{INT_MAX, -1, -1};
  for (int si = 0; si < (int((second).size()) + 1); si++) {
    int tn = (2 * si + int((t).size()) - int((second).size())) / 2;
    for (int ti = (max(tn - 3, 0)); ti < (min(tn + 3, int((t).size())) + 1);
         ti++) {
      ckmin(ans, {sim_swap(si, ti), si, ti});
    }
  }
  do_swap(ans[1], ans[2]);
  while (int((second).size()) > 1 || int((t).size()) > 1) {
    array<int, 3> best{INT_MAX, -1, -1};
    for (int si = 0; si < (min(2, int((second).size())) + 1); si++)
      for (int ti = (!si); ti < (min(2, int((t).size())) + 1); ti++)
        ckmin(best, {sim_swap(si, ti), si, ti});
    do_swap(best[1], best[2]);
  }
  ps(int((ops).size()));
  for (auto& p : ops) ps(p.first, p.second);
  return 0;
}

### Prompt

Your task is to create a Cpp solution to the following problem:

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·105).

The second line contains a string t (1 ≤ |t| ≤ 2·105).

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·105) — the number of operations.

Each of the next n lines should contain two space-separated integers ai, bi — 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.

Examples

Input

bab
bb


Output

2
1 0
1 3


Input

bbbb
aaa


Output

0

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vpdd = vector<pdd>;
using vvpdd = vector<vpdd>;
template <typename T>
void ckmin(T& a, const T& b) {
  a = min(a, b);
}
template <typename T>
void ckmax(T& a, const T& b) {
  a = max(a, b);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace __input {
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
template <class Arg, class... Args>
void re(Arg& first, Args&... rest) {
  re(first);
  re(rest...);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = 0; i < (int((a).size())); i++) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = 0; i < (SZ); i++) re(a[i]);
}
}  // namespace __input
using namespace __input;
namespace __output {
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T, size_t SZ>
void pr(const array<T, SZ>& x);
template <class T>
void pr(const vector<T>& x);
template <class T>
void pr(const deque<T>& x);
template <class T>
void pr(const set<T>& x);
template <class T1, class T2>
void pr(const map<T1, T2>& x);
template <class T>
void pr(const T& x) {
  cout << x;
}
template <class Arg, class... Args>
void pr(const Arg& first, const Args&... rest) {
  pr(first);
  pr(rest...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T, bool pretty = true>
void prContain(const T& x) {
  if (pretty) pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? pretty ? ", " : " " : "", a), fst = 0;
  if (pretty) pr("}");
}
template <class T>
void pc(const T& x) {
  prContain<T, false>(x);
  pr("\n");
}
template <class T, size_t SZ>
void pr(const array<T, SZ>& x) {
  prContain(x);
}
template <class T>
void pr(const vector<T>& x) {
  prContain(x);
}
template <class T>
void pr(const deque<T>& x) {
  prContain(x);
}
template <class T>
void pr(const set<T>& x) {
  prContain(x);
}
template <class T1, class T2>
void pr(const map<T1, T2>& x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg>
void ps(const Arg& first) {
  pr(first);
  ps();
}
template <class Arg, class... Args>
void ps(const Arg& first, const Args&... rest) {
  pr(first, " ");
  ps(rest...);
}
}  // namespace __output
using namespace __output;
namespace __algorithm {
template <typename T>
void dedup(vector<T>& v) {
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
}
template <typename T>
typename vector<T>::iterator find(vector<T>& v, const T& x) {
  auto it = lower_bound((v).begin(), (v).end(), x);
  return it != v.end() && *it == x ? it : v.end();
}
template <typename T>
size_t index(vector<T>& v, const T& x) {
  auto it = find(v, x);
  assert(it != v.end() && *it == x);
  return it - v.begin();
}
template <typename C, typename T, typename OP>
vector<T> prefixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = 0; i < (int((v).size())); i++) r[i + 1] = op(r[i], v[i]);
  return r;
}
template <typename C, typename T, typename OP>
vector<T> suffixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = (int((v).size())) - 1; i >= 0; i--) r[i] = op(v[i], r[i + 1]);
  return r;
}
}  // namespace __algorithm
using namespace __algorithm;
struct monostate {
  friend istream& operator>>(istream& is,
                             const __attribute__((unused)) monostate& ms) {
    return is;
  }
  friend ostream& operator<<(ostream& os,
                             const __attribute__((unused)) monostate& ms) {
    return os;
  }
} ms;
template <typename W = monostate>
struct wedge {
  int u, v, i;
  W w;
  wedge<W>(int _u = -1, int _v = -1, int _i = -1) : u(_u), v(_v), i(_i) {}
  int operator[](int loc) const { return u ^ v ^ loc; }
  friend void re(wedge& e) {
    re(e.u, e.v, e.w);
    --e.u, --e.v;
  }
  friend void pr(const wedge& e) { pr(e.u, "<-", e.w, "->", e.v); }
};
namespace __io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.precision(15);
  if (int((second).size())) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace __io
using namespace __io;
using dpii = deque<pii>;
dpii split(string str) {
  dpii res;
  for (int i = 0, j; i < int((str).size()); i = j) {
    j = i;
    while (j < int((str).size()) && str[j] == str[i]) j++;
    res.push_back({str[i] - 'a', j - i});
  }
  return res;
}
int main() {
  setIO();
  string _s, _t;
  re(_s, _t);
  dpii second = split(_s), t = split(_t);
  auto sim_swap = [&](int si, int ti) {
    assert(0 <= si && si <= int((second).size()));
    assert(0 <= ti && ti <= int((t).size()));
    int tsz = int((t).size()) - ti + si, tf = 0;
    if (tsz) {
      if (si > 0 && ti < int((t).size()) && second[si - 1].first == t[ti].first)
        tsz--;
      tf = si ? second.front().first : t[ti].first;
    }
    int ssz = int((second).size()) - si + ti, sf = 0;
    if (ssz) {
      if (ti > 0 && si < int((second).size()) &&
          t[ti - 1].first == second[si].first)
        ssz--;
      sf = ti ? t.front().first : second[si].first;
    }
    int ops = (si > 0 || ti > 0) + max(tsz - 1, 0) + max(ssz - 1, 0);
    if (tf == sf) {
      if (tsz > ssz)
        tsz--;
      else
        ssz--;
    }
    ops -= max(0, min(tsz, ssz) - 1);
    return ops;
  };
  vpii ops;
  auto do_swap = [&](int si, int ti) {
    if (si == 0 && ti == 0) return;
    ops.push_back({0, 0});
    stack<pii> st, ts;
    for (int i = 0; i < (si); i++) {
      pii p = second.front();
      second.pop_front();
      ops.back().first += p.second;
      st.push(p);
    }
    for (int i = 0; i < (ti); i++) {
      pii p = t.front();
      t.pop_front();
      ops.back().second += p.second;
      ts.push(p);
    }
    if (!ts.empty() && !second.empty() &&
        ts.top().first == second.front().first) {
      second.front().second += ts.top().second;
      ts.pop();
    }
    while (!ts.empty()) {
      second.push_front(ts.top());
      ts.pop();
    }
    if (!st.empty() && !t.empty() && st.top().first == t.front().first) {
      t.front().second += st.top().second;
      st.pop();
    }
    while (!st.empty()) {
      t.push_front(st.top());
      st.pop();
    }
  };
  array<int, 3> ans{INT_MAX, -1, -1};
  for (int si = 0; si < (int((second).size()) + 1); si++) {
    int tn = (2 * si + int((t).size()) - int((second).size())) / 2;
    for (int ti = (max(tn - 3, 0)); ti < (min(tn + 3, int((t).size())) + 1);
         ti++) {
      ckmin(ans, {sim_swap(si, ti), si, ti});
    }
  }
  do_swap(ans[1], ans[2]);
  while (int((second).size()) > 1 || int((t).size()) > 1) {
    array<int, 3> best{INT_MAX, -1, -1};
    for (int si = 0; si < (min(2, int((second).size())) + 1); si++)
      for (int ti = (!si); ti < (min(2, int((t).size())) + 1); ti++)
        ckmin(best, {sim_swap(si, ti), si, ti});
    do_swap(best[1], best[2]);
  }
  ps(int((ops).size()));
  for (auto& p : ops) ps(p.first, p.second);
  return 0;
}

```