Антон разрабатывает графический движок для 2D игр, который должен покорить рынок. Для того, чтобы объекты отображались корректно, ему нужно уметь выяснять, перекрывают ли объекты друг друга, если игрок смотрит в определённом направлении.
В предварительной версии движка объекты — это непересекающиеся отрезки на плоскости. Отрезок $$$a$$$ перекрывает отрезок $$$b$$$ по направлению вектора $$$\vec{v}$$$, если найдутся такие точки $$$A$$$ на отрезке $$$a$$$ и $$$B$$$ на отрезке $$$b$$$, что вектор $$$\overrightarrow{AB}$$$ сонаправлен с вектором $$$\vec{v}$$$. Другими словами, какая-либо точка отрезка $$$a$$$, двигаясь по направлению вектора $$$\vec{v}$$$, окажется на отрезке $$$b$$$.
Антон сейчас слишком занят поиском инвесторов, поэтому попросил вас реализовать часть движка, которая проверяет перекрытие отрезков.
Первая строка содержит целое число $$$n$$$ — количество проверок на перекрытие отрезков, которые необходимо выполнить ($$$1 \le n \le 50\,000$$$).
Каждая из следующих $$$n$$$ строк содержит 10 целых чисел: $$$ax_1$$$, $$$ay_1$$$, $$$ax_2$$$, $$$ay_2$$$, $$$bx_1$$$, $$$by_1$$$, $$$bx_2$$$, $$$by_2$$$, $$$vx$$$, $$$vy$$$ — координаты концов первого отрезка, координаты концов второго отрезка и координаты вектора, задающего направление, соответственно. Все координаты не превосходят $$$10^6$$$ по абсолютной величине. Гарантируется, что отрезки невырожденные и не содержат общих точек, а также что вектор $$$\vec{v}$$$ ненулевой.
Для каждой проверки выведите в отдельной строке «Yes», если первый отрезок перекрывает второй отрезок по заданному направлению, иначе выведите «No».
2 0 2 1 1 2 2 3 1 1 1 0 2 1 1 2 2 3 1 -1 -1
Yes No
