Програмчлалын олимпиадын бодлогын архив

Танд 3 зэрэгтүүдийн хэмжээтэй туухайнууд байгаа. Жишээлбэл 1,3,9,27,81 ... гэх мэт. Таны даалгавар бол Тодорхой М (1<=M<=10^100) хэмжээтэй бараа өгөхөд жинлүүр дээр туухайнуудаа тавих аргаар 2 талын жинг тэнцүүлэх явдал юм. Танд туухайнууд зөвхөн 1,1 л байгаа.

Input

Эхний мөрөнд M тоо байрлана

Output

2 мөрөөс тогтох ба эхний мөрөнд бараа дээрээ нэмэх туухайны тоо болон туухайнууд. Дараагийн мөрөнд нөгөө талд тавих туухайнуудын тоо болон туухайнуудын жин байна.

Example

Input:
42

Output:
3 3 9 27
1 81

Input:
30

Output:
0
2 3 27

Ц. Дүүрэнбаярын нэрэмжит олимпиад - 2008 он.