Desni klik

Το NFP είναι το μέλλον! Αυτό είναι κάτι που όλοι οι φίλοι του Noa περιμένουν πει όταν ανακύπτουν οικονομικά θέματα.

Το NFP είναι ένα από τα κρυπτονομίσματα. Η τιμή του NFP κατά τη διάρκεια ~s~ ημερών μπορεί να αναπαρασταθεί με έναν πίνακα με ~r~ σειρές και ~s~ στήλες, που αποτελείται μόνο από χαρακτήρες . και #. Ο χαρακτήρας # στην ~i~-οστή στήλη αντιπροσωπεύει την τιμή του NFP την ~i~-οστή ημέρα, με την τιμή να είναι ο αριθμός της σειράς, μετρημένος από κάτω προς τα πάνω.

Η τιμή του NFP από το δεύτερο παράδειγμα κατά τη διάρκεια ~7~ ημερών ήταν: ~3,\,2,\,2,\,3,\,4,\,4,\,1~. Η ανασφάλεια αυτού του NFP είναι ~3~.

Η ανασφάλεια του NFP ορίζεται ως η διαφορά μεταξύ της μέγιστης και της ελάχιστης τιμής που επιτυγχάνεται κατά τη διάρκεια ~s~ ημερών.

Ο Noa θέλει να προσδιορίσει την ανασφάλεια για ~n~ NFP, οι τιμές των οποίων αντιπροσωπεύονται από πίνακες με ~r~ σειρές και ~s~ στήλες.

Βοηθήστε τον να προσδιορίσει την ανασφάλεια καθενός από τα ~n~ NFP.

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~n~, ~r~ και ~s~ ~(1 \le n \le 20,\,2 \le r, s \le 50)~, τον αριθμό των NFP και τον αριθμό των σειρών και των στηλών των πινάκων.

Ακολουθούν ~n~ πίνακες, ο ένας κάτω από τον άλλο, ο καθένας με ~r~ σειρές και ~s~ στήλες, που αντιπροσωπεύουν τιμές NFP. Κάθε στήλη αποτελείται μόνο από χαρακτήρες ., εκτός από ακριβώς έναν χαρακτήρα #.

Έξοδος

Εκτυπώστε ~n~ γραμμές. Στην ~i~-οστή των ~n~ γραμμών εκτυπώστε την ανασφάλεια του ~i~-οστού NFP.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	5	~r = s = 2~
2	15	~n = 1~
3	30	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

4 2 2
##
..

..
##

#.
.#

.#
#.

output

0
0
1
1

Επεξήγηση του 1ου παραδείγματος:

Οι τιμές του πρώτου και του δεύτερου NFP δεν αλλάζουν κατά τη διάρκεια της ημέρας, άρα οι ανασφάλειές τους είναι ίσες με ~0~. Η τιμή του τρίτου NFP μειώνεται κατά ~1~ τη δεύτερη ημέρα, οπότε η ανασφάλεια είναι ίση με ~1~. Η τιμή του τέταρτου NFP αυξάνεται κατά ~1~ τη δεύτερη ημέρα, οπότε η ανασφάλεια είναι ίση με ~1~.

input

1 5 8
.....#.#
...#..#.
..#.#...
.#......
#.......

output

4

Επεξήγηση του 2ου παραδείγματος:

Η μέγιστη τιμή που έχει το NFP είναι ~5~ (τις ημέρες ~6~ και ~8~) και η ελάχιστη τιμή είναι ~1~ (την ημέρα ~1~). Επομένως,η ανασφάλεια είναι ίση με ~5 - 1 = 4~.

input

2 3 3
...
##.
..#

.#.
#..
..#

output

1
2

Σημείωση: Για λόγους σαφήνειας, στα παραδείγματα υπάρχουν κενές γραμμές μεταξύ πινάκων. Στην περίπτωση δοκιμής δεν θα υπάρχουν κενές γραμμές μεταξύ των πινάκων.