题目背景

一天，$\text{wind}\_\text{whisper}$ 遇到了一道题：“第二代图灵机”。

经过长时间的坐牢之后，他终于有了一个屎山做法。然而，这个做法虽然麻烦，但似乎可以不依赖随机数据？

但是由于 $\text{wind}\_\text{whisper}$ 码力太差，他发现自己根本写不出来...

于是他把操作进行了弱化，出成了这道简单题。

既然是弱化，不妨就叫它“第一代图灵机”吧。

题目描述

给出一个长度为 $n$ 的非负数字序列 $a_{1...n}$，每个数字有一个 $[1,m]$ 的颜色 $c_i$，要求进行 $q$ 次操作，操作分为两类：

• 1 l r：询问区间 $[l,r]$ 中没有重复颜色且数字和最大的子区间的数字和。
• 2 i w：把 $c_i$ 修改为 $w$。

输入格式

第一行三个正整数 $n,m,q$。

第二行 $n$ 个整数，表示 $a_{1...n}$。

第三行 $n$ 个整数，表示 $c_{1...n}$。

接下来的 $q$ 行，每行表示一次操作，格式如题目描述。

输出格式

对于每个第一类操作输出一行一个整数，表示答案。

样例数据

样例 1 输入

3 3 3
1 1 2
1 1 2
1 1 3
2 2 2
1 1 3

样例 1 输出

3
2

样例2 ~ 4

见下发文件。

数据范围

对于所有数据，$1\le m\le n\le 2\times 10^5,q\le 2\times 10^5,c_i\in [1,m],0\le a_i\le 10^9$。