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