#include <bits/stdc++.h>
using namespace std;
int n, pos[200001];
struct node {
  node *l, *r;
  long long int lazy, lazy2;
};
node *root[200001];
int build(int s, int e, node *n) {
  if (s == e) {
    n->l = n->r = NULL;
    n->lazy = -1, n->lazy2 = 1;
    return 0;
  }
  int mid = (s + e) / 2;
  n->l = new node, n->r = new node;
  build(s, mid, n->l), build(mid + 1, e, n->r);
  n->lazy = n->lazy2 = 0;
  return 0;
}
pair<long long int, long long int> query(int s, int e, int q, node *n) {
  if (s == e) return make_pair(n->lazy, n->lazy2);
  int mid = (s + e) / 2;
  pair<long long int, long long int> p;
  if (q <= mid)
    p = query(s, mid, q, n->l);
  else
    p = query(mid + 1, e, q, n->r);
  return make_pair(p.first + n->lazy, p.second + n->lazy2);
}
int update(int s, int e, int as, int ae, node *o, node *n, int x, int t) {
  if ((s >= as) && (e <= ae)) {
    n->l = o->l, n->r = o->r;
    n->lazy = o->lazy + x, n->lazy2 = o->lazy2 + (long long int)x * t;
    return 0;
  }
  int mid = (s + e) / 2;
  if (ae <= mid) {
    n->r = o->r, n->l = new node;
    update(s, mid, as, ae, o->l, n->l, x, t);
  } else if (as > mid) {
    n->l = o->l, n->r = new node;
    update(mid + 1, e, as, ae, o->r, n->r, x, t);
  } else {
    n->l = new node, n->r = new node;
    update(s, mid, as, ae, o->l, n->l, x, t);
    update(mid + 1, e, as, ae, o->r, n->r, x, t);
  }
  n->lazy = o->lazy, n->lazy2 = o->lazy2;
  return 0;
}
int tree[1 << 19];
int build2(int s, int e, int i) {
  if (s == e) {
    tree[i] = -1;
    return 0;
  }
  int mid = (s + e) / 2;
  build2(s, mid, 2 * i + 1), build2(mid + 1, e, 2 * i + 2);
  tree[i] = -1;
  return 0;
}
int query2(int s, int e, int qs, int qe, int i) {
  if ((s > qe) || (e < qs))
    return 1e9;
  else if ((s >= qs) && (e <= qe))
    return tree[i];
  int mid = (s + e) / 2;
  return min(query2(s, mid, qs, qe, 2 * i + 1),
             query2(mid + 1, e, qs, qe, 2 * i + 2));
}
int update2(int s, int e, int ai, int i, int num) {
  if ((s > ai) || (e < ai))
    return 0;
  else if (s == e) {
    tree[i] = num;
    return 0;
  }
  int mid = (s + e) / 2;
  update2(s, mid, ai, 2 * i + 1, num), update2(mid + 1, e, ai, 2 * i + 2, num);
  tree[i] = min(tree[2 * i + 1], tree[2 * i + 2]);
  return 0;
}
int update3(int s, int e, int as, int ae, int i, int ol, int nl, int t) {
  if ((s > ae) || (e < as))
    return 0;
  else if (ol == nl)
    return 0;
  else if ((s >= as) && (e <= ae)) {
    if (s == e) {
      nl = min(nl, tree[i]), ol = min(ol, tree[i]);
      if (nl > ol) {
        node *r2 = new node;
        update(0, n, s, e, root[t + 1], r2, nl - ol, t);
        root[t + 1] = r2;
      }
      return 0;
    } else if (nl <= tree[i]) {
      node *r2 = new node;
      update(0, n, s, e, root[t + 1], r2, nl - ol, t);
      root[t + 1] = r2;
      return 0;
    }
  }
  int mid = (s + e) / 2;
  update3(s, mid, as, ae, 2 * i + 1, ol, nl, t);
  update3(mid + 1, e, as, ae, 2 * i + 2, min(ol, tree[2 * i + 1]),
          min(nl, tree[2 * i + 1]), t);
  return 0;
}
long long int getAns(int l, int r, int k) {
  if (k == -1) return (long long int)(r - l + 1) * (r - l + 2) / 2;
  int s = 0, e = r + 1;
  while (s < e) {
    int m = (s + e) / 2;
    pair<long long int, long long int> p = query(0, n, k, root[m + 1]);
    if (p.first < l)
      s = m + 1;
    else
      e = m;
  }
  if (s > r)
    return 0;
  else {
    pair<long long int, long long int> p = query(0, n, k, root[r + 1]);
    pair<long long int, long long int> p2 = query(0, n, k, root[s]);
    return (p.first * (r + 1) - p.second) - (p2.first * s - p2.second) -
           (long long int)(r - s + 1) * (l - 1);
  }
}
int main() {
  int i;
  int a, l, r, k;
  long long int lans = 0;
  scanf("%d", &n);
  for (i = 0; i <= n; i++) pos[i] = -1;
  root[0] = new node;
  build(0, n, root[0]), build2(0, n, 0);
  for (i = 0; i < n; i++) {
    scanf("%d %d %d %d", &a, &l, &r, &k);
    a = (a + lans) % (n + 1);
    l = (l + lans) % (i + 1);
    r = (r + lans) % (i + 1);
    if (l > r) swap(l, r);
    k = (k + lans) % (n + 1);
    int q = query2(0, n, 0, a, 0);
    if (q != pos[a])
      pos[a] = i, update2(0, n, a, 0, i), root[i + 1] = root[i];
    else {
      pos[a] = i, update2(0, n, a, 0, i);
      int q2 = query2(0, n, 0, a, 0);
      root[i + 1] = root[i];
      update3(0, n, a, n, 0, q, q2, i);
    }
    lans = getAns(l, r, k - 1) - getAns(l, r, k);
    printf("%I64d\n", lans);
  }
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

You are given an array which is initially empty. You need to perform n operations of the given format: 

  * "a l r k": append a to the end of the array. After that count the number of integer pairs x, y such that l ≤ x ≤ y ≤ r and \operatorname{mex}(a_{x}, a_{x+1}, …, a_{y}) = k. 



The elements of the array are numerated from 1 in the order they are added to the array.

To make this problem more tricky we don't say your real parameters of the queries. Instead your are given a', l', r', k'. To get a, l, r, k on the i-th operation you need to perform the following: 

  * a := (a' + lans) mod(n + 1), 
  * l := (l' + lans) mod{i} + 1, 
  * r := (r' + lans) mod{i} + 1, 
  * if l > r swap l and r, 
  * k := (k' + lans) mod(n + 1), 

where lans is the answer to the previous operation, initially lans is equal to zero. i is the id of the operation, operations are numbered from 1.

The \operatorname{mex}(S), where S is a multiset of non-negative integers, is the smallest non-negative integer which does not appear in the set. For example, \operatorname{mex}(\{2, 2, 3\}) = 0 and \operatorname{mex} (\{0, 1, 4, 1, 6\}) = 2. 

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of the array.

The next n lines contain the description of queries.

Each of them n lines contains four non-negative integers a', l', r', k' (0, ≤ a', l', r', k' ≤ 10^9), describing one operation.

Output

For each query print a single integer — the answer to this query.

Examples

Input


5
0 0 0 1
0 1 0 5
5 2 1 0
5 2 1 0
2 4 3 3


Output


1
1
2
6
3


Input


5
2 0 0 2
2 0 1 1
0 0 2 0
3 2 2 0
0 2 3 0


Output


0
0
3
0
0

Note

For the first example the decoded values of a, l, r, k are the following:

a_1=0,l_1=1,r_1=1,k_1=1

a_2=1,l_2=1,r_2=2,k_2=0

a_3=0,l_3=1,r_3=3,k_3=1

a_4=1,l_4=1,r_4=4,k_4=2

a_5=2,l_5=1,r_5=5,k_5=3

For the second example the decoded values of a, l, r, k are the following:

a_1=2,l_1=1,r_1=1,k_1=2

a_2=2,l_2=1,r_2=2,k_2=1

a_3=0,l_3=1,r_3=3,k_3=0

a_4=0,l_4=2,r_4=2,k_4=3

a_5=0,l_5=3,r_5=4,k_5=0

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, pos[200001];
struct node {
  node *l, *r;
  long long int lazy, lazy2;
};
node *root[200001];
int build(int s, int e, node *n) {
  if (s == e) {
    n->l = n->r = NULL;
    n->lazy = -1, n->lazy2 = 1;
    return 0;
  }
  int mid = (s + e) / 2;
  n->l = new node, n->r = new node;
  build(s, mid, n->l), build(mid + 1, e, n->r);
  n->lazy = n->lazy2 = 0;
  return 0;
}
pair<long long int, long long int> query(int s, int e, int q, node *n) {
  if (s == e) return make_pair(n->lazy, n->lazy2);
  int mid = (s + e) / 2;
  pair<long long int, long long int> p;
  if (q <= mid)
    p = query(s, mid, q, n->l);
  else
    p = query(mid + 1, e, q, n->r);
  return make_pair(p.first + n->lazy, p.second + n->lazy2);
}
int update(int s, int e, int as, int ae, node *o, node *n, int x, int t) {
  if ((s >= as) && (e <= ae)) {
    n->l = o->l, n->r = o->r;
    n->lazy = o->lazy + x, n->lazy2 = o->lazy2 + (long long int)x * t;
    return 0;
  }
  int mid = (s + e) / 2;
  if (ae <= mid) {
    n->r = o->r, n->l = new node;
    update(s, mid, as, ae, o->l, n->l, x, t);
  } else if (as > mid) {
    n->l = o->l, n->r = new node;
    update(mid + 1, e, as, ae, o->r, n->r, x, t);
  } else {
    n->l = new node, n->r = new node;
    update(s, mid, as, ae, o->l, n->l, x, t);
    update(mid + 1, e, as, ae, o->r, n->r, x, t);
  }
  n->lazy = o->lazy, n->lazy2 = o->lazy2;
  return 0;
}
int tree[1 << 19];
int build2(int s, int e, int i) {
  if (s == e) {
    tree[i] = -1;
    return 0;
  }
  int mid = (s + e) / 2;
  build2(s, mid, 2 * i + 1), build2(mid + 1, e, 2 * i + 2);
  tree[i] = -1;
  return 0;
}
int query2(int s, int e, int qs, int qe, int i) {
  if ((s > qe) || (e < qs))
    return 1e9;
  else if ((s >= qs) && (e <= qe))
    return tree[i];
  int mid = (s + e) / 2;
  return min(query2(s, mid, qs, qe, 2 * i + 1),
             query2(mid + 1, e, qs, qe, 2 * i + 2));
}
int update2(int s, int e, int ai, int i, int num) {
  if ((s > ai) || (e < ai))
    return 0;
  else if (s == e) {
    tree[i] = num;
    return 0;
  }
  int mid = (s + e) / 2;
  update2(s, mid, ai, 2 * i + 1, num), update2(mid + 1, e, ai, 2 * i + 2, num);
  tree[i] = min(tree[2 * i + 1], tree[2 * i + 2]);
  return 0;
}
int update3(int s, int e, int as, int ae, int i, int ol, int nl, int t) {
  if ((s > ae) || (e < as))
    return 0;
  else if (ol == nl)
    return 0;
  else if ((s >= as) && (e <= ae)) {
    if (s == e) {
      nl = min(nl, tree[i]), ol = min(ol, tree[i]);
      if (nl > ol) {
        node *r2 = new node;
        update(0, n, s, e, root[t + 1], r2, nl - ol, t);
        root[t + 1] = r2;
      }
      return 0;
    } else if (nl <= tree[i]) {
      node *r2 = new node;
      update(0, n, s, e, root[t + 1], r2, nl - ol, t);
      root[t + 1] = r2;
      return 0;
    }
  }
  int mid = (s + e) / 2;
  update3(s, mid, as, ae, 2 * i + 1, ol, nl, t);
  update3(mid + 1, e, as, ae, 2 * i + 2, min(ol, tree[2 * i + 1]),
          min(nl, tree[2 * i + 1]), t);
  return 0;
}
long long int getAns(int l, int r, int k) {
  if (k == -1) return (long long int)(r - l + 1) * (r - l + 2) / 2;
  int s = 0, e = r + 1;
  while (s < e) {
    int m = (s + e) / 2;
    pair<long long int, long long int> p = query(0, n, k, root[m + 1]);
    if (p.first < l)
      s = m + 1;
    else
      e = m;
  }
  if (s > r)
    return 0;
  else {
    pair<long long int, long long int> p = query(0, n, k, root[r + 1]);
    pair<long long int, long long int> p2 = query(0, n, k, root[s]);
    return (p.first * (r + 1) - p.second) - (p2.first * s - p2.second) -
           (long long int)(r - s + 1) * (l - 1);
  }
}
int main() {
  int i;
  int a, l, r, k;
  long long int lans = 0;
  scanf("%d", &n);
  for (i = 0; i <= n; i++) pos[i] = -1;
  root[0] = new node;
  build(0, n, root[0]), build2(0, n, 0);
  for (i = 0; i < n; i++) {
    scanf("%d %d %d %d", &a, &l, &r, &k);
    a = (a + lans) % (n + 1);
    l = (l + lans) % (i + 1);
    r = (r + lans) % (i + 1);
    if (l > r) swap(l, r);
    k = (k + lans) % (n + 1);
    int q = query2(0, n, 0, a, 0);
    if (q != pos[a])
      pos[a] = i, update2(0, n, a, 0, i), root[i + 1] = root[i];
    else {
      pos[a] = i, update2(0, n, a, 0, i);
      int q2 = query2(0, n, 0, a, 0);
      root[i + 1] = root[i];
      update3(0, n, a, n, 0, q, q2, i);
    }
    lans = getAns(l, r, k - 1) - getAns(l, r, k);
    printf("%I64d\n", lans);
  }
  return 0;
}

```