Problem Statement

Consider a tree with V vertices labeled 0 through V-1. A bijective function f from {0, ..., V-1} to
{0, ..., V-1} is called an automorphism of this tree if for any u and v, vertices u and v are
directly connected by an edge if and only if vertices f(u) and f(v) are directly connected by an
edge. In other words, an automorphism is any permutation of vertex labels such that after the
permutation the tree looks the same as in the beginning. (Note that there is always at least one
automorphism: the identity function.)  

Cat Snuke became age years old today. You want to give him a birthday present that has something to
do with his age. As he likes trees, you decided to give him a tree with exactly age automorphisms.
Due to your budget you can only buy him a tree that contains between 1 and 200 vertices, inclusive.

You are given the int age. Find a tree that matches the above requirements and return a int[] with
its description in the format specified below. If there are many such trees, you may return any of
them. If there are no such trees, return an empty int[] instead.

Given that you want to return a tree with V vertices, you should return a int[] X with exactly 2V-1
elements: the number of vertices, followed by the list of edges. More precisely: X[0] should be V.
For each edge in your tree, there must be an i between 0 and V-2, inclusive, such that X[2*i+1] and
X[2*i+2] are the endpoints of that edge. Note that V must be between 1 and 200, inclusive.

Method signature: int[] construct(long age)
Time limit (s): 2.000
Memory limit (MB): 256

Constraints

- age will be between 1 and 10^18, inclusive.

Examples

0)

1
Returns: {1 }
A tree with only one vertex.


1)

8
Returns: {6, 0, 1, 1, 2, 3, 4, 4, 5, 4, 1 }
The return value describes the following tree with 6 vertices:
0      3
|      |
|      |
1------4
|      |
|      |
2      5
We can easily verify that it has exactly 8 automorphisms.

2)

1000000000000000000
Returns: { }


This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.