You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

小明看到一道小学奥数题。

有三个杯子：一个容量是$x$，一个容量是$y$，一个容量是$z$。

还有一个超级大的桶，这个桶没有标明容量。

小明每次操作可以干如下四件事：

（1）把某个杯子的水灌满。

（2）把某个杯子的水倒掉。

（3）把某个杯子水倒进桶里。

（4）把某个杯子的水倒进另一个杯子，直至这个杯子空了或者另一个杯子满了。

问：小明想让桶里的水恰好是$1,2,...,N$，最少要操作几次。

输入格式

第一行输入$x,y,z,N$。

输出格式

输出一行共$N$个数字，对于容量$i$，如果无解输出$-1$，否则输出最少的次数。

3 1 1 7

2 3 2 4 5 4 6

60 9 20 60

20 5 15 10 13 13 7 19 2 22 3 17 8 15 11 9 17 4 22 2 19 6 17 9 11 15 6 20 4 21 4 19 7 13 13 8 18 6 21 3 21 5 15 11 10 16 8 19 5 23 3 17 9 12 14 10 17 7 23 2

数据范围

对于5%的数据：$x=1,y=2,z=3,N\leq 10^5$。

对于另40%的数据：$x,y,z,N\leq 60$。

对于100%的数据：$1\leq x,y,z\leq 100,N\leq 10^5$。