B. Brickwork
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

We are attempting to design a wall as a tessellation of 2D rectangular brick shapes, with all of the bricks having exact integer coordinates and exact integer sizes.

Given a description of the brickwork in this 2D wall, determine if the wall is indeed a wall—covering a perfect rectangle with no overlapping bricks and with no empty spaces in between bricks. This means that every non-integer-coordinate inside the region should be covered by exactly one brick.

Brickwork illustrating samples 1, 2, and 3 respectively.

Input

  • One line containing the number of bricks, $$$n$$$ ($$$1 \le n \le 1\,000\,000$$$).
  • $$$n$$$ further lines, each containing the description of a brick as four integers $$$x y w h$$$ giving the xy-coordinates, width, and height ($$$0 \le x, y \le 10^8$$$; $$$1 \le w, h \le 10^8$$$).
Output

Output yes if the bricks constitute a valid wall, no otherwise.

Examples
Input
5
0 0 5 1
1 1 4 4
0 1 1 5
1 5 5 1
5 0 1 5
Output
yes
Input
3
1 0 3 3
0 1 3 3
3 3 1 1
Output
no
Input
4
1 1 2 1
0 0 2 1
0 1 1 1
2 0 1 1
Output
yes