철도

취리히와 루가노 사이에 길이 $s$ 킬로미터의 철도가 있다. 이 철도는 아름다운 알프스를 가로지르기 때문에 이동하는 동안 장관을 이루는 풍경을 볼 수 있다. 일부 고개는 철도가 지나가기에 너무 높기 때문에 선로에는 $t$개의 터널이 있다. 그중 $i$번째 터널은 취리히에서 $a_i$ 킬로미터 지점에서 시작해 취리히에서 $b_i$ 킬로미터 지점에서 끝난다. (따라서 $i$번째 터널의 길이는 $b_i - a_i$이다.)

두 도시 사이를 오가는 철도 $m$편의 시간표가 있다. 취리히에서 루가노로 가는 열차가 있는데, 그중 $j$번째 열차는 $c_j$분에 출발하고, 루가노에서 취리히로 가는 열차가 $n$편 있는데, 그중 $k$번째 열차는 $d_k$분에 출발한다. 선로를 달리는 모든 열차는 방향과 터널 안에 있는지 여부에 관계없이 시속 $1$ 킬로미터, 즉 분당 $1$ 킬로미터의 일정한 속력으로 움직인다. 경로에는 역이 없고 열차는 신호기에서 멈추지 않는다. 따라서 각 열차는 정확히 $s$분 만에 목적지에 도착한다.

열차의 길이는 철도의 길이에 비해 무시할 수 있으므로 이 문제에서는 각 열차를 철도를 따라 움직이는 점으로 간주한다.

보통 철도에는 각 방향마다 하나씩 두 개의 선로가 있다. 유일한 예외는 터널이다. 각 터널에는 양방향으로 사용할 수 있는 단일 선로만 있다.

반대 방향으로 가는 두 열차가 터널 밖에서 만나면 안전하게 서로 지나칠 수 있다. 이는 터널의 양 끝 중 한 곳에서 정확히 만나는 경우도 포함한다. 반면 한 쌍의 열차가 터널 내부에서 만나면 충돌한다.

터널과 열차 서비스에 대한 설명이 주어졌을 때 충돌이 발생하는지 판별하라.

첫째 줄에는 공백으로 구분된 네 개의 정수 $s$, $t$, $m$, $n$이 주어진다. ($1 \le s \le 1\,000\,000\,000$, $0 \le t \le 100\,000$, $0 \le m, n \le 2\,000$) 각각 선로의 길이, 터널의 개수, 취리히에서 출발하는 열차의 수, 루가노에서 출발하는 열차의 수이다.

둘째 줄에는 공백으로 구분된 $t$개의 정수 $a_i$가 주어진다. ($0 \le a_i < s$) 터널의 시작 위치이다.

셋째 줄에는 공백으로 구분된 $t$개의 정수 $b_i$가 주어진다. ($0 < b_i \le s$) 터널의 끝 위치이다.

$1$ 이상 $t$ 이하의 각 $i$에 대해 $a_i < b_i$이다. 또한 $1$ 이상 $t-1$ 이하의 각 $i$에 대해 $b_i < a_{i+1}$이다. (즉, 각 터널의 길이는 양수이고, 터널들은 서로 겹치지 않으며, 취리히에서의 거리가 증가하는 순서로 주어진다.)

넷째 줄에는 공백으로 구분된 $m$개의 정수 $c_j$가 주어진다. ($0 \le c_j \le 1\,000\,000\,000$) 취리히에서 출발하는 열차의 출발 시각(분)이다. 시각은 증가하는 순서로 주어지며, 모든 유효한 $j$에 대해 $c_j < c_{j+1}$이다.

다섯째 줄에는 공백으로 구분된 $n$개의 정수 $d_k$가 주어진다. ($0 \le d_k \le 1\,000\,000\,000$) 루가노에서 출발하는 열차의 출발 시각(분)이다. 시각은 증가하는 순서로 주어지며, 모든 유효한 $k$에 대해 $d_k < d_{k+1}$이다.

충돌이 한 번이라도 발생하면 "YES"를, 모든 열차가 안전하게 목적지에 도착하면 "NO"를 한 줄에 출력한다. (따옴표는 명확성을 위해 표시한 것이다.)

마지막을 제외한 모든 소문제에서 $s$의 값과 모든 $c_j$, $d_k$는 짝수이다.

첫 번째 예제에서 길이 $100$ 킬로미터의 선로에는 두 개의 터널이 있다. 하나는 취리히에서 $20$에서 $30$ 킬로미터 지점, 다른 하나는 취리히에서 $50$에서 $60$ 킬로미터 지점이다. 취리히에서 출발하는 유일한 열차는 다음과 같이 루가노에서 오는 모든 열차를 피한다.

• 첫 번째 열차는 취리히에서 $5$ 킬로미터 지점에서 만난다.
• 두 번째 열차는 두 터널 사이 중간 지점에서 만난다.
• 세 번째 열차는 루가노에서 $10$ 킬로미터 지점에서 만난다.
• 네 번째 열차는 취리히 열차가 목적지에 도착한 한참 후에 출발한다.

두 번째 예제에서 유일한 두 열차는 유일한 터널의 정중앙에서 만나 충돌한다.

세 번째 예제에서 두 열차는 취리히에 더 가까운 터널의 끝에서 정확히 만난다. 네 번째 예제에서는 터널의 다른 쪽 끝에서 만난다. 두 경우 모두 문제없이 열차가 서로를 지나쳐 목적지에 안전하게 도착한다.