One day, $\text{wind}\_\text{whisper}$ encountered a problem called "Second Generation Turing Machine."
After a long period of struggling, he finally came up with a messy solution. However, although this solution is complicated, it seems it does not rely on random data.
But because $\text{wind}\_\text{whisper}$ has poor coding skills, he found that he could not implement it at all...
So he simplified the operations and created this easy problem.
Since it is a simplified version, let's call it "First Generation Turing Machine."
Description
Given a sequence of $n$ non-negative integers $a_{1...n}$, where each number has a color $c_i \in [1, m]$, you are required to perform $q$ operations of two types:
1 l r: Query the maximum sum of a subsegment within $[l, r]$ that contains no duplicate colors.2 i w: Change the color $c_i$ to $w$.
Input
The first line contains three positive integers $n, m, q$.
The second line contains $n$ integers, representing $a_{1...n}$.
The third line contains $n$ integers, representing $c_{1...n}$.
The next $q$ lines each describe an operation in the format specified above.
Output
For each type 1 operation, output one integer per line representing the answer.
Examples
Input 1
3 3 3
1 1 2
1 1 2
1 1 3
2 2 2
1 1 3Output 1
3
2Examples 2 ~ 4
See the provided files.
Constraints
| Subtask ID | $n \le $ | $q \le $ | $m \le $ | Special Property | Score |
|---|---|---|---|---|---|
| $1$ | $5\,000$ | $5\,000$ | $n$ | None | $10$ |
| $2$ | $2 \times 10^5$ | $2 \times 10^5$ | $10$ | $10$ | |
| $3$ | $n$ | No type 2 operations | $20$ | ||
| $4$ | $5 \times 10^4$ | $5 \times 10^4$ | None | $20$ | |
| $5$ | $2 \times 10^5$ | $2 \times 10^5$ | $40$ |
For all data, $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$.