Infected Sheep

A farmer has (N) sheep arranged in a row in (N) consecutive pens. One day, exactly (x) of them become sick. Every night, each infected sheep infects exactly one of its adjacent sheep. In other words, the (i)th sheep is adjacent only to the (i-1)th and (i+1)th sheep (with the special cases that the first sheep is only adjacent to the second, and the (N)th sheep is only adjacent to the (N-1)th sheep). Note that the same sheep may be infected more than once. After (T) days (i.e. after (T) rounds of infections), the farmer wants to know, over all possible initial choices of the (x) sick sheep and over all possible infection choices, what are the maximum and minimum possible numbers of infected sheep.


Clarification:

• The infection process proceeds in rounds. Initially, exactly \(x\) sheep (distinct positions) are infected.
• In each round (night), every infected sheep simultaneously chooses exactly one adjacent pen and infects the sheep in that pen (even if that sheep is already infected).
• The farmer only notices the situation after \(T\) rounds. He wonders: in the best‐case scenario (maximizing infections) and in the worst‐case scenario (minimizing the spread), how many sheep are infected?

Important: Once a sheep is infected it remains infected. The adversary has full control of both the initial infected positions (subject to being (x) distinct pens) and the infection choices each round. Your task is to compute two numbers: the maximum possible number of infected sheep and the minimum possible number of infected sheep after (T) rounds.

Observations:

• It is optimal for minimizing spread to choose the initial infected sheep to be adjacent (so that many infection events occur within the already infected block). In this case, if \(x \ge 2\), the infection can be contained entirely within the initial block by having the sheep on the boundaries repeatedly infect an already infected neighbor. However, if \(x = 1\) then, when \(T \ge 1\), placing the sole infected sheep at an end minimizes the spread.
• For the maximum spread, one wants to choose the initial infected positions as spread out as possible. In an optimal strategy one may use the fact that even though a sheep only infects one neighbor per round, the newly infected sheep can help the infection propagate further. In particular:
  • If \(x = 0\) the answer is obviously 0.
  • If \(T=0\) no infection happens beyond the initial ones.
  • If \(x = 1\) (with \(T \ge 1\)) one can achieve at most a block of size \(2T\) (by placing the seed in an interior position) but if the chain is short this is limited by \(N\). In our answer we use \(\min(N, 2T)\) for \(x=1\) when \(T\ge1\).
  • If \(x \ge 2\) one may place one infected at the left end and one at the right end (to get the maximum gain from the boundaries) and the others in the interior. By a careful schedule the maximum infected count that can be achieved is \(2T(x-1)+2\) (again, not exceeding \(N\)).
  
  Thus, if we denote the answers by max and min, we have:

  [ \text{max} = \begin{cases} 0, & x = 0,\ x, & T = 0,\ \min(N, 2T) , & x = 1 \text{ and } T \ge 1,\ \min\Bigl(N, 2T(x-1) + 2\Bigr), & x \ge 2 \text{ and } T \ge 1. \end{cases} ]

  [ \text{min} = \begin{cases} 0, & x = 0,\ x, & x \ge 2,\ 1, & (x=1 \text{ and } T=0),\ 2, & (x=1 \text{ and } T \ge 1). \end{cases} ]

  Note that all answers must also not exceed (N), the total number of sheep.

  Your program should read the input and output the two numbers (maximum and minimum) separated by a space.

  inputFormat

  The input consists of a single line containing three integers \(N\), \(x\), and \(T\), where \(N\) is the total number of sheep, \(x\) is the number of initially infected sheep, and \(T\) is the number of rounds (days) of infection.

  Constraints:

  • \(0 \le x \le N\)
  • \(T \ge 0\)

  outputFormat

  Output a single line with two integers separated by a space: the maximum possible number of infected sheep and the minimum possible number of infected sheep after \(T\) rounds.

  sample

  5 1 2

  4 2