Problem description


Proste sumowanie
(proste-sumowanie)
Memory limit: 4 MB
Time limit: 2.50 s

Zwróć uwagę na limit pamięci (i pamiętaj, że do zużycia pamięci wliczane jest wszystko co musi zostać załadowane do pamięci w celu wykonania Twojego programu).

Czarno na białym – mamy daną tablicę i jesteśmy pytani o sumę elementów na poszczególnych przedziałach.

Tablica jest zadana następującym wzorem: TN = (TN − 12+(TN − 2+TN − 3)2+TN − 4TN − 5+P2+N) mod  1 000 000 033 gdzie zakładamy, że Tx = 0 dla x ≤ 0.

Napisz program, który: wczyta rozmiar tablicy, wartość P oraz zapytania, obliczy odpowiedzi dla poszczególnych zapytań, wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby naturalne D i P, oddzielone pojedynczym odstępem i określające kolejno: rozmiar tablicy oraz wartość pierwszego elementu tablicy. W drugim wierszu znajduje się jedna liczba naturalna Q, określająca liczbę zapytań. Każde zapytanie obejmuje jeden wiersz i składa się z dwóch liczb całkowitych S i K, oddzielonych pojedynczym odstępem i oznaczających początek i koniec przedziału (domkniętego) indeksów, na którym mamy policzyć sumę.

Wyjście

Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu wyjścia powinna się znaleźć odpowiedź dla i-tego zapytania.

Ograniczenia

1 ≤ D ≤ 4 000 000, 1 ≤ P ≤ 109, 1 ≤ S ≤ K ≤ D, 1 ≤ Q ≤ 100 000.

Przykład

Input Output
8 2
3
1 3
2 6
1 8
1029
1425267809
3046916568