W SBP (Super Bogatym Państwie) znajduje się mnóstwo miast. W każdym mieście można znaleźć m.in. domy, sklepy i ratusz. SBP jest bardzo uporządkowanym państwem, dlatego każde miasto ma swój stopień. Stopień o wartości k oznacza, że z każdego budynku wychodzi k jednokierunkowych dróg, ponumerowanych liczbami od 0 do k-1.</p>

Oczywiste jest, że szczególne znaczenie mają ścieżki, które zaczynają się z ratusza. Każdą taką ścieżkę można łatwo opisać sekwencją numerów kolejnych dróg. Przykładowo, plan realizacji ścieżki opisanej sekwencją 103 to:

1. Zaczynamy z ratusza. Wybieramy drogę oznaczoną numerem 1 przechodząc do budynku X.
2. Przechodzimy drogą numer 0 z budynku X do budynku Y.
3. Przechodzimy drogą numer 3 z budynku Y do budynku Z.
4. Ścieżka kończy się w budynku Z. Z może być domem, sklepem lub ratuszem.

Edek, znany wszystkim pracownik banku, już dawno porzucił swoją nudną pracę i przeniósł się do SBP. Nasz bohater zamieszkał w SBM (Super Bogatym Mieście) i podjął pracę w ratuszu miasta. Władze SBP od dawna zastanawiały się czemu SBM jest aż tak bogate. Jako najbardziej prawdopodobną przyczyną rozkwitu miasta wskazany został sposób numeracji dróg zastosowany w SBM. Aby potwierdzić te przypuszczenia, rząd SBP zlecił Edkowi następujące zadanie: mając dany opis dróg w SBM i jednego z innych miast, jaka jest najkrótsza sekwencja, która w jednym z miast opisuje ścieżkę z ratusza do domu, a w drugim z ratusza do budynku, który nie jest domem (sklepu lub ratusza) ?

입력 형식

W pierwszej linii znajduje się liczba testów T (1<=T<=20). Dalej, na wejściu pojawia się T zestawów testowych, których składania opisana jest poniżej.</p>

W pierwszej linii pojedynczego testu znajduje się 5 liczb naturalnych n₁, d₁, n₂, d₂, s (3<=n₁, n₂<=1000, 0<d₁<=n₁-2, 0<d₂<=n₂-2, 1<=s<=10). Jest to odpowiednio liczba budynków w SBM, liczba domów w SBM, liczba budynków w badanym mieście, liczba domów w badanym mieście oraz stopień obu miast. W SBM ratusz ma numer 0, domy mają numery od 1 do d₁, sklepy od d₁+1 do n₁-1. W drugim badanym mieście ratusz ma numer 0, domy mają numery od 1 do d₂, sklepy od d₂+1 do n₂-1. W następnych n₁ liniach znajduje się po s liczb całkowitych z przedziału od 0 do n₁-1. W i-tej linii znajdują się numery budynków, do których prowadzą drogi o numerze 0,1,...,(s-1) z budynku i. W kolejnych n₂ liniach znajduje się analogiczny opis drugiego miasta. Między dwoma budynkami może być wiele dróg, a także mogą być drogi, które zaczynają się i kończą w tym samym budynku.

출력 형식

Twój program powinien wypisać T linii. W i-tej z nich powinna znaleźć się odpowiedź dla i-tego testu. Jeżeli nie istnieje szukana sekwencja, Twój program powinien wypisać pojedynczą liczbę 0. W przeciwnym przypadku, Twój program powinien wypisać długość najkrótszej sekwencji, która spełnia warunki zadania, a następnie po pojedynczym odstępie szukaną sekwencję. Jeżeli jest wiele najkrótszych sekwencji, Twój program powinien wypisać sekwencję, która jest najmniejsza leksykograficznie, tj. pojawiłaby się jako pierwsza w słowniku.

예제 입력

3
3 1 3 1 1
1
2
0
1
2
2
4 1 6 2 2
2 0
1 3
2 1
3 3
4 3
2 5
2 5
4 3
4 1
5 5
3 1 3 1 2
0 2
1 1
1 2
0 2
1 1
2 1

예제 출력

4 0000
0
2 10

힌트

Test 1:</p>

• SBM: 0- ratusz; 1- dom; 2- sklep
• Drogi o numerze 0: 0->1, 1->2, 2->0
• Wszystkie sekwencje, które opisują ścieżki do domu w tym mieście to n wystąpień 0, gdzie (n-1) dzieli się przez 3
• Drugie miasto: 0- ratusz; 1- dom; 2 - sklep
• Drogi o numerze 0: 0->1, 1->2, 2->2
• Jedyną sekwencją, które opisuje ścieżkę do domu to 0.

Test 2: Każda sekwencja postaci (zero lub więcej wystąpień 1)(jedno lub więcej wystąpień 0)1(zero lub więcej wystąpień 0) prowadzi do domów w obu miastach. 

Test 3: Sekwencje 10 i 11 są najkrótszymi możliwymi sekwencjami spełniającymi warunki zadania.