U540166 【模板】诗乃莫队

题目提供者：朝田诗乃 数据制造者：LANSGANBS 对比原题修改了数据范围，放宽了时间限制。 1990年，Abbi提出了一种抽象的计算模型 —— 第三代图灵机 (The 3rd Generation Turing Machine）。  所谓的第三代图灵机就是指一个抽象的机器，它有一条长度为$n$的纸带，纸带分成了$n$个小方格，每个方格有不同的**颜色**和不同的**数字**。

有一条长度为$n$的纸带，纸带分成了$n$个小方格，每个方格有不同的**颜色**和不同的**数字**。 定义颜色$c$在$[l,r]$中的价值为：$[l,r]$中所有颜色为$c$的方格的数字和。 询问给定$[l,r]$，求$[l,r]$中所有颜色的价值的k次方和。 你需要支持修改

第$1$行，两个数$n,m,k$，表示数列长度和操作次数以及$k$。 第$2$行，$n$个数，表示每个方格上的数字$a_i$。 第$3$行，$n$个数，表示每个方格上的颜色$c_i$。 随后$m$行，每行代表一个操作。有3种操作： 1、$Q \ \ l \ \ r$ ，表示询问求$[l,r]$中所有颜色的价值的k次方和 2、$C \ \ x \ \ y$，表示将位置$x$的颜色改为$y$。 3、$R \ \ x \ \ y$，表示将位置$x$的数字改为$y$。 设上一次询问的答案为$lastans$，则输入数据要全部异或上$lastans$（除了操作名称

对于每个询问，输出$[l,r]$中所有颜色的价值的k次方和。

对于60%的数据，$1 ≤ n,m ≤ 1000$ 对于100%的数据，$1 ≤ n,m ≤ 50000$，$1 ≤ c_i ≤ 10^9$，$1≤a_i≤10^3$，$1 ≤ l, r ≤ n$，$1 ≤ l_0,r_0 ≤10^{18}$，$1≤k≤3$ 所有数据使用long long，如果溢出的话，就让数据自然溢出吧（测试点1）^_^ **所有数据点时空限制$3s/512MB$**