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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <class T>
inline T max1(T a, T b) {
  return b < a ? a : b;
}
template <class T>
inline T max1(T a, T b, T c) {
  return max1(max1(a, b), c);
}
template <class T>
inline T max1(T a, T b, T c, T d) {
  return max1(max1(a, b, c), d);
}
template <class T>
inline T max1(T a, T b, T c, T d, T e) {
  return max1(max1(a, b, c, d), e);
}
template <class T>
inline T min1(T a, T b) {
  return a < b ? a : b;
}
template <class T>
inline T min1(T a, T b, T c) {
  return min1(min1(a, b), c);
}
template <class T>
inline T min1(T a, T b, T c, T d) {
  return min1(min1(a, b, c), d);
}
template <class T>
inline T min1(T a, T b, T c, T d, T e) {
  return min1(min1(a, b, c, d), e);
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
int n;
const int maxn = 200100;
struct segment_node {
  int be, en;
  int minv;
};
struct segment_tree {
  int l;
  segment_node tree[200100 * 4];
  inline int gleft(int no) { return no << 1; }
  inline int gright(int no) { return (no << 1) + 1; }
  inline int gfa(int no) { return no >> 1; }
  inline segment_tree() { l = 0; }
  void build(int no, int l, int r, int orig = 0) {
    if (l > r) r = l;
    if (l == r) {
      tree[no].be = tree[no].en = l;
      tree[no].minv = orig;
      return;
    }
    tree[no].be = l;
    tree[no].en = r;
    int mid = (l + r) / 2;
    build(gleft(no), l, mid, orig);
    build(gright(no), mid + 1, r, orig);
    tree[no].minv = min(tree[gleft(no)].minv, tree[gright(no)].minv);
  }
  void upd(int loc, int no, int val) {
    if (loc <= tree[no].be && loc >= tree[no].en) {
      tree[no].minv = val;
      return;
    }
    int mid = (tree[no].be + tree[no].en) >> 1;
    if (loc <= mid)
      upd(loc, gleft(no), val);
    else
      upd(loc, gright(no), val);
    tree[no].minv = min(tree[gleft(no)].minv, tree[gright(no)].minv);
  }
  int getnxt(int l, int r, int no, int val) {
    if (l > r) return 0;
    if (l <= tree[no].be && r >= tree[no].en && tree[no].minv > val) return -1;
    if (tree[no].be == tree[no].en) return tree[no].be;
    int ans = -1;
    int mid = (tree[no].be + tree[no].en) >> 1;
    if (r >= tree[no].be && l <= mid) {
      ans = getnxt(l, r, gleft(no), val);
      if (ans != -1) return ans;
    }
    if (r >= mid + 1 && l <= tree[no].en) ans = getnxt(l, r, gright(no), val);
    return ans;
  }
} sgt1;
vector<int> mark_t[maxn];
vector<pair<int, int> > mark_range[maxn];
vector<long long> sum[maxn];
set<int> st;
int last[maxn];
int orig[maxn];
inline void UpdSum(int idx) {
  auto t2 = mark_t[idx][mark_t[idx].size() - 1],
       t1 = mark_t[idx][mark_t[idx].size() - 2];
  sum[idx].push_back(sum[idx].back());
  auto range = mark_range[idx][mark_range[idx].size() - 2];
  sum[idx][sum[idx].size() - 1] += (t2 - t1) * (range.second - range.first);
}
void Check() {
  map<pair<int, int>, int> should;
  for (int i = 0; i <= n; i++) {
    for (int j = 0, st = 0; j <= n; j++) {
      if (st < mark_t[i].size() - 1 && mark_t[i][st + 1] == j) st++;
      for (int k = mark_range[i][st].second; k > mark_range[i][st].first; k--) {
        should[make_pair(k, j)] = i;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    set<int> have;
    for (int j = i; j <= n; j++) {
      have.insert(orig[j]);
      int k = 0;
      while (have.find(k) != have.end()) k++;
      if (should[make_pair(i, j)] != k) {
        cout << i << ' ' << j << ' ' << k << endl;
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d", &n);
  long long ans = 0;
  memset(last, 0, sizeof(last));
  sgt1.build(1, 0, n + 1);
  for (int i = 0; i <= n + 1; i++) {
    mark_t[i].push_back(0);
    mark_range[i].push_back(make_pair(0, 0));
    sum[i].push_back(0);
    sgt1.upd(i, 1, 0);
    st.insert(i);
  }
  for (int i = 1; i <= n; i++) {
    int a, l, r, k;
    scanf("%d%d%d%d", &a, &l, &r, &k);
    orig[i] = a;
    a = (a + ans) % (n + 1);
    l = (l + ans) % i + 1;
    r = (r + ans) % i + 1;
    k = (k + ans) % (n + 1);
    if (l > r) swap(l, r);
    sgt1.upd(a, 1, i);
    last[a] = i;
    if (a != 0) {
      mark_range[0].push_back(mark_range[0].back());
      mark_t[0].push_back(i);
      mark_range[0][mark_range[0].size() - 1].second = i;
      UpdSum(0);
    }
    mark_t[a].push_back(i);
    mark_range[a].push_back(make_pair(i, i));
    UpdSum(a);
    auto it = st.find(a);
    if (it != st.end()) {
      auto bef = it;
      if (it != st.begin()) {
        bef--;
        st.erase(it);
        it = bef;
        it++;
      } else {
        it++;
      }
      while (bef != it) {
        int nxt = sgt1.getnxt(*bef + 1, n + 1, 1, last[*bef]);
        st.insert(nxt);
        mark_t[nxt].push_back(i);
        mark_range[nxt].push_back(
            make_pair(mark_range[nxt].back().first, last[*bef]));
        UpdSum(nxt);
        bef++;
      }
    }
    auto st = lower_bound(
                  mark_range[k].begin(), mark_range[k].end(), make_pair(-1, l),
                  [&](const pair<int, int> &a, const pair<int, int> &b) {
                    if (a.second != b.second) return a.second < b.second;
                    return a.first < b.first;
                  }) -
              mark_range[k].begin();
    auto en =
        upper_bound(mark_t[k].begin(), mark_t[k].end(), r) - mark_t[k].begin();
    auto mid = lower_bound(mark_range[k].begin(), mark_range[k].end(),
                           make_pair(l - 1, l)) -
               mark_range[k].begin();
    ans = 0;
    if (en > st) {
      en--;
      mid = min(mid, en);
      if (en > st) {
        ans = sum[k][en] - sum[k][st];
        if (mark_range[k][st].first < l - 1) {
          ans -= 1ll * (mark_t[k][mid] - mark_t[k][st]) *
                 (l - 1 - mark_range[k][st].first);
        }
      }
      ans += 1ll * (r - mark_t[k][en] + 1) *
             (mark_range[k][en].second - max(l - 1, mark_range[k][en].first));
    }
    printf("%I64d\n", ans);
  }
  return 0;
}