시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 2048 MB75571.429%

문제

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.

Figure B.1: Brickwork illustrating samples 1, 2, and 3 respectively.

입력

  • 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 yes if the bricks constitute a valid wall, no otherwise.

예제 입력 1

5
0 0 5 1
1 1 4 4
0 1 1 5
1 5 5 1
5 0 1 5

예제 출력 1

yes

예제 입력 2

3
1 0 3 3
0 1 3 3
3 3 1 1

예제 출력 2

no

예제 입력 3

4
1 1 2 1
0 0 2 1
0 1 1 1
2 0 1 1

예제 출력 3

yes