У Сони есть массив \(a_1, a_2, \ldots, a_n\) из \(n\) чисел и неотрицательное целое число \(x\). Ей нужно выполнить \(m\) запросов двух типов:
- \(1\) \(i\) \(y\): заменить \(i\)-й элемент на значение \(y\), то есть выполнить \(a_{i}\) := \(y\);
- \(2\) \(l\) \(r\): посчитать количество таких пар чисел (\(L\), \(R\)), что \(l\leq L\leq R\leq r\) и побитовое ИЛИ всех чисел подмассива \([L, R]\) не меньше \(x\) (обратите внимание, что \(x\) — константа для всех запросов).
Сможете ли вы помочь Соне выполнить все запросы?
Побитовое ИЛИ — это бинарная операция над парой неотрицательных целых чисел. Для подсчета побитового ИЛИ двух чисел надо рассмотреть запись обоих чисел в двоичной системе счисления. Результат — это такое число, в двоичном представлении которого в каждом разряде стоит единица если единица находится в двоичной записи хотя бы одного из аргументов. Например, \(10\) OR \(19\) = \(1010_2\) OR \(10011_2\) = \(11011_2\) = \(27\).
Выходные данные
Для каждого запроса второго типа выведите количество подмассивов на отрезке, что побитовое ИЛИ их чисел не меньше \(x\).
Примечание
В первом примере задан массив [\(0\), \(3\), \(6\), \(1\)] и запросы:
- на отрезке [\(1\ldots4\)] подходят пары (\(1\), \(3\)), (\(1\), \(4\)), (\(2\), \(3\)), (\(2\), \(4\)) и (\(3\), \(4\));
- на отрезке [\(3\ldots4\)] подходит пара (\(3\), \(4\));
- число на первой позиции изменяется на \(7\), после операции будет массив [\(7\), \(3\), \(6\), \(1\)];
- на отрезке [\(1\ldots4\)] подходят пары (\(1\), \(1\)), (\(1\), \(2\)), (\(1\), \(3\)), (\(1\), \(4\)), (\(2\), \(3\)), (\(2\), \(4\)) и (\(3\), \(4\));
- на отрезке [\(1\ldots3\)] подходят пары (\(1\), \(1\)), (\(1\), \(2\)), (\(1\), \(3\)) и (\(2\), \(3\));
- на отрезке [\(1\ldots1\)] подходит пара (\(1\), \(1\));
- число на третьей позиции изменяется на \(0\), после операции будет массив [\(7\), \(3\), \(0\), \(1\)];
- на отрезке [\(1\ldots4\)] подходят пары (\(1\), \(1\)), (\(1\), \(2\)), (\(1\), \(3\)) и (\(1\), \(4\)).
Во втором примере задан массив [\(6\), \(0\), \(3\), \(15\), \(2\)] и запросы:
- на отрезке [\(1\ldots5\)] подходят пары (\(1\), \(3\)), (\(1\), \(4\)), (\(1\), \(5\)), (\(2\), \(4\)), (\(2\), \(5\)), (\(3\), \(4\)), (\(3\), \(5\)), (\(4\), \(4\)) и (\(4\), \(5\));
- число на четвертой позиции изменяется на \(4\), после операции будет массив [\(6\), \(0\), \(3\), \(4\), \(2\)];
- на отрезке [\(1\ldots5\)] подходят пары (\(1\), \(3\)), (\(1\), \(4\)), (\(1\), \(5\)), (\(2\), \(4\)), (\(2\), \(5\)), (\(3\), \(4\)) и (\(3\), \(5\));
- на отрезке [\(3\ldots5\)] подходят пары (\(3\), \(4\)) и (\(3\), \(5\));
- на отрезке [\(1\ldots4\)] подходят пары (\(1\), \(3\)), (\(1\), \(4\)), (\(2\), \(4\)) и (\(3\), \(4\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 8 7
0 3 6 1
2 1 4
2 3 4
1 1 7
2 1 4
2 1 3
2 1 1
1 3 0
2 1 4
|
5
1
7
4
1
4
|
|
2
|
5 5 7
6 0 3 15 2
2 1 5
1 4 4
2 1 5
2 3 5
2 1 4
|
9
7
2
4
|