AlgoLiga 2018

Epicykloidory to interesujące zwierzęta, będące obiektem badań wielu naukowców - epicykloidorologów. Jednym z nich jest Bajteusz. Obecnie pracuje on nad badaniem gier, w jakie bawią się owe niezwykłe stworzenia, a przede wszystkim Głuchego telefonu. Zabawa ta nie różni się bardzo od ludzkiej wersji. Epicykloidory nie siedzą jednak w kółku, lecz przeskakują od stada do stada, poruszając się tylko na wschód (a więc w prawą stronę, wyobrażając sobie glob) o stałą dla każdego osobnika odledłość. Jak powszechnie wiadomo, epicykloidory potrafią bardzo wysoko skakać. Im większy ów ssak, tym wyżej i dalej może skoczyć. Każdego osobnika opisuje więc liczba l , oznaczająca długość każdego jego skoku w bajtometrach. Wiele osobników może być opisywanych przez tę samą liczbę l. Jeśli jakiś epicykloidor chce wrócić do swojego stada, po prostu okrąża glob (a konkretniej równik, bo przecież tam jest najlepszy klimat dla naszych zwierząt), który ma długość n, kilka razy. Stworzenia te są bardzo popularne, więc co bajtometr znajduje się dokładnie jedno stado, a więc zawsze jest możliwość wykonania skoku przez epicykloidora.

A zatem, ze stada nr a wyrusza jakiś epicykloidor (o indeksie i). Trafia do stada odległego o l_i bajtometrów i przekazuje innemu epicykloidorowi jakąś wiadomość. Ten następnie przeskakuje do kolejnego stada i tak x razy. Co więcej, w każdym stadzie znajdują się osobniki o wszystkich możliwych rozmiarach (a więc i długościach l), których to listę posiada Bajteusz. Problem w tym, że w zależności od rozmiaru epicykloidora zależy jak bardzo zmieni on poprzednią wiadomość. Wpływ na nią ma również numer stada, z którego wyszła (bo, jak wiemy, w różnych stadach osobniki mają różne akcenty) oraz stad, przez które przeszła (im więcej osobników weźmie udział w grze tym bardziej zniekształcony będzie końcowy komunikat).

Bajteusz, znając stado a (i-te stado znajduje się na i-tym bajtometrze), z którego wyszła wiadomość, stado b, na którym gra się zakończyła, x - ilość epicykloidorów, które uczestniczyły w zabawie oraz listę możliwych odległości, na które skaczą nasze stworzenia, chce poznać ilość możliwych tras, które mogły przebyć początkowe wiadomości.

Wejście

W pierwszej linii znajduje się liczba testów t (t < 101). Każdy test rozpoczyna się od trzech liczb naturalnych n, m i q (2 ≤ n, m ≤ 5000, q < 101) oznaczających długość globu, ilość możliwych odległości, na które mogą skakać epicykloidory oraz liczbę zapytań. W następnych m liniach znajduje się jedna liczba naturalna l (1 ≤ l ≤ 10⁹, n ∤ l), będąca odległością w bajtometrach, którą epicykloidory o odpowiednim rozmiarze mogą pokonać jednym skokiem. Kolejne q linii zawiera zapytanie składające się z trójki liczb a, b i x (1 ≤ a, b ≤ n, 1 ≤ x ≤ 10⁹) będących odpowiednio stadem początkowym i końcowym oraz ilością skoków między owymi stadami. Dodatkowo, max(n,m)*q ≤ 5000.

Wyjście

Dla każdego zapytania jedna liczba będąca ilością możliwych tras ze stada a do stada b o długości x, modulo 1010101.

Przykład

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

Wyjście:
1
2
4
1
6

Wyjaśnienie do przykładu:
Epicykloidory mogą skakać na odległość 5, 1 lub 2 bajtometrów.

Dla pierwszego zapytania musimy znaleźć ilość tras z pierwszego stada do drugiego o odległości jednego skoku (dowolnej długości). Jest tylko jedna taka możliwość - epicykloidor wykonujący skoki 1-bajtometrowe skacze ze stada początkowego do końcowego.

Dla drugiego zapytania mamy już dwie możliwości. Skok będzie miał długość 2 albo 5 bajtometrów. Skok na odległość 5 bajtometrów będzie wyglądał tak, że epicykloidor wyskoczy ze stada 2, przeskoczy stada: 3, 1, 2, 3 i wyląduje w stadzie 1 (okrążając de facto cały glob niecałym skokiem!).

Dla ostatniego zapytania jest aż 6 kombinacji skoków. Można przeskoczyć najpierw ze stada 3 do 1, następnie z 1 do 3 i ponownie z 3 do 1 (na 2 sposoby, gdyż z 1 do 3 można wykonać skok o długości 2 lub 5). Kolejną możliwą trasą jest 3-1-2-1 (również na 2 sposoby, jako że z 2 do 1 można dostać się skokiem o długości 2 lub 5). Ostatnią opcją jest 3-2-3-1 (także na 2 sposoby). Łącznie otrzymujemy 2+2+2=6 różnych tras.