AlgoLiga 2018

Studenci, którzy nie podeszli do zerówki i nie zdali egzaminu ze "Wstępu do algorytmów" w pierwszym terminie muszą zmierzyć się z zadaniem przygotowanym przez profesora Algobita. Wykładowca ma dziś zły humor, ale czy oznacza to, że zadanie będzie trudne? Brzmi ono tak:

Nauczyciel przygotował dla każdej osoby szyfrogram składający się z n liczb naturalnych nie większych niż 10⁹ oraz rosnący ciąg a_k składający się z k wyrazów o takiej własności, że każdy następny wyraz jest większy od sumy poprzednich, oraz pewne dwie względnie pierwsze liczby m i n. Następnie wytłumaczył w jaki sposób otrzymał liczby stanowiące szyfrogram:

Dla przykładu posłużymy się ciągiem o długości k = 4: {2, 3, 7, 14}. Następnie dobieramy dwie liczby n i m takie, że n jest względnie pierwsze ze wszystkimi elementami ciągu oraz m jest liczbą większą od sumy wszystkich liczb w ciągu i tworzymy nowy ciąg b_k zgodnie z zasadą:

b_i = a_i * n mod m, gdzie 1 ≤ i ≤ k

Np. dla n = 11 oraz m  = 30 wyrazy nowego ciągu będą miały następujące wartości:

{22, 3, 17, 4}.

Aby zaszyfrować wiadomość przedstawiamy ją w sposób binarny i dzielimy na segmenty o długości k. W naszym przykładzie są 4 segmenty o długości 4 bitów każdy:

1001 1101 1110 0101

Teraz, każdy bit mnożymy przez odpowiadający wyraz ciągu i otrzymane elementy segmentu sumujemy:

dla 1001 mamy 22 + 4 = 26

dla 1101 mamy 22 + 3 + 4 = 29

dla 1110 mamy 22 + 3 + 17 = 42

dla 0101 mamy 3 + 4 = 7

Szyfrogramem jest ciąg: {26, 29, 42, 7}.

Zadaniem studentów i twoim jest odszyfrowanie tajnej wiadomości.

Wejście

W pierwszym wierszu jedna liczba określająca ilość zestawów danych.

Dla każdego zestawu mamy:

W pierwszym wierszu trzy liczby całkowite n, m i k, gdzie n ≤ 1000, m jest nie większe niż podwojona suma wszystkich elementów ciągu oraz k takie, że 0 < k ≤ 20, w następnym wierszu k wyrazów ciągu a_k (maksymalny element ciągu jest nie większy niż 10⁹). Następnie jedna liczba d określająca ilość elementów szyfrogramu 0 < d < 10⁵. W ostatnim wierszu d liczb będących szyfrogramem. 

Wyjście

Dla każdego zestawu oryginalna wiadomość przedstawiona w postaci binarnej. Długość wiadomości jest nie większa niż 4*10⁵.

Przykład

Wejście:

1

11 30 4
2 3 7 14
4
26 29 42 7

Wyjście:

1001110111100101