Data Mining

Dr. Tuple is developing a new data-mining application for a commercial merchandise company. One of its subroutines works with two arrays $P$ and $Q$, each holding $N$ records (records are numbered from $0$ to $N-1$). Array $P$ holds a hash-like structure of keys and is used to locate a record; the data of that record is then read from array $Q$.

Every record in $P$ has size $S_P$ bytes and every record in $Q$ has size $S_Q$ bytes. This subroutine is a hot spot of the whole application, so it must run as fast as possible. Because $S_P$ and $S_Q$ are known only at run time, several compile-time optimizations become impossible.

The byte offset of the $i$-th record is normally computed as

$Pofs(i) = S_P \cdot i, \qquad Qofs(i) = S_Q \cdot i.$

Multiplication is much slower than addition on modern processors, so while scanning array $P$ Dr. Tuple keeps the byte offset $Pofs(i)$ instead of the index $i$, and moves to a neighbouring record with $Pofs(i+1) = Pofs(i) + S_P$ or $Pofs(i-1) = Pofs(i) - S_P$.

Whenever a record of $P$ is located, the matching record of $Q$ must be read, which needs its offset $Qofs(i)$. From the two formulas above one gets

$Qofs(i) = Pofs(i) / S_P \cdot S_Q.$

This contains both a multiplication and a (slow) integer division. To avoid them, Dr. Tuple uses the fast formula

$Qofs'(i) = \big(Pofs(i) + (Pofs(i) \ll A)\big) \gg B,$

where $A$ and $B$ are non-negative integers, $x \ll A$ is a left shift by $A$ bits (i.e. $x \cdot 2^A$) and $x \gg B$ is a right shift by $B$ bits (i.e. $\lfloor x / 2^B \rfloor$). Assume the registers are wide enough that overflow never occurs. Since $Pofs(i) = S_P \cdot i$, this equals

$Qofs'(i) = \left\lfloor \frac{S_P \cdot (1 + 2^A) \cdot i}{2^B} \right\rfloor.$

For most choices of $A$ and $B$ this does not equal $Qofs(i)$, but it can still be used at the cost of some extra memory. A conventional layout of $Q$ needs $N \cdot S_Q$ bytes. Dr. Tuple can always pick a $K$ (with $K \ge N \cdot S_Q$) such that, if $K$ bytes are allocated for $Q$ and $A$, $B$ are chosen carefully, the fast formula stores the $N$ records without overlap: record $i$ occupies the byte range $[Qofs'(i),\ Qofs'(i) + S_Q)$, all $N$ ranges are pairwise disjoint, and they all fit inside $[0, K)$.

Write a program that finds the minimal $K$ together with the corresponding $A$ and $B$. If several pairs $(A, B)$ give the same minimal $K$, output the one with the smallest $A$; if there is still a tie, output the one with the smallest $B$.

The input contains three integers $N$, $S_P$, and $S_Q$ separated by spaces ($1 \le N \le 2^{20}$, $1 \le S_P \le 2^{10}$, $1 \le S_Q \le 2^{10}$).

Print a single line with three integers $K$, $A$, and $B$ separated by spaces.