Κακόβουλοι Βάτραχοι

Στη λίμνη υπάρχουν ~N~ νούφαρα σε μια σειρά τα οποία έχουν το καθένα ενα διαφορετικό όνομα, έναν φυσικό αριθμό από το ~1~ μέχρι το ~10^9~. Εσείς γνωρίζετε τη σειρά των νουφάρων, όμως το βράδυ κάποιοι βάτραχοι κάνουν την εξής διαδικασία για να σας μπερδέψουν.

Διαλέγουν έναν διαιρέτη του ~N~, έστω τον ~M~ με ~M\le \sqrt N~ και για ~\frac N M~ φορές διαλέγουν ~M~ νούφαρα που δεν έχουν ξαναδιαλέξει και τα βάζουν σε ένα κύκλο, έτσι ώστε αν ξεκινήσεις απο τον αριθμό που ήταν πρώτος στη σειρά και συνεχίσεις δεξιόστροφα, τότε θα πάρεις την μέχρι πρότινος σχετική σειρά των νουφαρων. 

Έπειτα ξεκινούν από το ~2~ο νούφαρο του κύκλου και δεξιόστροφα τα επανατοποθετούν στη σειρά, καλύπτωντας κάθε φορα την πρώτη κενή θέση.

Την επόμενο πρωί το βλέπει αυτό ο συνάδελφος σας και θέλει να σας βάλει έναν γρίφο ώστε να καταφερετε να βρείτε το ~M~. Έχετε το δικαιώμα να του κάνετε μόνο ~200~ ερωτήσεις του τύπου: Ποιο είναι το όνομα του νουφάρου που είναι ~k~-οστο στη σειρά;

Δεδομένα εισόδου (STDIN) - εξόδου (STDOUT)

Το πρόβλημα είναι διαδραστικό, που σημαίνει ότι δίνετε οδηγίες στον judge και αυτός σας απαντάει με πληροφορίες για να συνεχίσετε.

1. Η πρώτη γραμμή περιέχει έναν ακεραίο ~N~: το πλήθος των νουφάρων.(~N\le 2 \cdot 10^4~)
2. Η δεύτερη περιέχει ~N~ ακεραίους, τα ονόματα των νουφάρων στην αρχική σειρά.
3. Μπορείτε να κάνετε ~2~ τύπου ερωτήσεις:
   
   • 1 Κ, όπου ρωτάτε ποιο είναι το νούφαρο στη θέση ~K~ της νέας σειράς και παίρνετε την απάντηση
   • 2 Μ, όπου μαντεύετε τον αριθμό ~M~ του μεγέθους της ομάδας

Έχετε δικαίωμα να κάνετε ~200~ ερωτήσεις τύπου ~1~ και μόνο μία τύπου ~2~. Όταν την κάνετε, σταματά η κρίση του προγράμματος.

Παράδειγμα

Είσοδος (STDIN)

9
6 3 90 45 67 87 777 4 21

Πιθανά θα μπορούσε να γίνουν οι ακόλουθες ερωτήσεις-απαντήσεις:

Ενώ ένας πιθανός χωρισμός σε ομάδες και η επανατοποθέτηση των νουφάρων θα μπορούσε να είναι αυτή: ~1~η ομάδα: ~6, 4, 21~ ~2~η ομάδα: ~90, 87, 777~ ~3~η ομάδα: ~3, 45, 67~

Τελική σειρά: 4 45 87 67 3 777 90 21 6

Υποπροβλήματα

Για το ~25~% των περιπτώσεων, τα ονόματα των νουφάρων είναι η θέση τους στην αρχική σειρά.

Σημείωση: για να λειτουργεί σωστά ο διαδραστικός grader, πρέπει να κάνετε flush τις γραμμές που εκτυπώνετε. Αυτό γίνεαι ως εξής:

• Στην Python: η print() το κάνει αυτόματα

  print("1 8")
  

• Στην C/C++ (cstdio): χρησιμοποιείστε την printf κανονικά

  printf("1 8\n");
  

• Στην C++ (iostream): χρησιμοποιείστε το endl

  cout << "1 8" << endl;