msc是个喜欢玩游戏的小女孩。
一天msc遇到了mas，msc取出了一个长度为n的序列a，并决定和mas一起玩游戏。
这个游戏是这样的：
1、一开始有一个给定的参数k.
2、mas选择一个区间[l,r]，取出序列a的a[l..r]这一段，记为序列A，长度为m=r-l+1
3、msc开始操作，她会选择序列A中的连续k个数，然后将这k 个数同时加上一个实数x（更具体的，msc会选择一个i满足，然后选择一个实数，将A[i..i+k-1]这些数都加上x），msc会重复这一步若干次，直到A中的数都变成0（这个时候msc就赢了），当然如果无论msc如何操作，A都不可能变成全为0的序列，那么msc就输了。
mas希望msc可以开开心心的，所以mas希望msc赢。
但是他发现msc给出的序列中大部分的区间[l,r]，msc都是会输掉游戏的，所以mas想知道，如果选出的区间是[l,r]，那么自己至少需要修改多少个位置上的数字才能够使msc胜利。（**注意：这只是“如果”，这里的修改并不会真正改变a中的值，就是说不会对后面的询问或修改产生影响**）
当然，由于游戏不够刺激，mas会在某些时候修改某个a_i
mas正忙于讨好msc，所以希望你能帮他求出答案

第一行三个整数n,k和q，表示序列a的长度，给定的参数k，以及mas给出的询问+操作数。
第二行n个整数ai，表示序列a
接下来q行，每行第一个数ty。
如果ty=1，那么接下来同一行有两个整数l,r，表示一次询问，如果选出的区间是[l,r]，那么mas至少需要修改多少个位置上的数字才能够使msc胜利。
如果ty=2，那么接下来同一行有两个整数x,v，表示一次修改，将ax修改为v
注意，询问不会对a产生影响。

对于每次询问输出一行表示答案。

8 3 5
4 -1 -3 -3 1 -4 -1 1
1 1 8
2 4 0
1 4 5
1 2 7
1 2 5

2
1
2
1

对于第一次询问l=1,r=8,那么A={4,-1,-3,-3,1,-4,-1,1}，mas将A[3]修改成4，A[5]修改成0，得到A'={4,-1,4,-3,0,-4,-1,1}，然后可以通过给[3,5]加上-5，[4,6]加上3，[2,4]加上5，[5,7]加上2，[1,3]加上-4，[6,8]加上-1，使得A'变成全为0的序列。

n,q≤ 105,1≤ k≤ 20,1≤ l≤ r≤ n,|ai|≤ 104,|v|≤ 1012,ty∈{1,2}