464. Оставаясь на связи

Альпинист Тимофей решил отправиться в долгий поход по горам Алтая. Тимофей знает, насколько важно иметь доступ к связи во время путешествия, и поэтому изучает карту вышек сотовой связи своего оператора, чтобы убедиться в наличии мобильной связи на своём маршруте. В последнее время Тимофею некогда анализировать данные вручную, и он решил написать программу, которая определит доступность связи на нужной Тимофею местности.

Будучи опытным программистом, Тимофей воспринимает карту местности как прямоугольную сетку. Для каждой вышки сотовой связи он выяснил её местоположение и радиус действия. Считается, что в точке на карте есть сотовая связь, если точка находится в радиусе действия хотя бы одной вышки сотовой связи. Современные вышки настолько продвинутые, что их радиус действия охватывает квадрат, а не круг:

Пример области действия вышки с радиусом, равным 2

Тимофей тоже продвинутый и умеет перемещаться из любой точки прямоугольной сетки не только по вертикали и горизонтали, но и по диагонали. Требуется понять, существует ли между двумя точками на карте такой маршрут, который подходит под требования Тимофея.

В первой строке входных данных находится количество вышек сотовой связи $N$.

В следующих $N$ строках находятся данные сотовой вышки $X_i$ $Y_i$ $R_i$, где $X_i$, $Y_i$ — координаты вышки, $R_i$ — радиус её действия и ($0 \le N, X_i, Y_i, R_i \le 1000$).

В следующей строке передаются координаты $X_s$ $Y_s$ — старт маршрута.

В следующей строке передаются координаты $X_f$ $Y_f$ — конец маршрута.

• 1 — если можно проложить маршрут, удовлетворяющий требованиям Тимофея.

• 0 — если такого маршрута не существует.