Description

Alice和Bob在玩取石子游戏，游戏规则是这样的：游戏开始时在他们面前有若干堆石子，Alice先手进行游戏，两人轮流操作，玩家每轮操作时可以选取一堆石子，并从中至少取走 1 颗石子，可以把这堆石子取空，如果某轮中某位玩家无法进行任何操作（即所有石子均被取完了），则她或他输掉游戏，另一方赢得游戏。 Alice和Bob两人都十分聪明，并且他们知道彼此均会以最优策略进行操作，所以他们可以在游戏开始前就预知游戏的赢家是谁。 Charlie为Alice和Bob准备了一项任务：在Alice和Bob面前有 n 堆石子，编号为 1∼n，初始时第 i 堆中有 a_i 个石子。 Charlie会依次执行 q 次操作，每次操作是以下两类之一： 格式为 1 l r x：对于编号在 l∼r 之间的石子堆 i，如果不足 x 颗石子，把它补充到 x 颗，否则不做变化。 格式为 2 l r x：询问Alice和Bob如果此时只保留编号在 l∼r 之间的石子堆，再加入一堆新的含有 x 个石子的石子堆，然后进行游戏，那么Alice在进行第一轮操作时有几种操作方案可以保证她的胜利，两种操作方案不同当且仅当选取了编号不同的石子堆，或选取了相同编号的石子堆但是取走了不同数量的石子。 注意在第2类操作中，Alice和Bob并不会真的进行游戏，所以也不会对石子堆有任何改变。 Alice和Bob虽然回答了询问，但是Charlie不相信他们的答案。请你编写程序计算每次游戏时Alice在第一轮中的可行操作数。

Format

Input

第一行，两个正整数 n,q。 第二行，n 个整数 a_1,a_2,…,a_n。 接下来 q 行，每行四个整数 t,l,r,x，表示一次操作。

Output

对于每次第2类操作，输出一行，一个整数，表示Alice在第一轮中的可行操作数。

Samples

5 4
1 2 1 4 1
2 1 3 1
1 2 4 3
2 2 4 4
2 1 4 4

1
0
3

【样例解释】 第一次操作中，进行了石子个数分别为 [1,2,1,1] 的游戏，Alice的唯一操作方案是在石子数量为 2 的石子堆中取走 1 颗石子。 第二次操作中，5 个石子堆的石子个数变为 [1,3,3,4,1]。 第三次操作中，进行了石子个数分别为 [3,3,4,4] 的游戏，Alice无论进行什么操作都会最终输掉游戏。 第四次操作中，进行了石子个数分别为 [1,3,3,4,4] 的游戏，Alice可以在石子数量为 1 的石子堆中取走 1 颗石子，或者在两堆石子数量为 3 的石子堆中任选其中一堆取走 1 颗石子。

【数据范围】 对于 20% 的数据，n,q≤3000。

对于另外 10% 的数据，不存在第1类操作。

对于另外 10% 的数据，第1类操作总是比第2类操作先执行 。 对于另外 10% 的数据，第1类操作中的 l=1 且 r=n。

对于另外 15% 的数据，a_i,x≤1。

对于 100% 的数据，1≤n,q≤2×〖10〗^5，t∈{1,2}，1≤l≤r≤n，0≤a_i,x<2^30，最后一次执行的是第2类操作。