정말 그레이트하군

격자(grating)는 "본질적으로 동일하고 서로 평행하며 길쭉한 요소들이 일정한 간격으로 늘어선 것"으로 정의된다. 대부분은 평행한 길쭉한 요소 한 묶음으로 이루어지지만, 두 묶음으로 이루어져 두 번째 묶음이 첫 번째와 수직인 경우도 있다. 격자 업계에서는 이런 격자가 자연스럽게 만들어내는 격자 모양 때문에 "grid" 또는 "mesh" 격자라고 부른다.

조지는 George and Gary's Great Grating Group의 수석 혁신가로, 격자 업계를 뒤흔들 다음 큰 아이디어를 찾고 있다. 어느 날 그는 번뜩이는 생각을 한다. 격자의 길쭉한 요소는 왜 꼭 평행해야 하는가? 임의의 방향으로 용접된 금속 선으로 격자를 만들면 어떨까? 선들은 수직일 수도 평행일 수도 있지만, 꼭 그럴 필요는 없다. 다만 모든 아이디어에는 한계가 있다. 격자는 가로 $l$, 세로 $w$인 직사각형 테두리 안에 있다. 그리고 $n$개의 금속 선을 격자에 용접하는데, 각 선은 두 끝점이 모두 직사각형 테두리 위에 놓인 선분으로 정의된다.

George and Gary's Great Grating Group이 만드는 격자 대부분은 빗물받이로 쓰인다. 빗물받이의 가장 큰 문제 중 하나는 사람들이 휴대폰을 빠뜨리는 것이다. 그래서 조지는 격자 설계가 주어졌을 때, 격자의 특정 위치에 평평하게 떨어진 휴대폰이 빠질지 알고 싶어 한다. 이를 위해 그는 수석 물리학자 Gary에게 자문을 구하고, Gary는 다음과 같이 설명한다.

직사각형 휴대폰이 격자의 어떤 위치에 평평하게 떨어졌다고 하자. 격자의 금속 선이 휴대폰 본체와 만나는 점을 모두 찾는다(무한히 많을 수도 있다). 그다음 이 교점들의 볼록 껍질(convex hull)을 구한다. 휴대폰의 무게중심이 볼록 껍질의 경계 위에 있거나 내부에 있으면 휴대폰은 격자를 통과하지 않는다. 그렇지 않으면 떨어진다. 무게중심이 볼록 껍질의 경계 위에 있으면 떨어지지 않는다는 점에 유의하라.

조지는 무게가 휴대폰 전체에 고르게 분포한다고 가정하므로, 무게중심은 직사각형의 중심에 있다. 휴대폰은 경계를 포함한다. 조지가 이 문제를 풀 수 있도록 도와줄 수 있는가?

첫 줄에는 공백으로 구분된 정수 네 개가 주어진다. $l$, $w$ ($1 \leq l, w \leq 10^6$), $n$ ($1 \leq n \leq 10^3$), $p$ ($1 \leq p \leq 10^2$)이며, 각각 격자의 길이, 격자의 너비, 격자에 용접된 금속 선의 개수, 조지가 고려하는 휴대폰 위치의 개수이다. 좌표평면에서 격자의 테두리는 한 꼭짓점이 $(0, 0)$이고 맞은편 꼭짓점이 $(l, w)$인, 축에 맞춰진 직사각형이다.

이어서 $n$개의 줄에 공백으로 구분된 정수 $x_1$, $y_1$, $x_2$, $y_2$가 각각 주어지며, 끝점이 $(x_1, y_1)$과 $(x_2, y_2)$인 선분으로 금속 선 하나를 나타낸다. 두 끝점은 격자 테두리의 서로 다른 두 변 위에 있다고 보장된다.

마지막으로 $p$개의 줄에 공백으로 구분된 정수 $a_1$, $b_1$, $a_2$, $b_2$가 각각 주어지며, 왼쪽 아래 꼭짓점이 $(a_1, b_1)$이고 오른쪽 위 꼭짓점이 $(a_2, b_2)$인, 축에 맞춰진 직사각형으로 휴대폰이 떨어진 위치를 나타낸다. $a_2 > a_1$이고 $b_2 > b_1$이며, $a_1$과 $a_2$는 $[0, l]$ 범위에, $b_1$과 $b_2$는 $[0, w]$ 범위에 있다고 보장된다.

휴대폰 낙하 위치마다, 휴대폰이 격자를 통과해 떨어지면 "Yes", 그렇지 않으면 "No"를 한 줄에 하나씩 출력한다.