Warm-up round completed


Show one task per page / all tasks on one page

"D" Knights and Knaves
Time limit 2 seconds
Memory limit 256 megabytes

Space Ranger has arranged his army in two rows of k soldiers. Neighbors of a soldier in this arrangement are soldiers to the left of it in the same row, to the right of it in the same row, and at the same position in the opposite row.

Ranger knows that there are knights that always tell truth, and knaves that lie to at least one question asked in his army.

Ranger chose one or two questions from the set:

  • "Is it true that there are exactly x knights among your neighbors?"
  • "Is it true that there are exactly y knaves among your neighbors?"
and asked each soldier. Each soldier was asked questions with the same values of x and/or y.

Suddenly all soldiers answers "yes" to all questions asked.

Now Space Ranger wants to know what minimal and maximal number of knights can be there in his army. Help him to find out.

Let us consider the second sample test. Each row has 5 soldiers, the questions asked are «Is it true that exactly one of your neighbors is a knight?» and «Is it true that exactly two of your neighbors are knaves?»

First, all soldiers can be knaves (they lied to the first question in this case, though the first and the last soldier in each row told the truth to the second question, but at least one lie is required). This variant gives the minimal number of knights: 0. Another variant is that there are two knights in each row: at the 2-nd and the 4-th position. In this case they told the truth to both questions, and others lied answering to the second question (each knave now has one knave neighbor). This variant gives the maximal number of knights: 4.

Input format

The input consists of one row that contains three integers: k, x, y — number of soldiers in each row, and the parameters of the questions (1 ≤ k ≤ 105,  - 1 ≤ x, y ≤ 3).

If x =  - 1 Space Ranger didn't ask the first question.

If y =  - 1 Space Ranger didn't ask the second question.

It is guaranteed that at least one question was asked.

Output format

If there is no possible answer for the given k, x and y, output  - 1.

In the other case two integers — the minimal possible number of knights in the army and the maximal possible number of knights in the army.

Input data
2 0 -1
Output data
Input data
5 1 2
Output data
Input data
1 2 2
Output data
Input data
10 0 3
Output data

Send solution

Upload Maximal size is 256kb

Log in

VK Facebook

Forgot password?


The instruction for password recovery
has been sent to your email