Вам дан массив, изначально он пустой. Вам нужно выполнить \(n\) операций следующего вида:
- «\(a\) \(l\) \(r\) \(k\)»: дописать \(a\) в конец текущего массива, а затем подсчитать число пар целых чисел \(x, y\) таких, что \(l \leq x \leq y \leq r\) и \(\operatorname{mex}(a_{x}, a_{x+1}, \ldots, a_{y}) = k\).
Элементы массива пронумерованы с \(1\) в том порядке, в котором они добавляются в массив.
Чтобы сделать эту задачу более идейной, мы не будем сообщать вам реальные параметры запросов. Вместо этого вам будут даны целые числа \(a'\), \(l'\), \(r'\), \(k'\). Чтобы получить \(a\), \(l\), \(r\), \(k\) на \(i\)-й операции, вам нужно выполнить следующие действия:
- \(a := (a' + lans) \bmod(n + 1)\),
- \(l := (l' + lans) \bmod{i} + 1\),
- \(r := (r' + lans) \bmod{i} + 1\),
- если \(l > r\), то поменять местами \(l\) и \(r\),
- \(k := (k' + lans) \bmod(n + 1)\),
где
\(lans\) — ответ на предыдущую операцию, изначально
\(lans\) равен нулю.
\(i\) — номер операции, операции нумеруются с
\(1\).
\(\operatorname{mex}(S)\), где \(S\) это мультимножество целых неотрицательных чисел, есть наименьшее неотрицательное целое число, не входящее в это множество. Например, \(\operatorname{mex}(\{2, 2, 3\}) = 0\), а \(\operatorname{mex} (\{0, 1, 4, 1, 6\}) = 2\).
Примечание
Для первого теста из условия расшифрованные значения \(a\), \(l\), \(r\), \(k\) следующие:
\(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\)
Для второго теста из условия расшифрованные значения \(a\), \(l\), \(r\), \(k\) следующие:
\(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\)