This page is still under construction.

Parts of this page are still being built. What you see may change.

Journey of a Knight

Interview

Time limit1sMemory limit128 MB

Summary
Given an n by m board, find the minimum number of knight moves from cell (1,1) to cell (i,j), or report that it is unreachable.
Level

Medium5 of 10

Topics
BFS, Graph, Shortest path, Implementation
Solved
No attempts yet

Problem

A rectangular chessboard has nn rows and mm columns, for a total of n×mn \times m cells. Each cell is identified by a pair of coordinates (r,c)(r, c), where rr is the row number (1≤r≤n1 \le r \le n) and cc is the column number (1≤c≤m1 \le c \le m). A knight starts on the bottom-left cell (1,1)(1, 1).

The knight moves according to the standard chess rules: in a single move it jumps one cell in one direction and two cells in the perpendicular direction (or two cells and then one cell). In other words, from cell (r,c)(r, c) the knight can move to any of the following eight cells that lie on the board: (r±1,c±2)(r \pm 1, c \pm 2) and (r±2,c±1)(r \pm 2, c \pm 1).

For example, if n=4n = 4 and m=3m = 3 and the knight is on cell (2,1)(2, 1), then in one move it can go to (1,3)(1, 3), (3,3)(3, 3), or (4,2)(4, 2).

You are given natural numbers nn, mm, ii, jj (1≤n≤1001 \le n \le 100, 1≤m≤1001 \le m \le 100, 1≤i≤n1 \le i \le n, 1≤j≤m1 \le j \le m). Determine the least possible number of moves the knight needs to reach cell (i,j)(i, j), starting from cell (1,1)(1, 1).

Pic. 1

Pic. 2

Input

A single line containing four integers nn, mm, ii, and jj, separated by spaces.

Output

Output the minimum number of moves required for the knight to reach cell (i,j)(i, j) from cell (1,1)(1, 1). If cell (i,j)(i, j) cannot be reached, output the single word NEVAR instead.

Examples2

  1. Example 1

    Input
    5 3 1 2
    
    Expected output
    3
    
  2. Example 2

    Input
    100 2 2 2
    
    Expected output
    NEVAR