Eddy likes to play with digits. However, as you may know, Eddy is a programmer not a normal human. Thus, he likes to play with hexadecimal digits(base 16) instead of decimal digits(base 10). One day, he found that sum of digits() is very interesting. Then, he invents following function.





After playing with several times, Eddy found that for one integer, the computation is too easy to make him happy. Thus, Eddy generates a string of hexadecimal digits S, and takes some subsegment(consecutive digits) of it. Then, Eddy takes all the non-empty subsequence(not necessary consecutive digits) from the subsegment as the inputs of the function. It becomes a little challenging for Eddy now. But, Eddy is still not satisfied. He wants to change the string sometimes and keeps taking some subsegments as queries. Now, it's really a problem for Eddy. You, as one of the friends of Eddy, come to rescue him and are going to compute the answer for him.

Since the number of outputs would be too many(which will be equal to the number of non-empty subsequences), you are only required to compute the number of each output and report the number to Eddy.

For example, the hexadecimal string S equals . Eddy takes the subsegment [1,1] which is . All the non-empty subsequence is . Thus, the answer will be .

If Eddy takes the subsegment [1,3] which is . All the non-empty subsequence is . Then, the answer will be 267411465.

First line of input contains two space-separated integer N, Q indicating the length of hexadecimal digits S and number of operations Eddy will take.

Second line of input contains a string S indicating the hexadecimal string Eddy generates.

Following Q lines, each line will be one of following form:
: changing p-th digit of S into c.
: taking the subsegment [l, r] and compute the answer.


1≤ N,Q≤ 105
|S|=N, length of S will be N
character of S will be hexadecimal digit()
1≤ p ≤ N, c will be hexadecimal digit
1≤ l ≤ r≤ N

For each second type operation(), output one line indicating the corresponding answer.

5 2
12345
2 1 1
2 1 3

1021
267411465

5 3
12345
2 1 5
1 1 A
2 1 5

930616025
659780022