Restore the Erased Numbers

Interview

Time limit1sMemory limit128 MB

Summary
Some of the four numbers a, b, a^2 b, ab^2 are replaced by 0; restore the original row, breaking ties toward the lexicographically smallest tuple.
Level

Medium4 of 10

Topics
Brute force, Math, Implementation, Number theory
Solved
No attempts yet

Problem

During an algebra lesson Liene chose two integers aa and bb with 0<∣a∣<10000 < |a| < 1000, 0<∣b∣<10000 < |b| < 1000, and a≥ba \ge b. In a single row she wrote four numbers in order: first aa and bb, then a2ba^2 b, and finally ab2ab^2. She made no calculation mistakes.

For example, the following are valid values of (a, b, a2b, ab2)(a,\ b,\ a^2 b,\ ab^2):

aabba2ba^2 bab2ab^2
12228848
-1-1-1-1
9-3-24381

Peter erased some of the four numbers and wrote 00 in their place. Because aa and bb are nonzero, all four numbers aa, bb, a2ba^2 b, ab2ab^2 are nonzero, so a value of 00 marks an erased cell.

Given one such (possibly damaged) row of four numbers, restore the original aa, bb, a2ba^2 b, ab2ab^2. If several restorations are possible, output the lexicographically smallest one: the smallest aa; if aa ties, the smallest bb; then the smallest a2ba^2 b; then the smallest ab2ab^2. (Because the numbers that were not erased are identical in every valid restoration, this is the same as minimizing the leftmost erased number first, then the remaining erased numbers from left to right.)

Input

One line with four space-separated integers: the possibly damaged row aa bb a2ba^2 b ab2ab^2, where every erased number is written as 00.

Output

Print the restored row as four space-separated integers aa bb a2ba^2 b ab2ab^2 on one line.

Constraints

  • 0<∣a∣<10000 < |a| < 1000, 0<∣b∣<10000 < |b| < 1000
  • a≥ba \ge b
  • The input always admits at least one valid restoration.

Examples2

  1. Example 1

    Input
    12 0 288 0
    
    Expected output
    12 2 288 48
    
  2. Example 2

    Input
    0 0 0 81
    
    Expected output
    1 -9 -9 81