题目描述

小 Y 又找不到他的作业啦！
小 Y 的房间十分杂乱，他决定替换其中一些物品。
小 Y 对心烦有自己独特的见解，如果一个区间内有 $c$ 件种类编号为 $K$ 的物品，这些物品对他的心烦程度是 $A_{c}$。$A$ 是一个给定的数列。
一个区间对小 Y 的心烦程度是，区间中每种物品对小 Y 的心烦程度的和。
小 Y 的房间里有 $n$ 个物品，共有 $m$ 种，编号为 $1 \dots m$。这些物品排成一排，依次以 $1 \dots n$ 编号。
小 Y 会向你发送 $q$ 询问和指令，你需要回答小 Y 的询问。
小 Y 会向你发送如下指令：

• $\texttt{1 x y}$：把第 $x$ 件物品替换为 $y$。
• $\texttt{2 x y}$：查询区间 $[x, y]$ 对小 Y 的心烦程度。

这些问题对小 Y 来说太难啦！他需要你的帮助！
小 Y 希望你能快速回答这些问题，这意味着你必须使用在线算法。

输入格式

第一行三个整数 $n$、$m$、$q$。
第二行有 $n$ 个整数，表示初始时每个位置物品种类的编号 (不一定每种物品都要出现)。
第三行有 $n$ 个整数，第 $i$ 个数表示 $A_{i}$ 的值。
接下来 $q$ 行，每一行三个数 $\text{op} \ x \ y$。 $\text{op}$ 表示指令编号。
每条指令除第一个数字之外，均要异或上一次输出的答案 $\mathrm{lastans}$，初始时 $\mathrm{lastans}=0$。 数据保证，物品编号在合法范围内。

输出格式

对于每一个 $\text{op}=2$ 的询问，输出一行，包含一个整数，表示询问的答案。

5 3 3
1 2 1 3 3
0 1 -4 -5 -4
2 4 5
1 4 2
2 2 2

1
0

数据范围与提示

对于 $30\%$ 的数据，$n \leq 1000, m \leq 1000$；
对于 $60\%$ 的数据，$n \leq 50000, m \leq 50000$；
对于 $100\%$ 的数据，$1 \leq n, q, m \leq 100000$，所有输入和答案保证在 32 位整型范围内。

输入数据量较大，请尽量使用快速的读入方式 (=ﾟωﾟ)ﾉ