Description

There are $n$ transformations. The $i$-th transformation has two attributes $p_i$ and $q_i$. When this transformation is applied to $x$, $x$ becomes $f_i(x)$. The definition of $f_i(x)$ is:

$$f_i(x)=\left\lfloor\dfrac{x}{p_i}\right\rfloor+q_i$$

You are given $m$ operations. There are two types of operations:

A modify operation can change the attribute values of a transformation.

A query operation gives $x$ and two indices $s$ and $t$. You need to compute and output:

$$f_{t}(f_{t-1}(\cdots f_{s+1}(f_{s}(x))))$$

Input Format

The first line contains two positive integers $n$ and $m$.

The second line contains $n$ integers, representing $p_1,p_2,\cdots,p_n$.

The third line contains $n$ integers, representing $q_1,q_2,\cdots,q_n$.

The next $m$ lines each describe one operation:

A modify operation starts with the letter m, followed by three parameters $i,p',q'$, meaning to modify the $i$-th transformation’s attributes to $p',q'$. It is guaranteed that at any time the attributes satisfy $1\leq p_i\leq 1000, 0\leq q_i\leq 1000$.

A query operation starts with the letter q, followed by three parameters $x,s,t$. The meaning is as described above. It is guaranteed that $s\leq t, 0\leq x\leq 10^6$.

Output Format

For each query operation, output one integer, the required answer, separated by newlines.

3 3
2 1 2
1 1 1
q 100 1 3
m 2 2 0
q 100 1 3

27
13

见附件中的 turn-big-sample1.in

见附件中的 turn-big-sample1.out

Hint

Constraints

• For $20\%$ of the testdata, $1 \le n \le 10^3,1 \le m \le 10^4$.
• For another $30\%$ of the testdata, $1 \le n \le 10^4,1 \le m \le 10^5$.
• For $100\%$ of the testdata, $1 \le n \le 10^5,1 \le m \le 2 \times 10^5$.

---

File Input/Output (for simulation; not needed when submitting code)

• Filename: turn.cpp
• Input filename: turn.in
• Output filename: turn.out

Translated by ChatGPT 5