I-O-I Triplets Query

You are given a string S of length \(n\) consisting only of the characters I and O. You are also given \(m\) operations. There are two types of operations:

1. Update: 1 x c — change the character at position \(x\) to c, where c is either I or O.
2. Query: 2 l r — count the number of ordered triplets \((i,j,k)\) such that \(l \le i < j < k \le r\), \(S_i = I\), \(S_j = O\), and \(S_k = I\).

For a query operation, for each position \(j\) (with \(l \le j \le r\)) where \(S_j = O\), if there are \(a\) positions with I in the interval \([l, j-1]\) and \(b\) positions with I in the interval \([j+1, r]\), then the contribution of this query is \(a \times b\). The final answer is the sum of contributions for all such \(j\).

inputFormat

The first line contains two integers \(n\) and \(m\). The second line contains a string S of length \(n\) consisting only of characters I and O. Each of the next \(m\) lines describes an operation in one of the following formats:

• 1 x c — update operation: change the character at position \(x\) to c (c is either I or O).
• 2 l r — query operation: count the number of triplets \((i,j,k)\) in the substring \(S[l...r]\) such that \(S_i = I\), \(S_j = O\), and \(S_k = I\) with \(i < j < k\).

outputFormat

For each query operation, output a single integer representing the answer to the query.

sample

5 5
IOIOI
2 1 5
1 3 O
2 1 5
1 5 O
2 1 5

4
3
0