Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS08NIM2 - Nim 2 or 3

Julia and Robert are playing a variant of the classical game Nim - let us call it Nim 2 or 3. There are some matches lying on the table. Julia and Robert take it in turns to pick up exactly 2 or 3 matches from the table. The player who is unable to complete his turn (i.e., when there are no matches or exactly one match lying on the table at the start of the turn) loses.

The task is to print all possible game play scenarios for a given initial number of matches. A scenario is understood as the sequence of numbers, corresponding to the number of matches collected in successive turns. The output should be sorted in lexicographic order.

Input

Input consists of exactly one integer 3 < x < 30 - the initial number of matches.

Output

All possible game sequences, ordered in lexicographic order.

Example

Input:
7

Output:
4 1
4 2 0
5 2 0
5 3 0
5 3 1

Comment:

In the first game play sequence the first player took 3 matches, and the opponent also took 3 matches. There is only one match left - the game is over.

Scoring

By solving this problem you score 10 points.


Added by:kuszi
Date:2009-01-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Resource:High School Programming League

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.