Greatest Common Divisor of Ones

Time limit2sMemory limit256 MB

Summary
Given the digit counts N and M of two repunits, print their GCD, which equals the repunit with gcd(N,M) ones, requiring big-number output construction.
Level

Medium6 of 10

Topics
Number theory, Math, String
Solved
No attempts yet

Problem

Two positive integers A and B are given. In decimal notation, every digit of each number is 1. Write a program that prints the greatest common divisor of A and B.

Input

The first line contains two positive integers N and M, separated by a space. N is the number of 1 digits in A, and M is the number of 1 digits in B.

Both N and M are less than 2^63.

Output

Print the greatest common divisor of A and B on the first line.

The answer has no more than 10,000,000 digits.

Examples3

  1. Example 1

    Input
    3 4
    Expected output
    1

  2. Example 2

    Input
    3 6
    Expected output
    111

  3. Example 3

    Input
    500000000000000000 500000000000000002
    Expected output
    11