Retro

Ο μικρός Mirko πήρε μια κονσόλα βιντεοπαιχνιδιών για τα Χριστούγεννα. Δεν ήταν ένα Playstation 4 ή ένα Xbox One, αλλά το Atari 2600, και ήρθε με ένα δωρεάν παιχνίδι. Ο πρωταγωνιστής του παιχνιδιού στέκεται στο κάτω μέρος της οθόνης και υπάρχουν διάφορα αντικείμενα διασκορπισμένα στο υπόλοιπο μέρος της οθόνης, που πέφτουν προς το κάτω μέρος.

Πιο συγκεκριμένα, η οθόνη μπορεί να αναπαρασταθεί ως ένα πλέγμα ~R \times S~ pixels διατεταγμένα σε σειρές ~R~ και στήλες ~S~. Ο πρωταγωνιστής καταλαμβάνει ένα pixel της χαμηλότερης γραμμής και σημειώνεται με το «M». Τα υπόλοιπα πίξελς επισημαίνονται με μερικούς από τους χαρακτήρες: '.' (κενός χώρος), '*' (βόμβα), '(' (ανοιχτή αγκύλη) ή ')' (κλειστή αγκύλη).

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

Μια έγκυρη έκφραση παρένθεσης ορίζεται επαγωγικά με τον ακόλουθο τρόπο:

• Το "()" είναι μια έγκυρη έκφραση.
• Αν το a είναι μια έγκυρη έκφραση, τότε το "(a)" είναι επίσης έγκυρη έκφραση.
• Εάν τα a και b είναι έγκυρες εκφράσεις, τότε το "ab" είναι επίσης έγκυρη έκφραση.

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

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους θετικούς ακέραιους αριθμούς ~R~ και ~S\;(1 \le R, S \le 300)~ που αντιπροσωπεύουν τις διαστάσεις της οθόνης.
Κάθε μία από τις ακόλουθες ~R~ γραμμές περιέχει ~S~ χαρακτήρες "M", ".", "*", "(" ή ")" που αντιπροσωπεύουν την αρχική κατάσταση της οθόνης.
Τα δεδομένα δοκιμής θα είναι τέτοια ώστε να υπάρχει πάντα τουλάχιστον μία έγκυρη έκφραση αγκύλης που είναι δυνατό να αποκτηθεί.

Έξοδος

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

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 25% των συνολικών πόντων, θα κρατήσει ~1 \le R \le 15~.
Σε δοκιμαστικές περιπτώσεις που αξίζει το 50% των συνολικών πόντων, θα κρατήσει ~1 \le R \le 100~.

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

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

input

5​ ​4
..).
.)(.
(.)*
*(.*
..M.

output

4
(())

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

Οι κινήσεις του πρωταγωνιστή είναι: αριστερά, αριστερά, δεξιά δεξιά.

input

6 3
)(.
*..
(**
)()
().
M..

output

4
()()

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

Οι κινήσεις του πρωταγωνιστή είναι: ακίνητος, ακίνητος, ακίνητος, δεξιά, αριστερά.

input

6 3
((.
*..
(**
)()
().
M..

output

2
()

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

Οι κινήσεις του πρωταγωνιστή είναι: ακίνητος, ακίνητος, δεξιά.