Problem U
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\le N\le 200000$) and $Q$ ($1\le Q\le 200000$), 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\le V_i\le {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\le P_i\le 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\le K_i\le N$) and $P_i$ ($1\le P_i\le 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\le P_i\le 6$) and $V_i$ ($1\le V_i\le {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\le L_i\le R_i\le 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