Problem description

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: T_N = (T_N − 1²+(T_N − 2+T_N − 3)²+T_N − 4⋅T_N − 5+P²+N) mod  1 000 000 033 gdzie zakładamy, że T_x = 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ść z wzoru powyżej. 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 L_i i R_i, 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 ≤ 10⁹, 1 ≤ L_i ≤ R_i ≤ D, 1 ≤ Q ≤ 100 000.

Przykład

8 2
3
1 3
2 6
1 8

1029
1425267809
3046916568