題干：

Little C loves number ?3? very much. He loves all things about it.

Now he has a positive integer?nn. He wants to split?nn?into?33?positive integers?a,b,ca,b,c, such that?a+b+c=na+b+c=n?and none of the?33?integers is a multiple of?33. Help him to find a solution.

Input

A single line containing one integer?nn?(3≤n≤1093≤n≤109) — the integer Little C has.

Output

Print?33?positive integers?a,b,ca,b,c?in a single line, such that?a+b+c=na+b+c=n?and none of them is a multiple of?33.

It can be proved that there is at least one solution. If there are multiple solutions, print any of them.

Examples

Input

3

Output

1 1 1

Input

233

Output

77 77 79

解題報告：

? 還有一個后續題目，是關于曼哈頓距離的，暫時還沒學，題解先放著? ?我是題解

? ?這道題就比較水了啊，屬于三元組但是卻不需要這么分析，因為n太大了，1e9，所以考慮構造。

? 其實也比較好構造啊，，比較容易滿足題意。

#include<bits/stdc++.h>using namespace std;int main() {int n;int a,b,c;cin>>n;if(n%3==0) {a=1;b=1;c=n-a-b;}else {a=1,b=2;c=n-a-b;}printf("%d %d %d\n",a,b,c);return 0; }

AC代碼：

?

總結

以上是生活随笔為你收集整理的*【CodeForces - 1047A】Little C Loves 3 I （水题，构造，三元组问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。