Coin Flip Game with Interval Updates

Mivik arranges n coins in a row. Each coin is either heads up (H) or tails up (T). W!ʌ!k then considers the following game on the coins, without actually performing the operations, and his goal is to simply compute how many operations will occur (or determine that they will continue indefinitely).

The game is played as follows: As long as there is at least one coin showing tails, do the following operation. Let \( k \) be the number of coins that are tails up. Then flip the first \( k \) coins (i.e. for each of the first \( k \) coins, if it is heads then it becomes tails, and vice versa).

Before W!ʌ!k starts playing the game, Mikiv challenges him. First, you are given an initial configuration of the coins. Then, Mikiv performs several update operations; in each update, he flips all coins in a given interval. After each update, you should compute (without actually performing the operations) the total number of operations that would be executed if one started the game on the current configuration, or determine that the operations will continue forever.

Note: W!ʌ!k only needs to calculate the total number of operations; he does not actually perform the coin flipping process.

The flipping game operation is defined mathematically as follows. Let the state of the coins be represented by a string \( s = s_1s_2\ldots s_n \) where \( s_i = H \) indicates that the i-th coin is heads up and \( s_i = T \) indicates tails up. Define the transformation \( f(s) \) as follows: If the number of tails in \( s \) is \( k \), then for \( 1 \le i \le k \) set \( s_i \) to its opposite state, and leave the other coins unchanged. The process terminates if \( s \) becomes an all-heads configuration, and if the process eventually repeats a configuration, it is considered infinite.

Your task is to answer Mikiv's queries.

inputFormat

The first line contains two integers n and q (1 ≤ n ≤ 50, 1 ≤ q ≤ 10⁴), where n is the number of coins and q is the number of update queries.

The second line contains a string of length n consisting only of characters 'H' and 'T', representing the initial configuration (H means heads, T means tails).

Each of the next q lines contains two integers l and r (1 ≤ l ≤ r ≤ n), denoting that the coins from position l to r (inclusive) are to be flipped (i.e. H becomes T and T becomes H).

outputFormat

For each query, output a single integer on a new line: the total number of operations the game will execute on the current configuration, or -1 if the game will never terminate.

sample

3 3
THH
1 3
2 2
3 3

-1
-1
0