Problem B: Paleta

Treść

Jedną z technik stosowanych przy kompresji obrazów jest ograniczenie liczby kolorów do ustalonej palety, implementowanej jako tablica. Dzięki temu zabiegowi pojedynczy piksel nie zajmuje już trzech bajtów (po jednym na składowe R, G i B). Zamiast tego jest on reprezentowany przez indeks do wspomnianej już palety. Indeks taki, w zależności od wielkości palety, zajmuje dużo mniej. Dla przykładu, dla palety 16-kolorowej będą to 4 bity, dla 256 kolorów 1 bajt, a dla 65536 kolorów 2 bajty.

Jedną ze składowych procesu kompresji jest kwantyzacja, czyli dobieranie koloru z palety dla każdego piksela z przetwarzanego obrazu. Dla zachowania możliwie najmniejszego odstępstwa od oryginału niezwykle ważne jest, by dobrany kolor był możliwie zbliżony do pierwowzoru. Jako miarę podobieństwa często przyjmuje się odległość euklidesową pomiędzy kolorem oryginalnym a kolorem z palety, w trójwymiarowej przestrzeni RGB. Oprócz precyzji istotna jest też szybkość kwantyzacji. Pojedynczy obraz może liczyć nawet kilkanaście milionów pikseli, a obrazów do przetworzenia mogą być dziesiątki, setki, a nawet tysiące.

Twoim zadaniem jest opracowanie i implementacja szybkiego, i oczywiście poprawnego, algorytmu kwantyzacji obrazu. Na podstawie podanej palety oraz oryginału twój program powinien dla każdego piksela wypisać jego kolor w obrazie wynikowym.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Pierwsza linia zestawu danych zawiera liczbę całkowitą n (1<=n<=30 000) oznaczająca liczbę kolorów w palecie. W kolejnych n wierszach podane są, jako liczby całkowite r_i, g_i, b_i (0<=r_i,g_i,b_i<=255) oddzielone pojedynczymi spacjami, poszczególne kolory palety. Kolory w palecie nie powtarzają się. We fragmencie przestrzeni RGB, który zajmują, są rozmieszczone w miarę równomiernie (a nie np. tylko na zewnętrznych ścianach lub prawie tylko w centrum), choć sam fragment może mieć różną wielkość i położenie w stosunku do całej przestrzeni. W następnym wierszu danych znajduje się liczba m (1<=m<=50 000) pikseli obrazu oryginalnego. W kolejnych m wierszach podane są liczby r_j, g_j, b_j (0<=r_j,g_j,b_j<=255), oddzielone pojedynczymi spacjami, definiujące kolory kolejnych pikseli.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest m linii reprezentujących obraz po skwantowaniu. Każda linia zawiera trzy liczby r_j, g_j, b_j oddzielone pojedynczymi spacjami – kolory wynikowych pikseli. W przypadku, gdy oryginalny piksel może być reprezentowany przez kilka wartości z palety (z takimi samymi, minimalnymi odległościami), należy wybrać ten z większą wartością r_i, a jeżeli te będą jednakowe, ten z większą wartością g_i, a jeśli i te będą równe, ten z większą wartością b_i.

Przykład

dane wejściowe:
1
9
0 0 0
255 255 255
128 128 128
64 64 64
192 192 192
32 32 32
96 96 96
160 160 160
224 224 224
5
0 0 0
45 67 42
121 45 255
47 48 48
48 48 48

wynik:
0 0 0
64 64 64
128 128 128
32 32 32
64 64 64