【模板】诗乃莫队

题目背景

题目提供者:朝田诗乃 1990年,Abbi提出了一种抽象的计算模型 —— 第三代图灵机 (The 3rd Generation Turing Machine)。 ![avartar](https://cdn.luogu.com.cn/upload/pic/52955.png) 所谓的第三代图灵机就是指一个抽象的机器,它有一条长度为$n$的纸带,纸带分成了$n$个小方格,每个方格有不同的**颜色**和不同的**数字**。 ### 数据暂未实装,请不要提交 ### 数据是假的是假的不是这题的数据我求求你们不要再交了QAQ

题目描述

有一条长度为$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次方和。

输入输出样例

输入样例 #1

12 1 2
1 1 4 5 1 4 1 9 1 9 8 1
1 2 2 3 2 2 2 1 1 2 1 1
Q 1 5

输出样例 #1

62

说明

对于30%的数据,$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$ 就装做答案不会爆longlong吧 **所有数据点时空限制$1s/512MB$**