Gradient Descent

Ο Troy θέλει να παίξει το ακόλουθο παιχνίδι μαζί σας.

Έχει ένα πλέγμα με ~R~ σειρές και ~C~ στήλες. Οι σειρές είναι αριθμημένες από το ~1~ έως το ~R~ και οι σειρές είναι αριθμημένες από το ~1~ έως το ~C~. Έστω το κελί στη σειρά ~p~ και στη στήλη ~q~ να συμβολίζεται ως (~p~, ~q~).

Υπάρχουν ~N~ κέρματα αριθμημένα από το ~1~ έως το ~N~. Το νόμισμα ~i~ είναι τοποθετημένο στη θέση (~X_i~, ~Y_i~) όπου ~1~ ~\le~ ~X_i~ ~\le~ ~R~ και ~1~ ~\le~ ~Y_i~ ~\le~ ~C~. Μπορεί να υπάρχουν πολλαπλά νομίσματα στο ίδιο κελί. Σε ένα δευτερόλεπτο, ο Troy μπορεί να μετακινήσει ένα νόμισμα σε ένα οριζόντια ή κάθετα γειτονικό κελί. Η βαθμολογία ενός κελιού ορίζεται ως ο ελάχιστον αριθμός δευτερολέπτων που χρειάζεται ο Troy για να μετακινήσει κάθε νόμισμα σε αυτό το κελί.

Ο στόχος σας είναι να βρείτε την ελάχιστη βαθμολογία οποιουδήποτε κελιού στο δίκτυο. Δυστυχώς, ο Troy δεν σας λέειπόσα νομίσματα υπάρχουν ή που βρίσκονται. Ωστόσο, μπορείτε να του κάνετε ερωτήσεις. Μπορείτε να ρωτήσετε τον Troy να σας πει τη βαθμολογία οποιουδήποτε κελιού (~p~, ~q~). Μπορείτε να κάνετε το πολύ ~K~ ερωτήσεις πριν βαρεθεί ο Troy.

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

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

Αρχικά, διαβάστε μία γραμμή με τρεις ακέραιους ~R~, ~C~, ~K~ (~1~ ~\le~ ~R~, ~C~ ~\le~ ~10\,000\,000~, ~1~ ~\le~ ~K~ ~\le~ ~170~).

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

Για να κάνετε μια ερώτηση σχετικά με το (~p~, ~q~) (~1~ ~\le~ ~p~ ~\le~ ~R~, ~1~ ~\le~ ~q~ ~\le~ ~C~), εκτυπώστε μία γραμμή της μορφής "? ~p~ ~q~". Έπειτα, διαβάστε μία γραμμή διαβάστε μία γραμμή με έναν ακέραιο ~s~ (~0~ ~\le~ ~s~ ~\le~ ~2\,000\,000\,000~), τη βαθμολογία του (~p~, ~q~).

Αφού το πρόγραμμά σας καθορίσει ότι η ελάχιστη βαθμολογία είναι ~Z~, εκτυπώστε μία γραμμή της μορφής "! ~Z~". Το πρόγραμμά σας θα πρέπει να τερματιστεί αμέσως μετά την εκτύπωση αυτής της γραμμής.

Η έξοδος θα πρέπει να γίνεται flush αφού εκτυπωθεί κάθε γραμμή, συμπεριλαμβανομένης της τελευταίας γραμμής. Για να κάνετε flush μπορείτε να χρησιμοποιήσετε την παρακάτω εντολή: fflush(stdout) ή cout << endl στην C/C++, System.out.flush() στην Java και flush(output) στην Pascal.

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

Για κάθε περίπτωση ελέγχου, το σύστημα βαθμολόγησης θα έχει σταθερές ακέραιες τιμές ~N~, ~R~, ~C~, ~K~, ~X_1~, ..., ~X_N~, ~Y_1~, ..., ~Y_N~ (~1~ ~\le~ ~N~ ~\le~ ~100~, ~1~ ~\le~ ~X_i~ ~\le~ ~R~, ~1~ ~\le~ ~Y_i~ ~\le~ ~C~). Αυτές οι τιμές θα παραμείνουν σταθερές όσο τρέχει το πρόγραμμά σας. Δηλαδή, το σύστημα βαθμολόγησης δεν είναι προσαρμοστικό.

Βαθμολογία

Για `~5~ από τους ~25~ διαθέσιμους βαθμούς, ~R~ = ~1~, ~C~ ~\le~ ~90~ και ~K~ = ~90~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~R~ = ~1~ και ~K~ = ~90~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~K~ = ~170~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~K~ = ~100~.

Για τους επιπλέον ~5~ βαθμούς, ~K~ = ~75~.

Αλληλεπιδράσεις

Επεξήγηση της πρώτης αλληλεπίδρασης

Αυτό το δείγμα αντιστοιχεί στα νομίσματα στα κελιά (~1~, ~2~), (~1~, ~4~) και (~1~, ~10~). Είναι εγγυημένο ότι αυτό το δείγμα θα αντιστοιχεί με το δοκιμαστικό δείγμα στον βαθμολογητή.

Η βαθμολογία του κελιού (~1~, ~3~) είναι ~1~ + ~1~ + ~7~ = ~9~.

Η βαθμολογία του κελιού (~1~, ~7~) είναι ~5~ + ~3~ + ~3~ = ~11~.

Η βαθμολογία του κελιού (~1~, ~4~) είναι ~2~ + ~0~ + ~6~ = ~8~ και είναι η ελάχιστη στο πλέγμα.

Πληροφοριακά, παρακάτω βρίσκονται οι βαθμολογίες αυτού του παραδείγματος:

Επεξήγηση της δεύτερης αλληλεπίδρασης

Αυτό το δείχμα αντιστοιχεί στα νομίσματα στα κελιά (~2~, ~3~), (~2~, ~3~), (~4~, ~3~) και (~5~, ~1~).