Foto stellare

Il dottor Hubb è un appassionato di astronomia.
Possiede una carta astronomica planare, composta dai due assi del piano cartesiano aventi l’origine in posizione (0,0).

ter_2004_fotoLa carta è suddivisa in quattro quadranti delimitati dagli assi cartesiani, dove a ciascun quadrante viene assegnata una lettera distinta come mostrato in figura:

Le stelle nella carta planare sono rappresentate mediante coordinate intere e un valore di intensità.
Precisamente, ciascuna stella è rappresentata da una tripla x, y, k, per individuare le coordinate (x, y) del centro della stella e la sua intensità espressa mediante un intero k Î {1,2,3}.

Al dottor Hubb piace molto scattare delle foto digitali al cielo stellato.
Ciascuna foto digitale è composta da zeri e da uni.
Lo sfondo del cielo è rappresentato dagli zeri, mentre una stella x, y, k è rappresentata dagli uni in accordo al valore di k:

						  1
			 1			 111
 1			111			11111
			 1			 111
						  1
In tal caso, la coordinata (x, y) si riferisce all’uno in posizione centrale.

Le stelle possono parzialmente sovrapporsi nelle foto ma le loro coordinate sono sicuramente distinte come coppie di valori.

Purtroppo il dottor Hubb è un pasticcione.
La sua carta astronomica contiene N stelle, e lui ha scattato una foto digitale di taglia MxM, ma non ricorda in quali quadranti.
Per l’elevata tecnologia adottata, non ci sono distorsioni ottiche: basta sovrapporre la foto digitale alla carta planare in una posizione opportuna, per farle combaciare e poter così ricostruire il quadrante (o i quadranti) di appartenenza.
Le risposte ammissibili sono A, B, C, D, AD, AB, BC, CD, ABCD, mentre AC, BD, ABC, ecc., non sono considerate valide.

Suggerimento

Quadrettare a griglia il piano cartesiano con le coordinate intere, assegnando le coordinate (x, y) al quadratino avente (x, y) come coordinata dello spigolo inferiore sinistro.

Dati di input

Il file di input contiene una sequenza di righe.
La prima riga contiene il valore di N e M.
Le N righe successive rappresentano le N stelle nella carta astronomica, ciascuna riga contenente una tripla x, y, k, interpretata in accordo a quanto descritto sopra.
Le M righe finali rappresentano la foto digitale, ogni riga contenente una sequenza di M valori scelti tra zeri e uni.

Dati di output

Il file di output contiene una sola delle risposte ammissibili, A, B, C, D, AD, AB, BC, CD, ABCD, in base alla posizione della foto digitale rispetto ai quadranti della carta astronomica.

Assunzioni

I numeri sono rappresentati con il segno.
Le coordinate (x, y) sono coppie di numeri, dove -1000 < x, y < 1000.
Per la conformazione della carta stessa e della foto c’è esattamente una risposta da fornire (non è possibile che la foto appaia due o più volte in posizioni distinte).
La foto non taglia le stelle: una stella è interamente catturata dalla foto oppure non è catturata affatto.
Infine, se una stella ha centro nel quadrante A ma la sua intensità è tale che induca un uno nel quadrante B, per esempio, allora la stella viene considerata a cavallo dei due quadranti A e B (non conta solo il centro, ma anche l’intensità).

Esempio di input e output

input.txt output.txt
9 7
3 7 1
2 6 1
1 2 2
2 1 1
1 7 1
1 3 3
2 3 2
2 -1 1
3 -1 1
1000100
0100000
0000100
0001110
0011111
0111110
0110100
AB

Motivazione per la risposta: la foto è stata scattata a cavallo dei quadranti A e B, e contiene le prime 7 stelle elencate nel file input.txt.