H. Holy Diver
data structures
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 \leq x \leq y \leq r\) and \(\operatorname{mex}(a_{x}, a_{x+1}, \ldots, 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) \bmod(n + 1)\), \(l := (l' + lans) \bmod{i} + 1\), \(r := (r' + lans) \bmod{i} + 1\), if \(l > r\) swap \(l\) and \(r\), \(k := (k' + lans) \bmod(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\).
The first line contains a single integer \(n\) (\(1 \leq n \leq 2 \cdot 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, \leq a', l', r', k' \leq 10^9\)), describing one operation.
For each query print a single integer — the answer to this query.
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\)