G. Игра на массиве
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим следующую игру для двух игроков:

Дан массив $$$b_1$$$, $$$b_2$$$, ..., $$$b_k$$$, состоящий из положительных целых чисел. В начале в первую ячейку массива помещается фишка, и $$$b_1$$$ уменьшается на $$$1$$$. Игроки по очереди делают ходы. В каждый ход текущий игрок делает следующее: если номер ячейки с фишкой равен $$$x$$$, то он или она выбирает некоторую позицию $$$y \in [x, min(k, x + m)]$$$ такую, что $$$b_y > 0$$$, двигает фишку в $$$y$$$ и уменьшает $$$b_y$$$ на $$$1$$$. Если невозможно сделать корректный ход, то текущий игрок проигрывает.

Ваша задача в следующем: дан массив $$$a$$$, состоящий из $$$n$$$ положительных целых чисел, и $$$q$$$ запросов к нему. Существуют два типа запросов:

  • $$$1$$$ $$$l$$$ $$$r$$$ $$$d$$$ — для каждого $$$i \in [l, r]$$$ увеличить $$$a_i$$$ на $$$d$$$;
  • $$$2$$$ $$$l$$$ $$$r$$$ — сказать, кто победит в игре на подмассиве $$$a$$$ с позиции $$$l$$$ до позиции $$$r$$$ включительно. Считается, что оба игрока играют оптимально.
Входные данные

В первой строке записаны три целых числа $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$, $$$1 \le m \le 5$$$) — количество элементов в $$$a$$$, параметр, описанный в игре, и количество запросов, соответственно.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) — элементы массива $$$a$$$.

Затем следуют $$$q$$$ строк, в каждой содержится один запрос. Есть два типа запросов. Запрос первого типа описывается строкой $$$1$$$ $$$l$$$ $$$r$$$ $$$d$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le d \le 10^{12}$$$) и обозначает, что для каждого $$$i \in [l, r]$$$ необходимо увеличить $$$a_i$$$ на $$$d$$$. Запрос второго типа описывается строкой $$$2$$$ $$$l$$$ $$$r$$$ ($$$1 \le l \le r \le n$$$) и обозначает, что требуется определить, кто выиграет в игре, если она будет сыграна на подмассиве $$$a$$$ с позиции $$$l$$$ до позиции $$$r$$$ (включительно).

Гарантируется, что существует хотя бы один запрос типа $$$2$$$.

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

Для каждого запроса типа $$$2$$$ выведите $$$1$$$, если первый игрок выигрывает в соответствующей игре, или $$$2$$$, если выигрывает второй игрок.

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