#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class t, class u>
void chmax(t& first, u second) {
  if (first < second) first = second;
}
template <class t, class u>
void chmin(t& first, u second) {
  if (second < first) first = second;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pi = pair<ll, ll>;
using vi = vc<ll>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
using uint = unsigned;
using ull = unsigned long long;
template <class t, size_t n>
ostream& operator<<(ostream& os, const array<t, n>& first) {
  return os << vc<t>(first.begin(), first.end());
}
template <ll i, class T>
void print_tuple(ostream&, const T&) {}
template <ll i, class T, class H, class... Args>
void print_tuple(ostream& os, const T& t) {
  if (i) os << ",";
  os << get<i>(t);
  print_tuple<i + 1, T, Args...>(os, t);
}
template <class... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
  os << "{";
  print_tuple<0, tuple<Args...>, Args...>(os, t);
  return os << "}";
}
template <class t>
void print(t x, ll suc = 1) {
  cout << x;
  if (suc == 1) cout << "\n";
  if (suc == 2) cout << " ";
}
ll read() {
  ll i;
  cin >> i;
  return i;
}
vi readvi(ll n, ll off = 0) {
  vi v(n);
  for (ll i = ll(0); i < ll(n); i++) v[i] = read() + off;
  return v;
}
template <class T>
void print(const vector<T>& v, ll suc = 1) {
  for (ll i = ll(0); i < ll(v.size()); i++)
    print(v[i], i == ll(v.size()) - 1 ? suc : 2);
}
string readString() {
  string s;
  cin >> s;
  return s;
}
template <class T>
T sq(const T& t) {
  return t * t;
}
void yes(bool ex = true) {
  cout << "Yes"
       << "\n";
  if (ex) exit(0);
}
void no(bool ex = true) {
  cout << "No"
       << "\n";
  if (ex) exit(0);
}
void possible(bool ex = true) {
  cout << "Possible"
       << "\n";
  if (ex) exit(0);
}
void impossible(bool ex = true) {
  cout << "Impossible"
       << "\n";
  if (ex) exit(0);
}
constexpr ll ten(ll n) { return n == 0 ? 1 : ten(n - 1) * 10; }
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
ll topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
ll topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
ll botbit(signed first) { return first == 0 ? 32 : __builtin_ctz(first); }
ll botbit(ll first) { return first == 0 ? 64 : __builtin_ctzll(first); }
ll popcount(signed t) { return __builtin_popcount(t); }
ll popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(ll i) { return i && (i & -i) == i; }
ll mask(ll i) { return (ll(1) << i) - 1; }
bool inc(ll first, ll second, ll c) { return first <= second && second <= c; }
template <class t>
void mkuni(vc<t>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
ll rand_int(ll l, ll r) {
  static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  return uniform_int_distribution<ll>(l, r)(gen);
}
template <class t>
void myshuffle(vc<t>& first) {
  for (ll i = ll(0); i < ll(ll(first.size())); i++)
    swap(first[i], first[rand_int(0, i)]);
}
template <class t>
ll lwb(const vc<t>& v, const t& first) {
  return lower_bound(v.begin(), v.end(), first) - v.begin();
}
template <class S>
struct eertree {
  struct N {
    ll suf, ser, l, r;
    ll len() { return r - l; }
    map<ll, ll> ch;
  };
  vc<N> x;
  ll dist(ll v) {
    if (x[v].suf <= 0) return -1;
    return x[v].len() - x[x[v].suf].len();
  }
  ll c;
  S s;
  eertree() {
    x.push_back({-1, -1, 1, 0, {}});
    x.push_back({0, -1, 0, 0, {}});
    c = 1;
  }
  bool chk(ll v, ll i) {
    x[v].l += i - x[v].r;
    x[v].r = i;
    return x[c].l > 0 && s[x[v].l - 1] == s[i];
  }
  template <class t>
  ll extend(t z) {
    ll i = ll(s.size());
    s.push_back(z);
    while (!chk(c, i)) c = x[c].suf;
    if (x[c].ch.count(s[i]) == 0) {
      ll d = x[c].suf;
      if (d != -1)
        while (!chk(d, i)) d = x[d].suf;
      ll e = d == -1 ? 1 : x[d].ch[s[i]];
      ll f = x[c].ch[s[i]] = x.size();
      x.push_back({e, e, x[c].l - 1, x[c].r + 1, {}});
      if (dist(f) == dist(e)) x[f].ser = x[e].ser;
    }
    return c = x[c].ch[s[i]];
  }
  N& operator[](ll i) { return x[i]; }
};
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
  string s;
  {
    string buf[2];
    for (ll k = ll(0); k < ll(2); k++) cin >> buf[k];
    ll n = ll(buf[0].size());
    for (ll i = ll(0); i < ll(n); i++) {
      s += buf[0][i];
      s += buf[1][i];
    }
  }
  ll n = ll(s.size());
  vc<pi> dp(n + 1, pi(inf, -1));
  dp[0] = pi(0, -1);
  vc<pi> buf(n * 2 + 2, pi(inf, -1));
  eertree<string> t;
  for (ll i = ll(0); i < ll(n); i++) {
    ll v = t.extend(s[i]);
    while (t[v].len()) {
      ll p = i + 1 - t[t[v].ser].len() - t.dist(v);
      buf[v] = pi(dp[p].first + 1, p);
      if (t[v].suf != t[v].ser) chmin(buf[v], buf[t[v].suf]);
      if (i % 2) chmin(dp[i + 1], buf[v]);
      v = t[v].ser;
    }
    if (i % 2 && s[i - 1] == s[i]) {
      chmin(dp[i + 1], pi(dp[i - 1].first, i - 1));
    }
  }
  ll cur = n;
  void(0);
  if (dp[cur].first == inf) {
    print(-1);
    return 0;
  }
  vc<pi> ans;
  while (cur) {
    assert(cur % 2 == 0);
    ll nx = dp[cur].second;
    if (cur - nx > 2) {
      ans.emplace_back(nx / 2, cur / 2);
    }
    cur = nx;
  }
  print(ll(ans.size()));
  for (auto v : ans) print(v.first + 1, 2), print(v.second);
}

### Prompt

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

Hurricane came to Berland and to suburbs Stringsvill. You are going to it to check if it's all right with you favorite string. Hurrinace broke it a bit by reversing some of its non-intersecting substrings. You have a photo of this string before hurricane and you want to restore it to original state using reversing minimum possible number of its substrings and find out which substrings you should reverse.

You are given a string s — original state of your string and string t — state of the string after hurricane. You should select k non-intersecting substrings of t in such a way that after reverse of these substrings string will be equal s and k is minimum possible.

Input

First line of input contains string s and second line contains string t. Both strings have same length and consist of lowercase English letters. 1 ≤ |s| = |t| ≤ 5·105

Output

In first line print k — minimum number of substrings you should reverse. Next output k lines. Each line should contain two integers li, ri meaning that you should reverse substring from symbol number li to symbol ri (strings are 1-indexed). These substrings shouldn't intersect. If there are multiple answers print any. If it's impossible to restore string output -1.

Example

Input

abcxxxdef
cbaxxxfed


Output

2
7 9
1 3

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class t, class u>
void chmax(t& first, u second) {
  if (first < second) first = second;
}
template <class t, class u>
void chmin(t& first, u second) {
  if (second < first) first = second;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pi = pair<ll, ll>;
using vi = vc<ll>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
using uint = unsigned;
using ull = unsigned long long;
template <class t, size_t n>
ostream& operator<<(ostream& os, const array<t, n>& first) {
  return os << vc<t>(first.begin(), first.end());
}
template <ll i, class T>
void print_tuple(ostream&, const T&) {}
template <ll i, class T, class H, class... Args>
void print_tuple(ostream& os, const T& t) {
  if (i) os << ",";
  os << get<i>(t);
  print_tuple<i + 1, T, Args...>(os, t);
}
template <class... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
  os << "{";
  print_tuple<0, tuple<Args...>, Args...>(os, t);
  return os << "}";
}
template <class t>
void print(t x, ll suc = 1) {
  cout << x;
  if (suc == 1) cout << "\n";
  if (suc == 2) cout << " ";
}
ll read() {
  ll i;
  cin >> i;
  return i;
}
vi readvi(ll n, ll off = 0) {
  vi v(n);
  for (ll i = ll(0); i < ll(n); i++) v[i] = read() + off;
  return v;
}
template <class T>
void print(const vector<T>& v, ll suc = 1) {
  for (ll i = ll(0); i < ll(v.size()); i++)
    print(v[i], i == ll(v.size()) - 1 ? suc : 2);
}
string readString() {
  string s;
  cin >> s;
  return s;
}
template <class T>
T sq(const T& t) {
  return t * t;
}
void yes(bool ex = true) {
  cout << "Yes"
       << "\n";
  if (ex) exit(0);
}
void no(bool ex = true) {
  cout << "No"
       << "\n";
  if (ex) exit(0);
}
void possible(bool ex = true) {
  cout << "Possible"
       << "\n";
  if (ex) exit(0);
}
void impossible(bool ex = true) {
  cout << "Impossible"
       << "\n";
  if (ex) exit(0);
}
constexpr ll ten(ll n) { return n == 0 ? 1 : ten(n - 1) * 10; }
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
ll topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
ll topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
ll botbit(signed first) { return first == 0 ? 32 : __builtin_ctz(first); }
ll botbit(ll first) { return first == 0 ? 64 : __builtin_ctzll(first); }
ll popcount(signed t) { return __builtin_popcount(t); }
ll popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(ll i) { return i && (i & -i) == i; }
ll mask(ll i) { return (ll(1) << i) - 1; }
bool inc(ll first, ll second, ll c) { return first <= second && second <= c; }
template <class t>
void mkuni(vc<t>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
ll rand_int(ll l, ll r) {
  static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  return uniform_int_distribution<ll>(l, r)(gen);
}
template <class t>
void myshuffle(vc<t>& first) {
  for (ll i = ll(0); i < ll(ll(first.size())); i++)
    swap(first[i], first[rand_int(0, i)]);
}
template <class t>
ll lwb(const vc<t>& v, const t& first) {
  return lower_bound(v.begin(), v.end(), first) - v.begin();
}
template <class S>
struct eertree {
  struct N {
    ll suf, ser, l, r;
    ll len() { return r - l; }
    map<ll, ll> ch;
  };
  vc<N> x;
  ll dist(ll v) {
    if (x[v].suf <= 0) return -1;
    return x[v].len() - x[x[v].suf].len();
  }
  ll c;
  S s;
  eertree() {
    x.push_back({-1, -1, 1, 0, {}});
    x.push_back({0, -1, 0, 0, {}});
    c = 1;
  }
  bool chk(ll v, ll i) {
    x[v].l += i - x[v].r;
    x[v].r = i;
    return x[c].l > 0 && s[x[v].l - 1] == s[i];
  }
  template <class t>
  ll extend(t z) {
    ll i = ll(s.size());
    s.push_back(z);
    while (!chk(c, i)) c = x[c].suf;
    if (x[c].ch.count(s[i]) == 0) {
      ll d = x[c].suf;
      if (d != -1)
        while (!chk(d, i)) d = x[d].suf;
      ll e = d == -1 ? 1 : x[d].ch[s[i]];
      ll f = x[c].ch[s[i]] = x.size();
      x.push_back({e, e, x[c].l - 1, x[c].r + 1, {}});
      if (dist(f) == dist(e)) x[f].ser = x[e].ser;
    }
    return c = x[c].ch[s[i]];
  }
  N& operator[](ll i) { return x[i]; }
};
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
  string s;
  {
    string buf[2];
    for (ll k = ll(0); k < ll(2); k++) cin >> buf[k];
    ll n = ll(buf[0].size());
    for (ll i = ll(0); i < ll(n); i++) {
      s += buf[0][i];
      s += buf[1][i];
    }
  }
  ll n = ll(s.size());
  vc<pi> dp(n + 1, pi(inf, -1));
  dp[0] = pi(0, -1);
  vc<pi> buf(n * 2 + 2, pi(inf, -1));
  eertree<string> t;
  for (ll i = ll(0); i < ll(n); i++) {
    ll v = t.extend(s[i]);
    while (t[v].len()) {
      ll p = i + 1 - t[t[v].ser].len() - t.dist(v);
      buf[v] = pi(dp[p].first + 1, p);
      if (t[v].suf != t[v].ser) chmin(buf[v], buf[t[v].suf]);
      if (i % 2) chmin(dp[i + 1], buf[v]);
      v = t[v].ser;
    }
    if (i % 2 && s[i - 1] == s[i]) {
      chmin(dp[i + 1], pi(dp[i - 1].first, i - 1));
    }
  }
  ll cur = n;
  void(0);
  if (dp[cur].first == inf) {
    print(-1);
    return 0;
  }
  vc<pi> ans;
  while (cur) {
    assert(cur % 2 == 0);
    ll nx = dp[cur].second;
    if (cur - nx > 2) {
      ans.emplace_back(nx / 2, cur / 2);
    }
    cur = nx;
  }
  print(ll(ans.size()));
  for (auto v : ans) print(v.first + 1, 2), print(v.second);
}

```