题目描述

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

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

• 修改操作可以修改某个变换的属性值；
• 查询操作将会给定 $x$ 以及两个序号 $s$ 和 $t$，你需要计算并输出　

输入格式

第一行：两个正整数表示 $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

数据范围

• 对 $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$。