問題文

以下で定義される長さ $N$ の論理ゲート式 $X$ が与えられます。
$Q$ 個のクエリが与えられるので順に処理してください。$k$ 番目のクエリは以下の通りです。

• 正の奇数 $L_k, R_k$ が与えられる。 $L_k \leq i \leq j \leq R_k$ を満たす整数の組 $(i, j)$ であって $X$ の $i$ から $j$ までの連続部分列が論理ゲート式として解釈可能かつその評価値がTであるような個数を求めよ。

論理ゲート式の定義

奇数番目の文字はTFのいずれかで、偶数番目の文字は+*^のいずれかであるような奇数長の文字列を論理ゲート式と呼びます。
T, Fはそれぞれ真, 偽、+*^はそれぞれ論理和、論理積、排他的論理和を表しています。 ここで，論理和，論理積，排他的論理和の真理値表はそれぞれ以下のようになります。

A	B	A + B (OR)	A * B (AND)	A ^ B (XOR)
T	T	T	T	F
T	F	T	F	T
F	T	T	F	T
F	F	F	F	F

• T: 評価値はTです。
• F+F*T: 評価値は((F+F)*T) = (F*T) = Fです。
• T^F+T^F*T: 評価値は((((T^F)+T)^F)*T) = Tです。

• FFT
• C+T+F
• +T^T+
• ^^

制約

• $1 \leq N \leq 252525$
• $N$ は奇数
• $1 \leq Q \leq 10^5$
• $|X| = N$
• $X$ は論理ゲート式として解釈可能
• $1 \leq L_k \leq R_k \leq N$
• $L_k, R_k$ は奇数

入力

$N$ $Q$
$X$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$

出力

$k$ 行目には $k$ 番目のクエリに対する答えを出力してください。

サンプル

9 4
T^T+F^T*T
3 7
1 9
1 3
5 5

4
10
2
0