Problem description


Obrazki logiczne
(J)
Limit pamięci: 256 MB
Limit czasu: 1.00 s

Obrazki logiczne (nonogramy) to łamigłówka, w której celem jest zamalowanie niektórych kratek w taki sposób, aby spełniały podane ograniczenia (co zwykle skutkuje ładnym obrazkiem). W każdej linii (czyli wierszu albo kolumnie) podany jest ciąg liczb, który oznacza długości poszczególnych spójnych fragmentów, jakie powinny być zamalowane. Nie mogą być one dłuższe ani krótsze, muszą być w dokładnie takiej kolejności jak liczby w ciągu, a między każdą ich parą musi się znaleźć co najmniej jedna niezamalowana kratka.

Przykładowy obrazek możecie zobaczyć poniżej.

Twoje zadanie jest nieco prostsze: dostaniesz dane długości zamalowanych odcinków z jednego wiersza łamigłówki, oraz częściowo zamalowane już kratki z tego wiersza. Za pomocą tych danych musisz wykryć, które z nieokreślonych jeszcze pól na pewno muszą zostać zamalowane, a które na pewno nie będą zamalowane.

Wejście

Pierwszy wiersz wejścia zawiera liczbę T, oznaczającą liczbę przypadków testowych.

W kolejnych 3 ⋅ T wierszach wejścia znajdują się kolejne przypadki testowe. Każdy z nich składa się z trzech wierszy.

W pierwszym wierszu każdego przypadku testowego znajdują się dwie liczby całkowite N i M, oznaczające kolejno długość wiersza, który powinien zostać uzupełniony, oraz liczbę kolejnych zamalowanych fragmentów.

Drugi wiersz przypadku testowego zawiera M oddzielonych pojedynczymi spacjami dodatnich liczb całkowitych, oznaczających długości kolejnych zamalowanych fragmentów.

Trzeci wiersz przypadku testowego składa się z ciągu N znaków ze zbioru {., #, ?}. Znak . oznacza, że dana kratka nie może zostać zamalowana, # oznacza, że dana kratka musi zostać zamalowana, a znak ? oznacza, że obie opcje są możliwe.

Możesz założyć, że dla każdego przypadku z wejścia istnieje co najmniej jedno poprawne zamalowanie.

Wyjście

Dla każdego przypadku testowego wypisz dokładnie jeden wiersz, składający się z ciągu N znaków ze zbioru {., #, ?}, w takim samym formacie jak opis wiersza na wejściu. Wiersz ten powinien zawierać informacje na temat wszystkich pól, co do których mamy pewność, że będą albo nie będą one zamalowane.

Ograniczenia

1 ≤ T ≤ 1000, 1 ≤ N ≤ 1000, 0 ≤ M ≤ 50.

Suma wartości N we wszystkich przypadkach testowych nie przekroczy 1000.

Przykłady

Wejście Wyjście Wyjaśnienie
5
10 5
1 1 1 1 1
??????????
9 5
1 1 1 1 1
?????????
20 3
1 2 3
?#??.#??????????????
20 2
14 1
????????????????????
13 3
3 2 2
?.?#????#?#??
??????????
#.#.#.#.#
.#...##.????????????
????##########??????
..?##?.##.##.

Dla przykładu, w pierwszym przypadku testowym nie jesteśmy w stanie określić położenia żadnego z przedziałów o szerokości 1. Za to w drugim przypadku możemy już jednoznacznie zlokalizować je wszystkie.