체스판의 각 사각형은 검은색 혹은 하얀색이 인접해 있다.( 왼쪽 아래 사각형은 검은색이다.)
이 사각형의 변의 길이 S 는 밀리미터 0 < S <= 1000 이다.
벼룩 한마리가 체스판 (x,y) 위치에 있다(단위는 밀리미터). 그런데 이 벼룩이 오른쪽으로 dx 만큼,위로 dy 밀리미터를 점프를 한다. 즉 벼룩이 한 번 뛴 후의 위치가 (x+dx,y+dy) 가 된다.
당신의 일은 벼룩의 처음 위치가 주어질 때 벼룩이 몇 번 점프해야 흰 사각형으로 갈 수 있는지를 알아내는 것이다.
벼룩이 경계선에 있다면 이를 흰사각형으로 간주해서는 안되고 결코 흰 사각형에 도달할 수 없을 수도 있다. 체스판의 크기는 무한하다.
입력 10 2 3 3 2 출력 After 3 jumps the flea lands at (11, 9). 입력 100 49 73 214 38 출력 After 1 jumps the flea lands at (263, 111). 입력 25 0 0 5 25 출력 The flea cannot escape from black squares. 입력 407 1270 1323 1 1 출력 After 306 jumps the flea lands at (1576, 1629). 입력 18 72 6 18 6 출력 The flea cannot escape from black squares. 입력 407 1270 1170 100 114 출력 After 0 jumps the flea lands at (1270, 1170).
출처:waterloo local
★마지막 두 개의 데이터(31 번째,32 번째) 2011.6.4 일 cryptographer 님의 요청에 의해 추가 했습니다.