CF1076G.Array Game

Consider a following game between two players:

There is an array $b_1$, $b_2$, ..., $b_k$, consisting of positive integers. Initially a chip is placed into the first cell of the array, and $b_1$ is decreased by $1$. Players move in turns. Each turn the current player has to do the following: if the index of the cell where the chip is currently placed is $x$, then he or she has to choose an index $y \in [x, min(k, x + m)]$ such that $b_y \gt 0$, move the chip to the cell $y$ and decrease $b_y$ by $1$. If it's impossible to make a valid move, the current player loses the game.

Your task is the following: you are given an array $a$ consisting of $n$ positive integers, and $q$ queries to it. There are two types of queries:

• $1$ $l$ $r$ $d$ — for every $i \in [l, r]$ increase $a_i$ by $d$;
• $2$ $l$ $r$ — tell who is the winner of the game that is played on the subarray of $a$ from index $l$ to index $r$ inclusive. Assume both players choose an optimal strategy.

考虑以下两个玩家之间的游戏：

给定一个由正整数构成的数组 $b_1$, $b_2$, ..., $b_k$。初始时，一枚棋子被放置在该数组的第一个单元格（即索引为 $1$ 的位置），且 $b_1$ 的值减 $1$。两名玩家轮流进行操作。在每一轮中，当前玩家必须执行以下操作：若棋子当前位于索引为 $x$ 的单元格，则他/她必须选择一个索引 $y \in [x, \min(k, x + m)]$，使得 $b_y > 0$，然后将棋子移动至单元格 $y$，并将 $b_y$ 的值减 $1$。若无法进行任何合法移动，则当前玩家输掉游戏。

你的任务如下：你将得到一个由 $n$ 个正整数组成的数组 $a$，以及对该数组的 $q$ 个查询。查询分为两类：

• $1$ $l$ $r$ $d$ — 对每个 $i \in [l, r]$，将 $a_i$ 增加 $d$；
• $2$ $l$ $r$ — 判断在数组 $a$ 的子数组 $a_l, a_{l+1}, \dots, a_r$ 上进行上述游戏时，哪位玩家获胜（假设双方均采用最优策略）。

The first line contains three integers $n$, $m$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$, $1 \le m \le 5$) — the number of elements in $a$, the parameter described in the game and the number of queries, respectively.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^{12}$) — the elements of array $a$.

Then $q$ lines follow, each containing a query. There are two types of queries. The query of the first type is denoted by a line $1$ $l$ $r$ $d$ ($1 \le l \le r \le n$, $1 \le d \le 10^{12}$) and means that for every $i \in [l, r]$ you should increase $a_i$ by $d$. The query of the second type is denoted by a line $2$ $l$ $r$ ($1 \le l \le r \le n$) and means that you have to determine who will win the game if it is played on the subarray of $a$ from index $l$ to index $r$ (inclusive).

There is at least one query of type $2$.

第一行包含三个整数 $n$、$m$ 和 $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$ 的子数组 $a[l..r]$（下标从 $l$ 到 $r$，含端点）上进行游戏，谁将获胜。

至少存在一个类型为 $2$ 的查询。

For each query of type $2$ print $1$ if the first player wins in the corresponding game, or $2$ if the second player wins.

对于每个类型为 $2$ 的查询，如果在对应游戏中先手玩家获胜，则输出 $1$；如果后手玩家获胜，则输出 $2$。