A Flea on a Chessboard

Time limit1sMemory limit128 MB

Summary
The flea jumps by (dx, dy) from (x, y) on a grid of square size S; find the first jump landing strictly inside a white square, or report that none exists.
Level

Medium6 of 10

Topics
Math, Number theory, Implementation
Solved
No attempts yet

Problem

An infinite chessboard is obtained by extending a finite chessboard infinitely to the right and up. Each square is either black or white and has side length SS millimeters (0<S≤10000 < S \le 1000). The bottom-left square is black. A flea sits on the board at the point (x,y)(x, y) (in millimeters) and, with each jump, moves dxdx millimeters to the right and dydy millimeters up (0<dx, dy0 < dx,\ dy); that is, a flea at (x,y)(x, y) lands at (x+dx, y+dy)(x+dx,\ y+dy) after one jump.

Given the flea's starting position, determine how many jumps it takes for the flea to reach a white square. If the flea lands on the boundary between two squares, that does not count as landing on a white square. It is possible that the flea never reaches a white square.

Input

The input consists of several test cases. Each test case is one line containing five non-negative integers SS, xx, yy, dxdx, and dydy separated by whitespace. A line containing five zeros follows the last test case and is not processed.

Output

For each test case print one line. If the flea first reaches a white square at (a,b)(a, b) after nn jumps, print After n jumps the flea lands at (a, b).. If the flea never reaches a white square, print The flea cannot escape from black squares..

Examples3

  1. Example 1

    Input
    10 2 3 3 2
100 49 73 214 38
25 0 0 5 25
407 1270 1323 1 1
18 72 6 18 6
407 1270 1170 100 114
0 0 0 0 0
    Expected output
    After 3 jumps the flea lands at (11, 9).
After 1 jumps the flea lands at (263, 111).
The flea cannot escape from black squares.
After 306 jumps the flea lands at (1576, 1629).
The flea cannot escape from black squares.
After 0 jumps the flea lands at (1270, 1170).

  2. Example 2

    Input
    10 15 3 1 1
0 0 0 0 0
    Expected output
    After 0 jumps the flea lands at (15, 3).

  3. Example 3

    Input
    10 1 1 2 1
0 0 0 0 0
    Expected output
    After 5 jumps the flea lands at (11, 6).