K. Xor and segments
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив a1, a2, ..., an, каждое ai равняется 0 или 1. Напишите программу, которая умеет выполнять две операции:

  1. по заданным числам l и r (1 ≤ l ≤ r ≤ n) меняет каждое из чисел al, al + 1, ..., ar на противоположное (0 на 1, 1 на 0);
  2. для заданных чисел l и r, (1 ≤ l ≤ r ≤ n) рассматривает все подотрезки массива длиной от l до r, вычисляет для каждого из них сумму чисел на этом подотрезке, возвращает остаток от деления этой суммы по всем подходящим подотрезкам на 2. Формально, вычисляется величина:
    .
Входные данные

В первой строке записаны числа n и q (1 ≤ n, q ≤ 250 000).

Во второй строке записаны n чисел a1, a2, ..., an, каждое из этих чисел равно 0 или 1.

В следующих q строках расположены параметры запросов. В i-й из этих строк записаны параметры i-го запроса — числа ti, li и ri, где ti равно 1 для запроса первого типа (замена чисел в массиве) и 2 для запроса второго типа (нахождение суммы), а li и ri, 1 ≤ li ≤ ri ≤ n есть параметры соответствующего запроса.

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

Для каждого запроса второго типа выведите в отдельной строке единственное число — ответ на соответствующий запрос.

Пример
Входные данные
5 10
0 0 0 0 0
1 2 4
2 2 2
2 1 1
2 1 2
2 2 3
1 3 5
2 2 2
2 3 3
2 2 4
2 1 5
Выходные данные
0
1
1
1
1
1
1
1