B. Илья болон хүсэлт

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Ильягийн найзууд бүгдээрээ шалгалтан дээр бие биедээ туслахыг хүсдэг. IT-гийн шалгалтан дээр дараах асуудал гарж ирсэн.

Бид нарт $s = s_1s_2... s_n$ ($n$ урттай ), зөвхөн "." болон "#" -с тогтсон тэмдэгт мөр өгөгдөнө. Бидэнд $m$ ширхэг хүсэлт өгөгдөнө. Хүсэлт бүр нЬ $l_i$ $r_i$ $(1 ≤ li < ri ≤ n)$ гэсэн хоёр бүхэл тооноос тогтоно. Зэрэгцэж суусан хоёр ижил вариант авсан хүүхдүүд хоорондоо туслах боломжтой өөрөөр хэлбэл вариантууд $s_i == s_i + 1$ $i(l_i ≤ i < r_i)$ бол нэгэндээ туслаж болно.

$l$-с $r$ завсарт нийт хэдэн хүүхэд нэгэндээ туслаж болохыг тооцоолно уу.

Оролт

Эхний мөрөнд $n (2 ≤ n ≤ 10^5)$ урттай $s$ тэмдэгт мөр өгөгдөнө. Зөвхөн $"."$ болон $"#"$ тэмдэгтээс тогтсон байна.

Дараагийн мөрөнд нийт хүсэлтийн тоо $m (1 ≤ m ≤ 10^5) $ өгөгдөнө. Хүсэлт бүрийн хувьд $l , r(1 ≤ l_i < r_i ≤ n).$ хоёр бүхэл тоо өгөгдөнө.

Гаралт

Хүсэлт бүрийн хувьд өгөгдсөн дараалалаар харгалзах утгыг хэвлэ.

Орчуулсан: Хүрэлцоож

Жишээ тэстүүд

Оролт
......
4
3 4
2 3
1 6
2 6
Гаралт
1
1
5
4
Оролт
#..###
5
1 3
5 6
1 5
3 6
3 4
Гаралт
1
1
2
2
0
Сэтгэгдлүүдийг ачааллаж байна...