Skandi

Η Dragica είναι αρχηγός μιας τοπικής ημι-επαγγελματικής ομάδας μπόουλινγκ, είναι παθιασμένη σεφ και πιθανώς μία από τις καλύτερες λύτες σταυρόλεξων στην Κροατία. Ένα σταυρόλεξο αποτελείται από ~N \times M~ τετράγωνα διατεταγμένα σε ~N~ γραμμές και ~M~ στήλες. Μερικά από τα τετράγωνα είναι άδεια (και θα πρέπει να γεμίσουν με γράμματα απαντώντας σε ερωτήσεις) και μερικά από τα τετράγωνα είναι γεμάτα. Τα συμπληρωμένα τετράγωνα περιέχουν το πολύ δύο ερωτήσεις που θα πρέπει να απαντηθούν είτε οριζόντια προς τα δεξιά είτε κάθετα προς τα κάτω. Οι απαντήσεις στις ερωτήσεις γράφονται στα κενά τετράγωνα μέχρι να φτάσουμε στο όριο του σταυρολέξου ή σε ένα αρχικά συμπληρωμένο τετράγωνο. Ένα αρχικώς συμπληρωμένο τετράγωνο περιέχει μια οριζόντια ερώτηση εάν ένα τετράγωνο στα δεξιά υπάρχει και είναι κενό. Αντίστοιχα, ένα τετράγωνο που είναι αρχικά συμπληρωμένο περιέχει μια κάθετη ερώτηση εάν ένα τετράγωνο από κάτω του υπάρχει και είναι άδειο. Η Dragica συνήθως γνωρίζει όλες τις απαντήσεις στις ερωτήσεις του σταυρόλεξου, αλλά θέλει να διαβάσει και να απαντήσει όσο το δυνατόν λιγότερες ερωτήσεις και να λύσει όλο το σταυρόλεξο. Βοηθήστε την να πετύχει τον στόχο της.

Είσοδος

Η πρώτη γραμμή περιέχει τους ακέραιους αριθμούς ~N~ και ~M\;(2 \le N, M \le 500)~.

Κάθε μία από τις επόμενες ~N~ γραμμές περιέχει ~M~ χαρακτήρες "0" ή "1", όπου το "0" υποδηλώνει ένα κενό τετράγωνο που θα πρέπει να συμπληρώνεται απαντώντας σε μια ερώτηση και το "1" υποδηλώνει ένα αρχικά συμπληρωμένο τετράγωνο που μπορεί να περιέχει το πολύ δύο ερωτήσεις όπως εξηγούνται στην περιγραφή της εργασίας. Η πρώτη γραμμή και η πρώτη στήλη θα γεμίσουν με χαρακτήρες "1".

Είναι εγγυημένο ότι θα υπάρχει τουλάχιστον ένας χαρακτήρας "0" στην είσοδο.

Έξοδος

Στην πρώτη γραμμή θα πρέπει να δώσετε τον ελάχιστο αριθμό ερωτήσεων που μπορούν να απαντηθούν για να λυθεί ένα ολόκληρο σταυρόλεξο. Ας συμβολίσουμε αυτόν τον αριθμό με ~X~.

Κάθε μία από τις επόμενες γραμμές ~X~ πρέπει να περιγράφει μία ερώτηση που πρέπει να απαντηθεί. Η περιγραφή της ερώτησης θα πρέπει να διατυπωθεί με τη μορφή ~R\;C~ κατεύθυνση, όπου ~R~ είναι ο αριθμός σειράς της ερώτησης, ~C~ είναι ο αριθμός στήλης της ερώτησης. Η κατεύθυνση της είναι είτε "DESNO" (στα Κροατικά το "ΔΕΞΙΑ") ή "DOLJE" (στα Κροατικά το "ΚΑΤΩ") ανάλογα με το αν η Dragica θα πρέπει να απαντήσει στην κάθετη ή οριζόντια ερώτηση.

Εάν υπάρχουν πολλές λύσεις, βγάλε οποιαδήποτε από αυτές.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	18	Θα υπάρχουν το πολύ 9 τετράγωνα με "1"
2	32	~N \le 500~ και ~M \le 10~
3	60	Κανένας επιπλέον περιορισμός.

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

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

input

4 5
11111
10000
10000
10000

output

3
2 1 DESNO
3 1 DESNO
4 1 DESNO

input

6 4
1111
1011
1000
1011
1010
1000

output

4
1 2 DOLJE
4 4 DOLJE
5 3 DOLJE
3 1 DESNO

input

9 8
11111111
10000000
10001000
10010001
11100001
10100110
10001000
10100001
10010001

output

14
5 2 DOLJE
5 8 DOLJE
8 3 DOLJE
2 1 DESNO
3 1 DESNO
3 5 DESNO
4 1 DESNO
4 4 DESNO
5 3 DESNO
6 3 DESNO
7 1 DESNO
7 5 DESNO
8 3 DESNO
9 4 DESNO

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

Ένα παράδειγμα πραγματικού σταυρόλεξου που ισοδυναμεί με αυτό που περιγράφεται στο παράδειγμα δίνεται στην επόμενη σελίδα. Τα αρχικά γεμάτα τετράγωνα είναι χρωματισμένα μαύρα και αυτά και τα τετράγωνα που περιέχουν τουλάχιστον μία ερώτηση είναι αριθμημένα. Κάτω από το παζλ μπορείτε να δείτε τις ερωτήσεις που θα πρέπει να λυθούν προς τα δεξιά (στήλη "οριζόντια") και εκείνα που θα πρέπει να λυθούν προς τα κάτω (στήλη "κάθετα"). Σημειώστε ότι ορισμένα τετράγωνα που είχαν αρχικά συμπληρωθεί δεν περιέχουν ερωτήσεις, μερικά περιέχουν μία ερώτηση (π.χ. 8 και 13), ενώ ορισμένα περιέχουν δύο ερωτήσεις (π.χ. 10 και 12). Για να λύσετε αυτό το σταυρόλεξο εσείς θα πρέπει να γνωρίζετε τις απαντήσεις σε τουλάχιστον 14 ερωτήσεις που αναφέρονται στην έξοδο. Μπορείτε να το λύσετε;