CSES - HIIT Open 2017 - Contest
  • Time limit: 1.00 s
  • Memory limit: 512 MB

There were n coders from Aalto and n coders from UH in a programming contest. It turned out that after the contest, each coder had a distinct score.

Your task is to find the kth highest score in the contest.

Interaction

This is a special task: you are not directly given the scores of the coders, but you can only ask a set of queries.

Your program should interact with the grader using standard input and output. Initially, the grader gives you the values of n and k. After this, you may perform a set of queries. There are three types of queries:

  • “1 i” where 1 \le i \le n: get the ith highest score for Aalto
  • “2 i” where 1 \le i \le n: get the ith highest score for UH
  • “3 s”: report that the kth highest score is s

You are allowed to perform at most 100 queries, and your program must terminate after performing a query of type 3.

Constraints

  • 1 \le n \le 10^5
  • 1 \le k \le 2n
  • each score is between 1 and 10^9

Note

In some languages, you may need to flush the output after printing a line. Do not use efficient I/O methods.

Example

Assume that n=3, k=1 and the scores for Aalto are [9,4,3] and the scores for UH are [8,6,1]. Here is an example of a valid interaction:

  • Grader outputs:
3 1
  • Your program outputs:
1 1
  • Grader outputs:
9
  • Your program outputs:
2 1
  • Grader outputs:
8
  • Your program outputs:
3 9