#include <bits/stdc++.h>
using std::abs;
using std::array;
using std::cerr;
using std::cin;
using std::cout;
using std::generate;
using std::get;
using std::make_pair;
using std::make_tuple;
using std::map;
using std::max;
using std::max_element;
using std::min;
using std::min_element;
using std::pair;
using std::reverse;
using std::set;
using std::sort;
using std::string;
using std::swap;
using std::tuple;
using std::unique;
using std::vector;
template <typename T>
T input() {
  T res;
  cin >> res;
  {};
  return res;
}
template <typename IT>
void input_seq(IT b, IT e) {
  std::generate(b, e,
                input<typename std::remove_reference<decltype(*b)>::type>);
}
template <typename A, typename B>
bool cmp_first(const pair<A, B>& x, const pair<A, B>& y) {
  return x.first < y.first;
}
template <typename T>
struct object_t {
  object_t(int* cur_time, T val) {
    this->cur_time = cur_time;
    log = {{*cur_time, val}};
  };
  T get(int tm) { return get2(tm).second; }
  T get() { return get2().second; }
  pair<int, T> get2(int tm) {
    auto it = std::upper_bound(log.begin(), log.end(), make_pair(tm, T()),
                               cmp_first<int, T>);
    --it;
    return *it;
  }
  pair<int, T> get2() { return log.back(); }
  void set(T val) {
    if (log.back().first == *cur_time)
      log.back().second = val;
    else
      log.emplace_back(*cur_time, val);
  }
  int* cur_time;
  vector<pair<int, T>> log;
};
struct rmq_t {
  rmq_t(vector<int>& arr) {
    tree.resize(4 * int((arr).size()));
    n = int((arr).size());
    build(0, 0, n, arr);
  }
  void build(int v, int nl, int nr, vector<int>& arr) {
    if (nl == nr - 1)
      tree[v] = arr[nl];
    else {
      int mi = nl + (nr - nl) / 2;
      build(2 * v + 1, nl, mi, arr);
      build(2 * v + 2, mi, nr, arr);
      tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
    }
  }
  void sett(int v, int nl, int nr, int i, int x) {
    if (nr - nl == 1) {
      tree[v] = x;
    } else {
      int mi = nl + (nr - nl) / 2;
      if (i < mi)
        sett(2 * v + 1, nl, mi, i, x);
      else
        sett(2 * v + 2, mi, nr, i, x);
      tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
    }
  }
  void change(int i, int x) { sett(0, 0, n, i, x); }
  int prefix_ge_than(int val) { return go_down(0, 0, n, val); }
  int go_down(int v, int nl, int nr, int val) {
    if (nr - nl == 1) {
      if (tree[v] >= val)
        return nl;
      else
        return nl - 1;
    } else {
      int mi = nl + (nr - nl) / 2;
      if (tree[2 * v + 1] >= val)
        return go_down(2 * v + 2, mi, nr, val);
      else
        return go_down(2 * v + 1, nl, mi, val);
    }
  }
  int n;
  vector<int> tree;
};
struct node_t;
node_t* new_node_t();
node_t* copy(node_t* a);
struct node_t {
  node_t() {}
  int64_t sum = 0;
  int modif = 0;
  node_t* left = nullptr;
  node_t* right = nullptr;
  int64_t get(int nl, int nr, int l, int r) {
    if (l <= nl and nr <= r) return sum + modif * 1ll * (nr - nl);
    if (nr <= l or r <= nl) return 0;
    int64_t ans = modif * 1ll * (min(nr, r) - max(nl, l));
    int mi = nl + (nr - nl) / 2;
    if (left) ans += left->get(nl, mi, l, r);
    if (right) ans += right->get(mi, nr, l, r);
    return ans;
  }
  void op(int nl, int nr, int l, int r, int64_t delta) {
    if (nr <= l or r <= nl) return;
    if (l <= nl and nr <= r) {
      modif += delta;
      return;
    }
    if (not left)
      left = new_node_t();
    else
      left = copy(left);
    if (not right)
      right = new_node_t();
    else
      right = copy(right);
    int mi = nl + (nr - nl) / 2;
    left->op(nl, mi, l, r, delta);
    right->op(mi, nr, l, r, delta);
    sum += delta * (min(nr, r) - max(nl, l));
  }
};
node_t* new_node_t() { return new node_t(); }
node_t* copy(node_t* a) {
  node_t* nw = new node_t();
  *nw = *a;
  return nw;
}
int main() {
  std::iostream::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n = input<int>();
  vector<int> arr;
  vector<int> last(n + 5, -1);
  rmq_t rmq(last);
  int cur_time = -1;
  vector<object_t<pair<int, int>>> segms;
  for (int i = 0; i != n + 5; ++i)
    segms.push_back(object_t<pair<int, int>>(&cur_time, make_pair(-1, -2)));
  set<int> alive;
  vector<object_t<node_t*>> trees;
  for (int i = 0; i != n + 5; ++i) {
    trees.push_back(object_t<node_t*>(&cur_time, new_node_t()));
  }
  auto apply_op = [&](int k, pair<int, int> seg, int delta) {
    if (seg == make_pair(-2, -1)) return;
    node_t* tr = trees[k].get();
    node_t* nw = copy(tr);
    nw->op(0, n + 3, seg.first, seg.second + 1, delta);
    trees[k].set(nw);
  };
  auto assign = [&](int k, pair<int, int> seg) {
    auto old = segms[k].get2();
    apply_op(k, old.second, cur_time - old.first);
    segms[k].set(seg);
  };
  auto append = [&](int elem) {
    ++cur_time;
    arr.push_back(elem);
    last[elem] = int((arr).size()) - 1;
    rmq.change(elem, int((arr).size()) - 1);
    if (not alive.count(0)) {
      alive.insert(0);
      assign(0, make_pair(int((arr).size()) - 1, int((arr).size()) - 1));
    } else {
      assign(0, make_pair(segms[0].get().first, int((arr).size()) - 1));
    }
    if (not alive.count(elem)) return;
    int pos = segms[elem].get().second;
    int p2 = segms[elem].get().first;
    alive.erase(elem);
    assign(elem, make_pair(-1, -2));
    while (p2 <= pos) {
      int mex = 1 + rmq.prefix_ge_than(pos);
      int L = max(p2, last[mex] + 1);
      alive.insert(mex);
      if (segms[mex].get().second == L - 1)
        assign(mex, make_pair(segms[mex].get().first, pos));
      else
        assign(mex, make_pair(L, pos));
      pos = L - 1;
    }
  };
  auto get = [&](int l, int r, int k) {
    int64_t ans = 0;
    for (int iter = 0; iter != 2; ++iter) {
      int pos = (iter == 0 ? r : l - 1);
      int sgn = (iter == 0 ? +1 : -1);
      if (pos == -1) continue;
      node_t* nd = trees[k].get(pos);
      auto segg = segms[k].get2(pos);
      auto seg = segg.second;
      int64_t delta = nd->get(0, n + 3, l, r + 1);
      if (max(seg.first, l) <= min(seg.second, r))
        delta += (pos + 1 - segg.first) *
                 int64_t(min(seg.second, r) - max(seg.first, l) + 1);
      ans += sgn * delta;
    }
    return ans;
  };
  int64_t lans = 0;
  for (int i = 0; i != n; ++i) {
    int ap, lp, rp, kp;
    cin >> ap >> lp >> rp >> kp;
    ap = (ap + lans) % (n + 1);
    lp = (lp + lans) % (i + 1);
    rp = (rp + lans) % (i + 1);
    kp = (kp + lans) % (n + 1);
    if (lp > rp) swap(lp, rp);
    append(ap);
    lans = get(lp, rp, kp);
    cout << lans << std::endl;
  }
  return 0;
}

### Prompt

Your task is to create 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 std::abs;
using std::array;
using std::cerr;
using std::cin;
using std::cout;
using std::generate;
using std::get;
using std::make_pair;
using std::make_tuple;
using std::map;
using std::max;
using std::max_element;
using std::min;
using std::min_element;
using std::pair;
using std::reverse;
using std::set;
using std::sort;
using std::string;
using std::swap;
using std::tuple;
using std::unique;
using std::vector;
template <typename T>
T input() {
  T res;
  cin >> res;
  {};
  return res;
}
template <typename IT>
void input_seq(IT b, IT e) {
  std::generate(b, e,
                input<typename std::remove_reference<decltype(*b)>::type>);
}
template <typename A, typename B>
bool cmp_first(const pair<A, B>& x, const pair<A, B>& y) {
  return x.first < y.first;
}
template <typename T>
struct object_t {
  object_t(int* cur_time, T val) {
    this->cur_time = cur_time;
    log = {{*cur_time, val}};
  };
  T get(int tm) { return get2(tm).second; }
  T get() { return get2().second; }
  pair<int, T> get2(int tm) {
    auto it = std::upper_bound(log.begin(), log.end(), make_pair(tm, T()),
                               cmp_first<int, T>);
    --it;
    return *it;
  }
  pair<int, T> get2() { return log.back(); }
  void set(T val) {
    if (log.back().first == *cur_time)
      log.back().second = val;
    else
      log.emplace_back(*cur_time, val);
  }
  int* cur_time;
  vector<pair<int, T>> log;
};
struct rmq_t {
  rmq_t(vector<int>& arr) {
    tree.resize(4 * int((arr).size()));
    n = int((arr).size());
    build(0, 0, n, arr);
  }
  void build(int v, int nl, int nr, vector<int>& arr) {
    if (nl == nr - 1)
      tree[v] = arr[nl];
    else {
      int mi = nl + (nr - nl) / 2;
      build(2 * v + 1, nl, mi, arr);
      build(2 * v + 2, mi, nr, arr);
      tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
    }
  }
  void sett(int v, int nl, int nr, int i, int x) {
    if (nr - nl == 1) {
      tree[v] = x;
    } else {
      int mi = nl + (nr - nl) / 2;
      if (i < mi)
        sett(2 * v + 1, nl, mi, i, x);
      else
        sett(2 * v + 2, mi, nr, i, x);
      tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
    }
  }
  void change(int i, int x) { sett(0, 0, n, i, x); }
  int prefix_ge_than(int val) { return go_down(0, 0, n, val); }
  int go_down(int v, int nl, int nr, int val) {
    if (nr - nl == 1) {
      if (tree[v] >= val)
        return nl;
      else
        return nl - 1;
    } else {
      int mi = nl + (nr - nl) / 2;
      if (tree[2 * v + 1] >= val)
        return go_down(2 * v + 2, mi, nr, val);
      else
        return go_down(2 * v + 1, nl, mi, val);
    }
  }
  int n;
  vector<int> tree;
};
struct node_t;
node_t* new_node_t();
node_t* copy(node_t* a);
struct node_t {
  node_t() {}
  int64_t sum = 0;
  int modif = 0;
  node_t* left = nullptr;
  node_t* right = nullptr;
  int64_t get(int nl, int nr, int l, int r) {
    if (l <= nl and nr <= r) return sum + modif * 1ll * (nr - nl);
    if (nr <= l or r <= nl) return 0;
    int64_t ans = modif * 1ll * (min(nr, r) - max(nl, l));
    int mi = nl + (nr - nl) / 2;
    if (left) ans += left->get(nl, mi, l, r);
    if (right) ans += right->get(mi, nr, l, r);
    return ans;
  }
  void op(int nl, int nr, int l, int r, int64_t delta) {
    if (nr <= l or r <= nl) return;
    if (l <= nl and nr <= r) {
      modif += delta;
      return;
    }
    if (not left)
      left = new_node_t();
    else
      left = copy(left);
    if (not right)
      right = new_node_t();
    else
      right = copy(right);
    int mi = nl + (nr - nl) / 2;
    left->op(nl, mi, l, r, delta);
    right->op(mi, nr, l, r, delta);
    sum += delta * (min(nr, r) - max(nl, l));
  }
};
node_t* new_node_t() { return new node_t(); }
node_t* copy(node_t* a) {
  node_t* nw = new node_t();
  *nw = *a;
  return nw;
}
int main() {
  std::iostream::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n = input<int>();
  vector<int> arr;
  vector<int> last(n + 5, -1);
  rmq_t rmq(last);
  int cur_time = -1;
  vector<object_t<pair<int, int>>> segms;
  for (int i = 0; i != n + 5; ++i)
    segms.push_back(object_t<pair<int, int>>(&cur_time, make_pair(-1, -2)));
  set<int> alive;
  vector<object_t<node_t*>> trees;
  for (int i = 0; i != n + 5; ++i) {
    trees.push_back(object_t<node_t*>(&cur_time, new_node_t()));
  }
  auto apply_op = [&](int k, pair<int, int> seg, int delta) {
    if (seg == make_pair(-2, -1)) return;
    node_t* tr = trees[k].get();
    node_t* nw = copy(tr);
    nw->op(0, n + 3, seg.first, seg.second + 1, delta);
    trees[k].set(nw);
  };
  auto assign = [&](int k, pair<int, int> seg) {
    auto old = segms[k].get2();
    apply_op(k, old.second, cur_time - old.first);
    segms[k].set(seg);
  };
  auto append = [&](int elem) {
    ++cur_time;
    arr.push_back(elem);
    last[elem] = int((arr).size()) - 1;
    rmq.change(elem, int((arr).size()) - 1);
    if (not alive.count(0)) {
      alive.insert(0);
      assign(0, make_pair(int((arr).size()) - 1, int((arr).size()) - 1));
    } else {
      assign(0, make_pair(segms[0].get().first, int((arr).size()) - 1));
    }
    if (not alive.count(elem)) return;
    int pos = segms[elem].get().second;
    int p2 = segms[elem].get().first;
    alive.erase(elem);
    assign(elem, make_pair(-1, -2));
    while (p2 <= pos) {
      int mex = 1 + rmq.prefix_ge_than(pos);
      int L = max(p2, last[mex] + 1);
      alive.insert(mex);
      if (segms[mex].get().second == L - 1)
        assign(mex, make_pair(segms[mex].get().first, pos));
      else
        assign(mex, make_pair(L, pos));
      pos = L - 1;
    }
  };
  auto get = [&](int l, int r, int k) {
    int64_t ans = 0;
    for (int iter = 0; iter != 2; ++iter) {
      int pos = (iter == 0 ? r : l - 1);
      int sgn = (iter == 0 ? +1 : -1);
      if (pos == -1) continue;
      node_t* nd = trees[k].get(pos);
      auto segg = segms[k].get2(pos);
      auto seg = segg.second;
      int64_t delta = nd->get(0, n + 3, l, r + 1);
      if (max(seg.first, l) <= min(seg.second, r))
        delta += (pos + 1 - segg.first) *
                 int64_t(min(seg.second, r) - max(seg.first, l) + 1);
      ans += sgn * delta;
    }
    return ans;
  };
  int64_t lans = 0;
  for (int i = 0; i != n; ++i) {
    int ap, lp, rp, kp;
    cin >> ap >> lp >> rp >> kp;
    ap = (ap + lans) % (n + 1);
    lp = (lp + lans) % (i + 1);
    rp = (rp + lans) % (i + 1);
    kp = (kp + lans) % (n + 1);
    if (lp > rp) swap(lp, rp);
    append(ap);
    lans = get(lp, rp, kp);
    cout << lans << std::endl;
  }
  return 0;
}

```