游戏
游戏
你在玩一个游戏。
给定一个都是正整数的序列b1,b2, ... ,bk。一开始有一个棋子放在b1，b1减少1。随后两位玩家轮流移动棋子。设当前棋子所在位置是x，每个人可以把棋子移动到y，保证by>0且x<=y<=min(k,x+M)，然后by减少1。如果无法移动棋子，当前的玩家就输了。
现在给你长度为N的正整数序列a和Q次询问，询问分两种：
1 l r d 对于所有整数i∈[l,r]，ai增加d。
2 l r 考虑如果游戏在al~ar上进行最后的胜者是谁。先手胜输出1，后手胜输出2。
Input
第一行三个整数N,M,Q。
第二行N个整数a1~an。
接下来Q行每一行四个整数1 l r d 或三个整数2 l r 。
Output
对于每个询问2一行一个整数表示答案。
Examples
| game.in | game.out |
|---|---|
| 5 2 4 | 1 |
| 1 2 3 4 5 | |
| 1 3 5 6 | |
| 2 2 5 | |
| 1 1 2 3 | |
| 2 1 5 |
样例2 game.in/out 见下发文件。
Notes
对于所有数据，1<=N,Q<=10^5 1<=ai<=10^9 1<=l<=r<=N 1<=d<=10^9 1<=M<=20
Subtask 1(20pts): 1<=N,Q<=5*10^3
Subtask 2(35pts): 没有询问1
Subtask 3(25pts): 1<=M<=5
Subtask 4(20pts): 无特殊限制