H. Hysteretic Racing
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Racing is for high speed usually. However, sloths enjoy hysteretic racing. They believe being slower could be better for exhibiting racers' skills, and all sloths will drive at the same speed. The winner is the one with the best driving skill throughout the journey.

There is the best fit for the figure: the sloth racer and DMV officer called Flash, in the movie Zootopia. However, we use this AI-generated sloth driver instead to avoid legal issues.

The giant race track consists of $$$n$$$ soil grids $$$0, 1, \dots, n - 1$$$ forming a circle, where the next grid of $$$i$$$ is $$$(i + 1) \bmod n$$$. The difficulty of the grid $$$i$$$ is a positive integer $$$d_i$$$, and the grid with lowest difficulty, $$$1$$$, is called a normal grid. The time cost to pass grid $$$i$$$ is defined as follows: if the velocity $$$v$$$ of sloths is higher than $$$\frac 1 {d_i}$$$ (normal grids per second) when entering grid $$$i$$$, the speed is adjusted to $$$\frac 1 {d_i}$$$ due to the laziness of sloths. After that, sloths will take $$$d_i$$$ times more than the normal grid to pass it, i.e., it will cost $$$\frac {d_i} {v}$$$ seconds.

Sometimes, the sloths pay for diligent humans to rebuild the giant race track. There are two kinds of the job that will occur:

  • Plow the soil in grids $$$l, (l + 1) \bmod n, \dots, r$$$, add a specific difficulty $$$\Delta$$$ to each grid.
  • Ram the soil in grids $$$l, (l + 1) \bmod n, \dots, r$$$, replace each grid's difficulty to a specific difficulty $$$d'$$$.

To begin a racing game, the judge will choose a start grid $$$s$$$ and the game's total time $$$t$$$ seconds, and the game is organized in the following method:

  • The sloths will have a velocity of $$$1$$$ initially.
  • At the beginning moment of the game, all sloths start entering the grid $$$s$$$.
  • After going through a grid, sloths enter the next grid, where "next" is defined above.
  • The game ends after $$$t$$$ seconds. All sloths take a sharp brake and stop there.
Sloths can only walk very slowly, so the judge will immediately start to walk to the end position of the game. Now, you are also one of the paid humans who are to tell the judge where to go at the beginning of the game.

Since you are not a sloth, you have to do it fast.

Input

The first line of input contains $$$n, q \, (2 \leq n, q \leq 2 \times 10 ^ 5)$$$ separated by a single space, denoting the length of the giant race track and the number of operations and queries.

The second line contains $$$n$$$ integer separated by spaces, the $$$i$$$-th denotes $$$d_{i - 1}$$$, the inital difficulty of the $$$i$$$-th grid.

The following $$$q$$$ lines contain queries and operations. Each line must fall in one of the three kinds:

  • $$$\texttt{P }l~r~\Delta$$$: Plow $$$l$$$-th to the $$$r$$$-th grid, with difficulty $$$\Delta$$$.
  • $$$\texttt{R }l~r~d'$$$: Ram $$$l$$$-th to the $$$r$$$-th grid, with difficulty $$$d'$$$.
  • $$$\texttt{Q }s~t$$$: Query the end position of a game starting at $$$s\,(0 \leq s \lt n)$$$ and with total time $$$t\,(0 \leq t \leq 2 \times 10 ^ {17})$$$ seconds. Note that the position at the boundary of two grids is defined as the "next" grid, meaning that if slots exactly stop when leaving the $$$i$$$-th grid for the next, the position is defined as the grid $$$(i + 1) \bmod n$$$.

It's guaranteed that $$$0 \leq l, r \lt n$$$ for all $$$l, r$$$ appeared in the $$$q$$$ lines. We define the intervals $$$[l, r]$$$ precisely as follows:

  • $$$l \leq r : \{l, l + 1, \dots, r\}$$$;
  • $$$l \gt r: \{l, l + 1, \dots, n - 1, 0, 1, \dots, r\}$$$.

It's also guaranteed that all difficulties appeared in the input, including $$$d_i, \Delta, d'$$$, are positive integers at most $$$10 ^ 6$$$; the difficulties of grids after each operation are at most $$$10 ^ 6$$$.

Output

In response to each query, you have to output a single integer in a single line denoting your answer.

Examples
Input
2 4
1 2
Q 0 0
Q 0 1
Q 0 4
Q 0 5
Output
0
1
1
0
Input
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
Output
0
3
0
4
1
Note

In the first sample we illustrate how do we define the boundary. Starting a game at $$$0$$$, it's considered in grid $$$0$$$ for $$$t=0$$$; it's considered in grid $$$1$$$ for $$$t = 1$$$, since it only takes $$$1$$$ second to pass the first grid. Then, the speed of sloths is reduced to $$$\frac 1 2$$$ afterwards, and it needs $$$4$$$ seconds to pass grid $$$1$$$.