После удаления кубика

C++17, C++20, Python 3, Go, Kotlindaily-space-003-removal-connectivity

Из модели, заданной различными единичными кубиками, удаляют один указанный кубик. Определите, остаётся ли модель связной по граням.

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

Входные данные

Первая строка содержит $N$ ( $1 \le N \le 100000$ ). Следующие $N$ строк содержат различные целые тройки $x_i,y_i,z_i$ ( $-10^6 \le x_i,y_i,z_i \le 10^6$ ). Последняя строка содержит тройку $a,b,c$ — координаты удаляемого кубика. Гарантируется, что такой кубик присутствует в модели.

Выходные данные

Выведите 1, если оставшаяся модель связна, и 0 иначе.

Примеры

Пример 1

Input

Output

Удаление среднего кубика разрывает цепь.

Пример 2

Input

1
0 0 0
0 0 0

Output

Пустой остаток.

Пример 3

Input

Output

Обходной путь в блоке.

Примечания

Исследуется только состояние после одного удаления. Падающие под действием тяжести кубики моделировать не нужно.