#include <bits/stdc++.h>
using namespace std;
class p445A {
 public:
  void solve() {
    long long n;
    cin >> n;
    unordered_map<long long, long long> cnt;
    long long mx = 0;
    for (int i = 0; i < n; i++) {
      long long a;
      cin >> a;
      mx = max(mx, a);
      cnt[a]++;
    }
    vector<long long> dp(mx + 1, 0);
    for (long long i = 1; i <= mx; i++) {
      dp[i] = max(dp[i], dp[i - 1]);
      if (!cnt.count(i)) continue;
      dp[i] = max(dp[i - 1], (i >= 2 ? dp[i - 2] : 0) + cnt[i] * i);
    }
    cout << dp[mx] << endl;
  }
};
class p550A {
 public:
  void solve() {
    string s;
    cin >> s;
    int l = -1;
    int cnt[2][2];
    memset(cnt, -1, sizeof(cnt));
    auto check = [&cnt](string &s, int flag) {
      for (int i = 0; i < s.size() - 1; i++) {
        if (s[i] == 'A' && s[i + 1] == 'B' && cnt[flag][0] == -1) {
          cnt[flag][0] = i + 1;
        }
        if (s[i] == 'B' && s[i + 1] == 'A' && cnt[flag][1] == -1) {
          cnt[flag][1] = i + 1;
        }
      }
    };
    check(s, 0);
    reverse(s.begin(), s.end());
    check(s, 1);
    if (cnt[0][1] != -1 && cnt[1][1] != -1 &&
        cnt[0][1] + 1 + cnt[1][1] + 1 <= s.size())
      cout << "YES" << endl;
    else if (cnt[0][0] != -1 && cnt[1][0] != -1 &&
             cnt[0][0] + 1 + cnt[1][0] + 1 <= s.size())
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
};
class p550C {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<int>> dp(n + 1, vector<int>(8, 0));
    vector<vector<int>> pre(n + 1, vector<int>(8, -1));
    bool ok = false;
    for (int i = 1; i <= n; i++) {
      int ai = s[i - 1] - '0';
      dp[i][ai % 8] = 1;
      for (int j = 0; j < 8; j++) {
        if (dp[i - 1][j] == 1) {
          dp[i][(10 * j + ai) % 8] = 1;
          dp[i][j] = 1;
          pre[i][(10 * j + ai) % 8] = j;
          pre[i][j] = j;
        }
      }
      if (dp[i][0] == 1) ok = 1;
    }
    if (ok == 0)
      cout << "NO" << endl;
    else {
      cout << "YES" << endl;
      string ans;
      for (int i = 1; i <= n; i++) {
        if (dp[i][0] == 1) {
          int ci = i, cj = 0;
          while (ci > 0) {
            if (pre[ci][cj] == -1 || pre[ci][cj] != cj) {
              ans.append(1, s[ci - 1]);
            }
            if (pre[ci][cj] == -1) break;
            cj = pre[ci][cj];
            ci--;
          }
          reverse(ans.begin(), ans.end());
          cout << ans << endl;
          break;
        }
      }
    }
  }
};
class p545C {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<pair<long long, long long>> tree;
    for (int i = 0; i < n; i++) {
      long long x, h;
      cin >> x >> h;
      tree.emplace_back(x, h);
    }
    if (n == 1)
      cout << 1 << endl;
    else {
      int res = 1;
      int pre = 0;
      for (int i = 1; i < n; i++) {
        if (pre == 0) {
          if (tree[i].first - tree[i].second > tree[i - 1].first) {
            res++;
          } else if (i == n - 1 ||
                     tree[i + 1].first > tree[i].first + tree[i].second) {
            pre = 1;
            res++;
          }
        } else {
          if (tree[i].first - tree[i].second >
              tree[i - 1].first + tree[i - 1].second) {
            pre = 0;
            res++;
          } else if (i == n - 1 ||
                     tree[i + 1].first > tree[i].first + tree[i].second) {
            pre = 1;
            res++;
          } else
            pre = 0;
        }
      }
      cout << res << endl;
    }
  }
};
class p166E {
 public:
  vector<vector<long long>> matrixmul(const vector<vector<long long>> &a,
                                      const vector<vector<long long>> &b) {
    int n = a.size();
    vector<vector<long long>> c(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
          c[i][j] += a[i][k] * b[k][j];
          c[i][j] %= 1000000007;
        }
      }
    }
    return c;
  }
  vector<vector<long long>> fmul(vector<vector<long long>> &matrix, int n) {
    vector<vector<long long>> res(matrix.size(),
                                  vector<long long>(matrix[0].size(), 0));
    for (int i = 0; i < matrix.size(); i++) res[i][i] = 1;
    while (n >= 1) {
      if (n & 1) {
        res = matrixmul(res, matrix);
      }
      n = n >> 1;
      matrix = matrixmul(matrix, matrix);
    }
    return res;
  }
  void solve() {
    int n;
    cin >> n;
    vector<vector<long long>> a(4, vector<long long>(4, 1));
    for (int i = 0; i < 4; i++) a[i][i] = 0;
    auto res = fmul(a, n);
    cout << res[3][3] << endl;
  }
};
class p676C {
 public:
  void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int a = 0, b = 0;
    int res = 0;
    for (int l = 0, r = 0; l < n; l++) {
      while (min(a, b) <= k && r < n) {
        res = max(res, a + b);
        if (s[r] == 'a')
          a++;
        else
          b++;
        r++;
      }
      if (min(a, b) <= k) res = max(res, a + b);
      if (s[l] == 'a')
        a--;
      else
        b--;
    }
    cout << res << endl;
  }
};
class p839C {
 public:
  double ans;
  vector<vector<int>> e;
  void dfs(int fa, int cur, double pre) {
    double pro = e[cur].size() <= 1
                     ? (fa == -1 ? pre : 0.0)
                     : pre / (fa == -1 ? e[cur].size() : (e[cur].size() - 1));
    for (int next : e[cur]) {
      if (next == fa) continue;
      ans += pro;
      dfs(cur, next, pro);
    }
  }
  void solve() {
    int n;
    cin >> n;
    e.clear();
    e = vector<vector<int>>(n);
    for (int i = 0; i < n - 1; i++) {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      e[u].push_back(v);
      e[v].push_back(u);
    }
    ans = 0.0;
    dfs(-1, 0, 1);
    printf("%.15lf\n", ans);
  }
};
class p1272D {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> l(n, 0), r(n, 0);
    l[0] = 1;
    for (int i = 1; i < n; i++) {
      l[i] = 1;
      if (a[i] > a[i - 1]) l[i] += l[i - 1];
    }
    r[n - 1] = 1;
    for (int i = n - 2; i >= 0; i--) {
      r[i] = 1;
      if (a[i] < a[i + 1]) r[i] += r[i + 1];
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
      res = max(res, l[i]);
      if (i < n - 2 && a[i] < a[i + 2]) res = max(res, l[i] + r[i + 2]);
    }
    cout << res << endl;
  }
};
class p1253C {
 public:
  void solve() {
    long long m, n;
    cin >> n >> m;
    vector<long long> a(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    vector<long long> res;
    vector<long long> sum(n + 1, 0);
    for (int i = 1; i <= n; i++) {
      sum[i] = sum[i - 1] + a[i - 1];
    }
    vector<long long> x(n + 1, 0);
    for (int i = 1; i <= n; i++) {
      x[i] = sum[i] + x[max(0ll, i - m)];
      res.push_back(x[i]);
    }
    for (auto i : res) cout << i << " ";
    cout << endl;
  }
};
class p1234C {
 public:
  void solve() {
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
      vector<string> s(2);
      int n;
      cin >> n >> s[0] >> s[1];
      int row = 0, pos = 0;
      bool ok = true;
      for (pos = 0; pos < n; pos++) {
        if (s[row][pos] >= '3') {
          if (s[1 - row][pos] < '3') {
            ok = false;
            break;
          } else {
            row = 1 - row;
          }
        }
      }
      if (ok && row == 1 && pos == n)
        cout << "YES" << endl;
      else
        cout << "NO" << endl;
    }
  }
};
class p1307C {
 public:
  void solve() {
    string s;
    cin >> s;
    vector<long long> cnt(26, 0);
    vector<long long> dict(1000, 0);
    long long mx = 0;
    for (int i = 0; i < s.size(); i++) {
      for (int j = 0; j < 26; j++) {
        dict[j * 30 + s[i] - 'a'] += cnt[j];
        mx = max(mx, dict[j * 30 + s[i] - 'a']);
      }
      cnt[s[i] - 'a']++;
      mx = max(mx, cnt[s[i] - 'a']);
    }
    cout << mx << endl;
  }
};
class p1207C {
 public:
  void solve() {
    int t;
    cin >> t;
    while (t--) {
      long long n, a, b;
      cin >> n >> a >> b;
      string s;
      cin >> s;
      vector<vector<long long>> dp(n + 1, vector<long long>(2, -1));
      dp[0][0] = b;
      for (int i = 1; i <= n; i++) {
        if (s[i - 1] == '1') {
          if (dp[i - 1][1] != -1) dp[i][1] = dp[i - 1][1] + 2 * b + a;
          if (dp[i - 1][0] != -1)
            dp[i][1] = dp[i][1] != -1
                           ? min(dp[i][1], dp[i - 1][0] + 3 * (a + b) - a)
                           : dp[i - 1][0] + 3 * (a + b) - a;
        } else {
          if (dp[i - 1][1] != -1) dp[i][1] = dp[i - 1][1] + 2 * b + a;
          if (dp[i - 1][0] != -1)
            dp[i][1] = dp[i][1] != -1
                           ? min(dp[i][1], dp[i - 1][0] + 3 * (a + b) - a)
                           : dp[i - 1][0] + 3 * (a + b) - a;
          if (dp[i - 1][0] != -1) dp[i][0] = dp[i - 1][0] + a + b;
          if (dp[i - 1][1] != -1)
            dp[i][0] = dp[i][0] != -1 ? min(dp[i][0], dp[i - 1][1] + 2 * a + b)
                                      : dp[i - 1][1] + 2 * a + b;
        }
      }
      cout << dp[n][0] << endl;
    }
  }
};
class p1105C {
 public:
  void solve() {
    long long n, l, r;
    cin >> n >> l >> r;
    l--;
    long long zero = r / 3 - l / 3;
    long long one = (r + 2) / 3 - (l + 2) / 3;
    long long two = (r + 1) / 3 - (l + 1) / 3;
    vector<vector<long long>> dp(n, vector<long long>(3, 0));
    dp[0][0] = zero;
    dp[0][1] = one;
    dp[0][2] = two;
    for (int i = 1; i < n; i++) {
      dp[i][0] =
          (dp[i - 1][0] * zero + dp[i - 1][1] * two + dp[i - 1][2] * one) %
          1000000007;
      dp[i][1] =
          (dp[i - 1][0] * one + dp[i - 1][1] * zero + dp[i - 1][2] * two) %
          1000000007;
      dp[i][2] =
          (dp[i - 1][0] * two + dp[i - 1][1] * one + dp[i - 1][2] * zero) %
          1000000007;
    }
    cout << dp[n - 1][0] << endl;
  }
};
class p611C {
 public:
  void solve() {
    int h, w;
    cin >> h >> w;
    vector<string> g(h);
    for (int i = 0; i < h; i++) cin >> g[i];
    vector<vector<vector<int>>> dp(
        h + 1, vector<vector<int>>(w + 1, vector<int>(2, 0)));
    for (int i = 1; i <= h; i++) {
      for (int j = 1; j <= w; j++) {
        for (int k = 0; k < 2; k++)
          dp[i][j][k] = dp[i - 1][j][k] + dp[i][j - 1][k] - dp[i - 1][j - 1][k];
        if (g[i - 1][j - 1] == '#') {
          continue;
        }
        if (i >= 2 && g[i - 2][j - 1] == '.') dp[i][j][0]++;
        if (j >= 2 && g[i - 1][j - 2] == '.') dp[i][j][1]++;
      }
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
      int r1, c1, r2, c2;
      cin >> r1 >> c1 >> r2 >> c2;
      int res = 0;
      res +=
          dp[r2][c2][0] - dp[r1][c2][0] - dp[r2][c1 - 1][0] + dp[r1][c1 - 1][0];
      res +=
          dp[r2][c2][1] - dp[r2][c1][1] - dp[r1 - 1][c2][1] + dp[r1 - 1][c1][1];
      cout << res << endl;
    }
  }
};
class p1051C {
 public:
  void solve() {
    int t, n = 0;
    cin >> t;
    vector<int> a(t, 0);
    for (auto &i : a) {
      cin >> i;
      n = max(n, i);
    }
    vector<int> cnt(n + 1, 0);
    vector<int> used(n + 1, -1);
    for (int i = 0; i < t; i++) {
      cnt[a[i]]++;
    }
    int odd = 0, even = 0;
    for (int i = 0; i <= n; i++) {
      if (cnt[i] == 1)
        odd++;
      else if (cnt[i] > 2)
        even++;
    }
    if (odd % 2 == 1 && even == 0) {
      cout << "NO" << endl;
      return;
    }
    if (odd % 2 == 1) {
      for (int i = 0; i <= n; i++)
        if (cnt[i] > 2) {
          cnt[i] = 1;
          break;
        }
    }
    cout << "YES" << endl;
    string s;
    char ch[2] = {'A', 'B'};
    int flag = 0;
    for (int i = 0; i < t; i++) {
      if (cnt[a[i]] != 1)
        s.append(1, 'A');
      else {
        if (used[a[i]] != -1)
          s.append(1, ch[used[a[i]] ^ 1]);
        else {
          used[a[i]] = flag;
          s.append(1, ch[flag]);
          flag ^= 1;
        }
      }
    }
    cout << s << endl;
  }
};
class p1313C1 {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<long long> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<vector<long long>> f(2, vector<long long>(n, 0));
    stack<int> left, right;
    auto monostack = [&n, &f](vector<long long> &a, stack<int> &left,
                              int flag) {
      for (int i = 0; i < n; i++) {
        while (left.size() != 0 && a[left.top()] > a[i]) left.pop();
        long long pre = left.size() == 0 ? 0 : f[flag][left.top()];
        long long len = left.size() == 0 ? i + 1 : i - left.top();
        f[flag][i] = pre + len * a[i];
        left.push(i);
      }
    };
    monostack(a, left, 0);
    reverse(a.begin(), a.end());
    monostack(a, right, 1);
    reverse(f[1].begin(), f[1].end());
    reverse(a.begin(), a.end());
    long long id = -1, mx = 0;
    for (int i = 0; i < n; i++) {
      if (f[0][i] + f[1][i] - a[i] > mx) {
        id = i;
        mx = f[0][i] + f[1][i] - a[i];
      }
    }
    vector<long long> res(n, 0);
    res[id] = a[id];
    for (long long i = id - 1; i >= 0; i--) {
      if (a[i] > res[i + 1])
        res[i] = res[i + 1];
      else
        res[i] = a[i];
    }
    for (long long i = id + 1; i < n; i++) {
      if (a[i] > res[i - 1])
        res[i] = res[i - 1];
      else
        res[i] = a[i];
    }
    for (long long i : res) cout << i << " ";
    cout << endl;
  }
};
class p982C {
 public:
  int ans = 0;
  vector<vector<int>> edge;
  int dfs(int cur, int fa) {
    int odd = 0;
    for (auto child : edge[cur]) {
      if (child == fa) continue;
      int temp = dfs(child, cur);
      if (temp == 0)
        ans++;
      else
        odd++;
    }
    if (odd % 2 == 1)
      return 0;
    else
      return 1;
  }
  void solve() {
    int n;
    cin >> n;
    ans = 0;
    edge = vector<vector<int>>(n);
    for (int i = 0; i < n - 1; i++) {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      edge[u].push_back(v);
      edge[v].push_back(u);
    }
    if (dfs(0, -1) != 0) {
      cout << -1 << endl;
    } else
      cout << ans << endl;
  }
};
class p891C {
 public:
  int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd(y, x % y);
  }
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      if (a[i] == 1) cnt++;
    }
    if (cnt > 0) {
      cout << n - cnt << endl;
      return;
    }
    bool ok = false;
    int len = n + 1;
    for (int l = 0; l < n; l++) {
      int temp = a[l];
      for (int r = l; r < n; r++) {
        temp = gcd(temp, a[r]);
        if (temp == 1) {
          len = min(len, r - l);
          break;
        }
      }
    }
    if (len == n + 1)
      cout << -1 << endl;
    else
      cout << len + n - 1 << endl;
  }
};
class p877B {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<int>> a(2, vector<int>(n + 1, 0));
    for (int i = 0; i < s.size(); i++) {
      int cur = s[i] - 'a';
      a[0][i + 1] += a[0][i];
      a[1][i + 1] += a[1][i];
      a[cur][i + 1]++;
    }
    int res = 0;
    for (int i = 0; i <= n; i++) {
      for (int j = i; j <= n; j++) {
        int t1 = a[1][i];
        int t2 = a[0][j] - a[0][i];
        int t3 = a[1][n] - a[1][j];
        res = max(res, n - t1 - t2 - t3);
      }
    }
    cout << res << endl;
  }
};
class p1005D {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> dp(n + 1, 0);
    int sum = 0;
    unordered_map<int, int> cnt;
    cnt[0] = 0;
    int res = 0;
    for (int i = 1; i <= n; i++) {
      sum += (s[i - 1] - '0');
      sum %= 3;
      dp[i] = dp[i - 1];
      if (cnt.count((sum))) {
        dp[i] = max(dp[i], dp[cnt[sum]] + 1);
      }
      res = max(res, dp[i]);
      cnt[sum] = i;
    }
    cout << res << endl;
  }
};
class p264B {
 public:
  int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
  }
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (auto &i : a) cin >> i;
    int res = 0;
    unordered_map<int, int> dp;
    for (int &i : a) {
      if (i == 1) {
        res = max(res, 1);
        continue;
      }
      vector<int> temp;
      int cur = 0;
      for (int j = 2; j <= i / j; j++) {
        if (i % j == 0) {
          temp.push_back(j);
          cur = max(cur, dp[j] + 1);
          while (i % j == 0) i /= j;
        }
      }
      if (i > 1) {
        temp.push_back(i);
        cur = max(cur, dp[i] + 1);
      }
      for (int j : temp) dp[j] = max(dp[j], cur);
      res = max(cur, res);
    }
    cout << res << endl;
  }
};
class p553A {
 public:
  void solve() {
    int k;
    cin >> k;
    vector<long long> a(k, 0);
    vector<long long> dp(k, 0);
    int maxn = 1010;
    vector<vector<long long>> f(maxn, vector<long long>(maxn, 0));
    f[0][0] = 1;
    for (int i = 1; i < maxn; i++) {
      f[i][0] = 1;
      for (int j = 1; j <= i; j++) {
        f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % 1000000007;
      }
    }
    for (auto &i : a) cin >> i;
    long long sum = a[0];
    dp[0] = 1;
    for (long long i = 1; i < k; i++) {
      sum += a[i] - 1;
      dp[i] = (dp[i - 1] * f[sum][a[i] - 1]) % 1000000007;
      sum++;
    }
    cout << dp.back() % 1000000007 << endl;
  }
};
class p322B {
 public:
  void solve() {
    int n, k;
    cin >> n >> k;
    vector<long long> v(n, 0);
    vector<long long> sum(n + 1, 0);
    vector<long long> dp(n + 1, 0);
    vector<long long> index(n + 1, 0);
    dp[0] = 0;
    index[0] = 0;
    long long res = 0;
    for (int i = 1; i <= n; i++) {
      cin >> v[i - 1];
      sum[i] += sum[i - 1] + v[i - 1];
      dp[i] = dp[i - 1];
      index[i] = index[i - 1];
      if (i >= k) {
        if (sum[i] - sum[i - k] > dp[i]) {
          dp[i] = sum[i] - sum[i - k];
          index[i] = i - k + 1;
        }
        res = max(res, sum[i] - sum[i - k] + dp[i - k]);
      }
    }
    vector<pair<long long, long long>> ans;
    for (int i = 1; i <= n; i++) {
      if (i >= k) {
        if (res == dp[i - k] + sum[i] - sum[i - k]) {
          ans.emplace_back(index[i - k], i - k + 1);
        }
      }
    }
    sort(ans.begin(), ans.end());
    cout << ans.begin()->first << " " << ans.begin()->second << endl;
  }
};
class p1084C {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<long long> a;
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
      if (s[i - 1] == 'a') {
        sum++;
      } else if (s[i - 1] == 'b') {
        a.push_back(sum);
        sum = 0;
      }
    }
    if (sum != 0) a.push_back(sum);
    long long res = 1;
    if (a.size() == 0) {
      cout << 0 << endl;
      return;
    }
    for (auto i : a) {
      res = (res * (i + 1)) % 1000000007;
    }
    res = (res - 1 + 1000000007) % 1000000007;
    cout << res << endl;
  }
};
class p991D {
 public:
  void solve() {
    vector<string> a(2);
    cin >> a[0] >> a[1];
    int n = a[0].size();
    if (n == 1) {
      cout << 0 << endl;
      return;
    }
    vector<vector<int>> dp(n + 1, vector<int>(3, 0));
    vector<int> v(n, 0);
    for (int i = 0; i < n; i++) {
      if (a[0][i] == '0') v[i]++;
      if (a[1][i] == '0') v[i]++;
    }
    for (int i = 2; i <= n; i++) {
      dp[i][2] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2]));
      if (v[i - 1] == 0) continue;
      int pre = max(dp[i - 2][0], max(dp[i - 2][1], dp[i - 2][2]));
      if (v[i - 1] == 2) {
        if (v[i - 2] > 0) {
          if (v[i - 2] == 2) {
            dp[i][0] = max(dp[i][0], pre + 1);
            dp[i][1] = max(dp[i][1], pre + 1);
            dp[i][1] = max(dp[i][1], max(dp[i - 1][0], dp[i - 1][2]) + 1);
          } else
            dp[i][1] = max(dp[i][1], dp[i - 1][2] + 1);
        }
      } else {
        if (v[i - 2] == 2) {
          dp[i][0] = max(dp[i][0], pre + 1);
        }
      }
    }
    cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << endl;
  }
};
class p855B {
 public:
  void solve() {
    long long n;
    cin >> n;
    vector<long long> v(3, 0);
    cin >> v[0] >> v[1] >> v[2];
    vector<long long> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<vector<long long>> dp(n, vector<long long>(3, 0));
    dp[0][0] = v[0] * a[0];
    dp[0][1] = v[0] * a[0] + v[1] * a[0];
    dp[0][2] = v[0] * a[0] + v[1] * a[0] + v[2] * a[0];
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < 3; j++) {
        dp[i][j] = dp[i - 1][j];
        long long temp = 0;
        for (int k = j; k >= 0; k--) {
          temp += v[k] * a[i];
          dp[i][j] = max(dp[i][j], temp + (k - 1 >= 0 ? dp[i - 1][k - 1] : 0));
        }
      }
    }
    cout << dp[n - 1][2] << endl;
  }
};
class p873B {
 public:
  void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    unordered_map<int, int> cnt;
    int zero = 0, one = 0;
    int res = 0;
    cnt[0] = -1;
    for (int i = 0; i < n; i++) {
      if (s[i] == '0')
        zero++;
      else
        one++;
      int diff = zero - one;
      if (cnt.count(diff)) {
        res = max(res, i - cnt[diff]);
      } else
        cnt[diff] = i;
    }
    cout << res << endl;
  }
};
class p340D {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<int> dp;
    for (int i : a) {
      auto pos = upper_bound(dp.begin(), dp.end(), i) - dp.begin();
      if (pos == dp.size())
        dp.push_back(i);
      else
        dp[pos] = i;
    }
    cout << dp.size() << endl;
  }
};
class p1081C {
 public:
  void solve() {
    long long n, m, k;
    cin >> n >> m >> k;
    vector<vector<long long>> dp(n, vector<long long>(k + 1, 0));
    long long modulo = 998244353;
    dp[0][0] = m;
    for (int i = 1; i < n; i++) {
      for (int j = k; j >= 0; j--) {
        dp[i][j] =
            (dp[i - 1][j] + (j > 0 ? dp[i - 1][j - 1] : 0) * (m - 1)) % modulo;
      }
    }
    cout << dp[n - 1][k] << endl;
  }
};
class p761C {
 public:
  void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    vector<vector<int>> a(n, vector<int>(3, -1));
    auto check = [](char c) {
      if (c == '#' || c == '*' || c == '&') return true;
      return false;
    };
    for (int i = 0; i < n; i++) {
      for (int j = m - 1; j >= 0; j--) {
        if (isdigit(v[i][j]))
          a[i][0] = a[i][0] == -1 ? min(j, m - j) : min(a[i][0], min(j, m - j));
        if (isalpha(v[i][j]))
          a[i][1] = a[i][1] == -1 ? min(j, m - j) : min(a[i][1], min(j, m - j));
        if (check(v[i][j]))
          a[i][2] = a[i][2] == -1 ? min(j, m - j) : min(a[i][2], min(j, m - j));
      }
    }
    vector<vector<int>> dp(n + 1, vector<int>(1 << 3, 10000));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
      dp[i][0] = dp[i - 1][0];
      for (int j = 1; j < (1 << 3); j++) {
        dp[i][j] = dp[i - 1][j];
        for (int k = 0; k < 3; k++) {
          if (((1 << k) & j) != 0 && a[i - 1][k] != -1) {
            int pre = (1 << k) ^ j;
            dp[i][j] = min(dp[i][j], dp[i - 1][pre] + a[i - 1][k]);
          }
        }
      }
    }
    cout << dp[n][(1 << 3) - 1] << endl;
  }
};
class p858C {
 public:
  void solve() {
    string s;
    cin >> s;
    unordered_set<char> dict{'a', 'e', 'i', 'o', 'u'};
    int block = 0, kind = 0;
    vector<char> res;
    bool first = 1;
    for (int i = 0; i < s.size(); i++) {
      if (!dict.count(s[i])) {
        block++;
        if (block > 2 && (s[i] != s[i - 1] || s[i - 1] != s[i - 2])) {
          res.push_back(' ');
          block = 1;
        }
      } else {
        block = kind = 0;
      }
      res.push_back(s[i]);
    }
    for (auto i : res) cout << i;
    cout << endl;
  }
};
class p204A {
 public:
  long long getTen(int x) {
    if (x == 0) return 1;
    long long temp = getTen(x / 2);
    if (x % 2 == 1) return temp * temp * 10;
    return temp * temp;
  }
  long long getDig(long long x) {
    if (x <= 0) return 0;
    if (x <= 9) return x;
    long long res = 0;
    vector<long long> a;
    while (x > 0) {
      a.emplace_back(x % 10);
      x /= 10;
    }
    reverse(a.begin(), a.end());
    int n = a.size();
    for (int i = 0; i < n; i++) {
      long long temp = getTen(max(0, n - 2 - (i + 1) + 1));
      int up = i > 0 ? 10 : a[i];
      for (int j = 1; j < up; j++) {
        res += temp;
      }
    }
    long long temp = 0;
    for (int i = 1; i < n - 1; i++) temp = temp * 10 + a[i];
    if (a.front() <= a.back()) temp++;
    res += temp;
    return res;
  }
  void solve() {
    long long l, r;
    cin >> l >> r;
    cout << getDig(r) - getDig(l - 1) << endl;
  }
};
class p859C {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<int> dp(n, 0);
    vector<int> sum(n, 0);
    sum[n - 1] = a[n - 1];
    dp[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--) sum[i] = sum[i + 1] + a[i];
    for (int i = n - 2; i >= 0; i--) {
      dp[i] = max(dp[i + 1], sum[i + 1] - dp[i + 1] + a[i]);
    }
    cout << sum[0] - dp[0] << " " << dp[0] << endl;
  }
};
class p159D {
 public:
  void solve() {
    string s;
    cin >> s;
    long long n = s.size();
    vector<vector<long long>> done(n, vector<long long>(n, 0));
    vector<long long> dp(n, 0);
    vector<long long> sum(n, 0);
    auto check = [&s, &done, &n](int l, int r) {
      while (l >= 0 && r < n && s[l] == s[r]) {
        done[l][r] = 1;
        l--;
        r++;
      }
    };
    for (int i = 0; i < n; i++) {
      int l = i, r = i;
      check(l, r);
      l = i, r = i + 1;
      check(l, r);
    }
    dp[0] = 0;
    sum[0] = 1;
    for (int i = 1; i < n; i++) {
      long long cnt = 0, cur = 0;
      for (int j = 0; j <= i; j++) {
        if (done[j][i]) {
          cnt++;
          cur += j == 0 ? 0 : sum[j - 1];
        }
      }
      dp[i] = dp[i - 1] + cur;
      sum[i] = sum[i - 1] + cnt;
    }
    cout << dp[n - 1] << endl;
  }
};
class p255C {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    unordered_map<int, vector<int>> cnt;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      cnt[a[i]].push_back(i);
    }
    vector<int> v;
    int res = 0;
    for (auto it : cnt) {
      v.push_back(it.first);
      res = max(res, (int)it.second.size());
    }
    int sz = v.size();
    auto check = [&cnt, &v](int a, int b) {
      int res = 0;
      int i = 0, j = 0, lena = cnt[v[a]].size(), lenb = cnt[v[b]].size();
      while (i < lena && j < lenb) {
        if (cnt[v[a]][i] < cnt[v[b]][j]) {
          while (i < lena && cnt[v[a]][i] < cnt[v[b]][j]) i++;
          if (i < lena) res++;
        } else {
          while (j < lenb && cnt[v[b]][j] < cnt[v[a]][i]) j++;
          if (j < lenb) res++;
        }
      }
      return res + 2;
    };
    for (int i = 0; i < sz; i++) {
      for (int j = i + 1; j < sz; j++) {
        res = max(res, check(i, j));
      }
    }
    cout << res << endl;
  }
  void solve2() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<vector<int>> dp(n, vector<int>(n, 0));
    int res = 1;
    for (int i = 1; i < n; i++) {
      int k = -1;
      for (int j = 0; j < i; j++) {
        if (k == -1)
          dp[i][j] = 2;
        else
          dp[i][j] = dp[j][k] + 1;
        if (a[i] == a[j]) k = j;
        res = max(res, dp[i][j]);
      }
    }
    cout << res << endl;
  }
};
class p868C {
 public:
  void solve() {
    int n, k;
    cin >> n >> k;
    unordered_map<int, int> cnt;
    for (int i = 0; i < n; i++) {
      int mask = 0;
      for (int j = 0; j < k; j++) {
        int t = 0;
        cin >> t;
        if (t == 1) mask |= (1 << j);
      }
      cnt[mask]++;
    }
    bool flag = false;
    for (int i = 0; i < (1 << k); i++) {
      for (int j = 0; j < (1 << k); j++) {
        if ((i & j) == 0 && (cnt[i] && cnt[j])) flag = true;
      }
    }
    if (flag)
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
};
class p22B {
 public:
  void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    vector<vector<int>> up(n, vector<int>(m, 0));
    vector<vector<int>> left(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      for (int j = 0; j < m; j++) {
        if (a[i][j] == '0') {
          up[i][j] = left[i][j] = 1;
          if (i - 1 >= 0) up[i][j] += up[i - 1][j];
          if (j > 0) left[i][j] += left[i][j - 1];
        }
      }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (a[i][j] == '1') continue;
        int len = 1000000;
        for (int k = 1; k <= up[i][j]; k++) {
          len = min(len, left[i - k + 1][j]);
          res = max(res, (len + k) * 2);
        }
      }
    }
    cout << res << endl;
  }
};
class p566F {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    unordered_map<int, int> cnt;
    int mx = -1;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      mx = max(mx, a[i]);
    }
    vector<int> dp(mx + 1, 1);
    for (int i = 0; i < n; i++) {
      for (int j = 2 * a[i]; j <= mx; j += a[i]) {
        dp[j] = max(dp[j], dp[a[i]] + 1);
      }
    }
    int res = 0;
    for (int i = 0; i < n; i++) res = max(res, dp[a[i]]);
    cout << res << endl;
  }
};
class p191A {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<string> s(n);
    vector<vector<int>> dp(26, vector<int>(26, -1));
    for (int i = 0; i < n; i++) cin >> s[i];
    int res = 0;
    for (int i = 0; i < n; i++) {
      int st = s[i].front() - 'a', ed = s[i].back() - 'a';
      for (int j = 0; j < 26; j++) {
        if (dp[j][st] != -1) {
          dp[j][ed] = max(dp[j][ed], dp[j][st] + (int)s[i].size());
        }
      }
      dp[st][ed] = max(dp[st][ed], (int)s[i].size());
    }
    for (int i = 0; i < 26; i++) res = max(res, dp[i][i]);
    cout << res << endl;
  }
};
class p417A {
 public:
  void solve() {
    int c, d, n, m, k;
    cin >> c >> d >> n >> m >> k;
    int res = 100000000;
    int remain = max(0, n * m - k);
    if (remain == 0) {
      cout << 0 << endl;
      return;
    }
    for (int i = 0; i * n <= remain + n - 1; i++) {
      int left = max(0, remain - i * n);
      res = min(res, i * c + left * d);
    }
    cout << res << endl;
  }
};
class p10B {
 public:
  void solve() {
    int n, k, m;
    cin >> n >> k;
    vector<vector<vector<int>>> dp(
        k + 1, vector<vector<int>>(k + 1, vector<int>(k + 1, 0x3f3f3f3f)));
    for (int i = 1; i <= k; i++) {
      for (int j = 1; j <= k; j++) {
        dp[i][j][0] = 0;
        for (int r = 1; r + j - 1 <= k; r++) {
          dp[i][j][r] = dp[i][j][r - 1] + abs(i - (k + 1) / 2) +
                        abs(j + r - 1 - (k + 1) / 2);
        }
      }
    }
    while (n--) {
      cin >> m;
      int ans = 0x3f3f3f3f, x, l, r;
      for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= k; j++) {
          if (dp[i][j][m] < ans) {
            x = i;
            l = j;
            r = j + m - 1;
            ans = dp[i][j][m];
          }
        }
      }
      if (ans == 0x3f3f3f3f)
        cout << -1 << endl;
      else {
        cout << x << " " << l << " " << r << endl;
        for (int i = 1; i <= k; i++) {
          for (int j = 1; j + i - 1 <= k; j++) {
            if (!(i + j - 1 < l || i > r)) {
              dp[x][i][j] = 0x3f3f3f3f;
            }
          }
        }
      }
    }
  }
};
class p74B {
 public:
  void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    string to, dir;
    cin >> to >> dir;
    int d = 0;
    string t;
    cin >> t;
    if (dir == "head")
      d = -1;
    else
      d = 1;
    int res = 0;
    bool win = true;
    auto move = [&k, &d, &n]() {
      k += d;
      if (k == 0)
        k = 2, d = -d;
      else if (k == n + 1)
        k = n - 1, d = -d;
    };
    for (int i = 0; i < t.size(); i++) {
      if (t[i] == '0') {
        if ((m - k) * d >= 0)
          m += d;
        else
          m -= d;
        if (m == 0) m = 1;
        if (m == n + 1) m = n;
        if (m == k) {
          win = false, res = i;
          break;
        }
        move();
      } else {
        move();
        if (d == -1) {
          m = (k == n ? 1 : n);
        } else
          m = (k == 1 ? n : 1);
      }
      if (m == k) {
        win = false, res = i;
        break;
      }
    }
    if (win)
      cout << "Stowaway" << endl;
    else {
      cout << "Controller " << res + 1 << endl;
    }
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  p74B ans;
  ans.solve();
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

A stowaway and a controller play the following game. 

The train is represented by n wagons which are numbered with positive integers from 1 to n from the head to the tail. The stowaway and the controller are initially in some two different wagons. Every minute the train can be in one of two conditions — moving or idle. Every minute the players move.

The controller's move is as follows. The controller has the movement direction — to the train's head or to its tail. During a move the controller moves to the neighbouring wagon correspondingly to its movement direction. If at the end of his move the controller enters the 1-st or the n-th wagon, that he changes the direction of his movement into the other one. In other words, the controller cyclically goes from the train's head to its tail and back again during all the time of a game, shifting during each move by one wagon. Note, that the controller always have exactly one possible move.

The stowaway's move depends from the state of the train. If the train is moving, then the stowaway can shift to one of neighbouring wagons or he can stay where he is without moving. If the train is at a station and is idle, then the stowaway leaves the train (i.e. he is now not present in any train wagon) and then, if it is not the terminal train station, he enters the train again into any of n wagons (not necessarily into the one he's just left and not necessarily into the neighbouring one). If the train is idle for several minutes then each such minute the stowaway leaves the train and enters it back.

Let's determine the order of the players' moves. If at the given minute the train is moving, then first the stowaway moves and then the controller does. If at this minute the train is idle, then first the stowaway leaves the train, then the controller moves and then the stowaway enters the train.

If at some point in time the stowaway and the controller happen to be in one wagon, then the controller wins: he makes the stowaway pay fine. If after a while the stowaway reaches the terminal train station, then the stowaway wins: he simply leaves the station during his move and never returns there again.

At any moment of time the players know each other's positions. The players play in the optimal way. Specifically, if the controller wins, then the stowaway plays so as to lose as late as possible. As all the possible moves for the controller are determined uniquely, then he is considered to play optimally always. Determine the winner.

Input

The first line contains three integers n, m and k. They represent the number of wagons in the train, the stowaway's and the controller's initial positions correspondingly (2 ≤ n ≤ 50, 1 ≤ m, k ≤ n, m ≠ k).

The second line contains the direction in which a controller moves. "to head" means that the controller moves to the train's head and "to tail" means that the controller moves to its tail. It is guaranteed that in the direction in which the controller is moving, there is at least one wagon. Wagon 1 is the head, and wagon n is the tail.

The third line has the length from 1 to 200 and consists of symbols "0" and "1". The i-th symbol contains information about the train's state at the i-th minute of time. "0" means that in this very minute the train moves and "1" means that the train in this very minute stands idle. The last symbol of the third line is always "1" — that's the terminal train station.

Output

If the stowaway wins, print "Stowaway" without quotes. Otherwise, print "Controller" again without quotes, then, separated by a space, print the number of a minute, at which the stowaway will be caught.

Examples

Input

5 3 2
to head
0001001


Output

Stowaway

Input

3 2 1
to tail
0001


Output

Controller 2

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
class p445A {
 public:
  void solve() {
    long long n;
    cin >> n;
    unordered_map<long long, long long> cnt;
    long long mx = 0;
    for (int i = 0; i < n; i++) {
      long long a;
      cin >> a;
      mx = max(mx, a);
      cnt[a]++;
    }
    vector<long long> dp(mx + 1, 0);
    for (long long i = 1; i <= mx; i++) {
      dp[i] = max(dp[i], dp[i - 1]);
      if (!cnt.count(i)) continue;
      dp[i] = max(dp[i - 1], (i >= 2 ? dp[i - 2] : 0) + cnt[i] * i);
    }
    cout << dp[mx] << endl;
  }
};
class p550A {
 public:
  void solve() {
    string s;
    cin >> s;
    int l = -1;
    int cnt[2][2];
    memset(cnt, -1, sizeof(cnt));
    auto check = [&cnt](string &s, int flag) {
      for (int i = 0; i < s.size() - 1; i++) {
        if (s[i] == 'A' && s[i + 1] == 'B' && cnt[flag][0] == -1) {
          cnt[flag][0] = i + 1;
        }
        if (s[i] == 'B' && s[i + 1] == 'A' && cnt[flag][1] == -1) {
          cnt[flag][1] = i + 1;
        }
      }
    };
    check(s, 0);
    reverse(s.begin(), s.end());
    check(s, 1);
    if (cnt[0][1] != -1 && cnt[1][1] != -1 &&
        cnt[0][1] + 1 + cnt[1][1] + 1 <= s.size())
      cout << "YES" << endl;
    else if (cnt[0][0] != -1 && cnt[1][0] != -1 &&
             cnt[0][0] + 1 + cnt[1][0] + 1 <= s.size())
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
};
class p550C {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<int>> dp(n + 1, vector<int>(8, 0));
    vector<vector<int>> pre(n + 1, vector<int>(8, -1));
    bool ok = false;
    for (int i = 1; i <= n; i++) {
      int ai = s[i - 1] - '0';
      dp[i][ai % 8] = 1;
      for (int j = 0; j < 8; j++) {
        if (dp[i - 1][j] == 1) {
          dp[i][(10 * j + ai) % 8] = 1;
          dp[i][j] = 1;
          pre[i][(10 * j + ai) % 8] = j;
          pre[i][j] = j;
        }
      }
      if (dp[i][0] == 1) ok = 1;
    }
    if (ok == 0)
      cout << "NO" << endl;
    else {
      cout << "YES" << endl;
      string ans;
      for (int i = 1; i <= n; i++) {
        if (dp[i][0] == 1) {
          int ci = i, cj = 0;
          while (ci > 0) {
            if (pre[ci][cj] == -1 || pre[ci][cj] != cj) {
              ans.append(1, s[ci - 1]);
            }
            if (pre[ci][cj] == -1) break;
            cj = pre[ci][cj];
            ci--;
          }
          reverse(ans.begin(), ans.end());
          cout << ans << endl;
          break;
        }
      }
    }
  }
};
class p545C {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<pair<long long, long long>> tree;
    for (int i = 0; i < n; i++) {
      long long x, h;
      cin >> x >> h;
      tree.emplace_back(x, h);
    }
    if (n == 1)
      cout << 1 << endl;
    else {
      int res = 1;
      int pre = 0;
      for (int i = 1; i < n; i++) {
        if (pre == 0) {
          if (tree[i].first - tree[i].second > tree[i - 1].first) {
            res++;
          } else if (i == n - 1 ||
                     tree[i + 1].first > tree[i].first + tree[i].second) {
            pre = 1;
            res++;
          }
        } else {
          if (tree[i].first - tree[i].second >
              tree[i - 1].first + tree[i - 1].second) {
            pre = 0;
            res++;
          } else if (i == n - 1 ||
                     tree[i + 1].first > tree[i].first + tree[i].second) {
            pre = 1;
            res++;
          } else
            pre = 0;
        }
      }
      cout << res << endl;
    }
  }
};
class p166E {
 public:
  vector<vector<long long>> matrixmul(const vector<vector<long long>> &a,
                                      const vector<vector<long long>> &b) {
    int n = a.size();
    vector<vector<long long>> c(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
          c[i][j] += a[i][k] * b[k][j];
          c[i][j] %= 1000000007;
        }
      }
    }
    return c;
  }
  vector<vector<long long>> fmul(vector<vector<long long>> &matrix, int n) {
    vector<vector<long long>> res(matrix.size(),
                                  vector<long long>(matrix[0].size(), 0));
    for (int i = 0; i < matrix.size(); i++) res[i][i] = 1;
    while (n >= 1) {
      if (n & 1) {
        res = matrixmul(res, matrix);
      }
      n = n >> 1;
      matrix = matrixmul(matrix, matrix);
    }
    return res;
  }
  void solve() {
    int n;
    cin >> n;
    vector<vector<long long>> a(4, vector<long long>(4, 1));
    for (int i = 0; i < 4; i++) a[i][i] = 0;
    auto res = fmul(a, n);
    cout << res[3][3] << endl;
  }
};
class p676C {
 public:
  void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int a = 0, b = 0;
    int res = 0;
    for (int l = 0, r = 0; l < n; l++) {
      while (min(a, b) <= k && r < n) {
        res = max(res, a + b);
        if (s[r] == 'a')
          a++;
        else
          b++;
        r++;
      }
      if (min(a, b) <= k) res = max(res, a + b);
      if (s[l] == 'a')
        a--;
      else
        b--;
    }
    cout << res << endl;
  }
};
class p839C {
 public:
  double ans;
  vector<vector<int>> e;
  void dfs(int fa, int cur, double pre) {
    double pro = e[cur].size() <= 1
                     ? (fa == -1 ? pre : 0.0)
                     : pre / (fa == -1 ? e[cur].size() : (e[cur].size() - 1));
    for (int next : e[cur]) {
      if (next == fa) continue;
      ans += pro;
      dfs(cur, next, pro);
    }
  }
  void solve() {
    int n;
    cin >> n;
    e.clear();
    e = vector<vector<int>>(n);
    for (int i = 0; i < n - 1; i++) {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      e[u].push_back(v);
      e[v].push_back(u);
    }
    ans = 0.0;
    dfs(-1, 0, 1);
    printf("%.15lf\n", ans);
  }
};
class p1272D {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> l(n, 0), r(n, 0);
    l[0] = 1;
    for (int i = 1; i < n; i++) {
      l[i] = 1;
      if (a[i] > a[i - 1]) l[i] += l[i - 1];
    }
    r[n - 1] = 1;
    for (int i = n - 2; i >= 0; i--) {
      r[i] = 1;
      if (a[i] < a[i + 1]) r[i] += r[i + 1];
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
      res = max(res, l[i]);
      if (i < n - 2 && a[i] < a[i + 2]) res = max(res, l[i] + r[i + 2]);
    }
    cout << res << endl;
  }
};
class p1253C {
 public:
  void solve() {
    long long m, n;
    cin >> n >> m;
    vector<long long> a(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    vector<long long> res;
    vector<long long> sum(n + 1, 0);
    for (int i = 1; i <= n; i++) {
      sum[i] = sum[i - 1] + a[i - 1];
    }
    vector<long long> x(n + 1, 0);
    for (int i = 1; i <= n; i++) {
      x[i] = sum[i] + x[max(0ll, i - m)];
      res.push_back(x[i]);
    }
    for (auto i : res) cout << i << " ";
    cout << endl;
  }
};
class p1234C {
 public:
  void solve() {
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
      vector<string> s(2);
      int n;
      cin >> n >> s[0] >> s[1];
      int row = 0, pos = 0;
      bool ok = true;
      for (pos = 0; pos < n; pos++) {
        if (s[row][pos] >= '3') {
          if (s[1 - row][pos] < '3') {
            ok = false;
            break;
          } else {
            row = 1 - row;
          }
        }
      }
      if (ok && row == 1 && pos == n)
        cout << "YES" << endl;
      else
        cout << "NO" << endl;
    }
  }
};
class p1307C {
 public:
  void solve() {
    string s;
    cin >> s;
    vector<long long> cnt(26, 0);
    vector<long long> dict(1000, 0);
    long long mx = 0;
    for (int i = 0; i < s.size(); i++) {
      for (int j = 0; j < 26; j++) {
        dict[j * 30 + s[i] - 'a'] += cnt[j];
        mx = max(mx, dict[j * 30 + s[i] - 'a']);
      }
      cnt[s[i] - 'a']++;
      mx = max(mx, cnt[s[i] - 'a']);
    }
    cout << mx << endl;
  }
};
class p1207C {
 public:
  void solve() {
    int t;
    cin >> t;
    while (t--) {
      long long n, a, b;
      cin >> n >> a >> b;
      string s;
      cin >> s;
      vector<vector<long long>> dp(n + 1, vector<long long>(2, -1));
      dp[0][0] = b;
      for (int i = 1; i <= n; i++) {
        if (s[i - 1] == '1') {
          if (dp[i - 1][1] != -1) dp[i][1] = dp[i - 1][1] + 2 * b + a;
          if (dp[i - 1][0] != -1)
            dp[i][1] = dp[i][1] != -1
                           ? min(dp[i][1], dp[i - 1][0] + 3 * (a + b) - a)
                           : dp[i - 1][0] + 3 * (a + b) - a;
        } else {
          if (dp[i - 1][1] != -1) dp[i][1] = dp[i - 1][1] + 2 * b + a;
          if (dp[i - 1][0] != -1)
            dp[i][1] = dp[i][1] != -1
                           ? min(dp[i][1], dp[i - 1][0] + 3 * (a + b) - a)
                           : dp[i - 1][0] + 3 * (a + b) - a;
          if (dp[i - 1][0] != -1) dp[i][0] = dp[i - 1][0] + a + b;
          if (dp[i - 1][1] != -1)
            dp[i][0] = dp[i][0] != -1 ? min(dp[i][0], dp[i - 1][1] + 2 * a + b)
                                      : dp[i - 1][1] + 2 * a + b;
        }
      }
      cout << dp[n][0] << endl;
    }
  }
};
class p1105C {
 public:
  void solve() {
    long long n, l, r;
    cin >> n >> l >> r;
    l--;
    long long zero = r / 3 - l / 3;
    long long one = (r + 2) / 3 - (l + 2) / 3;
    long long two = (r + 1) / 3 - (l + 1) / 3;
    vector<vector<long long>> dp(n, vector<long long>(3, 0));
    dp[0][0] = zero;
    dp[0][1] = one;
    dp[0][2] = two;
    for (int i = 1; i < n; i++) {
      dp[i][0] =
          (dp[i - 1][0] * zero + dp[i - 1][1] * two + dp[i - 1][2] * one) %
          1000000007;
      dp[i][1] =
          (dp[i - 1][0] * one + dp[i - 1][1] * zero + dp[i - 1][2] * two) %
          1000000007;
      dp[i][2] =
          (dp[i - 1][0] * two + dp[i - 1][1] * one + dp[i - 1][2] * zero) %
          1000000007;
    }
    cout << dp[n - 1][0] << endl;
  }
};
class p611C {
 public:
  void solve() {
    int h, w;
    cin >> h >> w;
    vector<string> g(h);
    for (int i = 0; i < h; i++) cin >> g[i];
    vector<vector<vector<int>>> dp(
        h + 1, vector<vector<int>>(w + 1, vector<int>(2, 0)));
    for (int i = 1; i <= h; i++) {
      for (int j = 1; j <= w; j++) {
        for (int k = 0; k < 2; k++)
          dp[i][j][k] = dp[i - 1][j][k] + dp[i][j - 1][k] - dp[i - 1][j - 1][k];
        if (g[i - 1][j - 1] == '#') {
          continue;
        }
        if (i >= 2 && g[i - 2][j - 1] == '.') dp[i][j][0]++;
        if (j >= 2 && g[i - 1][j - 2] == '.') dp[i][j][1]++;
      }
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
      int r1, c1, r2, c2;
      cin >> r1 >> c1 >> r2 >> c2;
      int res = 0;
      res +=
          dp[r2][c2][0] - dp[r1][c2][0] - dp[r2][c1 - 1][0] + dp[r1][c1 - 1][0];
      res +=
          dp[r2][c2][1] - dp[r2][c1][1] - dp[r1 - 1][c2][1] + dp[r1 - 1][c1][1];
      cout << res << endl;
    }
  }
};
class p1051C {
 public:
  void solve() {
    int t, n = 0;
    cin >> t;
    vector<int> a(t, 0);
    for (auto &i : a) {
      cin >> i;
      n = max(n, i);
    }
    vector<int> cnt(n + 1, 0);
    vector<int> used(n + 1, -1);
    for (int i = 0; i < t; i++) {
      cnt[a[i]]++;
    }
    int odd = 0, even = 0;
    for (int i = 0; i <= n; i++) {
      if (cnt[i] == 1)
        odd++;
      else if (cnt[i] > 2)
        even++;
    }
    if (odd % 2 == 1 && even == 0) {
      cout << "NO" << endl;
      return;
    }
    if (odd % 2 == 1) {
      for (int i = 0; i <= n; i++)
        if (cnt[i] > 2) {
          cnt[i] = 1;
          break;
        }
    }
    cout << "YES" << endl;
    string s;
    char ch[2] = {'A', 'B'};
    int flag = 0;
    for (int i = 0; i < t; i++) {
      if (cnt[a[i]] != 1)
        s.append(1, 'A');
      else {
        if (used[a[i]] != -1)
          s.append(1, ch[used[a[i]] ^ 1]);
        else {
          used[a[i]] = flag;
          s.append(1, ch[flag]);
          flag ^= 1;
        }
      }
    }
    cout << s << endl;
  }
};
class p1313C1 {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<long long> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<vector<long long>> f(2, vector<long long>(n, 0));
    stack<int> left, right;
    auto monostack = [&n, &f](vector<long long> &a, stack<int> &left,
                              int flag) {
      for (int i = 0; i < n; i++) {
        while (left.size() != 0 && a[left.top()] > a[i]) left.pop();
        long long pre = left.size() == 0 ? 0 : f[flag][left.top()];
        long long len = left.size() == 0 ? i + 1 : i - left.top();
        f[flag][i] = pre + len * a[i];
        left.push(i);
      }
    };
    monostack(a, left, 0);
    reverse(a.begin(), a.end());
    monostack(a, right, 1);
    reverse(f[1].begin(), f[1].end());
    reverse(a.begin(), a.end());
    long long id = -1, mx = 0;
    for (int i = 0; i < n; i++) {
      if (f[0][i] + f[1][i] - a[i] > mx) {
        id = i;
        mx = f[0][i] + f[1][i] - a[i];
      }
    }
    vector<long long> res(n, 0);
    res[id] = a[id];
    for (long long i = id - 1; i >= 0; i--) {
      if (a[i] > res[i + 1])
        res[i] = res[i + 1];
      else
        res[i] = a[i];
    }
    for (long long i = id + 1; i < n; i++) {
      if (a[i] > res[i - 1])
        res[i] = res[i - 1];
      else
        res[i] = a[i];
    }
    for (long long i : res) cout << i << " ";
    cout << endl;
  }
};
class p982C {
 public:
  int ans = 0;
  vector<vector<int>> edge;
  int dfs(int cur, int fa) {
    int odd = 0;
    for (auto child : edge[cur]) {
      if (child == fa) continue;
      int temp = dfs(child, cur);
      if (temp == 0)
        ans++;
      else
        odd++;
    }
    if (odd % 2 == 1)
      return 0;
    else
      return 1;
  }
  void solve() {
    int n;
    cin >> n;
    ans = 0;
    edge = vector<vector<int>>(n);
    for (int i = 0; i < n - 1; i++) {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      edge[u].push_back(v);
      edge[v].push_back(u);
    }
    if (dfs(0, -1) != 0) {
      cout << -1 << endl;
    } else
      cout << ans << endl;
  }
};
class p891C {
 public:
  int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd(y, x % y);
  }
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      if (a[i] == 1) cnt++;
    }
    if (cnt > 0) {
      cout << n - cnt << endl;
      return;
    }
    bool ok = false;
    int len = n + 1;
    for (int l = 0; l < n; l++) {
      int temp = a[l];
      for (int r = l; r < n; r++) {
        temp = gcd(temp, a[r]);
        if (temp == 1) {
          len = min(len, r - l);
          break;
        }
      }
    }
    if (len == n + 1)
      cout << -1 << endl;
    else
      cout << len + n - 1 << endl;
  }
};
class p877B {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<int>> a(2, vector<int>(n + 1, 0));
    for (int i = 0; i < s.size(); i++) {
      int cur = s[i] - 'a';
      a[0][i + 1] += a[0][i];
      a[1][i + 1] += a[1][i];
      a[cur][i + 1]++;
    }
    int res = 0;
    for (int i = 0; i <= n; i++) {
      for (int j = i; j <= n; j++) {
        int t1 = a[1][i];
        int t2 = a[0][j] - a[0][i];
        int t3 = a[1][n] - a[1][j];
        res = max(res, n - t1 - t2 - t3);
      }
    }
    cout << res << endl;
  }
};
class p1005D {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> dp(n + 1, 0);
    int sum = 0;
    unordered_map<int, int> cnt;
    cnt[0] = 0;
    int res = 0;
    for (int i = 1; i <= n; i++) {
      sum += (s[i - 1] - '0');
      sum %= 3;
      dp[i] = dp[i - 1];
      if (cnt.count((sum))) {
        dp[i] = max(dp[i], dp[cnt[sum]] + 1);
      }
      res = max(res, dp[i]);
      cnt[sum] = i;
    }
    cout << res << endl;
  }
};
class p264B {
 public:
  int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
  }
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (auto &i : a) cin >> i;
    int res = 0;
    unordered_map<int, int> dp;
    for (int &i : a) {
      if (i == 1) {
        res = max(res, 1);
        continue;
      }
      vector<int> temp;
      int cur = 0;
      for (int j = 2; j <= i / j; j++) {
        if (i % j == 0) {
          temp.push_back(j);
          cur = max(cur, dp[j] + 1);
          while (i % j == 0) i /= j;
        }
      }
      if (i > 1) {
        temp.push_back(i);
        cur = max(cur, dp[i] + 1);
      }
      for (int j : temp) dp[j] = max(dp[j], cur);
      res = max(cur, res);
    }
    cout << res << endl;
  }
};
class p553A {
 public:
  void solve() {
    int k;
    cin >> k;
    vector<long long> a(k, 0);
    vector<long long> dp(k, 0);
    int maxn = 1010;
    vector<vector<long long>> f(maxn, vector<long long>(maxn, 0));
    f[0][0] = 1;
    for (int i = 1; i < maxn; i++) {
      f[i][0] = 1;
      for (int j = 1; j <= i; j++) {
        f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % 1000000007;
      }
    }
    for (auto &i : a) cin >> i;
    long long sum = a[0];
    dp[0] = 1;
    for (long long i = 1; i < k; i++) {
      sum += a[i] - 1;
      dp[i] = (dp[i - 1] * f[sum][a[i] - 1]) % 1000000007;
      sum++;
    }
    cout << dp.back() % 1000000007 << endl;
  }
};
class p322B {
 public:
  void solve() {
    int n, k;
    cin >> n >> k;
    vector<long long> v(n, 0);
    vector<long long> sum(n + 1, 0);
    vector<long long> dp(n + 1, 0);
    vector<long long> index(n + 1, 0);
    dp[0] = 0;
    index[0] = 0;
    long long res = 0;
    for (int i = 1; i <= n; i++) {
      cin >> v[i - 1];
      sum[i] += sum[i - 1] + v[i - 1];
      dp[i] = dp[i - 1];
      index[i] = index[i - 1];
      if (i >= k) {
        if (sum[i] - sum[i - k] > dp[i]) {
          dp[i] = sum[i] - sum[i - k];
          index[i] = i - k + 1;
        }
        res = max(res, sum[i] - sum[i - k] + dp[i - k]);
      }
    }
    vector<pair<long long, long long>> ans;
    for (int i = 1; i <= n; i++) {
      if (i >= k) {
        if (res == dp[i - k] + sum[i] - sum[i - k]) {
          ans.emplace_back(index[i - k], i - k + 1);
        }
      }
    }
    sort(ans.begin(), ans.end());
    cout << ans.begin()->first << " " << ans.begin()->second << endl;
  }
};
class p1084C {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<long long> a;
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
      if (s[i - 1] == 'a') {
        sum++;
      } else if (s[i - 1] == 'b') {
        a.push_back(sum);
        sum = 0;
      }
    }
    if (sum != 0) a.push_back(sum);
    long long res = 1;
    if (a.size() == 0) {
      cout << 0 << endl;
      return;
    }
    for (auto i : a) {
      res = (res * (i + 1)) % 1000000007;
    }
    res = (res - 1 + 1000000007) % 1000000007;
    cout << res << endl;
  }
};
class p991D {
 public:
  void solve() {
    vector<string> a(2);
    cin >> a[0] >> a[1];
    int n = a[0].size();
    if (n == 1) {
      cout << 0 << endl;
      return;
    }
    vector<vector<int>> dp(n + 1, vector<int>(3, 0));
    vector<int> v(n, 0);
    for (int i = 0; i < n; i++) {
      if (a[0][i] == '0') v[i]++;
      if (a[1][i] == '0') v[i]++;
    }
    for (int i = 2; i <= n; i++) {
      dp[i][2] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2]));
      if (v[i - 1] == 0) continue;
      int pre = max(dp[i - 2][0], max(dp[i - 2][1], dp[i - 2][2]));
      if (v[i - 1] == 2) {
        if (v[i - 2] > 0) {
          if (v[i - 2] == 2) {
            dp[i][0] = max(dp[i][0], pre + 1);
            dp[i][1] = max(dp[i][1], pre + 1);
            dp[i][1] = max(dp[i][1], max(dp[i - 1][0], dp[i - 1][2]) + 1);
          } else
            dp[i][1] = max(dp[i][1], dp[i - 1][2] + 1);
        }
      } else {
        if (v[i - 2] == 2) {
          dp[i][0] = max(dp[i][0], pre + 1);
        }
      }
    }
    cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << endl;
  }
};
class p855B {
 public:
  void solve() {
    long long n;
    cin >> n;
    vector<long long> v(3, 0);
    cin >> v[0] >> v[1] >> v[2];
    vector<long long> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<vector<long long>> dp(n, vector<long long>(3, 0));
    dp[0][0] = v[0] * a[0];
    dp[0][1] = v[0] * a[0] + v[1] * a[0];
    dp[0][2] = v[0] * a[0] + v[1] * a[0] + v[2] * a[0];
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < 3; j++) {
        dp[i][j] = dp[i - 1][j];
        long long temp = 0;
        for (int k = j; k >= 0; k--) {
          temp += v[k] * a[i];
          dp[i][j] = max(dp[i][j], temp + (k - 1 >= 0 ? dp[i - 1][k - 1] : 0));
        }
      }
    }
    cout << dp[n - 1][2] << endl;
  }
};
class p873B {
 public:
  void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    unordered_map<int, int> cnt;
    int zero = 0, one = 0;
    int res = 0;
    cnt[0] = -1;
    for (int i = 0; i < n; i++) {
      if (s[i] == '0')
        zero++;
      else
        one++;
      int diff = zero - one;
      if (cnt.count(diff)) {
        res = max(res, i - cnt[diff]);
      } else
        cnt[diff] = i;
    }
    cout << res << endl;
  }
};
class p340D {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<int> dp;
    for (int i : a) {
      auto pos = upper_bound(dp.begin(), dp.end(), i) - dp.begin();
      if (pos == dp.size())
        dp.push_back(i);
      else
        dp[pos] = i;
    }
    cout << dp.size() << endl;
  }
};
class p1081C {
 public:
  void solve() {
    long long n, m, k;
    cin >> n >> m >> k;
    vector<vector<long long>> dp(n, vector<long long>(k + 1, 0));
    long long modulo = 998244353;
    dp[0][0] = m;
    for (int i = 1; i < n; i++) {
      for (int j = k; j >= 0; j--) {
        dp[i][j] =
            (dp[i - 1][j] + (j > 0 ? dp[i - 1][j - 1] : 0) * (m - 1)) % modulo;
      }
    }
    cout << dp[n - 1][k] << endl;
  }
};
class p761C {
 public:
  void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    vector<vector<int>> a(n, vector<int>(3, -1));
    auto check = [](char c) {
      if (c == '#' || c == '*' || c == '&') return true;
      return false;
    };
    for (int i = 0; i < n; i++) {
      for (int j = m - 1; j >= 0; j--) {
        if (isdigit(v[i][j]))
          a[i][0] = a[i][0] == -1 ? min(j, m - j) : min(a[i][0], min(j, m - j));
        if (isalpha(v[i][j]))
          a[i][1] = a[i][1] == -1 ? min(j, m - j) : min(a[i][1], min(j, m - j));
        if (check(v[i][j]))
          a[i][2] = a[i][2] == -1 ? min(j, m - j) : min(a[i][2], min(j, m - j));
      }
    }
    vector<vector<int>> dp(n + 1, vector<int>(1 << 3, 10000));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
      dp[i][0] = dp[i - 1][0];
      for (int j = 1; j < (1 << 3); j++) {
        dp[i][j] = dp[i - 1][j];
        for (int k = 0; k < 3; k++) {
          if (((1 << k) & j) != 0 && a[i - 1][k] != -1) {
            int pre = (1 << k) ^ j;
            dp[i][j] = min(dp[i][j], dp[i - 1][pre] + a[i - 1][k]);
          }
        }
      }
    }
    cout << dp[n][(1 << 3) - 1] << endl;
  }
};
class p858C {
 public:
  void solve() {
    string s;
    cin >> s;
    unordered_set<char> dict{'a', 'e', 'i', 'o', 'u'};
    int block = 0, kind = 0;
    vector<char> res;
    bool first = 1;
    for (int i = 0; i < s.size(); i++) {
      if (!dict.count(s[i])) {
        block++;
        if (block > 2 && (s[i] != s[i - 1] || s[i - 1] != s[i - 2])) {
          res.push_back(' ');
          block = 1;
        }
      } else {
        block = kind = 0;
      }
      res.push_back(s[i]);
    }
    for (auto i : res) cout << i;
    cout << endl;
  }
};
class p204A {
 public:
  long long getTen(int x) {
    if (x == 0) return 1;
    long long temp = getTen(x / 2);
    if (x % 2 == 1) return temp * temp * 10;
    return temp * temp;
  }
  long long getDig(long long x) {
    if (x <= 0) return 0;
    if (x <= 9) return x;
    long long res = 0;
    vector<long long> a;
    while (x > 0) {
      a.emplace_back(x % 10);
      x /= 10;
    }
    reverse(a.begin(), a.end());
    int n = a.size();
    for (int i = 0; i < n; i++) {
      long long temp = getTen(max(0, n - 2 - (i + 1) + 1));
      int up = i > 0 ? 10 : a[i];
      for (int j = 1; j < up; j++) {
        res += temp;
      }
    }
    long long temp = 0;
    for (int i = 1; i < n - 1; i++) temp = temp * 10 + a[i];
    if (a.front() <= a.back()) temp++;
    res += temp;
    return res;
  }
  void solve() {
    long long l, r;
    cin >> l >> r;
    cout << getDig(r) - getDig(l - 1) << endl;
  }
};
class p859C {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<int> dp(n, 0);
    vector<int> sum(n, 0);
    sum[n - 1] = a[n - 1];
    dp[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--) sum[i] = sum[i + 1] + a[i];
    for (int i = n - 2; i >= 0; i--) {
      dp[i] = max(dp[i + 1], sum[i + 1] - dp[i + 1] + a[i]);
    }
    cout << sum[0] - dp[0] << " " << dp[0] << endl;
  }
};
class p159D {
 public:
  void solve() {
    string s;
    cin >> s;
    long long n = s.size();
    vector<vector<long long>> done(n, vector<long long>(n, 0));
    vector<long long> dp(n, 0);
    vector<long long> sum(n, 0);
    auto check = [&s, &done, &n](int l, int r) {
      while (l >= 0 && r < n && s[l] == s[r]) {
        done[l][r] = 1;
        l--;
        r++;
      }
    };
    for (int i = 0; i < n; i++) {
      int l = i, r = i;
      check(l, r);
      l = i, r = i + 1;
      check(l, r);
    }
    dp[0] = 0;
    sum[0] = 1;
    for (int i = 1; i < n; i++) {
      long long cnt = 0, cur = 0;
      for (int j = 0; j <= i; j++) {
        if (done[j][i]) {
          cnt++;
          cur += j == 0 ? 0 : sum[j - 1];
        }
      }
      dp[i] = dp[i - 1] + cur;
      sum[i] = sum[i - 1] + cnt;
    }
    cout << dp[n - 1] << endl;
  }
};
class p255C {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    unordered_map<int, vector<int>> cnt;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      cnt[a[i]].push_back(i);
    }
    vector<int> v;
    int res = 0;
    for (auto it : cnt) {
      v.push_back(it.first);
      res = max(res, (int)it.second.size());
    }
    int sz = v.size();
    auto check = [&cnt, &v](int a, int b) {
      int res = 0;
      int i = 0, j = 0, lena = cnt[v[a]].size(), lenb = cnt[v[b]].size();
      while (i < lena && j < lenb) {
        if (cnt[v[a]][i] < cnt[v[b]][j]) {
          while (i < lena && cnt[v[a]][i] < cnt[v[b]][j]) i++;
          if (i < lena) res++;
        } else {
          while (j < lenb && cnt[v[b]][j] < cnt[v[a]][i]) j++;
          if (j < lenb) res++;
        }
      }
      return res + 2;
    };
    for (int i = 0; i < sz; i++) {
      for (int j = i + 1; j < sz; j++) {
        res = max(res, check(i, j));
      }
    }
    cout << res << endl;
  }
  void solve2() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<vector<int>> dp(n, vector<int>(n, 0));
    int res = 1;
    for (int i = 1; i < n; i++) {
      int k = -1;
      for (int j = 0; j < i; j++) {
        if (k == -1)
          dp[i][j] = 2;
        else
          dp[i][j] = dp[j][k] + 1;
        if (a[i] == a[j]) k = j;
        res = max(res, dp[i][j]);
      }
    }
    cout << res << endl;
  }
};
class p868C {
 public:
  void solve() {
    int n, k;
    cin >> n >> k;
    unordered_map<int, int> cnt;
    for (int i = 0; i < n; i++) {
      int mask = 0;
      for (int j = 0; j < k; j++) {
        int t = 0;
        cin >> t;
        if (t == 1) mask |= (1 << j);
      }
      cnt[mask]++;
    }
    bool flag = false;
    for (int i = 0; i < (1 << k); i++) {
      for (int j = 0; j < (1 << k); j++) {
        if ((i & j) == 0 && (cnt[i] && cnt[j])) flag = true;
      }
    }
    if (flag)
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
};
class p22B {
 public:
  void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    vector<vector<int>> up(n, vector<int>(m, 0));
    vector<vector<int>> left(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      for (int j = 0; j < m; j++) {
        if (a[i][j] == '0') {
          up[i][j] = left[i][j] = 1;
          if (i - 1 >= 0) up[i][j] += up[i - 1][j];
          if (j > 0) left[i][j] += left[i][j - 1];
        }
      }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (a[i][j] == '1') continue;
        int len = 1000000;
        for (int k = 1; k <= up[i][j]; k++) {
          len = min(len, left[i - k + 1][j]);
          res = max(res, (len + k) * 2);
        }
      }
    }
    cout << res << endl;
  }
};
class p566F {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    unordered_map<int, int> cnt;
    int mx = -1;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      mx = max(mx, a[i]);
    }
    vector<int> dp(mx + 1, 1);
    for (int i = 0; i < n; i++) {
      for (int j = 2 * a[i]; j <= mx; j += a[i]) {
        dp[j] = max(dp[j], dp[a[i]] + 1);
      }
    }
    int res = 0;
    for (int i = 0; i < n; i++) res = max(res, dp[a[i]]);
    cout << res << endl;
  }
};
class p191A {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<string> s(n);
    vector<vector<int>> dp(26, vector<int>(26, -1));
    for (int i = 0; i < n; i++) cin >> s[i];
    int res = 0;
    for (int i = 0; i < n; i++) {
      int st = s[i].front() - 'a', ed = s[i].back() - 'a';
      for (int j = 0; j < 26; j++) {
        if (dp[j][st] != -1) {
          dp[j][ed] = max(dp[j][ed], dp[j][st] + (int)s[i].size());
        }
      }
      dp[st][ed] = max(dp[st][ed], (int)s[i].size());
    }
    for (int i = 0; i < 26; i++) res = max(res, dp[i][i]);
    cout << res << endl;
  }
};
class p417A {
 public:
  void solve() {
    int c, d, n, m, k;
    cin >> c >> d >> n >> m >> k;
    int res = 100000000;
    int remain = max(0, n * m - k);
    if (remain == 0) {
      cout << 0 << endl;
      return;
    }
    for (int i = 0; i * n <= remain + n - 1; i++) {
      int left = max(0, remain - i * n);
      res = min(res, i * c + left * d);
    }
    cout << res << endl;
  }
};
class p10B {
 public:
  void solve() {
    int n, k, m;
    cin >> n >> k;
    vector<vector<vector<int>>> dp(
        k + 1, vector<vector<int>>(k + 1, vector<int>(k + 1, 0x3f3f3f3f)));
    for (int i = 1; i <= k; i++) {
      for (int j = 1; j <= k; j++) {
        dp[i][j][0] = 0;
        for (int r = 1; r + j - 1 <= k; r++) {
          dp[i][j][r] = dp[i][j][r - 1] + abs(i - (k + 1) / 2) +
                        abs(j + r - 1 - (k + 1) / 2);
        }
      }
    }
    while (n--) {
      cin >> m;
      int ans = 0x3f3f3f3f, x, l, r;
      for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= k; j++) {
          if (dp[i][j][m] < ans) {
            x = i;
            l = j;
            r = j + m - 1;
            ans = dp[i][j][m];
          }
        }
      }
      if (ans == 0x3f3f3f3f)
        cout << -1 << endl;
      else {
        cout << x << " " << l << " " << r << endl;
        for (int i = 1; i <= k; i++) {
          for (int j = 1; j + i - 1 <= k; j++) {
            if (!(i + j - 1 < l || i > r)) {
              dp[x][i][j] = 0x3f3f3f3f;
            }
          }
        }
      }
    }
  }
};
class p74B {
 public:
  void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    string to, dir;
    cin >> to >> dir;
    int d = 0;
    string t;
    cin >> t;
    if (dir == "head")
      d = -1;
    else
      d = 1;
    int res = 0;
    bool win = true;
    auto move = [&k, &d, &n]() {
      k += d;
      if (k == 0)
        k = 2, d = -d;
      else if (k == n + 1)
        k = n - 1, d = -d;
    };
    for (int i = 0; i < t.size(); i++) {
      if (t[i] == '0') {
        if ((m - k) * d >= 0)
          m += d;
        else
          m -= d;
        if (m == 0) m = 1;
        if (m == n + 1) m = n;
        if (m == k) {
          win = false, res = i;
          break;
        }
        move();
      } else {
        move();
        if (d == -1) {
          m = (k == n ? 1 : n);
        } else
          m = (k == 1 ? n : 1);
      }
      if (m == k) {
        win = false, res = i;
        break;
      }
    }
    if (win)
      cout << "Stowaway" << endl;
    else {
      cout << "Controller " << res + 1 << endl;
    }
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  p74B ans;
  ans.solve();
  return 0;
}

```