#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;
}
