Problem G
Just for Sidekicks
The ponies’ pets are playing with some gems they found. There are six types of gems, with values $V_1, V_2, \dots , V_6$, respectively.
They have laid out $N$ gems in a row. The $i^\text {th}$ of these gems is of type $P_ i$.
Now, with nothing better to do and no better way to hide a queries on an array problem, they make $Q$ queries on the gems. In the $i^\text {th}$ query, either:
-
they replace the $K_ i^\text {th}$ gem with a gem of type $P_ i$,
-
they revalue the $P_ i^\text {th}$ type of gem as having value $V_ i$, or
-
they want to know the total value of the gems from the $L_ i^\text {th}$ one to the $R_ i^\text {th}$ one, inclusive.
Please help them answer the queries!
Input
The first line of input contains two integers, $N$ ($1 \leq N \leq 200\, 000$) and $Q$ ($1 \leq Q \leq 200\, 000$), the number of gems, and the number of queries, respectively.
The second line of input contains six integers, $V_1, V_2, \dots , V_6$ ($1 \leq V_ i \leq 10^9$), the values of the types of gems.
The third line of input contains a string of $N$ characters. In particular, the $i^\text {th}$ of these characters contains $P_ i$ ($1 \leq P_ i \leq 6$), the type of the $i^\text {th}$ gem.
The next $Q$ lines contain the queries. In particular, the $i^\text {th}$ of these lines begins with a single integer:
-
If this integer is $1$, two integers $K_ i$ ($1 \leq K_ i \leq N$) and $P_ i$ ($1 \leq P_ i \leq 6$) follow, indicating that they replace the $K_ i^\text {th}$ gem with a gem of type $P_ i$. It is guaranteed that $P_ i$ is different from the type of the $K_ i^\text {th}$ gem.
-
If this integer is $2$, two integers $P_ i$ ($1 \leq P_ i \leq 6$) and $V_ i$ ($1 \leq V_ i \leq 10^9$) follow, indicating that they revalue the $P_ i^\text {th}$ type of gem as having value $V_ i$. It is guaranteed that $V_ i$ is different from the value of the $P_ i^\text {th}$ type of gem.
-
If this integer is $3$, two integers $L_ i$ and $R_ i$ ($1 \leq L_ i \leq R_ i \leq N$) follow, indicating that they want to know the total value of the gems from the $L_ i^\text {th}$ one to the $R_ i^\text {th}$ one, inclusive.
It is guaranteed that there is at least one query of type $3$.
Output
For each query of type $3$, output a single integer on a line by itself, the total value of gems from the $L_ i^\text {th}$ one to the $R_ i^\text {th}$ one, inclusive.
Sample Input 1 | Sample Output 1 |
---|---|
8 5 10 30 25 420 39 69 55513642 3 2 6 1 1 6 2 6 3286 3 2 6 3 1 8 |
182 3399 7135 |