题目描述

阿兔已经连续五年坚持在山坡上种树。他不仅为家乡增添了满山青绿，还代表学校参加过 International College Planting Competition（国际大学生种树竞赛）。如今，在技能节竞赛上，他又准备了一道与“种树”相关的题目。

题目是这样的，在一条长长的山坡上有 $n$ 个位置，依次编号为 $1,2,\dots,n$。位置 $i$ 的高度为 $h_i$。 初始时，所有位置上都没有树。接下来有 $q$ 次操作，分为以下三种类型：

1. 往高处种树 1 x k 在所有满足 $h_i > x$ 的位置 $i$ 上，各种植 $k$ 棵树。

2. 往低处种树 2 x k 在所有满足 $h_i \le x$ 的位置 $i$ 上，各种植 $k$ 棵树。

3. 查询 3 p 输出位置 $p$ 上目前共有多少棵树。

题目要求在规定时间内完成，你解决阿兔的问题吗？

输入格式

第一行包含两个整数 $n,q$ $(1 \le n,q \le 10^5)$。

第二行包含 $n$ 个整数 $h_1,h_2,\dots,h_n$ $(|h_i| \le 10^9)$。

接下来 $q$ 行，每行表示一次操作，格式如上 $(1 \le p \le n, |x|\le 10^9, 1\le k \le 10^9)$。

输出格式

对于每个查询操作，输出一个整数表示答案。

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

0
1
5