Queries on the String  Problem code: QSET

SUBMIT MY SUBMISSIONS ALL SUBMISSIONS

All submissions for this problem are available.

Read problems statements in Mandarin Chinese and Russian.

You have a string of N decimal digits, denoted by numbers A₁,A₂, ..., A_N.

Now you are given M queries, each of whom is of following two types.

• Type 1: 1 X Y: Replace A_X by Y.
• Type 2: 2 C D: Print the number of sub-strings divisible by 3 of the string denoted by A_C,A_C+1 ...
  A_D.
  
  
  Formally, you have to print the number of pairs (i,j) such that the string A_i,A_i+1...A_j,
  (C ≤ i ≤ j ≤ D), when considered as a decimal number, is divisible by 3.

Input

• There is only one test case.
• First line of input contains two space separated integers N, M.
• Next line contains a string of N digits, denoting string A.
• For next M lines, each line contains a query.
• Each query is given by three space separated integers.
• The first integer denotes type of the query. For each query of type 1, next two integers denote X_i, Y_i.
  For each query of type 2, next two integers denote C_i, D_i.

Output

For each query of type 2, print the required answer in a single line.

Constraints

• 0 ≤ A_i ≤ 9
• 1 ≤ X_i ≤ N
• 0 ≤ Y_i ≤ 9
• 1 ≤ C_i ≤ D_i ≤ N

Subtasks

• Subtask #1 (10 points): 1 ≤ N, M ≤ 10³ and only type 2 queries.
• Subtask #2 (15 points): 1 ≤ N, M ≤ 10³
• Subtask #3 (20 points): 1 ≤ N, M ≤ 10⁵ and only type 2 queries
• Subtask #4 (55 points): 1 ≤ N, M ≤ 10⁵

Example

Input:
5 3
01245
2 1 3
1 4 5
2 3 5

Output:
3
1

Explanation

For first query, the sub-strings S[1,1]="0", S[1,3]="012" and S[2,3]="12" are divisible by 3.
After second query, the string A becomes "01255".
For third query, only sub-string S[3,5]="255" is divisible by 3.

A very firm understanding of this question is the key to solve it .

For each node we require 4 things.    the number of substrings divisible by 3 on the segment , the total sum of the segment and the prefix and the suffix array .

where prefix array stands for the number of elements starting with the prefix and whos sum%3 gives 0,1 ,2. It is the same for prefix array. Now while ,merging two nodes , we first need to create the prefix and suffix arrays for the node