Problem Description

Takahashi learned the Euclidean algorithm but became curious about how fast it operates.

Therefore, he wrote the following C code:

#include <stdio.h>

int counter = 0;
int gcd(int a, int b) {
    if (b == 0) return a;
    counter++;
    return gcd(b, a%b);
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    gcd(a, b);
    printf("%d\n", counter);
}

This code takes two integers as input from standard input, calculates their gcd using the Euclidean algorithm, and outputs the number of recursive calls made during the calculation.

You want to test this program with various values.

Specifically, given a value \( K \), find a pair of integers \( a \) and \( b \) such that the output of this program is \( K \).

Input Format

The input is given from standard input in the following format:

\( K \)

Output Format

Output \( a \) and \( b \) separated by a space in one line. The following constraints must be satisfied:

\( 1 \leq a, b \leq 1,000,000,000 \)

Sample Input and Output

Sample Input #1

1

Sample Output #1

1 1

Sample Input #2

3

Sample Output #2

4 5

Sample Input #3

12

Sample Output #3

314159265 358979323

Notes/Hints

Constraints

• \( 1 \leq K \leq 40 \)

However, if all test cases satisfying the following constraints are correctly answered, 30 points will be awarded:

• \( 1 \leq K \leq 10 \)

Sample Explanation 3

Each input/output example has many other outputs that satisfy the conditions.

见题面 Input 部分

见题面 Output 部分