#include <bits/stdc++.h>
using namespace std;
int n;
struct seg {
  long long int sum;
  long long int cont;
  seg *l;
  seg *r;
  seg() {
    l = r = NULL;
    sum = cont = 0;
  }
};
struct st {
  vector<seg *> root;
  vector<int> tim;
  vector<pair<pair<int, int>, pair<int, int> > > ad;
  long long int cont(seg *b) {
    if (b == NULL) return 0;
    return b->cont;
  }
  inline void add(seg *&b, int l, int r, int ll, int rr, long long int x) {
    if (r <= ll || rr <= l) {
      return;
    }
    if (b == NULL) {
      b = new seg();
    } else {
      auto f = b;
      b = new seg();
      (*b) = (*f);
    }
    if (ll <= l && r <= rr) {
      b->sum += x;
      b->cont += x * (r - l);
      return;
    }
    add(b->l, l, (l + r) >> 1, ll, rr, x);
    add(b->r, (l + r) >> 1, r, ll, rr, x);
    b->cont = cont(b->l) + cont(b->r) + b->sum * (r - l);
  }
  inline long long int sum(seg *&b, int l, int r, int ll, int rr) {
    if (b == NULL) return 0;
    if (r <= ll || rr <= l) {
      return 0;
    }
    if (ll <= l && r <= rr) {
      return b->cont;
    }
    int rg = min(r, rr) - max(l, ll);
    return sum(b->l, l, (l + r) >> 1, ll, rr) +
           sum(b->r, (l + r) >> 1, r, ll, rr) + rg * b->sum;
  }
  st() {}
};
st bit[200013 + 3];
struct tt {
  int val;
  int lef;
  int rig;
  int tim;
};
bool operator<(const tt &a, const tt &b) {
  return make_tuple(a.val, a.lef, a.rig, a.tim) <
         make_tuple(b.val, b.lef, b.rig, b.tim);
}
set<tt> rng;
int CUR_TIM;
vector<int> ar;
void remove_rng(tt a) {
  int X = CUR_TIM - a.tim;
  bit[a.val].tim.push_back(ar.size() - 1);
  bit[a.val].root.push_back(NULL);
  if (bit[a.val].root.size() > 1) {
    bit[a.val].root.back() = bit[a.val].root[bit[a.val].root.size() - 2];
  }
  bit[a.val].ad.push_back({{a.tim, ar.size() - 1}, {a.lef, a.rig}});
  bit[a.val].add(bit[a.val].root.back(), 0, n, a.lef, a.rig + 1, X);
}
int im[200];
void ins(tt a) {
  auto u = rng.lower_bound({a.val, -1, 0, 0});
  if (u != rng.end() && u->val == a.val) {
    a.lef = min(a.lef, u->lef);
    a.rig = max(a.rig, u->rig);
    remove_rng(*u);
    rng.erase(u);
  }
  rng.insert(a);
}
int seg2[(200013 + 5) * 4];
int lb;
inline void add(int b, int l, int r, int ll, int x) {
  if (l <= ll && ll < r) {
    if (l + 1 == r) {
      seg2[b] = x;
      return;
    }
    add(b * 2 + 1, l, (l + r) >> 1, ll, x);
    add(b * 2 + 2, (l + r) >> 1, r, ll, x);
    seg2[b] = min(seg2[b * 2 + 1], seg2[b * 2 + 2]);
  }
}
inline int query(int b, int l, int r, int x) {
  if (l + 1 == r) {
    if (seg2[b] < x) {
      lb = seg2[b];
      return l;
    }
    return -1;
  }
  if (seg2[b] >= x) {
    return -1;
  }
  int u = query(b * 2 + 1, l, (l + r) >> 1, x);
  if (u != -1) return u;
  return query(b * 2 + 2, (l + r) >> 1, r, x);
}
int mex(int pos) { return query(0, 0, 200013 + 4, pos); }
void add_val(int val) {
  auto z = rng.upper_bound({val, -1, 0, 0});
  int pos = 0;
  if (rng.size() == 0) {
    pos = 0;
  } else {
    if (z != rng.begin()) {
      pos = (*prev(z)).lef - 1;
    } else {
      pos = ar.size();
    }
  }
  while (z != rng.end() && z->val == val) {
    auto t = next(z);
    remove_rng(*z);
    rng.erase(z);
    z = t;
  }
  add(0, 0, 200013 + 4, val, ar.size());
  ar.push_back(val);
  int want = 1;
  int until = 0;
  if (z != rng.end()) {
    until = (*z).rig + 1;
  }
  if (true) {
    if (val == 0) {
      ins({1, (int)ar.size() - 1, (int)ar.size() - 1, CUR_TIM});
    } else {
      ins({0, (int)ar.size() - 1, (int)ar.size() - 1, CUR_TIM});
    }
    pos = min(pos, (int)ar.size() - 2);
  }
  if (pos >= until) {
    int R = pos;
    while (pos >= until) {
      want = mex(pos);
      pos = max(until - 1, lb);
      ins({want, pos + 1, R, CUR_TIM});
      R = pos;
    }
    if (pos >= until) {
      want = mex(until);
      ins({want, until, R, CUR_TIM});
    }
  }
}
long long int overlap(int l1, int r1, int l2, int r2) {
  if (r2 < l1 || r1 < l2) {
    return 0;
  }
  if (l1 <= l2 && r2 <= r1) {
    return r2 - l2 + 1;
  }
  if (l2 <= l1 && r1 <= r2) {
    return r1 - l1 + 1;
  }
  return min(r2, r1) - max(l1, l2) + 1;
}
long long int query(int k, int l, int r) {
  int zz =
      upper_bound(bit[k].tim.begin(), bit[k].tim.end(), r) - bit[k].tim.begin();
  long long int z = 0;
  if (zz > 0) {
    z = bit[k].sum(bit[k].root[zz - 1], 0, n, l, r + 1);
  }
  if (zz != bit[k].tim.size()) {
    auto u = bit[k].ad[zz];
    z += overlap(l, r, u.second.first, u.second.second) *
         overlap(l, r, u.first.first, u.first.second);
  }
  auto f = rng.upper_bound({k, -1, 0, 0});
  while (f != rng.end() && f->val == k) {
    z += overlap(l, r, f->lef, f->rig) * overlap(l, r, f->tim, ar.size() - 1);
    f++;
  }
  return z;
}
int main() {
  memset(seg2, -1, sizeof(seg2));
  cin >> n;
  long long int lans = 0;
  for (int i = 1; i <= n; i++) {
    int a, l, r, k;
    scanf("%d%d%d%d", &a, &l, &r, &k);
    a = (a + lans) % (n + 1);
    l = (l + lans) % i;
    r = (r + lans) % i;
    if (l > r) swap(l, r);
    k = (k + lans) % (n + 1);
    if (a >= 200013) {
      add_val(200013);
    } else {
      add_val(a);
    }
    lans = 0;
    if (k >= 200013) {
      puts("0");
    } else {
      lans = query(k, l, r);
      printf("%lld\n", lans);
    }
    CUR_TIM++;
  }
  return 0;
}

### Prompt

In CPP, your task is to solve 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;
struct seg {
  long long int sum;
  long long int cont;
  seg *l;
  seg *r;
  seg() {
    l = r = NULL;
    sum = cont = 0;
  }
};
struct st {
  vector<seg *> root;
  vector<int> tim;
  vector<pair<pair<int, int>, pair<int, int> > > ad;
  long long int cont(seg *b) {
    if (b == NULL) return 0;
    return b->cont;
  }
  inline void add(seg *&b, int l, int r, int ll, int rr, long long int x) {
    if (r <= ll || rr <= l) {
      return;
    }
    if (b == NULL) {
      b = new seg();
    } else {
      auto f = b;
      b = new seg();
      (*b) = (*f);
    }
    if (ll <= l && r <= rr) {
      b->sum += x;
      b->cont += x * (r - l);
      return;
    }
    add(b->l, l, (l + r) >> 1, ll, rr, x);
    add(b->r, (l + r) >> 1, r, ll, rr, x);
    b->cont = cont(b->l) + cont(b->r) + b->sum * (r - l);
  }
  inline long long int sum(seg *&b, int l, int r, int ll, int rr) {
    if (b == NULL) return 0;
    if (r <= ll || rr <= l) {
      return 0;
    }
    if (ll <= l && r <= rr) {
      return b->cont;
    }
    int rg = min(r, rr) - max(l, ll);
    return sum(b->l, l, (l + r) >> 1, ll, rr) +
           sum(b->r, (l + r) >> 1, r, ll, rr) + rg * b->sum;
  }
  st() {}
};
st bit[200013 + 3];
struct tt {
  int val;
  int lef;
  int rig;
  int tim;
};
bool operator<(const tt &a, const tt &b) {
  return make_tuple(a.val, a.lef, a.rig, a.tim) <
         make_tuple(b.val, b.lef, b.rig, b.tim);
}
set<tt> rng;
int CUR_TIM;
vector<int> ar;
void remove_rng(tt a) {
  int X = CUR_TIM - a.tim;
  bit[a.val].tim.push_back(ar.size() - 1);
  bit[a.val].root.push_back(NULL);
  if (bit[a.val].root.size() > 1) {
    bit[a.val].root.back() = bit[a.val].root[bit[a.val].root.size() - 2];
  }
  bit[a.val].ad.push_back({{a.tim, ar.size() - 1}, {a.lef, a.rig}});
  bit[a.val].add(bit[a.val].root.back(), 0, n, a.lef, a.rig + 1, X);
}
int im[200];
void ins(tt a) {
  auto u = rng.lower_bound({a.val, -1, 0, 0});
  if (u != rng.end() && u->val == a.val) {
    a.lef = min(a.lef, u->lef);
    a.rig = max(a.rig, u->rig);
    remove_rng(*u);
    rng.erase(u);
  }
  rng.insert(a);
}
int seg2[(200013 + 5) * 4];
int lb;
inline void add(int b, int l, int r, int ll, int x) {
  if (l <= ll && ll < r) {
    if (l + 1 == r) {
      seg2[b] = x;
      return;
    }
    add(b * 2 + 1, l, (l + r) >> 1, ll, x);
    add(b * 2 + 2, (l + r) >> 1, r, ll, x);
    seg2[b] = min(seg2[b * 2 + 1], seg2[b * 2 + 2]);
  }
}
inline int query(int b, int l, int r, int x) {
  if (l + 1 == r) {
    if (seg2[b] < x) {
      lb = seg2[b];
      return l;
    }
    return -1;
  }
  if (seg2[b] >= x) {
    return -1;
  }
  int u = query(b * 2 + 1, l, (l + r) >> 1, x);
  if (u != -1) return u;
  return query(b * 2 + 2, (l + r) >> 1, r, x);
}
int mex(int pos) { return query(0, 0, 200013 + 4, pos); }
void add_val(int val) {
  auto z = rng.upper_bound({val, -1, 0, 0});
  int pos = 0;
  if (rng.size() == 0) {
    pos = 0;
  } else {
    if (z != rng.begin()) {
      pos = (*prev(z)).lef - 1;
    } else {
      pos = ar.size();
    }
  }
  while (z != rng.end() && z->val == val) {
    auto t = next(z);
    remove_rng(*z);
    rng.erase(z);
    z = t;
  }
  add(0, 0, 200013 + 4, val, ar.size());
  ar.push_back(val);
  int want = 1;
  int until = 0;
  if (z != rng.end()) {
    until = (*z).rig + 1;
  }
  if (true) {
    if (val == 0) {
      ins({1, (int)ar.size() - 1, (int)ar.size() - 1, CUR_TIM});
    } else {
      ins({0, (int)ar.size() - 1, (int)ar.size() - 1, CUR_TIM});
    }
    pos = min(pos, (int)ar.size() - 2);
  }
  if (pos >= until) {
    int R = pos;
    while (pos >= until) {
      want = mex(pos);
      pos = max(until - 1, lb);
      ins({want, pos + 1, R, CUR_TIM});
      R = pos;
    }
    if (pos >= until) {
      want = mex(until);
      ins({want, until, R, CUR_TIM});
    }
  }
}
long long int overlap(int l1, int r1, int l2, int r2) {
  if (r2 < l1 || r1 < l2) {
    return 0;
  }
  if (l1 <= l2 && r2 <= r1) {
    return r2 - l2 + 1;
  }
  if (l2 <= l1 && r1 <= r2) {
    return r1 - l1 + 1;
  }
  return min(r2, r1) - max(l1, l2) + 1;
}
long long int query(int k, int l, int r) {
  int zz =
      upper_bound(bit[k].tim.begin(), bit[k].tim.end(), r) - bit[k].tim.begin();
  long long int z = 0;
  if (zz > 0) {
    z = bit[k].sum(bit[k].root[zz - 1], 0, n, l, r + 1);
  }
  if (zz != bit[k].tim.size()) {
    auto u = bit[k].ad[zz];
    z += overlap(l, r, u.second.first, u.second.second) *
         overlap(l, r, u.first.first, u.first.second);
  }
  auto f = rng.upper_bound({k, -1, 0, 0});
  while (f != rng.end() && f->val == k) {
    z += overlap(l, r, f->lef, f->rig) * overlap(l, r, f->tim, ar.size() - 1);
    f++;
  }
  return z;
}
int main() {
  memset(seg2, -1, sizeof(seg2));
  cin >> n;
  long long int lans = 0;
  for (int i = 1; i <= n; i++) {
    int a, l, r, k;
    scanf("%d%d%d%d", &a, &l, &r, &k);
    a = (a + lans) % (n + 1);
    l = (l + lans) % i;
    r = (r + lans) % i;
    if (l > r) swap(l, r);
    k = (k + lans) % (n + 1);
    if (a >= 200013) {
      add_val(200013);
    } else {
      add_val(a);
    }
    lans = 0;
    if (k >= 200013) {
      puts("0");
    } else {
      lans = query(k, l, r);
      printf("%lld\n", lans);
    }
    CUR_TIM++;
  }
  return 0;
}

```