Description

Today, your good friend—Minke—came to you and claimed that he proved “half” of the graph coloring problem, and he wants you to check whether his method is correct. If you can help him verify it, he will consider sharing the Turing Award prize money with you.

Minke claims that he solved the following problem: for an undirected graph with $n$ vertices, where all vertices are numbered $1,2,\ldots,n$, there is an edge between two vertices if and only if their indices differ by at most $k$ in modulo $n$. That is, there is an undirected edge between $(x,y)$ if and only if $x \neq y$ and there exists an integer $i$ satisfying $1 \le i \le k$ such that

or

He can quickly compute the chromatic number of this graph. As a judge, you only need to solve a decision problem: for each test case, Minke will give three positive integers $n$, $k$, and $x$. When $n$ and $k$ are fixed (with the meanings described above), he believes the chromatic number of this graph is $x$. You need to determine whether his answer is correct.

If you think his answer is correct, output one line Correct, but it doesn't necessarily mean that you can win the Turing Award.. If you think his answer is wrong, output Wrong, don't cheat me, you are too far away from the Turing Award. in the first line. To make your answer more convincing, you also need to output a character 0 or 1 in the second line: 0 means you think Minke’s answer is smaller than the actual chromatic number of this graph, and 1 means you think his answer is larger than the actual chromatic number. If you think this problem cannot be judged accurately with current computing power, output one line The problem is unsolvable, please stop cheating me, Mr.Minke..

Input Format

The input contains only one line, with three positive integers $n, k, x$, with meanings as described in the statement.

Constraints: $1 \le x, n \le 10^{1,000,000}$, $1 \le k \le 100$. All inputs are positive integers, and for all testdata, $n$ can only satisfy $n \le 10^5$ or $n \ge 10^{100}$.

Output Format

Output consists of $1$ or $2$ lines. The first line is your judgment result, in the format described in the statement.

If you successfully make a judgment and think Minke’s answer is wrong, then you need to output a character 0 or 1 in the second line: 0 means Minke’s answer is too small, and 1 means Minke’s answer is too large.

6 2 4

Wrong, don't cheat me, you are too far away from the Turing Award.
1

Hint

[Sample Explanation]

Obviously, coloring vertices $1 \sim 6$ as $1, 2, 3, 1, 2, 3$ is feasible, so when $n = 6$ and $k = 2$, the chromatic number is $3$.

[Hint]

1. If you have no idea, please read the Constraints in the statement again. It may help you solve the problem.
2. Hint 1 may be useless.

[Source]

From the 2021 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2021).

Solutions and other resources can be found at https://github.com/yylidiw/thupc_1/tree/master.

Translated by ChatGPT 5