Задача F. Марсианские автобусы ≡

Условие

В марсианской столице очень необычная система общественного транспорта: остановки делятся на те, на которых можно выходить из автобуса, и те, на которых можно в него садиться. При этом для каждой остановки есть отрезок дороги, до каждой точки которого можно добраться из этой остановки. До точек, не принадлежащих отрезку добраться из этой остановки невозможно.

В столице всего одна дорога, весь город построен вдоль нее, так что положение каждой остановки задается одной координатой.

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

Администрация города решила разработать систему, воспользовавшись которой каждый житель сможет определить существует ли для него путь из дома до работы. Считается, что зарплаты жителей хватает только на один проезд на автобусе(жители не могут ехать с пересадками). Эту работу решено поручить вам.

N - количество жителей города. M - количество автобусных маршрутов.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

2
1 3
2 4
3
1 1 3 3
2 2 4 4
-100 100 1024 1024

1 1

3
3 9
8 2
5 9
4
7 9 1 9
0 7 4 8
3 3 7 8
7 8 2 6

0 1 1

5
9 4
5 8
0 7
3 0
2 1
7
5 7 3 6
1 8 3 9
0 3 4 6
2 6 1 2
2 9 7 9
2 2 0 0
3 3 2 2

2 0 0 0 2