Dany jest ciąg dodatnich liczb całkowitych a_i (dla i=1,2,...,n). Ciąg ten jest używany do szyfrowania n-bitowych wiadomości. Jeśli mamy wiadomość, której kolejne bity tworzą ciąg (t₁,...,t_n) (t_i ze zbioru {0,1}), to po zaszyfrowaniu ma ona postać liczby:

S=t₁a₁+t₂a₂+...+t_na_n

Zadanie

Masz dane zaszyfrowane wiadomości oraz ciągi liczb (a_i), których użyto do ich zaszyfrowania. Twoje zadanie polega na odkodowaniu zaszyfrowanych wiadomości i zapamiętaniu ich w określonych plikach. Nie musisz dostarczać żadnego programu. Wystarczy, że zapiszesz odszyfrowane wiadomości.

Wejście

Dysponujesz kilkoma zestawami danych. Każdy zestaw jest zapisany w osobnym pliku: szyk.in, gdzie k jest numerem zestawu. W pierwszym wierszu każdego z tych plików znajduje się jedna liczba całkowita n, 5<=n<=40. W kolejnych n wierszach zapisany jest ciąg liczb (a_i): w i+1-ym wierszu zapisana jest jedna dodatnia liczba całkowita a_i. Suma liczb a_i nie przekracza 2 000 000 000. W n+2-im wierszu zapisana jest jedna liczba całkowita S - zaszyfrowana wiadomość, 0<=S<=a₁+a₂+...+a_n.

Wyjście

Przykład

Dla pliku wejściowego szy.in:

24
19226985
123697
67356296
19721773
1113273
69335448
23680077
9029881
85168664
93676782
5253843
77616588
78572630
13375812
17199980
101508862
59248276
3505733
35790095
62028546
85726819
56462819
103373994
91757169
667509506

poprawną odpowiedzią jest plik wyjściowy szy.out:

110001000101101100010101