考虑两个玩家之间的以下游戏:
有一个数组 $$$b_1$$$, $$$b_2$$$, ..., $$$b_k$$$,由正整数组成。最初,将一个筹码放入阵列的第一个单元中,$$$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$$$ — 对于 [l, r]$$$ 中的每个 $$$i \,将 $$$a_i$$$ 增加 $$$d$$$;
- $$$2$$$ $$$l$$$ $$$r$$$ — 告诉谁是在 $$$a$$$ 子数组上从索引 $$$l$$$ 到索引 $$$r$$$ 进行的游戏的获胜者。假设双方都选择最优策略。
输入
第一行包含三个整数 $$$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$$$ 的子数组上从索引 $$$l$$$ 到索引 $$$r$$$(含)之间进行游戏,则必须确定谁将赢得比赛。
至少有一个 $$$2$$$ 类型的查询。
输出
对于 $$$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 1
输入 #2
5 1 3 1 1 3 3 4 2 1 5 2 2 5 2 3 5
输出 #2
1 2 1