Problem Description

A farmer has $N$ lambs. They are kept in a single consecutive row of $N$ pens.

One day, $x$ different lambs got sick. Every night, each lamb that is already infected will randomly infect one of its adjacent lambs. Also, the same lamb may be infected multiple times.

The $i$-th lamb is adjacent only to lambs $i-1$ and $i+1$. In particular, the only adjacent lamb of lamb $1$ is $2$, and the only adjacent lamb of lamb $N$ is $N-1$.

After $T$ days (i.e. after $T$ rounds of infection), the farmer finally discovers this. He is very anxious and urgently wants to know: among all possible situations, what are the maximum and minimum possible numbers of infected lambs now.

Input Format

The first line contains $3$ integers $N, T, x$.

Output Format

Output $2$ integers in the first line, representing the maximum and minimum possible numbers of infected lambs.

If at least one number in your output is correct, you will get $50\%$ of the score for that test point. If you cannot output one of them, please use $0$ instead, otherwise you will not get any points.

2 3 1

2 2

7 2 3

7 3

Hint

[Sample Explanation #1]

After the first round of infection, both lambs will be infected, so the maximum and minimum numbers of infected lambs are both $2$.

[Constraints]

This problem uses bundled tests.

• Subtask #1 ($20\text{ pts}$): $N, T \le 20$.
• Subtask #2 ($20\text{ pts}$): $N \le 20$.
• Subtask #3 ($20\text{ pts}$): $x = 1$.
• Subtask #4 ($40\text{ pts}$): no special constraints.

For $100\%$ of the testdata, $2 \le N, T \le 10^9$, $1 \le x \le N$.

Translated by ChatGPT 5