Next: Sparse Vectors Up: No Title Previous: Computer Networks

Sequence of Differences

Consider a circular list with four integers, e.g., (0,1,4,11). For small non-negative integer values, repeatedly taking the absolute values of the differences of adjacent numbers eventually results in a list with identical values in each position.

  (0,1,4,11) -> (1,3,7,11) -> (2,4,4,10) -> (2,0,6,8) -> (2,6,2,6) -> (4,4,4,4)

In this case, we needed five steps to reach a list with identical values. We could have started with smaller integer values and still needed five steps to reach a list with identical values.

  (0,0,1,3) -> (0,1,2,3) -> (1,1,1,3) -> (0,0,2,2) -> (0,2,0,2) -> (2,2,2,2)

This sequence of five steps started with a list of non-negative integer values, each of which was less than or equal to 3. However, if all the list values were less than 3, no sequences of five steps would occur.

You are to write a program that computes the smallest maximum integer value needed in order to ensure that a sequence of N steps is used to reach a list all of whose elements have identical values. To make the problem simpler, you may assume N is 10 or less.

For example, to ensure a sequence of 3 steps, the value 1 is needed. The value 0 is not sufficient, since the sequence (0,0,0,0) already has identical values. The value 1 is sufficient, since we can find a four-member list consisting of 0's and 1's which will require 3 steps to reach identical values.

  (1,0,0,0) -> (1,0,0,1) -> (1,0,1,0) -> (1,1,1,1)

In comparison, to ensure a sequence of 4 steps, the value of 1 is not sufficient since all four-member lists consisting of 0's and 1's will reach identical values in 3 or fewer steps.

Input Format

The input will be the value N, the number of steps needed to reach identical values.

Output Format

The output should produce one line of output containing N, the number of steps, and the smallest maximum integer value needed to create a four-member list which requires N steps to reach identical values.

Examples

Input 1:

3

Output 1:

3   1

Input 2:

5

Output 2:

5   3

Test data used in judging

Input 1	Output 1
Input 2	Output 2
Input 3	Output 3
Input 4	Output 4
Input 5	Output 5
Input 6	Output 6
Input 7	Output 7
Input 8	Output 8
Input 9	Output 9

Our Solution

Next: Sparse Vectors Up: No Title Previous: Computer Networks