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 INF = 2147483647;
const long long LLINF = 9223372036854775807LL;
struct TreeNodeData {
  long long sum;
  int cnt;
  TreeNodeData() {}
  TreeNodeData(long long sum, int cnt) : sum(sum), cnt(cnt) {}
  TreeNodeData combine(const TreeNodeData& oth) const {
    return TreeNodeData(sum + oth.sum, cnt + oth.cnt);
  }
};
struct TreeNode {
  int x, y;
  int L, R;
  TreeNodeData data;
  TreeNodeData subdata;
  TreeNode(int x, int y, int L, int R, TreeNodeData data, TreeNodeData subdata)
      : x(x), y(y), L(L), R(R), data(data), subdata(subdata) {}
};
vector<TreeNode> tree;
int get_node(int x, TreeNodeData data) {
  TreeNode cur_node(x, rand(), -1, -1, data, data);
  int res = int((tree).size());
  tree.push_back(cur_node);
  return res;
}
TreeNodeData get_subdata(int v) {
  if (v == -1) return TreeNodeData(0, 0);
  return tree[v].subdata;
}
void update_node(int v) {
  tree[v].subdata = get_subdata(tree[v].L)
                        .combine(get_subdata(tree[v].R))
                        .combine(tree[v].data);
}
int merge(int l, int r) {
  if (l == -1) return r;
  if (r == -1) return l;
  if (tree[l].y > tree[r].y) {
    tree[l].R = merge(tree[l].R, r);
    update_node(l);
    return l;
  } else {
    tree[r].L = merge(l, tree[r].L);
    update_node(r);
    return r;
  }
}
void split(int v, int k, int& L, int& R) {
  if (v == -1) {
    L = -1;
    R = -1;
    return;
  }
  if (tree[v].x <= k) {
    split(tree[v].R, k, tree[v].R, R);
    L = v;
    update_node(v);
  } else {
    split(tree[v].L, k, L, tree[v].L);
    R = v;
    update_node(v);
  }
}
template <long long base>
struct Pnum {
  long long d0, d1;
  Pnum<base>() : d0(0), d1(0) {}
  Pnum<base>(long long d0, long long d1) : d0(d0), d1(d1) {}
  explicit Pnum<base>(long long x) {
    d0 = x % base;
    d1 = x / base;
  }
  Pnum<base> operator+(const Pnum<base>& oth) const {
    long long res_d0 = d0 + oth.d0;
    long long res_d1 = d1 + oth.d1;
    if (res_d0 >= base) res_d0 -= base, res_d1 += 1;
    return Pnum<base>(res_d0, res_d1);
  }
};
typedef Pnum<(long long)1e18> pnum10;
vector<long long> tmin;
long long cinf = 1e18;
long long getmin(int v, int L, int R, int l, int r) {
  if (L > r || l > R) return cinf;
  if (l <= L && R <= r) return tmin[v];
  int m = (L + R) >> 1;
  long long v1 = getmin(2 * v + 1, L, m, l, r);
  long long v2 = getmin(2 * v + 2, m + 1, R, l, r);
  return min(v1, v2);
}
void update_tree(int v, int L, int R, int pos, int val) {
  if (L == R) {
    tmin[v] = val;
    return;
  }
  int m = (L + R) >> 1;
  if (pos <= m)
    update_tree(v * 2 + 1, L, m, pos, val);
  else
    update_tree(v * 2 + 2, m + 1, R, pos, val);
  tmin[v] = min(tmin[v * 2 + 1], tmin[v * 2 + 2]);
}
struct Solver {
  int n;
  string s;
  long long total_min;
  int root;
  vector<int> p;
  vector<bool> is_removed;
  vector<pair<int, int> > skips;
  explicit Solver(int n) {
    this->n = n;
    this->total_min = 1e18;
    this->root = -1;
    int pw = 1;
    while (pw < n) pw <<= 1;
    tmin = vector<long long>(pw * 2 + 10);
    tree.clear();
    p = vector<int>(n);
    is_removed = vector<bool>(n);
    skips = vector<pair<int, int> >(n + 1, make_pair(-1, -1));
  }
  long long query(char c, int wi) {
    int i = int((s).size());
    s += c;
    update_tree(0, 0, n - 1, i, wi);
    total_min = min(total_min, (long long)wi);
    long long cur_add = total_min;
    if (i > 0) {
      vector<int> to_rem;
      int suff_len = p[i - 1];
      while (true) {
        if (s[suff_len] == c) {
          p[i] = suff_len + 1;
          break;
        } else if (suff_len == 0)
          break;
        if (suff_len > 0) {
          int fr = i - suff_len;
          int to = i - 1;
          int cmin = getmin(0, 0, n - 1, fr, to);
          if (!is_removed[fr]) {
            to_rem.push_back(cmin);
            is_removed[fr] = true;
          }
          suff_len = p[suff_len - 1];
        }
      };
      auto get_pred = [](int sl, const vector<int>& p) {
        if (sl == 0) return -1;
        return p[sl - 1];
      };
      if (p[i] > 0) {
        int ptr1 = get_pred(p[i], p);
        int ptr2 = get_pred(p[i] - 1, p);
        while (ptr1 != -1 && ptr2 != -1) {
          if (ptr1 == ptr2 + 1) {
            skips[p[i]] = skips[ptr1];
            break;
          } else {
            if (ptr1 > ptr2)
              ptr1 = get_pred(ptr1, p);
            else {
              skips[p[i]] = make_pair(ptr1, ptr2);
              break;
            }
          }
        }
      }
      pair<int, int> cur = skips[p[i]];
      int cc = 0;
      while (cur.first != -1 && cur.second != -1) {
        if (cur.first == cur.second + 1) {
          cur = skips[cur.first];
          continue;
        }
        if (cur.first > cur.second) {
          cur.first = get_pred(cur.first, p);
        } else {
          int fr = i - cur.second;
          int to = i - 1;
          if (cur.second > 0) {
            int cmin = getmin(0, 0, n - 1, fr, to);
            if (!is_removed[fr]) {
              to_rem.push_back(cmin);
              is_removed[fr] = true;
            }
          }
          cur.second = get_pred(cur.second, p);
        }
      }
      for (int rem_val : to_rem) {
        int tl, tm, tr;
        split(root, rem_val, tm, tr);
        split(tm, rem_val - 1, tl, tm);
        assert(tm != -1);
        tree[tm].data.cnt -= 1;
        tree[tm].data.sum -= rem_val;
        tree[tm].subdata = tree[tm].data;
        if (tree[tm].data.cnt == 0) tm = -1;
        root = merge(tl, merge(tm, tr));
      }
      int tl, tm, tr;
      split(root, wi, tm, tr);
      split(tm, wi - 1, tl, tm);
      int rcnt = get_subdata(tr).cnt;
      if (tm != -1) {
        tree[tm].data.cnt += rcnt;
        tree[tm].data.sum += rcnt * (long long)wi;
        tree[tm].subdata = tree[tm].data;
      } else {
        tm = get_node(wi, TreeNodeData(wi * (long long)rcnt, rcnt));
      }
      root = merge(tl, tm);
      if (c == s[0]) {
        int tl, tm, tr;
        split(root, wi, tm, tr);
        split(tm, wi - 1, tl, tm);
        if (tm == -1) {
          tm = get_node(wi, TreeNodeData(wi, 1));
        } else {
          tree[tm].data.cnt += 1;
          tree[tm].data.sum += wi;
          tree[tm].subdata = tree[tm].data;
        }
        root = merge(tl, merge(tm, tr));
      }
    }
    cur_add += get_subdata(root).sum;
    return cur_add;
  }
};
struct StupidSolver {
  int n;
  string s;
  vector<int> weights;
  explicit StupidSolver(int n) : n(n) {}
  long long query(char c, int wi) {
    long long result = 0;
    s += c;
    weights.push_back(wi);
    long long cur_min = 1e18;
    for (int sufflen = 1; sufflen <= int((s).size()); ++sufflen) {
      cur_min = min(cur_min, (long long)weights[int((s).size()) - sufflen]);
      string pref = s.substr(0, sufflen);
      string suff = s.substr(int((s).size()) - sufflen);
      if (pref == suff) result += cur_min;
    }
    return result;
  }
};
void stress() {
  for (int iterind = 0; iterind <= 1000000; ++iterind) {
    cout << "ITER " << iterind << endl;
    int curlen = rand() % 20 + 1;
    string s;
    vector<int> weights;
    for (int i = 0; i < curlen; ++i) {
      char cur_char = 'a' + rand() % 2;
      int cur_weight = rand() % 4;
      s += cur_char;
      weights.push_back(cur_weight);
    }
    Solver solver1(curlen);
    StupidSolver solver2(curlen);
    for (int i = 0; i < curlen; ++i) {
      long long resp1 = solver1.query(s[i], weights[i]);
      long long resp2 = solver2.query(s[i], weights[i]);
      if (resp1 != resp2) {
        cout << "FAIL!!!!" << endl;
        cout << "STR: " << s << endl;
        for (int j = 0; j < curlen; ++j) cout << weights[j] << " ";
        cout << endl;
        cout << "POS: " << i << endl;
        cout << "EXP: " << resp2 << endl;
        cout << "ACT: " << resp1 << endl;
        exit(0);
      }
    }
  }
}
int main() {
  int root = -1;
  int n;
  scanf("%d", &n);
  Solver solver(n);
  pnum10 total_ans10;
  long long ans2 = 0;
  long long ans26 = 0;
  for (int i = 0; i < n; ++i) {
    char c = 0;
    while (!(c >= 'a' && c <= 'z')) c = getchar();
    int wi;
    scanf("%d", &wi);
    wi ^= (int)ans2;
    c = 'a' + (c - 'a' + ans26) % 26;
    long long cur_add = solver.query(c, wi);
    ans2 = (ans2 + cur_add) & ((1 << 30) - 1);
    ans26 = (ans26 + cur_add) % 26;
    total_ans10 = total_ans10 + pnum10(cur_add);
    if (total_ans10.d1 == 0)
      printf("%lld\n", total_ans10.d0);
    else
      printf("%lld%018lld\n", total_ans10.d1, total_ans10.d0);
  }
  return 0;
}