Knights and Knaves

Time limit2sMemory limit512 MB

Summary

Given two rows of k soldiers, each asked the same one or two questions about exact knight or knave counts among neighbors and all answering yes, find the minimum and maximum possible number of knights, or -1.

Level: Medium7 of 10
Topics: Dynamic programming, Implementation, Brute force, Greedy
Solved: No attempts yet

Problem

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

Ranger knows that there are knights, who always tell the truth, and knaves, who 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 answered "yes" to all questions asked.

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

Consider the second sample test. Each row has 5 soldiers, and 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 (in this case they lied to the first question, although the first and 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 2nd and 4th positions. In this case they told the truth to both questions, and the others lied answering the second question (each knave now has one knave neighbor). This variant gives the maximal number of knights: 4.

Input

The input consists of one row containing three integers: $k$ , $x$ , $y$ , the number of soldiers in each row and the parameters of the questions ( $1 \le k \le 10^5$ , $-1 \le x, y \le 3$ ).

If $x = -1$ , Space Ranger did not ask the first question.

If $y = -1$ , Space Ranger did not ask the second question.

It is guaranteed that at least one question was asked.

Output

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

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

Examples4

Example 1
Input
```
2 0 -1
```
Expected output
```
2
2
```
Example 2
Input
```
5 1 2
```
Expected output
```
0
4
```
Example 3
Input
```
1 2 2
```
Expected output
```
0
0
```
Example 4
Input
```
10 0 3
```
Expected output
```
5
8
```