Twin Cookies

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

Η Sophie ετοιμάζει το πάρτι γενεθλίων των διδύμων. Τα δίδυμα λατρεύουν τα μπισκότα. Για τα γενέθλιά τους θα ήθελαν να δοκιμάσουν κάτι νέο: cookies από την εταιρεία Unique Cookie Tastiness (UCTC).

Κάθε μπισκότο που παράγεται από την UCTC έχει ακέραια τιμή γευσιγνωσίας μεταξύ ~1~ και ~10^{16}~ αποκλειστικά. Δεδομένου ότι τα δίδυμα της Sophie ζηλεύουν το ένα το άλλο, καθένα από αυτά πρέπει να λαμβάνει μπισκότα με το ίδιο άθροισμα τιμών γευσιγνωσίας.

Η UCTC δέχεται μόνο παραγγελίες από ακριβώς ~n~ μπισκότα. Σε κάθε παραγγελία ο πελάτης καθορίζει την νοστιμιά του καθενός από τα μπισκότα που θέλει.

Παραμένοντας πιστή στο όνομά της, η εταιρεία Unique Cookie Tastiness αρνείται να παράγει δύο μπισκότα της ίδιας γεύσης για τον ίδιο πελάτη. Η Sophie πρέπει να βεβαιωθεί ότι δεν παραγγέλνει ποτέ την ίδια λιχουδιά δύο φορές - ούτε στην ίδια σειρά, ούτε σε δύο διαφορετικές παραγγελίες. Η Sophie δεν έχει αγοράσει ποτέ από το UCTC στο παρελθόν, οπότε μπορεί να παραγγείλει κάθε διαθέσιμη λιχουδιά μία φορά.

Υπάρχει ένα ακόμη εμπόδιο στον τρόπο της Sophie: Είναι γνωστό ότι η υπηρεσία παράδοσης της UCTC είναι απαίσια. Κάθε φορά που ένας πελάτης παραγγέλνει μπισκότα, μόνο ένα από αυτά τα μπισκότα φτάνει τελικά στον πελάτη. Τα υπόλοιπα τρώγονται στο δρόμο από τους υπαλλήλους της υπηρεσίας παράδοσης. Ο πελάτης δεν μπορεί να ξέρει ποιο από τα ~n~ παραγγελθέντα μπισκότα θα παραδοθούν τελικά σε αυτόν.

Δεδομένου ότι τα γενέθλια πλησιάζουν γρήγορα, η Sophie έχει το χρόνο να κάνει το πολύ ~101~ παραγγελίες. Ο στόχος σας είναι να τη βοηθήσετε.

Πιο συγκεκριμένα, πρέπει να κάνετε τα εξής:

1. Πρώτα, παραγγείλετε τα μπισκότα. Μπορείτε να πραγματοποιήσετε έως και ~101~ παραγγελίες, καθεμία από τις οποίες αξίζει ακριβώς ~n~ επιθυμητές τιμές γευστικότητας. Κάνετε μια παραγγελία κάθε φορά. Αμέσως μετά από κάθε παραγγελία θα σας δίνεται η γευστικότητα ενός cookie που πραγματικά λάβατε.

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

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

Έξοδος

Κάθε φορά που το πρόγραμμά σας τυπώνει μία ή περισσότερες γραμμές στην έξοδο, πρέπει να ακολουθείτε την ενέργεια "έκθεσης" της ροής εξόδου / flushing the output stream. Αυτό είναι απαραίτητο για να βεβαιωθείτε ότι τα δεδομένα που εξάγετε φτάνουν αμέσως στο βαθμολογητή.

Παραδείγματα για το πώς μπορεί να γίνει αυτό:

• Σε C++ υπάρχουν πολλές επιλογές.
  • fflush(stdout);
  • std::cout << std::flush;
  • std::cout << std::endl; (σημειώστε ότι αυτό εκτυπώνει μια επιπλέον νέα γραμμή)
  • διαβάζοντας από std::cin επίσης "εκθέτει" την έξοδο
• σε Java, μπορείτε να χρησιμοποιήσετε System.out.flush()
• σε Python, μπορείτε να χρησιμοποιήσετε sys.stdout.flush()

Πρωτόκολλο αλληλεπίδρασης

Το πρόγραμμά σας θα πρέπει να εκτελεί την ακόλουθη σειρά ενεργειών:

1. Διαβάστε την τιμή από την είσοδο.
2. Το πολύ ~101~ φορές:
   1. Πρώτα, γράψτε μια γραμμή που περιγράφει μια σειρά μπισκότων στην έξοδο.
   2. Στη συνέχεια, διαβάστε την γευστικότητα του μπισκότου που λάβατε από την είσοδο. Είναι εγγυημένο ότι αυτή η τιμή είναι μεταξύ των τιμών που ήταν στην τρέχουσα σειρά.
3. Παραγάγετε τρεις γραμμές που περιγράφουν έναν έγκυρο τρόπο για να δώσετε μερικά από τα μπισκότα που λάβατε για τα δίδυμα.

Ο βαθμολογητής θα γράψει κάθε ακέραιο σε ξεχωριστή γραμμή.

Για να παραγγείλετε μπισκότα, δημιουργήστε μία γραμμή με ~?~ ακολουθούμενη από ~n~ ακέραιους: οι τιμές γευστικότητας των μπισκότων που θέλετε να παραγγείλετε. Αφήνετε ένα κενό πριν από κάθε ακέραιο αριθμό. μεμονωμένου χώρου πριν από κάθε ένα ακέραιο.

Θυμηθείτε ότι μπορείτε να κάνετε το πολύ ~101~ παραγγελίες και ότι δεν επιτρέπεται να χρησιμοποιείτε την ίδια αξία γευστικότητας δύο φορές.

Μόλις παραγγείλετε αρκετά μπισκότα, τυπώστε τις τρεις τελευταίες γραμμές που περιγράφουν ποια cookies πρέπει να δώσει η Sophie στα δίδυμα.

Η πρώτη από αυτές τις γραμμές πρέπει να έχει τη μορφή "~!\,m\,k~" με ~m, k > 0~: τον αριθμό των μπισκότων που πρέπει να λάβουν το πρώτο και το δεύτερο δίδυμο, αντίστοιχα.

Η δεύτερη από αυτές τις γραμμές πρέπει να περιέχει ακέραιους αριθμούς χωρισμένους από μεμονωμένα κενά: οι τιμές γευσιγνωσίας των μπισκότων που πρέπει να λάβει το πρώτο δίδυμο.

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

Η έξοδος πρέπει να πληροί τις ακόλουθες προϋποθέσεις:

1. Κάθε δίδυμο πρέπει να λαμβάνει τουλάχιστον ένα μπισκότο.
2. Κάθε δίδυμο θα πρέπει να λαμβάνει μπισκότα με την ίδια συνολική γευστικότητα.
3. Μόνο τα μπισκότα που λάβατε πραγματικά μετά την παραγγελία σας μπορούν να χρησιμοποιηθούν.
4. Κάθε ένα από αυτά τα μπισκότα μπορεί να δοθεί μόνο σε ένα από τα δίδυμα.

Κάθε έξοδος που πληροί αυτούς τους όρους θα γίνει αποδεκτή. Συγκεκριμένα, μπορείτε να εξάγετε τα επιλεγμένα μπισκότα με οποιαδήποτε σειρά.

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

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~8~	~n = 1~
~2~	~9~	~1 \le n \le 2~
~3~	~18~	~1 \le n \le 25~
~4~	~16~	~1 \le n \le 200~
~5~	~13~	~1 \le n \le 1000~
~6~	~36~	~1 \le n \le 5000~

Παράδειγμα

input

1
13
7
31
12
5
3

output

? 13
? 7
? 31
? 12
? 5
? 3
! 2 3
7 13
12 5 3

input

2
7
2
5

output

? 3 7
? 2 8
? 1 5
! 2 1
2 5
7

Σημείωση: Παραδείγματα εισόδου και εξόδου πρέπει να διαβάζονται ανά σειρά. Το πρόγραμμά σας διαβάζει εναλλάξ μια τιμή από την τυπική είσοδο και γράφει μία γραμμή (ή τρεις γραμμές στο τέλος) στην τυπική έξοδο.

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