Problem D
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.

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