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 $k$th 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 $i$th highest score for Aalto
  • “2 $i$” where $1 \le i \le n$: get the $i$th highest score for UH
  • “3 $s$”: report that the $k$th 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