Problem Description

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 a clockwise order:

Among the k letters A, some are defined as "strong". Specifically, starting from X and moving clockwise to an A, if the number of A's encountered is strictly more than the number of B's, then this letter A is considered strong.

For the example above, the first and second A's clockwise from letter X are strong, while the third A is not.

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

Genius kid KT has made a 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 possible keys because there are k + 1 possible positions for letter X.)

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

Similarly, if the positions of the k letters B are fixed, the characteristic values of all k + 1 possible keys are also distinct and exactly 0, 1, ..., k.

Now, you need to solve the following three problems:

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

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

Example 1

Assume 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.

Example 2

Assume 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 Format

A single test case is provided.

The first line contains an integer k, as described.

The second line contains an integer seed, which will be used to generate a k-element set P.

The third line contains an integer S, as described.

It is guaranteed that 0 ≤ S ≤ k ≤ 10^7. 1 ≤ seed ≤ 10000.

In the cipher/ directory, there are two files cipher.cpp/pas for generating input data. The reading part is already done, and in the array p[], if p[i] = 0, it means i does not belong to set P; otherwise, i belongs to set P.

Baidu Netdisk Link>> Password: 9vr3 Please compile it yourself.

#include <stdio.h>
#include <string.h>
int p[20000005];
int seed, n, k, S;
int getrand() {
    seed = ((seed * 12321) ^ 9999) % 32768;
    return seed;
}
void generateData() {
    scanf( "%d%d%d", &k, &seed, &S );
    int t = 0;
    n = k * 2 + 1;
    memset(p, 0, sizeof(p));
    for( int i = 1; i <= n; ++i ) {
        p[i] = (getrand() / 128) % 2;
        t += p[i];
    }
    int i = 1;
    while( t > k ) {
        while ( p[i] == 0 ) ++i;
        p[i] = 0;
        --t;
    }
    while( t < k ) {
        while( p[i] == 1 ) ++i;
        p[i] = 1;
        ++t;
    }
}
int main() {
    generateData();
    return 0;
}

Output Format

Output three lines, each containing a number, corresponding to the answers to the three sub-problems in the problem description.

That is:
1. The first number indicates 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 indicates 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 indicates the position of X when the k-element set P represents the positions of B and the characteristic value is S.

Sample Input and Output

Input Sample #1

5
3344
2

Output Sample #1

10
1
2

Input Sample #2

500000
4545
234567

Output Sample #2

999992
246922
753067

Notes/Hints

Sample Explanation

In the first sample, the indices of elements in the P array that are 1 are 5, 6, 7, 8, 9.

Data Range and Constraints

For 30% of the data, k ≤ 10^3.

For 50% of the data, k ≤ 10^5.

For 100% of the data, k ≤ 10^7.

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

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

If you only know part of the answers, please also output three numbers strictly in this format. Otherwise, you may not get points due to format errors.

见题面 Input 部分

见题面 Output 部分