Jabuke

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

Η Εθνική Στατιστική Υπηρεσία παρακολουθεί την πτώση μήλων σε έναν οπωροφόρο κήπο για ~G~ συνεχόμενα έτη. Ο οπωροφόρος κήπος μπορεί να αναπαρασταθεί ως πίνακας με διαστάσεις ~R \times S~. Κάθε πεδίο του πίνακα μπορεί να περιέχει περισσότερες από μία μηλιές.

Είναι αρκετά ενδιαφέρον ότι κάθε χρόνο γινόταν ακριβώς μια πτώση μήλων, οπότε το Τμήμα αποφάσισε να γράψει ~G~ ζεύγη αριθμών ~(r_i,\;s_i)~ που δηλώνουν τη γραμμή και τη στήλη της τοποθεσίας όπου έπεσε το μήλο κατά το ~i~-οστό έτος. Επιπλέον, μέχρι το επόμενο έτος, ένα νέο δέντρο είχε φυτρώσει σε αυτή τη θέση.

Ο στόχος σας είναι να προσδιορίσετε την τετραγωνισμένη απόσταση (squared distance) μεταξύ του πλησιέστερου δέντρου και του μήλου που έπεσε, μετρημένη σε πεδία μονάδων του πίνακα (υποθέτουμε ότι είναι εκείνο το δέντρο από το οποίο έπεσε το μήλο).

Η απόσταση μεταξύ των πεδίων ~(r_1,\;s_1)~ και ~(r_2,\;s_2 )~ στον πίνακα υπολογίζεται ως εξής:

~d((r_1,\;s_1),\;(r_2,\;s_2 )) = \sqrt{\;(r_1 - r_2 )^2 \;+\;(s_1 - s_2 )^2\;}~

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους αριθμούς, ~R~ και ~S\;(1 \leq R,\;S \leq 500)~, τον αριθμό των γραμμών και των στηλών του πίνακα.

Κάθε μία από τις ακόλουθες ~R~ γραμμές περιέχει ~S~ χαρακτήρες "~x~" ή ".". Ο χαρακτήρας "." υποδηλώνει ένα κενό πεδίο και ο χαρακτήρας "~x~" υποδηλώνει ένα πεδίο με τουλάχιστον ένα δέντρο. Ο οπωρόκηπος θα περιέχει αρχικά τουλάχιστον ένα δέντρο.

Μετά από αυτό, ακολουθεί ένας ακέραιος αριθμός ~G\;(1 \leq G \leq 10^5 )~, ο αριθμός των ετών που ο οπωρόκηπος ήταν υπό παρατήρηση.

Κάθε μία από τις ακόλουθες ~G~ γραμμές περιγράφει τις πτώσεις των μήλων. Κάθε γραμμή περιέχει ένα ζεύγος ακεραίων αριθμών ~(r_i,\;s_i )~ που δηλώνουν τη γραμμή και τη στήλη της τοποθεσίας όπου έπεσε το μήλο το 1ο έτος.

Έξοδος

Τυπώστε ~G~ αριθμούς, τις απαιτούμενες τετραγωνισμένες αποστάσεις της εργασίας, καθένα στη δική του γραμμή.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας ~30~% των συνολικών πόντων, θα κατέχει ~G \leq 500~.

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

input

3 3
x..
...
...
3
1 3
1 1
3 2

output

4
0
5

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

Το πιο κοντινό μήλο σε αυτό που έπεσε τον πρώτο χρόνο είναι το μήλο στο χωράφι ~(1\;1)~. Το μήλο που έπεσε τον δεύτερο χρόνο έπεσε ακριβώς στο χωράφι όπου βρίσκεται το δέντρο, άρα η τετραγωνισμένη απόσταση είναι 0. Το μήλο που έπεσε τον τρίτο χρόνο είναι εξίσου μακριά και από τα τρία υπάρχοντα δέντρα στον οπωροφόρo κήπο.

input

5 5
..x..
....x
.....
.....
.....
4
3 1
5 3
4 5
3 5

output

8
8
4
1