题目描述
有 $n$ 个变换，其中第 $i$ 个有两个属性值 $p_i$ 和 $q_i$，当这个变换作用到 $x$ 时，$x$ 将会变成 $f_i(x)$，$f_i(x)$ 的定义为：
$$f_i(x)=\lfloor \frac{x}{p_i} \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$。
输出
对每个**询问**操作，输出一个整数，表示所求的答案，以换行分隔。
样例输入输出
输入#1
复制
3 3
2 1 2
1 1 1
q 100 1 3
m 2 2 0
q 100 1 3
提示
+ 对 $20\%$ 的数据，$1\leq n\leq 10^3$, $1\leq m\leq 10^4$
+ 对 $50\%$ 的数据，$1\leq n\leq 10^4$, $1\leq m\leq 10^5$
+ 对 $100\%$ 的数据，$1\leq n\leq 10^5$, $1\leq m\leq 2\cdot 10^5$。