Турист#2773

Турист

2 секунди

64 мегабайти

Дуже складна

Туристу набридло подорожувати вздовж координатної осі, і він вирішив подорожувати по координатній площині. Він починає зі своєї бази в точці $A_{1}$ A_1 з координатами $x_{1}$ x_1 $y_{1}$ y_1, рухається прямою лінією до орієнтира $A_{2}$ A_2 з координатами $x_{2}$ x_2 $y_{2}$ y_2, потім, не зупиняючись, продовжує прямою до наступного орієнтира $A_{3}$ A_3 у $x_{3}$ x_3 $y_{3}$ y_3, і так далі. Досягнувши останнього даного орієнтира $A_{n}$ A_n у $x_{n}$ x_n $y_{n}$ y_n, він повертається прямо на свою базу. Турист вважає свій маршрут неприємним, якщо існує пряма, по якій він не рухався, але перетнув її строго більше двох разів. Якщо такої прямої не існує, маршрут приємний.

Турист вважає, що перетнув пряму, якщо в певний момент часу він знаходився в одній півплощині відносно неї, а через дуже малий проміжок часу — в іншій (сама пряма не належить жодній із півплощин).

Напишіть програму, яка, прочитавши описи кількох маршрутів, визначає для кожного з них, чи є він приємним.

Вхідні дані

Спочатку програма повинна зчитати число маршрутів $K$ ( $2 \leq K \leq 12$ 2 \leq K \leq 12). Далі слідують $K$ однакових блоків, кожен описує один маршрут. Кожен блок починається з числа $n$ ( $2 \leq n \leq 98765$ 2 \leq n \leq 98765), після чого йдуть $n$ пар чисел, жодне з яких за модулем не перевищує $1 0^{8}$ 10^8 — це координати $x_{1}$ x_1 $y_{1}$ y_1 $x_{2}$ x_2 $y_{2}$ y_2 … $x_{n}$ x_n $y_{n}$ y_n. Усі числа для всіх маршрутів записані в одному рядку та розділені одним пробілом. Загальна кількість вершин серед усіх маршрутів, які програма повинна опрацювати за раз, не перевищує $123456$ .

Вихідні дані

Програма повинна вивести один рядок із $K$ нулів та/або одиниць, розділених пробілами, які позначають, чи відповідний маршрут є приємним ( $1$ ) чи неприємним ( $0$ ).

Приклади

Приклад 1