题目描述

小 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 $ 的询问，输出一行，包含一个整数，表示询问的答案。

样例

input

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

output

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 位整型范围内。

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