Under construction

Still being built. Things may change

Hate Coprime

Time limit1sMemory limit1024 MB

Summary
Given x and y, add or subtract a z that shares a factor with the current x, at most twice, so that x becomes equal to y.
Level

Medium6 of 10

Topics
Number theory, Math, Implementation
Solved
No attempts yet

Problem

Two integers xx and yy are given, with 2≤x,y≤1092\leq x,y\leq 10^9. Using the following operation at most twice, make xx and yy equal.

  • Choose an integer zz with 1≤z≤10181\leq z\leq 10^{18} that is not coprime to xx. Add zz to xx, or subtract zz from xx.

After each operation, xx must still be an integer with 1≤x≤10181\leq x\leq 10^{18}.

It can be proven that xx can always be turned into yy with at most two operations.

Output

The first line contains the integer MM, the number of operations used (0≤M≤2)(0\leq M \leq 2).

From the second line onward, print the operations in order, one per line.

  • If the operation adds zz to xx, print zz.
  • If the operation subtracts zz from xx, print −z-z.

Examples3

  1. Example 1

    Input
    4 4
    
    Expected output
    2
    4
    -4
    
  2. Example 2

    Input
    7 12
    
    Expected output
    2
    7
    -2
    
  3. Example 3

    Input
    6 9
    
    Expected output
    1
    3