Clickbait

Καθώς πλοηγούταν στο διαδίκτυο, ο Slavko συνάντησε μια διαφήμιση που εμφανίζει ένα σύστημα δοχείων και σωληνών (ένα παράδειγμα τέτοιου συστήματος φαίνεται στην παρακάτω εικόνα) με το μήνυμα: "Εάν το δοχείο 1 αρχίζει να γεμίζει με νερό, καθορίστε τη σειρά με την οποία γεμίζουν τα δοχεία".

Το σύστημα αποτελείται από ~K~ δοχεία που συμβολίζονται με αριθμούς από το ~1~ έως το ~K~ και μπορούμε να το περιγράψουμε χρησιμοποιώντας έναν πίνακα χαρακτήρων με ~N~ σειρές και ~M~ στήλες. Τα δοχεία έχουν σχήμα ορθογωνίου και τα περιγράμματα των δοχείων και των σωλήνων εμφανίζονται με τους ακόλουθους χαρακτήρες:

• '-' εάν είναι ένα οριζόντιο τμήμα του περιγράμματος,
• '|' εάν είναι κατακόρυφο τμήμα του περιγράμματος και
• "+" εάν είναι ένα σημείο όπου συνδέονται τα οριζόντια και κατακόρυφα μέρη του περιγράμματος. Μια εξαίρεση είναι όταν συνδέονται τα δοχεία και οι σωλήνες. Σε αυτήν την περίπτωση, κυριαρχεί το περίγραμμα του δοχείου (βλ. παραδείγματα δοκιμών).

Σε ένα αυθαίρετο μέρος μέσα σε κάθε κοντέινερ, υπάρχει μια σειρά από ψηφία που αντιπροσωπεύουν την ετικέτα του κοντέινερ και όλα τα άλλα πεδία στον πίνακα είναι ίσα με "." (κουκκίδα).

Όλα τα δοχεία, εκτός από αυτό που φέρει την ένδειξη 1, έχουν ακριβώς έναν σωλήνα τροφοδοσίας που εισέρχεται στο δοχείο στην επάνω πλευρά του. Το δοχείο με την ένδειξη 1 δεν έχει σωλήνα τροφοδοσίας.

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

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

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

Βοηθήστε τον Slavko και καθορίστε τη σειρά με την οποία θα γεμίσουν τα δοχεία.

Σημείωση:

• Τα δεδομένα της δοκιμής είναι τέτοια ώστε κάθε χαρακτήρας '+' περιβάλλεται με ακριβώς έναν χαρακτήρα '-' στην αριστερή ή τη δεξιά πλευρά και ακριβώς έναν χαρακτήρα '|' στην επάνω ή στην κάτω πλευρά, και όλους τους άλλους παρακείμενους χαρακτήρες στο οι κατευθύνσεις πάνω, κάτω, αριστερά και δεξιά θα είναι ίσες με "." (κουκκίδα).
• Τα μόνα σημεία όπου ο σωλήνας στον πίνακα βρίσκεται σε ένα πεδίο δίπλα στο περίγραμμα του δοχείου είναι τα σημεία όπου ο σωλήνας εισέρχεται ή εξέρχεται από το δοχείο. Με άλλα λόγια, ένας σωλήνας δεν θα τρέχει ποτέ ακριβώς δίπλα σε ένα δοχείο (εκτός από το σημείο που συνδέεται με το δοχείο). Η είσοδος για το σωλήνα παροχής επισημαίνεται με τον χαρακτήρα "|" πάνω από ένα δοχείο, ενώ η έξοδος του σωλήνα εκκένωσης επισημαίνεται με τον χαρακτήρα "-" στην πλευρική πλευρά ενός δοχείου.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς ~N~ και ~M\;(1 \le N, M \le 1\,000)~, τις διαστάσεις πίνακα. Οι ακόλουθες γραμμές ~N~ περιέχουν χαρακτήρες ~M~ που περιγράφουν το σύστημα κοντέινερ.

Έξοδος

Πρέπει να τυπώσετε ~K~ γραμμές. Η γραμμή ~i~ περιέχει την ετικέτα του δοχείου που γεμίζει ~i~-οστό (κατά σειρά). Μια λύση θα υπάρχει πάντα και θα είναι μοναδική.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 70% των συνολικών πόντων, θα ισχύει ~N, M \le 100~.

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

input

12 13
..+--+.......
+-|..|.......
|.|.1|--+....
|.+--+..|....
|......+----+
+---+..|..2.|
....|..+----+
.+--+........
.|...........
+---+........
|.3.|........
+---+........

output

2
3
1

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

Το δοχείο 1 αρχίζει να γεμίζει με νερό.
Η στάθμη του νερού στο δοχείο 1 αυξάνεται και σε μια στιγμή φτάνει στο επίπεδο του σωλήνα εκκένωσης που οδηγεί στο δοχείο 2. Το νερό ρέει μέσω του σωλήνα μέχρι να γεμίσει το δοχείο 2.
Μετά από αυτό, η στάθμη του νερού στο δοχείο 1 συνεχίζει να αυξάνεται μέχρι να φτάσει στο επίπεδο του σωλήνα εκκένωσης που οδηγεί στο δοχείο 3, το οποίο γεμίζει στη συνέχεια.
Τέλος, η στάθμη του νερού στο δοχείο 1 συνεχίζει να αυξάνεται και το δοχείο γεμίζει.

input

8 10
..........
.......+-+
...+---|1|
...|...+-+
...|......
..+-+.....
..|2|.....
..+-+.....

output

2
1