百钱买百鸡II

在中国古代有这么一道题:

  • 今有鸡翁一,值钱伍;鸡母一,值钱三;鸡雏三,值钱一。凡百钱买鸡百只,问鸡翁、母、雏各几何?

这道题从现代数学观点来看,实际上是一个求不定方程整数解的问题。解法如下:

设公鸡、母鸡、小鸡分别为x、y、z 只,由题意得:

x+y+z=100①式

5x+3y+(1/3)z=100②式

现在有两个方程,三个未知量,我们称其称为不定方程组,有多种解,利用消元法对它进行求解即可知道原问题的答案。

我们已经学会了编程,那可不可以从中剖析出思想去解决这一系列的问题呢?

比如用 N 钱买 N 只鸡。那么来试一下吧!

Input

输入一个整数 N (1≤N≤1000) 表示需要使用 N 钱买 N 只鸡。

Output

如有方案,请按照样例格式输出,基本格式为:第几种方案: 公鸡数,母鸡数,小鸡数。 如果发现没有解,请输出 None。

Examples

Input

100

Output

1: 0,25,75
2: 4,18,78
3: 8,11,81
4: 12,4,84

来源

lema
Time limit 1 second
Memory limit 128 MB
讨论 统计