题目背景

传说上古时期，发生了一场极其惨烈的战争，有一方决定建立了许多魔法炮，这些魔法炮威力比人类的氢弹还要大

题目描述

这些魔法炮被放置在一条长为\(n\)的河岸上，从\(1\)到\(n\)每个位置上都有一个炮塔，第\(i\)个炮塔的位置为\(i\)，且炮塔不会移动，初始时每个炮塔上都只有一门炮，每门炮都有一个威力值，炮之间可能会发生冲突。设两门炮之间的"冲突程度"为这两门炮的位置之差与威力值之差的和。炮塔上可能会新增一些炮，且炮不会消失，及炮塔上可能有很多门炮。

现在，另一方的首领想随时知道：对于某个炮塔上的主炮（主炮是指该炮塔上最迟添加的一门炮，没添加则是初始的那门炮），有多少门炮（是炮不是炮塔！！）与其的冲突程度\( \le k\)（包括该门炮和同一炮塔上的炮）

有时炮塔上会新增一门炮，当然这也会告诉你

输入输出格式

输入格式：

第一行输入两个数\(n\)，\(q\)，及炮塔数和操作数

第二行输入\(n\)个数，为初始时炮塔上的炮的威力值

第3~2+q行，两种操作：
1. Q x k:询问有多少门炮与第\(x\)个炮塔上的主炮的冲突程度\( \le k\)
2. A x k:在第\(x\)个炮塔上新增一门威力值为\(k\)的炮

输出格式：

对于每次询问，输出一个非负整数表示答案

Sample 1

Input

3 5
2 4 3
Q 2 2
A 1 3
Q 2 2
A 1 2
Q 1 1

Output

2
3
3

时空限制

1~2s, 256000KiB for each test case.

说明

• \(n \le 60000\)
• 修改操作数\( \le 40000\)
• 询问数\( \le 50000\)
• 过程中炮的威力值\(\le 100000\)