Runda 11 [Hard] - Żniwa

Zadanie tygodnia

runda 11; kategoria Hard

Limit czasowy: 2s; Limit pamięciowy: 128MB

Żniwa

Jak co roku w dalekich krainach liczb pierwszych nadszedł czas żniw. Każdy rolnik planuje zebrać ze swojego pola owoc całorocznych prac - dorodne liczby nieujemne. Powierzchnię upraw można podzielić na małe poletka rozmiaru 1x1, każde rodzące w czasie upraw jedną liczbę nieujmną. Kiedy rolnik decyduje się na zbiór, wyznacza prostokąt składający się z sąsiadujących małych poletek i zbiera z niego plon - iloczyn liczb ze składających się nań poletek, modulo pewna liczba pierwsza.

Zostałeś wyznaczony do pomiaru plonu dla różnych możliwych scenariuszy zbioru. Otrzymałeś listę prostokątów, o które mogą pytać Cię rolnicy, a Twoim zadaniem jest odpowiedzieć im, jak duży plon zbiorą.

Wejście:

Pierwsza linia wejścia zawiera trzy liczby , oraz - odpowiednio wysokość i szerokość pola uprawnego oraz liczbę pierwszą, modulo którą należy podawać wyniki. () W kolejnych liniach dla znajduje się po liczb całkowitych () - liczb które rosną na poletkach od do . 

Kolejna linia zawiera jedną liczbę całkowitą - liczbę zapytań o prostokąty.(. W kolejnych liniach znajdują się czwórki liczb całkowitych - współrzędne lewego górnego i prawego dolnego rogu prostokąta. (Zatem prostokąt składa się z poletek dla i , ponadto ).

Wyjście:

Dla każdego zapytania należy wypisać jedną liczbę calkowitą - iloczyn liczb z poletek znajdujących się w prostokącie modulo .

Przykład:

Wejście:

Wyjście: