Koto Distance

Time limit2sMemory limit512 MB

Summary

Given N access points, each covering points whose Koto distance (the minimum of the x-gap and y-gap) is at most w_i, decide whether their union covers the whole W by H rectangle.

Level: Hard8 of 10
Topics: Geometry, Sorting, Intervals, Union-find
Solved: No attempts yet

Problem

Koto is a well-known city laid out on a grid. The city occupies a rectangular area that extends $W$ meters from east to west and $H$ meters from north to south. The point $x$ meters from the west edge and $y$ meters from the south edge is written $(x, y)$ . The people of this city value their own culture handed down from long ago, and one part of it is an unusual distance measure called the Koto distance. The Koto distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is defined as $\min(|x_1 - x_2|, |y_1 - y_2|)$ .

Recently a plan was launched to make Wifi available throughout the city. The current plan calls for building $N$ access points. The $i$ -th access point is installed at the point $(x_i, y_i)$ and provides Wifi to the region whose Koto distance from it is at most $w_i$ .

Determine whether Wifi can be provided to the entire interior and boundary of the city if the access points are built as planned.

Keep it between us, but the Koto distance generally does not satisfy the triangle inequality, so it does not satisfy the axioms of a metric.

Input

The input is given in the following format.

$N$ $W$ $H$

$x_1$ $y_1$ $w_1$

$...$

$x_N$ $y_N$ $w_N$

Output

If Wifi can be provided to the entire interior and boundary of the city, output “Yes”; otherwise, output “No”.

Constraints

$1 \le N \le 10^5$
$1 \le W \le 10^5$
$1 \le H \le 10^5$
$0 \le x_i \le W$
$0 \le y_i \le H$
$1 \le w_i \le 10^5$
No two access points share the same coordinates

Examples3

Example 1
Input
```
3 9 9
2 2 2
5 5 2
8 8 2
```
Expected output
```
Yes
```
Example 2
Input
```
2 7 7
2 2 1
6 6 1
```
Expected output
```
No
```
Example 3
Input
```
3 10 20
5 10 5
2 10 1
8 10 1
```
Expected output
```
Yes
```