問題文

あるベッティングマシンがあります。最初に $S$ 枚のコインを持っており、所持コイン数を $T$ 枚以上にすることが目標です。

このマシンは最大 $N$ 回まで利用できます。

現在の所持コイン数を $W$ とします。ただし $0 \lt W \lt T$ です。
マシンを利用する前に、$1 \le X \le W$ を満たす整数 $X$ を賭け金として選びます。

まず、マシンは賭けた $X$ 枚のコインを受け取ります。
その後、3 種類の結果のうちちょうど 1 つが発生します。

結果 $i$ は確率 $P_i\%$ で発生し、このときマシンから $\left\lfloor A_i X / B_i \right\rfloor$ 枚のコインが返されます。したがって、結果 $i$ が発生した後の所持コイン数は

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

となります。

所持コイン数が $T$ 枚以上になった時点で成功となり、それ以降は賭けを行いません。
$T$ 枚に到達する前に所持コイン数が $0$ 枚になった場合、それ以上賭けることはできません。
最大 $N$ 回の賭けを行っても $T$ 枚以上に到達できなかった場合は失敗です。

各賭けの結果を確認した後、次の賭け金を新たに選ぶことができます。
したがって、2 回目以降の賭け金は現在の所持コイン数やそれまでの結果に応じて変えて構いません。

最大 $N$ 回の賭け以内に所持コイン数を $T$ 枚以上にできる確率を最大化してください。

入力

入力は次の形式で与えられます。

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

制約

• 入力される値はすべて整数
• $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$
• 少なくとも 1 つの結果について $A_i \gt B_i$
• 少なくとも 1 つの結果について $A_i \lt B_i$

出力

成功できる最大確率を $q\ (0 \le q \le 1)$ とします。

1 行目に $\left\lfloor 100q \right\rfloor$ を出力してください。

最初の賭けで $X$ を選び、その後のすべての選択を最適に行ったときに最大成功確率 $q$ を達成できるなら、$X$ を 最適な最初の賭け金 と呼びます。

2 行目に、最適な最初の賭け金となる整数 $X$ の個数 $K$ を出力してください。

3 行目に、その $K$ 個の整数 $X$ を昇順に、空白区切りで出力してください。

最大成功確率が $0$ の場合も含め、最大値を達成する最初の賭け金をすべて出力してください。

出力の最後には改行を入れてください。

サンプル

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

60
1
8