The Battle for Wesnoth

The Battle for Wesnoth is a turn based fantasy strategy game with elves, orcs, undead, dwarves and drakes. Only two facts about it matter here. Every unit has a number of hitpoints, and combat takes hitpoints away. We look at the simplest kind of combat, a plain attack on a defenseless unit.

An attack is described by three integers:

• $d$, the damage of one successful blow;
• $b$, the number of blows;
• $p$, the probability in percent that a single blow succeeds.

Each of the $b$ blows succeeds independently with probability $p/100$, and every successful blow takes away $d$ hitpoints. In the game $d$ and $b$ are properties of the attacker, while $p$ usually comes from the terrain the defender stands on, but here $p$ is a property of the attacker as well, the way magical attacks work.

Take an attack with $d=6$, $b=2$ and $p=60$. It has three outcomes:

• with probability $16\%$ both blows miss and no damage is done;
• with probability $48\%$ exactly one blow lands and the damage is $6$ hitpoints;
• with probability $36\%$ both blows land and the damage is $12$ hitpoints.

A unit dies once its hitpoints become zero or less.

David plays an add-on in which the Elvish Princess has a special magical attack. She is described by a single integer $m$ instead of $d$ and $b$: when she attacks, the player may choose any positive integers $d$ and $b$ with $d \times b \le m$.

David regularly needs the Elvish Princess to kill an ugly skeleton or a stinking orcish warrior, so he wants to know which choice of $d$ and $b$ gives the highest probability of killing the enemy. Find that choice for every unit he needs to kill.

The first line contains two integers $m$ ($1 \le m \le 10^6$) and $p$ ($1 \le p \le 99$), the parameters of the attacker. The second line contains an integer $n$ ($1 \le n \le 10^5$), the number of units to be killed. The third line contains $n$ integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^6$), where $h_i$ is the number of hitpoints of the $i$-th unit to be killed.

For each unit print one line with two integers $d$ and $b$, the choice that maximizes the probability of killing that unit.

Several choices can reach the same maximum probability. In that case print the one with the smallest $d$, and among those the one with the smallest $b$. When the unit cannot be killed at all, so that every choice has probability $0$, print 1 1.

For $m=10$ and $p=60$, a unit with $5$ hitpoints is killed with probability $84\%$, a unit with $6$ hitpoints with probability $68.256\%$, and a unit with $7$ hitpoints with probability $60\%$.

Double precision is enough for the whole computation, but watch out for overflow and underflow, and avoid unsafe operations such as adding numbers of very different magnitude. For $a=0.5$ and $b=10^{-100}$, the sum $a+b$ evaluates to $a$.