F. Соня и побитовое ИЛИ
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Сони есть массив $$$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$$$.

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$x$$$ ($$$1\leq n, m\leq 10^5$$$, $$$0\leq x<2^{20}$$$) — количество чисел, запросов и константа для второго типа запросов соответственно.

Вторая стркоа содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i<2^{20}$$$) — числа массива.

Далее, в $$$m$$$ строках заданы запросы, по одному в строке. Строка имеет вид:

  • $$$1$$$ $$$i$$$ $$$y$$$ ($$$1\leq i\leq n$$$, $$$0\leq y<2^{20}$$$), что означает, что нужно изменить число $$$a_{i}$$$ на $$$y$$$, или
  • $$$2$$$ $$$l$$$ $$$r$$$ ($$$1\leq l\leq r\leq n$$$), что означет, что нужно посчитать количество подмассивов на отрезке с $$$l$$$ по $$$r$$$, что побитовое ИЛИ их чисел не меньше $$$x$$$.
Выходные данные

Для каждого запроса второго типа выведите количество подмассивов на отрезке, что побитовое ИЛИ их чисел не меньше $$$x$$$.

Примеры
Входные данные
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
Входные данные
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
Примечание

В первом примере задан массив [$$$0$$$, $$$3$$$, $$$6$$$, $$$1$$$] и запросы:

  1. на отрезке [$$$1\ldots4$$$] подходят пары ($$$1$$$, $$$3$$$), ($$$1$$$, $$$4$$$), ($$$2$$$, $$$3$$$), ($$$2$$$, $$$4$$$) и ($$$3$$$, $$$4$$$);
  2. на отрезке [$$$3\ldots4$$$] подходит пара ($$$3$$$, $$$4$$$);
  3. число на первой позиции изменяется на $$$7$$$, после операции будет массив [$$$7$$$, $$$3$$$, $$$6$$$, $$$1$$$];
  4. на отрезке [$$$1\ldots4$$$] подходят пары ($$$1$$$, $$$1$$$), ($$$1$$$, $$$2$$$), ($$$1$$$, $$$3$$$), ($$$1$$$, $$$4$$$), ($$$2$$$, $$$3$$$), ($$$2$$$, $$$4$$$) и ($$$3$$$, $$$4$$$);
  5. на отрезке [$$$1\ldots3$$$] подходят пары ($$$1$$$, $$$1$$$), ($$$1$$$, $$$2$$$), ($$$1$$$, $$$3$$$) и ($$$2$$$, $$$3$$$);
  6. на отрезке [$$$1\ldots1$$$] подходит пара ($$$1$$$, $$$1$$$);
  7. число на третьей позиции изменяется на $$$0$$$, после операции будет массив [$$$7$$$, $$$3$$$, $$$0$$$, $$$1$$$];
  8. на отрезке [$$$1\ldots4$$$] подходят пары ($$$1$$$, $$$1$$$), ($$$1$$$, $$$2$$$), ($$$1$$$, $$$3$$$) и ($$$1$$$, $$$4$$$).

Во втором примере задан массив [$$$6$$$, $$$0$$$, $$$3$$$, $$$15$$$, $$$2$$$] и запросы:

  1. на отрезке [$$$1\ldots5$$$] подходят пары ($$$1$$$, $$$3$$$), ($$$1$$$, $$$4$$$), ($$$1$$$, $$$5$$$), ($$$2$$$, $$$4$$$), ($$$2$$$, $$$5$$$), ($$$3$$$, $$$4$$$), ($$$3$$$, $$$5$$$), ($$$4$$$, $$$4$$$) и ($$$4$$$, $$$5$$$);
  2. число на четвертой позиции изменяется на $$$4$$$, после операции будет массив [$$$6$$$, $$$0$$$, $$$3$$$, $$$4$$$, $$$2$$$];
  3. на отрезке [$$$1\ldots5$$$] подходят пары ($$$1$$$, $$$3$$$), ($$$1$$$, $$$4$$$), ($$$1$$$, $$$5$$$), ($$$2$$$, $$$4$$$), ($$$2$$$, $$$5$$$), ($$$3$$$, $$$4$$$) и ($$$3$$$, $$$5$$$);
  4. на отрезке [$$$3\ldots5$$$] подходят пары ($$$3$$$, $$$4$$$) и ($$$3$$$, $$$5$$$);
  5. на отрезке [$$$1\ldots4$$$] подходят пары ($$$1$$$, $$$3$$$), ($$$1$$$, $$$4$$$), ($$$2$$$, $$$4$$$) и ($$$3$$$, $$$4$$$).