Problem description
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 − 4⋅TN − 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 | |
|
|