Big Numbers for Little Vasya

Time limit1sMemory limit1024 MB

Summary

Given a digit D repeated N and M times, print the GCD of the two numbers, or its last 10^6 digits if it is longer.

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

Statement

Vasya received two numbers for his birthday.

The first number is the digit $D$ written $N$ times in a row. The second number is the same digit $D$ written $M$ times in a row.

Vasya wanted to find the greatest common divisor of the two numbers, but they are too large for him to compute. Help Vasya find the greatest common divisor of the numbers he received.

The greatest common divisor is the largest natural number that divides both numbers without a remainder.

Input

The first line contains two integers $N$ and $M$ separated by a space ( $1 \leq N, M \leq 10^{18}$ ), the number of digits in the first and second number. The second line contains one integer $D$ ( $1 \leq D \leq 9$ ), the digit both numbers are made of.

Output

If the decimal representation of the greatest common divisor has at most $10^6$ digits, print the greatest common divisor itself. Otherwise, print its last $10^6$ digits. Do not print leading zeros.

Examples1

Example 1
Input
```
1 1
1
```
Expected output
```
1
```