Problem: Fedya has a string S, initially empty, and an array W, also initially empty.

There are n queries to process, one at a time. Query i consists of a lowercase English letter c_i and a nonnegative integer w_i. First, c_i must be appended to S, and w_i must be appended to W. The answer to the query is the sum of suspiciousnesses for all subsegments of W [L, \ R], (1 ≤ L ≤ R ≤ i).

We define the suspiciousness of a subsegment as follows: if the substring of S corresponding to this subsegment (that is, a string of consecutive characters from L-th to R-th, inclusive) matches the prefix of S of the same length (that is, a substring corresponding to the subsegment [1, \ R - L + 1]), then its suspiciousness is equal to the minimum in the array W on the [L, \ R] subsegment. Otherwise, in case the substring does not match the corresponding prefix, the suspiciousness is 0.

Help Fedya answer all the queries before the orderlies come for him!

Input

The first line contains an integer n (1 ≤ n ≤ 600 000) — the number of queries.

The i-th of the following n lines contains the query i: a lowercase letter of the Latin alphabet c_i and an integer w_i (0 ≤ w_i ≤ 2^{30} - 1).

All queries are given in an encrypted form. Let ans be the answer to the previous query (for the first query we set this value equal to 0). Then, in order to get the real query, you need to do the following: perform a cyclic shift of c_i in the alphabet forward by ans, and set w_i equal to w_i ⊕ (ans \ \& \ MASK), where ⊕ is the bitwise exclusive "or", \& is the bitwise "and", and MASK = 2^{30} - 1.

Output

Print n lines, i-th line should contain a single integer — the answer to the i-th query.

Examples

Input


7
a 1
a 0
y 3
y 5
v 4
u 6
r 8


Output


1
2
4
5
7
9
12


Input


4
a 2
y 2
z 0
y 2


Output


2
2
2
2


Input


5
a 7
u 5
t 3
s 10
s 11


Output


7
9
11
12
13

Note

For convenience, we will call "suspicious" those subsegments for which the corresponding lines are prefixes of S, that is, those whose suspiciousness may not be zero.

As a result of decryption in the first example, after all requests, the string S is equal to "abacaba", and all w_i = 1, that is, the suspiciousness of all suspicious sub-segments is simply equal to 1. Let's see how the answer is obtained after each request:

1. S = "a", the array W has a single subsegment — [1, \ 1], and the corresponding substring is "a", that is, the entire string S, thus it is a prefix of S, and the suspiciousness of the subsegment is 1.

2. S = "ab", suspicious subsegments: [1, \ 1] and [1, \ 2], total 2.

3. S = "aba", suspicious subsegments: [1, \ 1], [1, \ 2], [1, \ 3] and [3, \ 3], total 4.

4. S = "abac", suspicious subsegments: [1, \ 1], [1, \ 2], [1, \ 3], [1, \ 4] and [3, \ 3], total 5.

5. S = "abaca", suspicious subsegments: [1, \ 1], [1, \ 2], [1, \ 3], [1, \ 4] , [1, \ 5], [3, \ 3] and [5, \ 5], total 7.

6. S = "abacab", suspicious subsegments: [1, \ 1], [1, \ 2], [1, \ 3], [1, \ 4] , [1, \ 5], [1, \ 6], [3, \ 3], [5, \ 5] and [5, \ 6], total 9.

7. S = "abacaba", suspicious subsegments: [1, \ 1], [1, \ 2], [1, \ 3], [1, \ 4] , [1, \ 5], [1, \ 6], [1, \ 7], [3, \ 3], [5, \ 5], [5, \ 6], [5, \ 7] and [7, \ 7], total 12.

In the second example, after all requests S = "aaba", W = [2, 0, 2, 0].

1. S = "a", suspicious subsegments: [1, \ 1] (suspiciousness 2), totaling 2.

2. S = "aa", suspicious subsegments: [1, \ 1] (2), [1, \ 2] (0), [2, \ 2] ( 0), totaling 2.

3. S = "aab", suspicious subsegments: [1, \ 1] (2), [1, \ 2] (0), [1, \ 3] ( 0), [2, \ 2] (0), totaling 2.

4. S = "aaba", suspicious subsegments: [1, \ 1] (2), [1, \ 2] (0), [1, \ 3] ( 0), [1, \ 4] (0), [2, \ 2] (0), [4, \ 4] (0), totaling 2.

In the third example, from the condition after all requests S = "abcde", W = [7, 2, 10, 1, 7].

1. S = "a", suspicious subsegments: [1, \ 1] (7), totaling 7.

2. S = "ab", suspicious subsegments: [1, \ 1] (7), [1, \ 2] (2), totaling 9.

3. S = "abc", suspicious subsegments: [1, \ 1] (7), [1, \ 2] (2), [1, \ 3] ( 2), totaling 11.

4. S = "abcd", suspicious subsegments: [1, \ 1] (7), [1, \ 2] (2), [1, \ 3] ( 2), [1, \ 4] (1), totaling 12.

5. S = "abcde", suspicious subsegments: [1, \ 1] (7), [1, \ 2] (2), [1, \ 3] ( 2), [1, \ 4] (1), [1, \ 5] (1), totaling 13.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int base = 1000000000;
const int base_digits = 9;
struct bigint_t {
  vector<int> z;
  int sign;
  bigint_t() : sign(1) {}
  bigint_t(long long v) { *this = v; }
  bigint_t(const string &s) { read(s); }
  void operator=(const bigint_t &v) {
    sign = v.sign;
    z = v.z;
  }
  void operator=(long long v) {
    sign = 1;
    if (v < 0) {
      sign = -1, v = -v;
    }
    z.clear();
    for (; v > 0; v = v / base) {
      z.push_back(v % base);
    }
  }
  bigint_t operator+(const bigint_t &v) const {
    if (sign == v.sign) {
      bigint_t res = v;
      for (int i = 0, carry = 0; i < (int)max(z.size(), v.z.size()) || carry;
           ++i) {
        if (i == (int)res.z.size()) {
          res.z.push_back(0);
        }
        res.z[i] += carry + (i < (int)z.size() ? z[i] : 0);
        carry = res.z[i] >= base;
        if (carry) {
          res.z[i] -= base;
        }
      }
      return res;
    } else {
      return *this - (-v);
    }
  }
  bigint_t operator-(const bigint_t &v) const {
    if (sign == v.sign) {
      if (abs() >= v.abs()) {
        bigint_t res = *this;
        for (int i = 0, carry = 0; i < (int)v.z.size() || carry; ++i) {
          res.z[i] -= carry + (i < (int)v.z.size() ? v.z[i] : 0);
          carry = res.z[i] < 0;
          if (carry) {
            res.z[i] += base;
          }
        }
        res.trim();
        return res;
      } else {
        return -(v - *this);
      }
    } else {
      return *this + (-v);
    }
  }
  void operator*=(int v) {
    if (v < 0) {
      sign = -sign, v = -v;
    }
    for (int i = 0, carry = 0; i < (int)z.size() || carry; ++i) {
      if (i == (int)z.size()) {
        z.push_back(0);
      }
      long long cur = (long long)z[i] * v + carry;
      carry = cur / base;
      z[i] = cur % base;
    }
    trim();
  }
  bigint_t operator*(int v) const {
    bigint_t res = *this;
    res *= v;
    return res;
  }
  friend pair<bigint_t, bigint_t> divmod(const bigint_t &a1,
                                         const bigint_t &b1) {
    int norm = base / (b1.z.back() + 1);
    bigint_t a = a1.abs() * norm;
    bigint_t b = b1.abs() * norm;
    bigint_t q, r;
    q.z.resize(a.z.size());
    for (int i = a.z.size() - 1; i >= 0; i--) {
      r *= base;
      r += a.z[i];
      int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
      int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
      int d = ((long long)s1 * base + s2) / b.z.back();
      r -= b * d;
      while (r < 0) {
        r += b, --d;
      }
      q.z[i] = d;
    }
    q.sign = a1.sign * b1.sign;
    r.sign = a1.sign;
    q.trim();
    r.trim();
    return make_pair(q, r / norm);
  }
  friend bigint_t sqrt(const bigint_t &a1) {
    bigint_t a = a1;
    while (a.z.empty() || a.z.size() % 2 == 1) {
      a.z.push_back(0);
    }
    int n = a.z.size();
    int firstDigit = sqrt((long long)a.z[n - 1] * base + a.z[n - 2]);
    int norm = base / (firstDigit + 1);
    a *= norm;
    a *= norm;
    while (a.z.empty() || a.z.size() % 2 == 1) {
      a.z.push_back(0);
    }
    bigint_t r = (long long)a.z[n - 1] * base + a.z[n - 2];
    firstDigit = sqrt((long long)a.z[n - 1] * base + a.z[n - 2]);
    int q = firstDigit;
    bigint_t res;
    for (int j = n / 2 - 1; j >= 0; j--) {
      for (;; --q) {
        bigint_t r1 =
            (r - (res * 2 * base + q) * q) * base * base +
            (j > 0 ? (long long)a.z[2 * j - 1] * base + a.z[2 * j - 2] : 0);
        if (r1 >= 0) {
          r = r1;
          break;
        }
      }
      res *= base;
      res += q;
      if (j > 0) {
        int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;
        int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;
        int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;
        q = ((long long)d1 * base * base + (long long)d2 * base + d3) /
            (firstDigit * 2);
      }
    }
    res.trim();
    return res / norm;
  }
  bigint_t operator/(const bigint_t &v) const { return divmod(*this, v).first; }
  bigint_t operator%(const bigint_t &v) const {
    return divmod(*this, v).second;
  }
  void operator/=(int v) {
    if (v < 0) {
      sign = -sign, v = -v;
    }
    for (int i = z.size() - 1, rem = 0; i >= 0; --i) {
      long long cur = z[i] + (long long)rem * base;
      z[i] = cur / v;
      rem = cur % v;
    }
    trim();
  }
  bigint_t operator/(int v) const {
    bigint_t res = *this;
    res /= v;
    return res;
  }
  int operator%(int v) const {
    if (v < 0) {
      v = -v;
    }
    int m = 0;
    for (int i = z.size() - 1; i >= 0; --i) {
      m = ((long long)m * base + z[i]) % v;
    }
    return m * sign;
  }
  void operator+=(const bigint_t &v) { *this = *this + v; }
  void operator-=(const bigint_t &v) { *this = *this - v; }
  void operator*=(const bigint_t &v) { *this = *this * v; }
  void operator/=(const bigint_t &v) { *this = *this / v; }
  bool operator<(const bigint_t &v) const {
    if (sign != v.sign) {
      return sign < v.sign;
    }
    if (z.size() != v.z.size()) {
      return z.size() * sign < v.z.size() * v.sign;
    }
    for (int i = z.size() - 1; i >= 0; i--) {
      if (z[i] != v.z[i]) {
        return z[i] * sign < v.z[i] * sign;
      }
    }
    return false;
  }
  bool operator>(const bigint_t &v) const { return v < *this; }
  bool operator<=(const bigint_t &v) const { return !(v < *this); }
  bool operator>=(const bigint_t &v) const { return !(*this < v); }
  bool operator==(const bigint_t &v) const {
    return !(*this < v) && !(v < *this);
  }
  bool operator!=(const bigint_t &v) const { return *this < v || v < *this; }
  void trim() {
    while (!z.empty() && z.back() == 0) {
      z.pop_back();
    }
    if (z.empty()) {
      sign = 1;
    }
  }
  bool isZero() const { return z.empty() || (z.size() == 1 && !z[0]); }
  bigint_t operator-() const {
    bigint_t res = *this;
    res.sign = -sign;
    return res;
  }
  bigint_t abs() const {
    bigint_t res = *this;
    res.sign *= res.sign;
    return res;
  }
  long long longValue() const {
    long long res = 0;
    for (int i = z.size() - 1; i >= 0; i--) {
      res = res * base + z[i];
    }
    return res * sign;
  }
  friend bigint_t gcd(const bigint_t &a, const bigint_t &b) {
    return b.isZero() ? a : gcd(b, a % b);
  }
  friend bigint_t lcm(const bigint_t &a, const bigint_t &b) {
    return a / gcd(a, b) * b;
  }
  void read(const string &s) {
    sign = 1;
    z.clear();
    int pos = 0;
    while (pos < (int)s.size() && (s[pos] == '-' || s[pos] == '+')) {
      if (s[pos] == '-') {
        sign = -sign;
      }
      ++pos;
    }
    for (int i = s.size() - 1; i >= pos; i -= base_digits) {
      int x = 0;
      for (int j = max(pos, i - base_digits + 1); j <= i; j++) {
        x = x * 10 + s[j] - '0';
      }
      z.push_back(x);
    }
    trim();
  }
  friend istream &operator>>(istream &stream, bigint_t &v) {
    string s;
    stream >> s;
    v.read(s);
    return stream;
  }
  friend ostream &operator<<(ostream &stream, const bigint_t &v) {
    if (v.sign == -1) {
      stream << '-';
    }
    stream << (v.z.empty() ? 0 : v.z.back());
    for (int i = v.z.size() - 2; i >= 0; --i) {
      stream << setw(base_digits) << setfill('0') << v.z[i];
    }
    return stream;
  }
  static vector<int> convert_base(const vector<int> &a, int old_digits,
                                  int new_digits) {
    vector<long long> p(max(old_digits, new_digits) + 1);
    p[0] = 1;
    for (int i = 1; i < (int)p.size(); i++) {
      p[i] = p[i - 1] * 10;
    }
    vector<int> res;
    long long cur = 0;
    int cur_digits = 0;
    for (int i = 0; i < (int)a.size(); i++) {
      cur += a[i] * p[cur_digits];
      cur_digits += old_digits;
      while (cur_digits >= new_digits) {
        res.push_back(cur % p[new_digits]);
        cur /= p[new_digits];
        cur_digits -= new_digits;
      }
    }
    res.push_back(cur);
    while (!res.empty() && res.back() == 0) {
      res.pop_back();
    }
    return res;
  }
  static vector<long long> karatsubaMultiply(const vector<long long> &a,
                                             const vector<long long> &b) {
    int n = a.size();
    vector<long long> res(n + n);
    if (n <= 32) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          res[i + j] += a[i] * b[j];
        }
      }
      return res;
    }
    int k = n >> 1;
    vector<long long> a1(a.begin(), a.begin() + k);
    vector<long long> a2(a.begin() + k, a.end());
    vector<long long> b1(b.begin(), b.begin() + k);
    vector<long long> b2(b.begin() + k, b.end());
    vector<long long> a1b1 = karatsubaMultiply(a1, b1);
    vector<long long> a2b2 = karatsubaMultiply(a2, b2);
    for (int i = 0; i < k; i++) {
      a2[i] += a1[i];
    }
    for (int i = 0; i < k; i++) {
      b2[i] += b1[i];
    }
    vector<long long> r = karatsubaMultiply(a2, b2);
    for (int i = 0; i < (int)a1b1.size(); i++) {
      r[i] -= a1b1[i];
    }
    for (int i = 0; i < (int)a2b2.size(); i++) {
      r[i] -= a2b2[i];
    }
    for (int i = 0; i < (int)r.size(); i++) {
      res[i + k] += r[i];
    }
    for (int i = 0; i < (int)a1b1.size(); i++) {
      res[i] += a1b1[i];
    }
    for (int i = 0; i < (int)a2b2.size(); i++) {
      res[i + n] += a2b2[i];
    }
    return res;
  }
  bigint_t operator*(const bigint_t &v) const {
    vector<int> a6 = convert_base(this->z, base_digits, 6);
    vector<int> b6 = convert_base(v.z, base_digits, 6);
    vector<long long> a(a6.begin(), a6.end());
    vector<long long> b(b6.begin(), b6.end());
    while (a.size() < b.size()) {
      a.push_back(0);
    }
    while (b.size() < a.size()) {
      b.push_back(0);
    }
    while (a.size() & (a.size() - 1)) {
      a.push_back(0);
      b.push_back(0);
    }
    vector<long long> c = karatsubaMultiply(a, b);
    bigint_t res;
    res.sign = sign * v.sign;
    for (int i = 0, carry = 0; i < (int)c.size(); i++) {
      long long cur = c[i] + carry;
      res.z.push_back(cur % 1000000);
      carry = cur / 1000000;
    }
    res.z = convert_base(res.z, 6, base_digits);
    res.trim();
    return res;
  }
};
class segtree {
 public:
  struct node {
    int val = INT_MAX;
    int p = INT_MAX;
    void apply(int l, int r, int v) {
      val = min(val, v);
      p = min(p, v);
    }
  };
  node unite(const node &a, const node &b) const {
    node res;
    res.val = min(a.val, b.val);
    return res;
  }
  inline void push(int x, int l, int r) {
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    if (tree[x].p != INT_MAX) {
      tree[x + 1].apply(l, y, tree[x].p);
      tree[z].apply(y + 1, r, tree[x].p);
      tree[x].p = INT_MAX;
    }
  }
  inline void pull(int x, int z) { tree[x] = unite(tree[x + 1], tree[z]); }
  int n;
  vector<node> tree;
  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }
  template <typename M, typename... T>
  void build(int x, int l, int r, const vector<M> &v, const T &...t) {
    if (l == r) {
      tree[x].apply(l, r, v[l], t...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v, t...);
    build(z, y + 1, r, v, t...);
    pull(x, z);
  }
  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }
  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M &...v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }
  int find_first_knowingly(int x, int l, int r,
                           const function<bool(const node &)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }
  int find_first(int x, int l, int r, int ll, int rr,
                 const function<bool(const node &)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
  int find_last_knowingly(int x, int l, int r,
                          const function<bool(const node &)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }
  int find_last(int x, int l, int r, int ll, int rr,
                const function<bool(const node &)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }
  template <typename M, typename... T>
  segtree(const vector<M> &v, const T &...t) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v, t...);
  }
  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }
  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }
  template <typename... M>
  void modify(int ll, int rr, const M &...v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }
  int find_first(int ll, int rr, const function<bool(const node &)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }
  int find_last(int ll, int rr, const function<bool(const node &)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};
int n;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  vector<int> par(n + 1, -1);
  bigint_t res = 0;
  long long ans = 0;
  string s;
  const int MASK = (1 << 30) - 1;
  const int N = 26;
  vector<vector<int>> to(n + 1, vector<int>(N, -1));
  segtree st(n);
  map<int, int> pt;
  for (int i = 0; i < n; i++) {
    char c;
    int t;
    cin >> c >> t;
    c = 'a' + ((res + (c - 'a')) % N);
    int ss = res % (MASK + 1);
    t ^= ss;
    s += c;
    int p = par[i];
    while (~p) {
      if (s[p] == c) break;
      p = par[p];
    }
    par[i + 1] = p + 1;
    to[i + 1] = to[p + 1];
    to[i + 1][s[p + 1] - 'a'] = p + 1;
    st.modify(0, i, t);
    int cnt = 0;
    while (!pt.empty() && prev(pt.end())->first > t) {
      ans -= 1LL * prev(pt.end())->first * prev(pt.end())->second;
      cnt += prev(pt.end())->second;
      pt.erase(prev(pt.end()));
    }
    pt[t] += cnt + 1;
    ans += 1LL * t * (cnt + 1);
    int cur = i;
    while (true) {
      int nxt = -1;
      for (int j = 0; j < 26; j++) {
        if (j == c - 'a') continue;
        nxt = max(nxt, to[cur][j]);
      }
      cur = nxt;
      if (cur == -1) break;
      int z = st.get(i - cur, i - cur).val;
      ans -= z;
      pt[z]--;
      if (!pt[z]) pt.erase(z);
    }
    res += ans;
    cout << res << endl;
  }
  return 0;
}