Background

Amazing John had a dream that in his previous life he was a vast, misty butterfly.

Deep ravines and hidden orchids, rain falling into the boundless haze.

Pity its broken wings, sorrow for its stubborn obsession.

Jade-like flakes weave wings, flower dew sees it off.

A lonely butterfly shatters, the orchid withers yet still has feelings.

You do not know me, yet I still miss you.

Problem Description

Amazing John likes flowers very much.

There are $n$ flowers in Amazing John's garden, and every day he takes a walk in it.

For each flower, Amazing John will judge it as beautiful or not beautiful. A flower judged as beautiful has beauty value $2$, and a flower judged as not beautiful has beauty value $1$.

We can abstract these $n$ flowers as being on a straight line. During each walk, Amazing John may start from any flower and keep moving to the next flower, and end at any flower. Along the way, he sums up the beauty values of all flowers he passes (including the starting flower and the ending flower).

Now Amazing John wants to know whether there exists a walking plan such that the sum of beauty values from the $l$-th flower to the $r$-th flower is exactly $s$.

To walk less, among all valid plans, Amazing John asks you to output the plan with the smallest $l$.

Of course, to avoid the walk being too boring, Amazing John may change the beauty value of a flower at any time.

Each query is independent. That is, flowers counted in one query can still be counted in the next query.

Input Format

The first line contains two numbers $n,m$, representing the number of flowers and the number of requests from Amazing John.

The second line contains $n$ numbers $a_i$, where $a_i$ is the beauty value of the $i$-th flower.

The next $m$ lines each describe either a query operation or a modification operation.

The query operation format is A s, asking whether there exists a walking plan such that the sum of beauty values is $s$.

The modification operation format is C i val, meaning to change the beauty value of the $i$-th flower to $val(val=1$ or $2)$.

Output Format

If there are $q$ operations of type A, the output should contain $q$ lines.

For each query, if there is a valid plan, output the left and right endpoint positions of that plan (if there are multiple plans, output the one with the smallest left endpoint). Otherwise, output none.

You should guarantee that $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)$: For testdata points $1\sim 5$, $1\leq n,m\leq 1000$.

$\operatorname{Subtask\ 2}\ (30pts)$: For testdata points $6\sim 10$, $1\leq n,m\leq 2.5\times 10^5$.

$\operatorname{Subtask\ 3}\ (50pts)$: For testdata points $11\sim 15$, $1\leq n,m\leq 2\times 10^6$.

For $100\%$ of the testdata, $1\leq n,m\leq 2\times 10^6,0\leq s\leq 2^{31}-1$. For each modification operation, $i\in[1,n],val\in\{1,2\}$.

For all testdata points, the time limit is $2000\operatorname{ms}$ and the memory limit is $256\operatorname{MB}$.

Translated by ChatGPT 5