Wstęp do programowania w C++

Dziś jest Dzień Edukacji Narodowej. Co to oznacza? Oznacza to, że już niedługo odbędzie się akademia zorganizowana przez uczniów.

Uczniowie ustawili się na scenie w jednym rzędzie patrząc w stronę widowni. Na znak prowadzącego, każdy z uczniów obrócił się o 90 stopni w lewo lub w prawo (można powiedzieć, że postała losowa konfiguracja). Następnie prowadzący prosi, aby osoby od pozyci a do pozycji b odwróciły się o 180 stopni. Tę czynność wykonano jeszcze wiele razy. 

Teraz, jeśli dwóch uczniów ustawionych jest miedzy sobą twarzą w twarz, to przybijają sobie piątkę. Ile razy zostanie przybita piątka po wykonaniu opisanych czynności?

Wejście

W pierwszym wierszu jedna naturalna liczba n określająca ilość uczniów (nie więcej niż milion).

W drugim wierszu n znaków należących do zbioru {l, p}. Jeśli na itej pozycji pojawi się znak l, to uczeń początkowo patrzy w lewą stronę. Jeśli p, to w prawą stronę.

W trzecim wierszu jedna liczba q okraślająca liczbę zapytań (nie więcej niż 100 000).

Każde zapytanie składa się z dwóch liczb a i b, takich, że 0 < a < b <= n, określające przedział osób, które muszą się odwrócić o 180 stopni.

Wyjście

Jedna liczba, określająca ilość przybitych piątek po wykonaniu wszystkich zapytań.

Przykład

Wejście:
5
llppl
3
1 5
2 4
3 5

Wyjście:
1