NurlashKO 去年表现良好，因此 Ded Moroz 在新年送给他一条包含 $N$ 个顶点的折线。该折线的第 $i$ 个顶点位于坐标 $(i, y_i)$ 处。 很快，人们又发明了一种关于这个几何图形的新游戏：执行 $M$ 次以下操作：

• 修改折线中某个顶点的 $y$ 坐标。
• 画一条高度为 $H$ 的水平线，并计算它与折线的交点个数。注意，水平线上所有点的 $y$ 坐标均等于 $H$。

NurlashKO 很喜欢这个游戏，他请求你帮忙编写一个程序来处理这些操作。

输入格式

输入的第一行包含两个正整数 $N, M(1 \le N, M \le 100\,000)$，分别表示折线的顶点数和操作次数。 第二行包含 $N$ 个正整数，由空格分隔，表示 $h_i(1 \le h_i \le 1\,000\,000)$，其中 $h_i$ 是第 $i$ 个顶点的初始高度。 接下来的 $M$ 行描述了游戏操作，格式如下：

• 1 pos val $(1 \le pos \le N, 1 \le val \le 1\,000\,000)$ —— 分别表示顶点编号及其新的高度。
• 2 H $(1 \le H \le 1\,000\,000)$ —— 水平线的高度。保证该水平线永远不会与折线的顶点相交。

输出格式

对于每个第二类查询，在单独的一行中输出水平线与折线的交点个数。按输入文件中查询出现的顺序输出答案。

子任务

本题包含 3 个子任务：

1. $1 \le N, M \le 1\,000$。分值为 22 分。
2. $1 \le N, M \le 100\,000$。仅包含第二类查询操作。分值为 27 分。
3. $1 \le N, M \le 100\,000$。分值为 51 分。

仅当解决方案成功通过所有前置子任务时，该子任务才会得分。

样例

输入 1

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

输出 1

2
1