Zagrade

Είναι γνωστό ότι η Κεντρική Υπηρεσία Πληροφοριών είναι επιφορτισμένη με τη συλλογή, την επεξεργασία και την ανάλυση πληροφοριών εθνικής ασφάλειας. Υπάρχει επίσης η υποψία ότι κατέχουν αρκετά μεγάλες συλλογές κοινώς χρησιμοποιούμενων κωδικών πρόσβασης υπολογιστών και αναπτύσσουν αρκετά εξελιγμένα εργαλεία που μπορούν να παραβιάσουν συστήματα υπολογιστών που προστατεύονται με κωδικό πρόσβασης.
Οι ρόλοι, όμως, έχουν αλλάξει και το καθήκον σας είναι να θέσετε σε κίνδυνο την ασφάλεια ενός διακομιστή της CIA. Καλή τύχη!
Φυσικά, γνωρίζουν καλά τα συνηθισμένα μοτίβα που χρησιμοποιούν οι άνθρωποι όταν θέτουν σε ένα σύστημα κωδικούς πρόσβασης. Επομένως, προσπάθειες όπως 123456, password, 1q2w3e4r ή welcome είναι μάταιες. Ευτυχώς, έχουμε αποκαλύψει ορισμένες πληροφορίες που μπορεί να σας φανούν χρήσιμες.
Δηλαδή, ο κύριος κωδικός τους αποτελείται από ακριβώς ~N~ χαρακτήρες με το N να είναι ένας ζυγός αριθμός. Ακριβώς οι μισοί από αυτούς τους χαρακτήρες είναι ίσοι με το άνοιγμα παρένθεσης ~('(')~, ενώ οι άλλοι μισοί είναι ίσοι με το κλείσιμο παρένθεσης ~(')')~. Επιπλέον, αντί για τη συνηθισμένη «Μήπως ξέχασες τον κωδικό πρόσβασής σου» λειτουργία, οι μηχανικοί τους αποφάσισαν να εκθέσουν ένα API στον ξεχασιάρη διαχειριστή. Χρησιμοποιώντας το API, ένας διαχειριστής μπορεί εκτελέσει το πολύ ~Q~ ερωτήματα ρωτώντας αν το διάστημα του κωδικού πρόσβασης από τον ~a~-οστό στο ~b~-οστό χαρακτήρα είναι μαθηματικά έγκυρο.
Η μαθηματική εγκυρότητα μιας ακολουθίας παρενθέσεων ορίζεται επαγωγικά ως:

• () είναι μια μαθηματικά έγκυρη ακολουθία.
• Εάν η ~A~ είναι μια μαθηματικά έγκυρη ακολουθία, τότε η (\(Α\)) είναι επίσης μια μαθηματικά έγκυρη ακολουθία.
• Εάν και η ~A~ και η ~B~ είναι μαθηματικά έγκυρες ακολουθίες, τότε η \(ΑΒ\) είναι επίσης μαθηματικά έγκυρο.

Αλληλεπίδραση

Αυτό είναι ένα διαδραστική πρόβλημα. Το πρόγραμμά σας πρέπει να επικοινωνεί με ένα πρόγραμμα που φτιάχτηκε από τους διοργανωτές και προσομοιώνει τη λειτουργικότητα ενός εικονικού ανασφαλούς διακομιστή της CIA από την περιγραφή του προβλήματος.
Πριν από την αλληλεπίδραση, το πρόγραμμά σας θα πρέπει να διαβάσει έναν άρτιο ακέραιο αριθμό ~N~ και έναν ακέραιο αριθμό ~Q~ από την είσοδο. Η σημασία και των δύο αριθμών βρίσκεται στην περιγραφή του προβλήματος.
Μετά από αυτό, το πρόγραμμά σας μπορεί να στείλει ερωτήματα γράφοντας στην έξοδο. Κάθε ερώτημα πρέπει να εκτυπώνεται σε ξεχωριστή γραμμή και έχει τη μορφή ~?\;a\;b~, όπου ισχύει ~1 \le a \le b \le N~. Αφού κάθε ερώτημα έχει γραφτεί, το πρόγραμμά σας θα πρέπει να καθαρίσει (flush) την έξοδο και να διαβάσει την απάντηση από την είσοδο. Η απάντηση είναι ~1~ εάν το διάστημα του κωδικού πρόσβασης που ξεκινά από τον ~a~-οστό και τελειώνει στον ~b~-οστό χαρακτήρα σχηματίζει μία μαθηματικά έγκυρη ακολουθία παρενθέσεων. Διαφορετικά, η απάντηση είναι ~0~. Το πρόγραμμά σας μπορεί να κάνει το πολύ ~Q~ τέτοια ερωτήματα.
Αφού το πρόγραμμά σας συναγάγει τον μυστικό κωδικό πρόσβασης, θα πρέπει να γράψει μια γραμμή στην έξοδο στη μορφή "! ~x_1,\,x_2,\,\ldots,\,x_N~", όπου οι χαρακτήρες ~x_1,\,x_2,\,\ldots,\,x_N~ αντιπροσωπεύουν τους χαρακτήρες του μυστικού κωδικού πρόσβασης. Μετά από αυτό, το πρόγραμμά σας θα πρέπει να ξεπλύνει ξανά την έξοδο και να τερματίσει την εκτέλεσή του.
Σημείωση: Μπορείτε να πραγματοποιήσετε λήψη του πηγαίου κώδικα από το σύστημα κρίσης με το οποίο αλληλεπιδράει σωστά ο διακομιστής CIA, συμπεριλαμβανομένου του ξεπλύματος εξόδου.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	14	~1 \le N \le 1\,000,\,Q = \frac{N^2}{4}~, ολόκληρος ο κωδικός είναι μια μαθηματικά έγκυρη ακολουθία.
2	4	~1 \le N \le 1\,000,\,Q = \frac{N^2}{4}~.
3	57	~1 \le N \le 100\,000,\,Q = N - 1~, ολόκληρος ο κωδικός είναι μια μαθηματικά έγκυρη ακολουθία.
4	51	~1 \le N \le 100\,000,\,Q = N - 1~.

Παράδειγματα Αλληλεπίδρασης

Είσοδος	Έξοδος	Σχόλιο
	6 9	Ο μυστικός κωδικός είναι ο ακόλουθος: ((())). Έχει μήκος 6 και το πρόγαμμα μπορεί να κάνει το πολύ ~9~ ερωτήσεις.
? 1 6	1	Ολόκληρος ο κωδικός είναι μαθηματικά έγκυρος.
? 1 2	0	Η υπακολουθία (( είναι μαθηματικά άκυρη.
? 2 4	0	Η υπακολουθία (() είναι μαθηματικά άκυρη.
? 2 5	1	Η υπακολουθία (()) είναι μαθηματικά έγκυρη.
? 3 4	1	Η υπακολουθία () είναι μαθηματικά έγκυρη.
! ((()))		Ο κωδικός πρόσβασης είναι σωστός και η CIA έχει παραβιαστεί.