Horrible Sequence

Time limit2sMemory limit128 MB

Summary

Given M, find the max and min lengths of sequences with sum M that maximize the product, and sequences with product M that minimize the sum.

Level: Medium6 of 10
Topics: Math, Number theory, Greedy, Implementation
Solved: No attempts yet

Problem

The length of a sequence <a_1, a_2, ..., a_k> of positive integers is the number of integers in the sequence, k. Given a positive integer M, consider the following two tasks.

Task A: Among all sequences of positive integers whose sum satisfies a_1 + a_2 + ... + a_n = M, find those whose product a_1 × a_2 × ... × a_n is as large as possible. If optimal sequences with different lengths exist, find both the maximum and minimum possible values of the length n.
Task B: Among all sequences of positive integers whose product satisfies a_1 × a_2 × ... × a_m = M, find those whose sum a_1 + a_2 + ... + a_m is as small as possible. If optimal sequences with different lengths exist, find both the maximum and minimum possible values of the length m.

Write a program that outputs the maximum and minimum possible lengths for task A, followed by the maximum and minimum possible lengths for task B.

Input

The first line contains an integer M. (1 ≤ M ≤ 1,000,000)

Output

Print four integers on one line, separated by spaces: the maximum possible length n for task A, the minimum possible length n for task A, the maximum possible length m for task B, and the minimum possible length m for task B, in that order.

Examples1

Example 1
Input
```
6
```
Expected output
```
2 2 2 2
```