Problem Statement

There is a betting machine. You initially have $S$ coins, and your goal is to have at least $T$ coins.

This machine can be used at most $N$ times.

Let $W$ be the number of coins you currently have, where $0 \lt W \lt T$.
Before using the machine, you choose an integer $X$ satisfying $1 \le X \le W$ as your bet.

First, the machine takes the $X$ coins you bet.
Then, exactly one of 3 types of outcomes occurs.

Outcome $i$ occurs with probability $P_i\%$, in which case the machine returns $\left\lfloor A_i X / B_i \right\rfloor$ coins. Therefore, the number of coins you have after outcome $i$ occurs is

$$ W-X+\left\lfloor\frac{A_iX}{B_i}\right\rfloor $$

.

You succeed as soon as you have at least $T$ coins, and you place no further bets after that.
If the number of coins you have becomes $0$ before reaching $T$ coins, you cannot bet any more.
If you have not reached at least $T$ coins after placing at most $N$ bets, you fail.

After seeing the result of each bet, you may choose the next bet anew.
Therefore, from the second bet onward, your bet may depend on your current number of coins and the results so far.

Maximize the probability that you have at least $T$ coins within at most $N$ bets.

Input

The input is given in the following format.

S T N
P_1 A_1 B_1
P_2 A_2 B_2
P_3 A_3 B_3

Constraints

• All input values are integers.
• $1 \le S \lt T \le 1000$
• $1 \le N \le 9$
• $1 \le P_i \le 98$
• $P_1+P_2+P_3=100$
• $0 \le A_i \le 1000$
• $1 \le B_i \le 1000$
• $A_i \gt B_i$ for at least one outcome.
• $A_i \lt B_i$ for at least one outcome.

Output

Let $q\ (0 \le q \le 1)$ be the maximum probability of success.

On the 1st line, print $\left\lfloor 100q \right\rfloor$.

If the maximum probability of success $q$ can be achieved by choosing $X$ for the first bet and making all subsequent choices optimally, $X$ is called an optimal first bet.

On the 2nd line, print the number $K$ of integers $X$ that are optimal first bets.

On the 3rd line, print those $K$ integers $X$ in ascending order, separated by spaces.

Print all first bets that achieve the maximum, including when the maximum probability of success is $0$.

Print a newline at the end of the output.

Sample

20 35 3
20 3 1
30 2 1
50 0 1

60
1
8