Under construction

Still being built. Things may change

Watch the Marathon

Time limit8sMemory limit1024 MB

Summary
Given a segment from the origin to (a, b), find the integer lattice point off the segment closest to it, breaking ties by smallest X, then smallest Y.
Level

Medium6 of 10

Topics
Number theory, Geometry
Solved
No attempts yet

Problem

You are a track and field fan and decide to watch a marathon in person. In this race, the course is the line segment connecting the origin on the XYXY plane and the point (a,b)(a, b). Because of traffic control during the race, you can watch only from points whose XX and YY coordinates are both integers and that are not on the course.

You want to watch from as close to the course as possible. Among the points that satisfy the conditions above, find the point with the smallest Euclidean distance to the course. If several points tie, output the one with the smallest XX coordinate. If there is still a tie, output the one with the smallest YY coordinate.

Input

The input consists of at most 300,000300{,}000 datasets. Each dataset is given in this format:

aa bb

aa and bb are integers from 11 to 10910^9, inclusive, and give the coordinates of one endpoint of the marathon course.

The input ends with a line containing two zeros.

Output

For each dataset, print the XX and YY coordinates of the best point to watch the race, separated by a space, on one line.

Examples1

  1. Example 1

    Input
    2 3
    2 9
    7 2
    9 8
    4 9
    6 6
    5 7
    9 1
    5 3
    65537 735134400
    0 0
    
    Expected output
    1 1
    1 4
    3 1
    1 1
    1 2
    0 1
    2 3
    1 0
    2 1
    23788 266832127