题目背景
一天，$\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
见下发文件。
数据范围
| 子任务编号 | $n \le $ | $q \le $ | $m \le $ | 特殊性质 | 分值 |
|---|---|---|---|---|---|
| $1$ | $5\,000$ | $5\,000$ | $n$ | 无 | $10$ |
| $2$ | $2 \times 10^5$ | $2 \times 10^5$ | $10$ | $10$ | |
| $3$ | $n$ | 没有第二种操作 | $20$ | ||
| $4$ | $5 \times 10^4$ | $5 \times 10^4$ | 无 | $20$ | |
| $5$ | $2 \times 10^5$ | $2 \times 10^5$ | $40$ |
对于所有数据，$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$。