Restore the Erased Numbers
InterviewTime limit1sMemory limit128 MB
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 and with , , and . In a single row she wrote four numbers in order: first and , then , and finally . She made no calculation mistakes.
For example, the following are valid values of :
Peter erased some of the four numbers and wrote in their place. Because and are nonzero, all four numbers , , , are nonzero, so a value of marks an erased cell.
Given one such (possibly damaged) row of four numbers, restore the original , , , . If several restorations are possible, output the lexicographically smallest one: the smallest ; if ties, the smallest ; then the smallest ; then the smallest . (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 , where every erased number is written as .
Output
Print the restored row as four space-separated integers on one line.
Constraints
- ,
- The input always admits at least one valid restoration.