题目描述

有 $n$ 个变换，其中第 $i$ 个有两个属性值 $p_i$ 和 $q_i$，当这个变换作用到 $x$ 时，$x$ 将会变成 $f_i(x),f_i(x)$ 的定义为：

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

给定 $m$ 条操作，操作分两种：

修改操作可以修改某个变换的属性值；

查询操作将会给定 $x$ 以及两个序号 $s$ 和 $t$，你需要计算并输出：

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

输入格式

第一行：两个正整数表示 $n$ 和 $m$。

第二行：$n$ 个整数，表示 $p_1,p_2,\cdots,p_n$。

第三行：$n$ 个整数，表示 $q_1,q_2,\cdots,q_n$。

接下来 $m$ 行，每行表示一个操作：

修改 操作以字母 m 开头，后接三个参数 $i,p',q'$，表示将第 $i$ 个变换的属性值修改成 $p',q'$。保证任何时候属性都满足 $1\leq p_i\leq 1000, 0\leq q_i\leq 1000$。

查询 操作以字母 q 开头，后接三个参数 $x,s,t$，意义见题面，保证 $s\leq t, 0\leq x\leq 10^6$。

输出格式

对每个询问操作，输出一个整数，表示所求的答案，以换行分隔。

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

提示

【数据范围】

• 对于 $20\%$ 的数据，$1 \le n \le 10^3,1 \le m \le 10^4$。
• 对于另外 $30\%$ 的数据，$1 \le n \le 10^4,1 \le m \le 10^5$。
• 对于 $100\%$ 的数据，$1 \le n \le 10^5,1 \le m \le 2 \times 10^5$。

---

【文件读入读出】（模拟，提交代码时不需使用）

• 文件名：turn.cpp
• 读入文件名：turn.in
• 读出文件名：turn.out