Move & Meet

Interview

Time limit2sMemory limit512 MB

Summary
Two pieces start at given grid cells and each must make exactly d orthogonal steps; decide whether some cell can be the common endpoint, and print one.
Level

Medium5 of 10

Topics
Math, Implementation, Geometry, Brute force
Solved
No attempts yet

Problem

Ernesto and Penelope are playing a board game on an infinite grid. Instead of rolling dice, each of them generated a random number, and now they have to move their piece that many times. A single move consists of placing the piece in an adjacent cell; moving diagonally or waiting in place are not legal moves. However, it is permitted to move the piece in the direction it just came from in the previous move.

Ernesto and Penelope are trying to move in such a way that their pieces end up in the same cell. Is there a cell for which this is possible?

Figure M.1: Visualisation of the first sample, including possible paths for the given output.

Input

The input consists of two lines, both containing three integers x, y (−1012 ≤ x, y ≤ 1012) and d (0 ≤ d ≤ 1012), giving for either player the piece's initial coordinates and the randomly generated number.

Output

If there is a cell that both players can end up on, output its coordinates. If there are multiple valid solutions, any will be accepted. If there is no valid cell, output impossible.

Examples3

  1. Example 1

    Input
    1 -2 5
-3 3 8
    Expected output
    -3 -1

  2. Example 2

    Input
    0 -1000000000000 0
0 -1000000000000 0
    Expected output
    0 -1000000000000

  3. Example 3

    Input
    -5 -426 932111
83 -870 478692
    Expected output
    impossible