Wookje 正在玩《英雄联盟》游戏，游戏中两支玩家队伍相互对抗。每个玩家控制一个英雄，其状态可以用两个整数表示：当前生命值 $h$ 和最大生命值 $H$。如果英雄的生命值小于或等于零（$h \le 0$），该英雄死亡并立即离开游戏，此时 $h = 0$。如果英雄的生命值超过了最大生命值（$h > H$），则其生命值会被调整为最大生命值 $H$。$H$ 始终是一个正整数。

在团战中，英雄的生命值可能会增加或减少。具体来说，在一次团战中，英雄会受到 $n$ 次操作的影响。第 $i$（$1 \le i \le n$）次操作会使英雄的生命值增加 $a_i$（同样遵循上述规则）。如果 $a_i$ 为正数，表示英雄获得了治疗；如果 $a_i$ 为负数，表示英雄受到了攻击；如果 $a_i$ 为零，则英雄没有发生任何变化。

Wookje 在《英雄联盟》中最喜欢的英雄是永猎双子——千珏（Kindred）。千珏拥有一个名为“羊灵生息”（Lamb's Respite）的终极技能。让我们来看看这个技能的效果。

正式地，考虑一个最大生命值为 $H$ 的英雄。如果 Wookje 在第 $l$ 次操作即将开始前，到第 $r$ 次操作刚刚结束后激活了“羊灵生息”，那么在这些操作期间，英雄的生命值永远不会降至 $\lceil H / 10 \rceil$ 以下。如果在第 $l$ 次操作即将开始前，英雄的生命值已经小于或等于 $\lceil H / 10 \rceil$；或者对于某个 $l \le i \le r$，在第 $i$ 次操作之后，英雄的生命值在假设情况下会小于或等于 $\lceil H / 10 \rceil$，那么它的生命值将被设定为 $\lceil H / 10 \rceil$，并且在第 $r$ 次操作结束之前不会再发生任何改变。否则，“羊灵生息”不会对英雄生命值的变化产生任何影响。

在何时激活“羊灵生息”是一个非常重要的决策。Wookje 想要提高自己的决策水平。然而，团战过于复杂，他很难知道何时应该激活“羊灵生息”。为了帮助他，请处理以下 $q$ 个查询：

• 1 l r x：英雄的最大生命值为 $x$，且初始生命值为 $x$。“羊灵生息”在第 $l$ 次操作即将开始前到第 $r$ 次操作刚刚结束后处于激活状态。输出在全部 $n$ 次操作后英雄的生命值。如果英雄死亡，输出 0。（$1 \le l \le r \le n$，$1 \le x \le 10^9$）。
• 2 i x：将 $a_i$ 修改为 $x$。（$1 \le i \le n$，$-10^9 \le x \le 10^9$）。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 300\,000$）。

第二行包含 $n$ 个整数。第 $i$ 个整数为 $a_i$（$|a_i| \le 10^9$）。

接下来的 $q$ 行，每行包含若干个整数，表示上述格式的查询。

输入中至少包含一个类型为 1 的查询。

输出格式

对于每个类型为 1 的查询，输出一个整数表示该查询的答案。每个答案占一行。

样例

输入样例 1

4 10
0 1 1 -1
1 2 4 2
2 2 -1
1 2 4 2
1 2 3 2
2 1 -1
1 1 4 2
1 2 4 2
2 1 -2
1 1 4 2
1 2 4 2

输出样例 1

1
1
0
1
1
1
0

输入样例 2

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

输出样例 2

3
0
0
1