A key is a string of length $n = 2k+1$ containing $1$ letter X, $k$ letters A, and $k$ letters B. For example, when $k=3$, BAXABAB is a key.

As shown in the figure below, these $2k+1$ letters can be arranged in a circle in clockwise order:

Among the $k$ letters A, some can be defined as "strong".

Specifically, starting from X and moving clockwise to a certain A, if the number of A's encountered is strictly greater than the number of B's encountered along the way, then this letter A is called strong.

For the example above, the $1$st and $2$nd letters A encountered clockwise from X are strong, while the $3$rd letter A is not strong.

The characteristic value of a key is the number of strong letters A it contains.

A genius child, KT, provided the following conclusion:

Suppose the positions of the $k$ letters A are fixed, but the positions of the remaining $k$ letters B and $1$ letter X are unknown. (Note that there are $k+1$ such keys, because there are $k+1$ possible positions for the letter X.)

It can be proven that the characteristic values of all these $k+1$ possible keys are distinct, and they are exactly $0, 1, 2, \dots, k$.

The figure on the next page shows a specific example, where the four sub-figures from left to right have $3, 2, 1, 0$ letters A that are strong, respectively.

Similarly, if the positions of the $k$ letters B are fixed, the characteristic values of all $k+1$ keys satisfying the condition are also distinct, and are exactly $0, 1, \dots, k$.

Now you need to solve the following three problems:

1. Given the positions of all A's in the key, find the position of X when the characteristic value of the key is $0$.
2. Given the positions of all A's in the key, find the position of X when the characteristic value of the key is $S$.
3. Given the positions of all B's in the key, find the position of X when the characteristic value of the key is $S$.

Note: The positions of the $2k+1$ letters in the string are numbered from $1$ to $2k+1$.

Examples

Suppose $k=3, S=2$. Then:

When the positions of A are $\{2, 4, 6\}$ and the characteristic value is $0$, the position of X is $7$;

When the positions of A are $\{2, 4, 6\}$ and the characteristic value is $2$, the position of X is $3$;

When the positions of B are $\{2, 4, 6\}$ and the characteristic value is $2$, the position of X is $5$.

Suppose $k=9, S=7$. Then:

When the positions of A are $\{3, 4, 5, 9, 10, 12, 13, 16, 19\}$ and the characteristic value is $0$, the position of X is $14$;

When the positions of A are $\{3, 4, 5, 9, 10, 12, 13, 16, 19\}$ and the characteristic value is $7$, the position of X is $18$;

When the positions of B are $\{3, 4, 5, 9, 10, 12, 13, 16, 19\}$ and the characteristic value is $7$, the position of X is $17$.

Input

The input contains only one test case.

The first line contains an integer $k$, as described in the problem.

The second line contains an integer $seed$, which will be used to generate a set $P$ of size $k$.

The third line contains an integer $S$, as described in the problem.

It is guaranteed that $0 \le S \le k \le 10^7$ and $1 \le seed \le 10000$.

The provided files include three files cipher.cpp/c/pas for generating the input data. The reading part is already completed; in the array $p[]$, if $p[i] = 0$, it means $i$ does not belong to set $P$, otherwise, $i$ belongs to set $P$.

Output

Output three lines, each containing one number, corresponding to the answers to the three sub-problems described in the problem statement.

That is:

1. The first number represents the position of X when the $k$-element set $P$ represents the positions of A and the characteristic value is $0$.
2. The second number represents the position of X when the $k$-element set $P$ represents the positions of A and the characteristic value is $S$.
3. The third number represents the position of X when the $k$-element set $P$ represents the positions of B and the characteristic value is $S$.

Examples

Input 1

5
3344
2

Output 1

10
1
2

Note 1

In the first example, the indices of elements where the $P$ array is $1$ are $5, 6, 7, 8, 9$.

Input 2

500000
4545
234567

Output 2

999992
246922
753067

Constraints

For $30\%$ of the data, $k \le 10^3$.

For $50\%$ of the data, $k \le 10^5$.

For $100\%$ of the data, $k \le 10^7$.

For each test point, the score is the sum of the scores of the following three parts:

1. If the first question is answered correctly, you will receive $3$ points.
2. If the second question is answered correctly, you will receive $4$ points.
3. If the third question is answered correctly, you will receive $3$ points.

If you only know part of the answers, please still output three numbers according to this format. Otherwise, you may not receive any points due to formatting errors.