#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXQ = 200000;
const int MAXK = MAXQ;
const int MAXS = 4 * (MAXK + 1);
struct Seg {
  int lx, hx, ly, hy;
  long long psum;
  Seg() {}
  Seg(int lx, int hx, int ly, int hy, long long psum)
      : lx(lx), hx(hx), ly(ly), hy(hy), psum(psum) {}
};
int nq;
int qval[MAXQ], ql[MAXQ], qr[MAXQ], qk[MAXQ];
long long qans[MAXQ];
int sval[MAXS];
void sinit(int x, int l, int r) {
  if (l == r) {
    sval[x] = -1;
  } else {
    int m = l + (r - l) / 2;
    sinit(2 * x + 1, l, m);
    sinit(2 * x + 2, m + 1, r);
    sval[x] = min(sval[2 * x + 1], sval[2 * x + 2]);
  }
}
void sset(int x, int l, int r, int IDX, int VAL) {
  if (l == r) {
    sval[x] = VAL;
  } else {
    int m = l + (r - l) / 2;
    if (IDX <= m)
      sset(2 * x + 1, l, m, IDX, VAL);
    else
      sset(2 * x + 2, m + 1, r, IDX, VAL);
    sval[x] = min(sval[2 * x + 1], sval[2 * x + 2]);
  }
}
int sgetlower(int x, int l, int r, int VAL) {
  assert(sval[x] < VAL);
  if (l == r) {
    return l;
  } else {
    int m = l + (r - l) / 2;
    return sval[2 * x + 1] < VAL ? sgetlower(2 * x + 1, l, m, VAL)
                                 : sgetlower(2 * x + 2, m + 1, r, VAL);
  }
}
int lst[MAXK + 1];
vector<int> arr;
vector<Seg> seg[MAXK + 1];
void addseg(int k, int lx, int hx, int ly, int hy) {
  assert(hy == INT_MAX);
  if (((int)(seg[k]).size()) == 0) {
    seg[k].push_back(Seg(lx, hx, ly, hy, 0));
    return;
  }
  Seg &lastseg = seg[k][((int)(seg[k]).size()) - 1];
  if (lastseg.hy != INT_MAX) {
    assert(ly >= lastseg.hy);
    long long nsum = lastseg.psum + (long long)(lastseg.hx - lastseg.lx) *
                                        (lastseg.hy - lastseg.ly);
    seg[k].push_back(Seg(lx, hx, ly, hy, nsum));
  } else if (lastseg.ly != ly) {
    assert(ly > lastseg.ly);
    assert(lastseg.hx == lx);
    lastseg.hy = ly;
    lx = lastseg.lx;
    long long nsum = lastseg.psum + (long long)(lastseg.hx - lastseg.lx) *
                                        (lastseg.hy - lastseg.ly);
    seg[k].push_back(Seg(lx, hx, ly, hy, nsum));
  } else {
    if (lastseg.lx == hx)
      lastseg.lx = lx;
    else if (lastseg.hx == lx)
      lastseg.hx = hx;
    else
      assert(false);
  }
}
void append(int k) {
  int t = ((int)(arr).size());
  arr.push_back(k);
  lst[k] = t;
  sset(0, 0, MAXK, k, t);
  if (((int)(seg[k]).size()) != 0 &&
      seg[k][((int)(seg[k]).size()) - 1].hy == INT_MAX) {
    Seg lastseg = seg[k][((int)(seg[k]).size()) - 1];
    seg[k][((int)(seg[k]).size()) - 1].hy = t;
    int x = lastseg.hx;
    while (x > lastseg.lx) {
      int kk = sgetlower(0, 0, MAXK, x - 1);
      int nx = max(lastseg.lx, lst[kk] + 1);
      assert(nx < x);
      addseg(kk, nx, x, t, INT_MAX);
      x = nx;
    }
  }
  addseg(k != 0 ? 0 : 1, t, t + 1, t, INT_MAX);
}
long long calcstupid(int l, int r, int k) {
  long long ret = 0;
  for (int cl = (l); cl <= (r); ++cl)
    for (int cr = (cl); cr <= (r); ++cr) {
      long long mask = 0;
      for (int i = (cl); i <= (cr); ++i) mask |= 1LL << arr[i];
      int cur = 0;
      while ((mask & (1LL << cur)) != 0) ++cur;
      if (cur == k) ++ret;
    }
  return ret;
}
long long calc(int l, int r, int k) {
  int a;
  {
    int lo = -1, hi = ((int)(seg[k]).size());
    while (lo + 1 < hi) {
      int mi = lo + (hi - lo) / 2;
      if (seg[k][mi].hx > l)
        hi = mi;
      else
        lo = mi;
    }
    a = hi;
  }
  int b;
  {
    int lo = -1, hi = ((int)(seg[k]).size());
    while (lo + 1 < hi) {
      int mi = lo + (hi - lo) / 2;
      if (seg[k][mi].lx >= l)
        hi = mi;
      else
        lo = mi;
    }
    b = hi;
  }
  int c;
  {
    int lo = -1, hi = ((int)(seg[k]).size());
    while (lo + 1 < hi) {
      int mi = lo + (hi - lo) / 2;
      if (seg[k][mi].ly > r)
        hi = mi;
      else
        lo = mi;
    }
    c = hi;
  }
  b = min(b, c);
  long long ret = 0;
  if (a < c) {
    if (c - 1 >= 0) {
      Seg s = seg[k][c - 1];
      ret += s.psum;
      ret +=
          (long long)(min(s.hy, r + 1) - max(s.ly, l)) * (s.hx - max(s.lx, l));
      b = min(b, c - 1);
    }
    if (a < ((int)(seg[k]).size())) {
      Seg s = seg[k][a];
      ret -= s.psum;
    }
    if (a < b) {
      Seg sl = seg[k][a], sr = seg[k][b - 1];
      assert(sl.lx == sr.lx);
      ret -= (long long)(sr.hy - sl.ly) * (l - sl.lx);
    }
  }
  return ret;
}
void solve() {
  arr.clear();
  for (int k = (0); k <= (MAXK); ++k) {
    lst[k] = -1;
    seg[k].clear();
  }
  sinit(0, 0, MAXK);
  long long lastans = 0;
  for (int i = (0); i < (nq); ++i) {
    int val = (qval[i] + lastans) % (nq + 1);
    int l = (ql[i] + lastans) % (i + 1);
    int r = (qr[i] + lastans) % (i + 1);
    if (l > r) swap(l, r);
    int k = (qk[i] + lastans) % (nq + 1);
    append(val);
    lastans = qans[i] = calc(l, r, k);
  }
}
void run() {
  scanf("%d", &nq);
  for (int i = (0); i < (nq); ++i)
    scanf("%d%d%d%d", &qval[i], &ql[i], &qr[i], &qk[i]);
  solve();
  for (int i = (0); i < (nq); ++i) printf("%lld\n", qans[i]);
}
void stress() {
  for (int rep = (0); rep < (10000); ++rep) {
    nq = rand() % 60 + 1;
    for (int i = (0); i < (nq); ++i)
      qval[i] = rand() % 10, ql[i] = rand() % 1000, qr[i] = rand() % 1000,
      qk[i] = rand() % 1000;
    solve();
    printf(".");
  }
}
int main() {
  run();
  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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXQ = 200000;
const int MAXK = MAXQ;
const int MAXS = 4 * (MAXK + 1);
struct Seg {
  int lx, hx, ly, hy;
  long long psum;
  Seg() {}
  Seg(int lx, int hx, int ly, int hy, long long psum)
      : lx(lx), hx(hx), ly(ly), hy(hy), psum(psum) {}
};
int nq;
int qval[MAXQ], ql[MAXQ], qr[MAXQ], qk[MAXQ];
long long qans[MAXQ];
int sval[MAXS];
void sinit(int x, int l, int r) {
  if (l == r) {
    sval[x] = -1;
  } else {
    int m = l + (r - l) / 2;
    sinit(2 * x + 1, l, m);
    sinit(2 * x + 2, m + 1, r);
    sval[x] = min(sval[2 * x + 1], sval[2 * x + 2]);
  }
}
void sset(int x, int l, int r, int IDX, int VAL) {
  if (l == r) {
    sval[x] = VAL;
  } else {
    int m = l + (r - l) / 2;
    if (IDX <= m)
      sset(2 * x + 1, l, m, IDX, VAL);
    else
      sset(2 * x + 2, m + 1, r, IDX, VAL);
    sval[x] = min(sval[2 * x + 1], sval[2 * x + 2]);
  }
}
int sgetlower(int x, int l, int r, int VAL) {
  assert(sval[x] < VAL);
  if (l == r) {
    return l;
  } else {
    int m = l + (r - l) / 2;
    return sval[2 * x + 1] < VAL ? sgetlower(2 * x + 1, l, m, VAL)
                                 : sgetlower(2 * x + 2, m + 1, r, VAL);
  }
}
int lst[MAXK + 1];
vector<int> arr;
vector<Seg> seg[MAXK + 1];
void addseg(int k, int lx, int hx, int ly, int hy) {
  assert(hy == INT_MAX);
  if (((int)(seg[k]).size()) == 0) {
    seg[k].push_back(Seg(lx, hx, ly, hy, 0));
    return;
  }
  Seg &lastseg = seg[k][((int)(seg[k]).size()) - 1];
  if (lastseg.hy != INT_MAX) {
    assert(ly >= lastseg.hy);
    long long nsum = lastseg.psum + (long long)(lastseg.hx - lastseg.lx) *
                                        (lastseg.hy - lastseg.ly);
    seg[k].push_back(Seg(lx, hx, ly, hy, nsum));
  } else if (lastseg.ly != ly) {
    assert(ly > lastseg.ly);
    assert(lastseg.hx == lx);
    lastseg.hy = ly;
    lx = lastseg.lx;
    long long nsum = lastseg.psum + (long long)(lastseg.hx - lastseg.lx) *
                                        (lastseg.hy - lastseg.ly);
    seg[k].push_back(Seg(lx, hx, ly, hy, nsum));
  } else {
    if (lastseg.lx == hx)
      lastseg.lx = lx;
    else if (lastseg.hx == lx)
      lastseg.hx = hx;
    else
      assert(false);
  }
}
void append(int k) {
  int t = ((int)(arr).size());
  arr.push_back(k);
  lst[k] = t;
  sset(0, 0, MAXK, k, t);
  if (((int)(seg[k]).size()) != 0 &&
      seg[k][((int)(seg[k]).size()) - 1].hy == INT_MAX) {
    Seg lastseg = seg[k][((int)(seg[k]).size()) - 1];
    seg[k][((int)(seg[k]).size()) - 1].hy = t;
    int x = lastseg.hx;
    while (x > lastseg.lx) {
      int kk = sgetlower(0, 0, MAXK, x - 1);
      int nx = max(lastseg.lx, lst[kk] + 1);
      assert(nx < x);
      addseg(kk, nx, x, t, INT_MAX);
      x = nx;
    }
  }
  addseg(k != 0 ? 0 : 1, t, t + 1, t, INT_MAX);
}
long long calcstupid(int l, int r, int k) {
  long long ret = 0;
  for (int cl = (l); cl <= (r); ++cl)
    for (int cr = (cl); cr <= (r); ++cr) {
      long long mask = 0;
      for (int i = (cl); i <= (cr); ++i) mask |= 1LL << arr[i];
      int cur = 0;
      while ((mask & (1LL << cur)) != 0) ++cur;
      if (cur == k) ++ret;
    }
  return ret;
}
long long calc(int l, int r, int k) {
  int a;
  {
    int lo = -1, hi = ((int)(seg[k]).size());
    while (lo + 1 < hi) {
      int mi = lo + (hi - lo) / 2;
      if (seg[k][mi].hx > l)
        hi = mi;
      else
        lo = mi;
    }
    a = hi;
  }
  int b;
  {
    int lo = -1, hi = ((int)(seg[k]).size());
    while (lo + 1 < hi) {
      int mi = lo + (hi - lo) / 2;
      if (seg[k][mi].lx >= l)
        hi = mi;
      else
        lo = mi;
    }
    b = hi;
  }
  int c;
  {
    int lo = -1, hi = ((int)(seg[k]).size());
    while (lo + 1 < hi) {
      int mi = lo + (hi - lo) / 2;
      if (seg[k][mi].ly > r)
        hi = mi;
      else
        lo = mi;
    }
    c = hi;
  }
  b = min(b, c);
  long long ret = 0;
  if (a < c) {
    if (c - 1 >= 0) {
      Seg s = seg[k][c - 1];
      ret += s.psum;
      ret +=
          (long long)(min(s.hy, r + 1) - max(s.ly, l)) * (s.hx - max(s.lx, l));
      b = min(b, c - 1);
    }
    if (a < ((int)(seg[k]).size())) {
      Seg s = seg[k][a];
      ret -= s.psum;
    }
    if (a < b) {
      Seg sl = seg[k][a], sr = seg[k][b - 1];
      assert(sl.lx == sr.lx);
      ret -= (long long)(sr.hy - sl.ly) * (l - sl.lx);
    }
  }
  return ret;
}
void solve() {
  arr.clear();
  for (int k = (0); k <= (MAXK); ++k) {
    lst[k] = -1;
    seg[k].clear();
  }
  sinit(0, 0, MAXK);
  long long lastans = 0;
  for (int i = (0); i < (nq); ++i) {
    int val = (qval[i] + lastans) % (nq + 1);
    int l = (ql[i] + lastans) % (i + 1);
    int r = (qr[i] + lastans) % (i + 1);
    if (l > r) swap(l, r);
    int k = (qk[i] + lastans) % (nq + 1);
    append(val);
    lastans = qans[i] = calc(l, r, k);
  }
}
void run() {
  scanf("%d", &nq);
  for (int i = (0); i < (nq); ++i)
    scanf("%d%d%d%d", &qval[i], &ql[i], &qr[i], &qk[i]);
  solve();
  for (int i = (0); i < (nq); ++i) printf("%lld\n", qans[i]);
}
void stress() {
  for (int rep = (0); rep < (10000); ++rep) {
    nq = rand() % 60 + 1;
    for (int i = (0); i < (nq); ++i)
      qval[i] = rand() % 10, ql[i] = rand() % 1000, qr[i] = rand() % 1000,
      qk[i] = rand() % 1000;
    solve();
    printf(".");
  }
}
int main() {
  run();
  return 0;
}

```