Thoát Khỏi Tầm Hậu · canuc80k0129

Trên bàn cờ $n \times n$ , một quân hậu đứng yên tại $(a_{x}, a_{y})$ . Hậu khống chế mọi ô cùng hàng, cùng cột hoặc cùng một trong hai đường chéo với nó. Một quân vua bắt đầu ở $(b_{x}, b_{y})$ và muốn tới $(c_{x}, c_{y})$ .

Mỗi bước, vua có thể đi sang bất kỳ ô kề cạnh hoặc kề góc, nhưng không được đứng trên ô bị hậu khống chế. Đầu và đích đã được bảo đảm an toàn. Hãy xác định vua có thể tới đích hay không.

Input

Dòng đầu chứa $n$ - kích thước bàn cờ $n \times n$ .
Dòng thứ hai chứa tọa độ hậu $(a_{x}, a_{y})$ .
Dòng thứ ba chứa vị trí đầu của vua $(b_{x}, b_{y})$ .
Dòng thứ tư chứa đích $(c_{x}, c_{y})$ .

Output

In YES nếu vua có thể tới đích mà không bao giờ đứng trên ô bị hậu khống chế; ngược lại in NO.

Constraints

$3 \leq n \leq 1000$ .
Mọi tọa độ nằm trong $1, \dots, n$ .
Ba ô hậu, vị trí đầu và đích đôi một khác nhau.
Vị trí đầu và đích không nằm cùng hàng, cùng cột hoặc cùng đường chéo với hậu.
Hậu đứng yên; mỗi bước vua có thể sang một trong tối đa $8$ ô kề cạnh hoặc kề góc.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 60$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

YES

Giải thích: Cả vị trí đầu và đích đều nằm phía trên hàng của hậu và bên trái cột của hậu, nên vua có thể di chuyển trong cùng miền an toàn để tới đích.

Ý tưởng: Hàng a_x và cột a_y do hậu khống chế chia các ô an toàn thành bốn miền theo hai dấu của x-a_x và y-a_y. Vua không thể đổi dấu một tọa độ mà không bước qua hàng hoặc cột của hậu, nên hai điểm ở khác miền chắc chắn không nối được.
Ý tưởng: Ngược lại, trong cùng một miền, vua dùng các bước ngang, dọc và chéo để đi tới đích mà tránh đường chéo của hậu; một bước chéo có thể vượt từ một phía của đường chéo sang phía kia mà không đứng trên nó. Vì vậy điều kiện cần và đủ là (b_x<a_x)==(c_x<a_x) và (b_y<a_y)==(c_y<a_y). Độ phức tạp O(1).