Which k-th are you?

Kozak Vus possesses three secret arrays $a$, $b$, and $c$, each containing positive integers. The lengths of these arrays are $|a|$, $|b|$, and $|c|$, respectively, and they may differ from one another. Each array is sorted in non-decreasing order.

Your task is to determine the $k$-th smallest element in the sorted union of these arrays. This means you need to merge the three arrays into a single array of length $|a|+|b|+|c|$, sort it, and identify the $k$-th element.

Kozak Vus will not reveal the arrays directly, but he allows you to query specific elements. You can select an array and a position within that array, and Kozak Vus will provide the value at that position. You can perform this operation multiple times, across any of the arrays, but you are limited to a maximum of $Q$ queries.

Your goal is to find the $k$-th smallest element in the combined sorted array.

Input

The first line contains five integers: $|a|$, $|b|$, $|c|$, $k$, and $g$ ($0\le |a|,|b|,|c|\le 10^6$, $1\le k\le |a|+|b|+|c|$).

All numbers in the arrays are guaranteed to be within the range $[1,10^9]$.

The integer $g$ ($0\le g\le 9$) indicates the test group number (refer to Scoring).

Interaction

First, read the five integers $|a|$, $|b|$, $|c|$, $k$, and $g$.

To make a query, output "1 $r$ $m$", where $r$ specifies the array (1 for $a$, 2 for $b$, 3 for $c$), and $m$ is the position within that array. For example, querying the first element of array $a$ requires $m=1$, and querying the last element requires $m=|a|$.

An example query "1 3 10" requests the 10th element of array $c$.

After issuing a query, ensure you output a newline character and flush the output buffer to avoid a Time Limit Exceeded verdict. Use the following commands to flush the buffer:

• fflush(stdout) or cout.flush() in C++;

• System.out.flush() in Java;

• flush(output) in Pascal;

• stdout.flush() in Python;

Refer to the documentation for other languages.

If a query is invalid (exceeding the query limit or not meeting constraints), the interactor will return "-1" and terminate. If you receive "-1", immediately terminate your program to avoid an arbitrary verdict and receive a Wrong Answer verdict instead.

Once you determine the answer $x$, output "2 $x$".

Examples

3 3 3 2 0

2

5

5

2

6

6

6

7

10

1 1 1

1 1 2

1 1 3

1 2 1

1 2 2

1 2 3

1 3 1

1 3 2

1 3 3

2 2

Scoring

Let $n=\max (|a|,|b|,|c|)$, and $m=\max (a_i,b_j,c_t)$.

1. ($6$ points): $n\le 10,Q=150$;

2. ($4$ points): $|b|=0,|c|=0,m\le 2,Q=150$;

3. ($9$ points): $|c|=0,m\le 2,Q=125$;

4. ($10$ points): $m\le 2,Q=125$;

5. ($13$ points): $|c|=0,Q=1000$;

6. ($13$ points): $|c|=0,Q=125$;

7. ($17$ points): $Q=1000$;

8. ($21$ points): $Q=125$;

9. ($7$ points): $Q=65$.