Description

Amazing John 很喜欢花。

Amazing John 的花圃里有 $n$ 朵花，他每天都会在花园里散步。

对于每一朵花 Amazing John 会评价它好看或不好看。被评价好看的花的美丽值为 $2$，被评价不好看的花的美丽值为 $1$。

我们可以抽象的把这 $n$ 朵花看做在一条直线上。每次散步时， Amazing John 会从任意一朵花开始，一直往下一朵花走。到任意一朵花结束。在路途中，他会将所有经过的花的美丽值统计下来。（当然包括开始的花和结束的花）

现在 Amazing John 想知道，能否有一种散步方案，使得他从第 $l$ 朵花走到第 $r$ 朵花的美丽值之和正好是 $s$？

为了少走一些路， Amazing John 要你给出在所有方案中 $l$ 最小的方案。

当然，为了避免在花圃中散步过于单调， Amazing John 随时可能会将一朵花的美丽值更改。

每个询问之间互相独立，即统计过的花朵在下次询问时仍可被统计。

Input Format

第一行两个数 $n,m$，分别表示花的个数和 Amazing John 的要求个数。

第二行 $n$ 个数字 $a_i$，表示第 $i$ 朵花的美丽值。

接下来 $m$ 行，每一行表示一个询问操作或一个修改操作。

询问操作格式为 A s，表示询问是否有一种散步方案使得美丽值之和为 $s$。

修改操作格式为 C i val，表示将第 $i$ 朵花的美丽值改成 $val(val=1$ 或 $2)$。

Output Format

若有 $q$ 个 A 操作，输出应有 $q$ 行。

对于每一个询问，若有合法的方案，输出这个方案的左右端点位置（多种方案时输出左端点最小的方案），否则输出 none。

您应该保证 $1\leq l\leq r\leq n$。

5 4
1 2 2 1 1
A 5
C 1 2
A 5
A 233

1 3
2 4
none

Hint

$\operatorname{Subtask\ 1}\ (20pts)$：对于数据点 $1\sim 5$，满足 $1\leq n,m\leq 1000$。

$\operatorname{Subtask\ 2}\ (30pts)$：对于数据点 $6\sim 10$，满足 $1\leq n,m\leq 2.5\times 10^5$。

$\operatorname{Subtask\ 3}\ (50pts)$：对于数据点 $11\sim 15$，满足 $1\leq n,m\leq 2\times 10^6$。

对于 $100\%$ 的数据，有 $1\leq n,m\leq 2\times 10^6,0\leq s\leq 2^{31}-1$。每次修改操作时 $i\in[1,n],val\in\{1,2\}$。

对于所有数据点，时间限制 $2000\operatorname{ms}$，空间限制 $256\operatorname{MB}$。