Board Covering

Time limit1sMemory limit128 MB

Summary

Given an odd n by n board with three unit squares removed, decide whether the rest tiles perfectly with dominoes.

Level: Medium6 of 10
Topics: Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

You are given a board of $n \times n$ unit squares, where $n$ is an odd integer with $3 \le n < 50$ . The squares are numbered consecutively row by row: the squares in the first row (left to right) get numbers $1$ to $n$ , the second row gets $n+1$ to $2n$ , and so on, down to the bottom-right square, which is numbered $n^2$ .

Three of the squares are cut out of the board. We then try to cover the remaining squares with dominoes. Each domino is a $1 \times 2$ tile that covers exactly two squares sharing an edge. A valid covering uses exactly $k = (n^2 - 3)/2$ dominoes so that every remaining square is covered by exactly one domino and no domino covers a cut-out square.

Determine whether such a covering of the board (with the three squares removed) is possible.

Input

A single line with four integers separated by single spaces: the board size $n$ , followed by the numbers of the three cut-out squares. The three numbers are distinct and each lies between $1$ and $n^2$ . The input is always well formed, so your program does not need to validate it.

Output

Print YES if the board with the three squares removed can be completely covered by dominoes under the rules above, otherwise print NO.

Examples3

Example 1
Input
```
7 17 25 40
```
Expected output
```
YES
```
Example 2
Input
```
7 25 32 40
```
Expected output
```
NO
```
Example 3
Input
```
3 1 2 3
```
Expected output
```
YES
```