ビ太郎が通っている魔法学校では，間もなく運動会が開催される． 運動会では，スタートの魔法陣からゴールの魔法陣へ素早く移動する競技が行われる． この競技では，N 個の魔法陣が等間隔に円形に並べられており，時計回りに 1 から N までの番号が付けられている． それぞれの魔法陣は青色か赤色である． この色の情報は b, r からなる長さ N の文字列 S によって与えられ，S の j 文字目 (1 \leqq j \leqq N) が b ならば魔法陣 j は青色であり，r ならば魔法陣 j は赤色である．

ビ太郎は，この競技において以下の 2 種類の移動手段を用いることができる．

• 今いる魔法陣と隣り合う魔法陣をひとつ選び，その魔法陣へ 1 秒かけて移動する． すなわち，魔法陣 j と魔法陣 j + 1 (1 \leqq j \leqq N - 1) の間か，魔法陣 1 と魔法陣 N の間を 1 秒かけて移動する．
• 今いる魔法陣と同じ色の魔法陣をひとつ選び，その魔法陣へ 1 秒かけて移動する．

いま，魔法陣の数や色の情報は分かっているが，どの魔法陣がスタートとゴールであるかは運動会当日にならないと分からない． そこで，スタートとゴールの魔法陣の組を Q パターン考え，それぞれについて何秒かかるかを予め求めておくことにした． パターン i (1 \leqq i \leqq Q) において，スタートは魔法陣 X_i，ゴールは魔法陣 Y_i である．

魔法陣の情報とパターンの情報が与えられたとき，それぞれのパターンについてビ太郎がスタートからゴールへ移動するのに必要な時間の最小値を求めるプログラムを作成せよ．

制約

• 3 \leqq N \leqq 500\,000．
• 1 \leqq Q \leqq 500\,000．
• S は b, r からなる長さ N の文字列である．
• 1 \leqq X_i \leqq N (1 \leqq i \leqq Q)．
• 1 \leqq Y_i \leqq N (1 \leqq i \leqq Q)．
• X_i \neq Y_i (1 \leqq i \leqq Q)．
• N, Q, X_i, Y_i は整数である (1 \leqq i \leqq Q)．

小課題

1. (6 点) N = 3，Q \leqq 100．
2. (13 点) S は 1 文字目のみ b であり，2 文字目以降はすべて r である．
3. (18 点) N は偶数であり，S は奇数文字目が b，偶数文字目が r である．
4. (23 点) N は偶数であり，S は前半の \frac{N}2 文字が b，後半の \frac{N}2 文字が r である．
5. (21 点) N \leqq 100，Q \leqq 100．
6. (19 点) 追加の制約はない．

入力例 1

5 2
rbrbb
5 3
4 5

出力例 1

2
1

この例においては，赤色，青色，赤色，青色，青色の魔法陣がこの順に円形に並べられている．

パターン 1 について，ビ太郎は以下のようにして魔法陣 5 から魔法陣 3 へ 2 秒で移動することができる：

1. 魔法陣 5 と魔法陣 1 は隣り合っているため，魔法陣 5 から魔法陣 1 へ 1 秒で移動する．
2. 魔法陣 1 と魔法陣 3 は共に赤色であるため，魔法陣 1 から魔法陣 3 へ 1 秒で移動する．

2 秒未満で移動することはできないため，1 行目には 2 を出力する．

パターン 2 について，ビ太郎は以下のようにして魔法陣 4 から魔法陣 5 へ 1 秒で移動することができる：

1. 魔法陣 4 と魔法陣 5 は共に青色であるため，魔法陣 4 から魔法陣 5 へ 1 秒で移動する．

1 秒未満で移動することはできないため，2 行目には 1 を出力する．

この入力例は小課題 5, 6 の制約を満たす．

入力例 2

4 3
brrr
2 4
1 3
3 1

出力例 2

1
2
2

この入力例は小課題 2, 5, 6 の制約を満たす．

入力例 3

6 3
brbrbr
1 2
2 5
2 4

出力例 3

1
2
1

この入力例は小課題 3,5,6 の制約を満たす．

入力例 4

6 5
bbbrrr
2 3
2 4
2 5
2 6
2 1

出力例 4

1
2
3
2
1

この入力例は小課題 4,5,6 の制約を満たす．