滞后赛车（Hysteretic Racing）通常是为了追求高速。然而，树懒们却喜欢滞后赛车。它们认为，慢一点可能更有利于展现赛车手的技巧，并且所有树懒都会以相同的速度行驶。获胜者是在整个旅程中驾驶技术最好的人。

图中展示了最贴切的形象：电影《疯狂动物城》中的树懒赛车手兼车管所职员“闪电”。不过，为了避免法律问题，我们使用了这个人工智能生成的树懒司机。

巨大的赛道由 $n$ 个土壤网格 $0, 1, \dots, n-1$ 组成，它们首尾相连形成一个圆环，其中网格 $i$ 的下一个网格是 $(i+1) \pmod n$。网格 $i$ 的难度是一个正整数 $d_i$，难度最低的网格（即难度为 $1$ 的网格）被称为普通网格。通过网格 $i$ 的时间成本定义如下：如果树懒进入网格 $i$ 时的速度 $v$ 高于 $\frac{1}{d_i}$（单位：普通网格/秒），则由于树懒的懒惰，速度会被调整为 $\frac{1}{d_i}$。此后，树懒通过该网格所需的时间将是普通网格的 $d_i$ 倍，即耗时 $\frac{d_i}{v}$ 秒。

有时，树懒会花钱请勤劳的人类来重建巨大的赛道。将会发生两种工作：

• Plow（耕地）：在网格 $l, (l+1) \pmod n, \dots, r$ 中，为每个网格增加特定的难度 $\Delta$。
• Ram（夯土）：在网格 $l, (l+1) \pmod n, \dots, r$ 中，将每个网格的难度替换为特定的难度 $d'$。

为了开始一场赛车游戏，裁判会选择一个起始网格 $s$ 和游戏总时间 $t$ 秒，游戏组织方式如下：

• 树懒初始速度为 $1$。
• 在游戏开始时刻，所有树懒开始进入网格 $s$。
• 通过一个网格后，树懒进入下一个网格，其中“下一个”的定义如上所述。
• 游戏在 $t$ 秒后结束。所有树懒会紧急刹车并停在那里。

树懒只能走得很慢，所以裁判会立即开始走向游戏的终点位置。现在，你也是受雇的人类之一，需要告诉裁判在游戏开始时该去哪里。

既然你不是树懒，你必须快速完成这项工作。

输入格式

第一行包含两个整数 $n, q$ ($2 \le n, q \le 2 \times 10^5$)，由空格分隔，分别表示巨大赛道的长度以及操作和查询的数量。

第二行包含 $n$ 个整数，由空格分隔，第 $i$ 个数表示 $d_{i-1}$，即第 $i$ 个网格的初始难度。

接下来的 $q$ 行包含查询和操作。每一行必须属于以下三种类型之一：

• P l r Δ：Plow，从第 $l$ 个网格到第 $r$ 个网格，增加难度 $\Delta$。
• R l r d'：Ram，从第 $l$ 个网格到第 $r$ 个网格，将难度替换为 $d'$。
• Q s t：Query，查询从 $s$ ($0 \le s < n$) 开始且总时间为 $t$ ($0 \le t \le 2 \times 10^{17}$) 秒的游戏的终点位置。注意，两个网格边界处的位置被定义为“下一个”网格，这意味着如果树懒在离开第 $i$ 个网格进入下一个网格时恰好停止，则该位置被定义为网格 $(i+1) \pmod n$。

保证对于所有出现在 $q$ 行中的 $l, r$，都有 $0 \le l, r < n$。我们精确定义区间 $[l, r]$ 如下：

• $l \le r$：$\{l, l+1, \dots, r\}$；
• $l > r$：$\{l, l+1, \dots, n-1, 0, 1, \dots, r\}$。

同时保证输入中出现的所有难度，包括 $d_i, \Delta, d'$，均为不超过 $10^6$ 的正整数；每次操作后网格的难度均不超过 $10^6$。

输出格式

对于每个查询，你需要输出一个整数，占一行，表示你的答案。

样例

样例输入 1

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

样例输出 1

0
1
1
0

样例输入 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

说明

在第一个样例中，我们说明了如何定义边界。从 $0$ 开始游戏，在 $t=0$ 时被认为在网格 $0$ 中；在 $t=1$ 时被认为在网格 $1$ 中，因为它通过第一个网格仅需 $1$ 秒。此后，树懒的速度降低为 $\frac{1}{2}$，通过网格 $1$ 需要 $4$ 秒。