Рассмотрим следующую игру для двух игроков:
Дан массив \(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\) включительно. Считается, что оба игрока играют оптимально.
Выходные данные
Для каждого запроса типа \(2\) выведите \(1\), если первый игрок выигрывает в соответствующей игре, или \(2\), если выигрывает второй игрок.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2 4
1 2 3 4 5
1 3 5 6
2 2 5
1 1 2 3
2 1 5
|
1
1
|
|
2
|
5 1 3
1 1 3 3 4
2 1 5
2 2 5
2 3 5
|
1
2
1
|