题目背景

他们让小时候的我 去寻找飞花漫天

想不到消失的那座 山和念已成云烟

我永远被困在燃烧的诗篇

无路可逃，轮回无道

——MOCKER44.《花草野》

题目描述

“诸事顺遂　似有天助　一子既落　已在局中”

小 K 被困在了“诗篇”之中，只能通过以下方式逃离。

“诗篇”是一个轮回，共有 $n$ 个区域，每个区域有属性 $a_i$。它们首尾相接形成了一个环，即 $\forall i\in[0,n-1]$，区域 $i$ 的下一个区域为区域 $(i+1)\bmod n$。

小 K 需要按顺序经过环上区域，当然也可能绕环走很多圈。通过区域 $i$ 的过程中，他共能获得 $p\times a_i$ 的经验值，其中 $p$ 表示此前经过的区域（包括自身）中 $a_i$ 的最大值。

只有收集到第 $X$ 点经验值的瞬间可以逃出轮回，小 K 请你帮他计算当 $X=z$，且从区域 $i$ 的起点开始走时，他将从哪个区域逃离。

注意若经过区域 $i$ 后恰好收集到了 $X$ 点经验值，会被认为是从区域 $(i+1)\bmod n$ 的起点逃离的。更具体地说，一定存在唯一的 $i$ 使得某次进入区域 $i$ 前经验值不大于 $X$，且当次经过之后经验值大于 $X$，该编号 $i$ 即为答案。

然而这还是太简单了，“诗篇”也不是永恒不变的，有时会有一段区间 $[l,r]$ 的属性被加上 $x$ 或被赋值为 $y$。在修改过程中小 K 会多次询问，请你依次给出答案。注意可能存在 $l>r$ 的操作区间，这在环上是合法的，可以认为操作的是 $[l,n-1]$ 和 $[0,r]$ 两个区间。

输入格式

第一行两个整数 $n,q$，表示区域个数和操作个数。

接下来 $n$ 个整数 $a_i$，表示每个区域的初始属性。

接下来 $q$ 行，每行输入以下三个操作之一：

• 字母 P，整数 $l,r,x$：给该区间内的 $a_i$ 加上 $x$。
• 字母 R，整数 $l,r,y$：将该区间内的 $a_i$ 赋值为 $y$。
• 字母 Q，整数 $i,z$：询问从区域 $i$ 起点出发且 $X=z$ 时逃离的区域编号。

输出格式

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

输入输出样例 #1

输入 #1

2 4
1 2
Q 0 0
Q 0 1
Q 0 4
Q 0 5

输出 #1

0
1
1
0

输入输出样例 #2

输入 #2

5 7
2 5 1 4 3
Q 3 28
Q 0 39
P 4 0 3
Q 2 60
R 4 1 2
Q 1 22
Q 3 19260817

输出 #2

0
3
0
4
1

输入输出样例 #3

输入 #3

6 6
879 879 879 879 879 879
P 0 5 69
Q 2 87984009
Q 5 98459810
R 0 5 317
P 0 5 46
Q 2 58708233

输出 #3

3
0
3

说明/提示

对于所有数据，$2\le n,q\le 2\times 10^5,1\le a_i,y\le 10^6,0\le x\le 10^3,0\le i,l,r\le n-1,0\le z\le 2\times 10^{17}$，保证 $a_i$ 任意时刻不超过 $10^6$。

\begin{array}{|c|c|} \hline \textbf{测试点编号} & \textbf{特殊性质} \\ \hline 1,2 & n,q\le 2\times 10^3 \\ \hline 3 & \forall i\in[1,n-1],a_i=a_{i-1} \textbf{且 }l=0,r=n-1 \\ \hline 4,5 & \textbf{不存在 }P \textbf{ 操作}\\ \hline 6,7 & \textbf{不存在 }R \textbf{ 操作}\\ \hline 8,9,10 & \textbf{最难做} \\ \hline \end{array}