题目描述：

一天，大雄收到小夫的邀请前往小夫家的别墅，在小夫家里，大雄和胖虎以及静香看到了小夫最新收藏的恐龙模型，这个模型十分逼真，小夫一直不停炫耀自己的这个恐龙模型，这使得大雄羡慕不已，大雄夸下海口，说自己要拍一张和霸王龙的合照，然后胖虎和小夫开始嘲笑大雄的愚蠢。

胖虎说：“霸王龙在几个世纪前就已经灭绝了，笨蛋大雄。”

然后大雄跑回家哭着向哆啦A梦求助，然后哆啦A梦实在受不了大雄，他决定和大雄穿越到白垩纪时代，让他见一见真正的霸王龙。

他俩通过时光机到达白垩纪后，他们戴着竹蜻蜓，在空中寻找霸王龙的身影。不幸的是，他们遇到了 \(N\) 只翼龙。现在每只翼龙的血量为 \(B_i\) 点，糟糕的事情发生了，哆啦A梦的百宝袋昨天刚好送到 22 世纪去修理，他现在只能从备用百宝袋中拿出一把武器——空气炮和一个放大灯，如果空气炮打中翼龙，可以对其造成 \(w\) 点伤害，如果使用放大灯，可以使得空气炮的伤害增加 \(K\) 倍。如果放大灯对翼龙使用，也可以使翼龙的血量增加 \(K\) 倍，对于第 \(i\) 只翼龙，空气炮的使用者可以自行决定是否使用放大灯。

现在，哆啦A梦有两个选择：

• 选择 \(1\) ：它可以自己使用空气炮，然后把放大灯给大雄使用。
• 选择 \(2\) ：它可以自己使用放大灯，让大雄使用空气炮。

附：每使用一次空气炮花费 \(1\) 秒钟，哆啦A梦射击的命中率为 \(50 \%\)，大雄的射击命中率为 \(99.9999999 \%\)。

输入描述：

第一行三个整数，分别表示翼龙数量 \(N(1 \le N \le 10^6)\)，空气炮的伤害 \(w(1 \le w \le 10^6)\)，放大灯放大的倍数 \(K(1 \le K \le 10^6)\)。

第二行包含 \(N\) 个整数，分别表示 \(B_1, B_2,...,B_N(1 \le B_i \le 10^6)\)。

输出描述：

输出包含两行。

第一行输出哆啦A梦的选择 \(op \in(1, 2)\)。

第二行输出哆啦A梦和大雄打败所有翼龙所花费的最小时间，以及此时放大灯的最小使用次数。

样例

输入

5 10 4
1 20 15 30 17

输出

2
5 4