Background

kls is a person who always wins.

Problem Description

kls has recently been playing a game similar to 2048. The rules are as follows.

At the beginning, there are $n$ blocks, and each block has an integer from $1$ to $m$ written on it.

kls can perform two kinds of operations.

1. Choose two blocks with the same number (they do not have to be adjacent) and merge them into one block whose number is twice the original.
2. Decrease the number on a block.

There is no limit on the number of operations. The final score is the maximum number among all blocks.

Since kls is going to spend time with a girl and has no time to keep playing, he wants you to help him compute the maximum score he can get.

Input Format

Because the testdata may be large and direct input may easily time out, kls provides you with a C++ random number generator.

void generate_array(int a[], int n, int m, int seed) {
    unsigned x = seed;
    for (int i = 0; i < n; ++i) {
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
        a[i] = x % m + 1;
    }
}

Copy this function into your program. Use a sufficiently large array, and call this function with $n$, $m$, and $seed$ given in the input as parameters. Then the numbers in this array are the initial numbers on the blocks (the index starts from 0).

Input one line with three numbers $n, m, seed$, with meanings as above.

Output Format

Output one line with one number, representing the maximum score.

5 10 233

24

5 50 3

48

1000 1000 666

374784

Hint

Sample Explanation

The numbers generated in sample 1 are 6 10 7 5 4.

The numbers generated in sample 2 are 8 12 48 4 4.

Constraints

For 30% of the testdata, $n, m \le 10$.

For 60% of the testdata, $n, m \le 10^5$.

For 100% of the testdata, $n, m \le 10^7$, $1 \le seed \le 10^9$.

Translated by ChatGPT 5