题目背景

Day 2 Problem B.

题面译自 EGOI2021 railway。

题目描述

有一条连接苏黎世和卢加诺的长度为 $s$ 千米的铁路。铁路穿过了美丽的阿尔卑斯山，造就了旅程中壮观的景色。由于一些山口对铁路来说太高了，在线路上修剪了 $t$ 条隧道。第 $i$ 条隧道在距离苏黎世 $a_i$ 千米处开始，在 $b_i$ 千米处结束。（因此，第 $i$ 条隧道的长度为 $b_i-a_i$。）

你有一份两地之间的列车时刻表。从苏黎世到卢加诺有 $m$ 班列车，第 $j$ 班列车在 $c_j$ 分钟发车；从卢加诺到苏黎世有 $n$ 班列车，第 $k$ 班列车在 $d_k$ 分钟发车。所有运行中的列车，无论其方向和是否在隧道内，速度均恒为 $1$ 千米每分钟。路程中没有车站，列车也不会在信号灯处停车。因此，每班列车恰好花费 $s$ 分钟到达终点站。

与铁路的长度相比，列车的长度可以忽略不计，所以在本题中，请假设每班列车是一个沿铁路移动的点。

通常情况下，铁路有两条轨道：两个方向各有一条。唯一的例外是隧道。每个隧道只有一条轨道，可以从任何方向通行。

无论何时，只要两班反向运行的列车在隧道外相遇时，他们总是可以安全地经过对方。这包括列车正好在隧道的端点处相遇。但另一方面，如果两班反向运行的列车在隧道内严格$^\dagger$相遇，就会发生碰撞。

已知隧道信息和列车时刻表，请判断是否会发生碰撞。

$^\dagger$严格：原文如此（strictly）。

输入格式

第一行四个整数 $s,t,m,n$——铁路长度、隧道个数、从苏黎世和卢加诺发车的列车数量。

第二行 $t$ 个整数 $a_i$——每个隧道的起点。

第三行 $t$ 个整数 $b_i$——每个隧道的终点。

第四行 $m$ 个整数 $c_j$——从苏黎世发车的时间。

第五行 $n$ 个整数 $d_k$——从卢加诺发车的时间。

输出格式

一行，一个为 YES 或 NO 的字符串，代表是否会发生碰撞。

100 2 1 4
20 50
30 60
120
30 100 200 250

NO

1000 1 1 1
600
700
100
400

YES

1000 1 1 1
600
700
100
300

NO

1000 1 1 1
600
700
100
500

NO

提示

样例 $1$ 解释

在长度为 $100$ 千米的铁路上，有两条隧道：距离苏黎世 $20\sim 30$ 千米处和 $50\sim 60$ 千米处。唯一一班从苏黎世发车的列车避开了所有从卢加诺发车的列车，如下：

• 与第一班车在距离苏黎世 $5$ 千米处相遇。
• 与第二班车在两个隧道间相遇。
• 与第三班车在距离卢加诺 $10$ 千米处相遇。
• 第四班车在该班车到站后很久才发车。

---

样例 $2$ 解释

两班列车在唯一的隧道中间相撞。

---

样例 $3$ 解释

两班列车在隧道靠近苏黎世的一端相遇。

---

样例 $4$ 解释

两班列车在隧道靠近卢加诺的一端相遇。

---

数据范围

对于全部数据，$1\le s\le 10^9$，$0\le t\le 10^5$，$0\le m,n\le 2\times 10^3$，$0\le a_i < s$，$0 < b_i\le s$，$a_i < b_i$，$b_i < a_{i+1}$，$0\le c_j,d_k\le 10^9$，$c_j < c_{j+1}$，$d_k < d_{k+1}$。

在前三个子任务中，保证 $s,c_j,d_k$ 均为偶数。

• 子任务一（$14$ 分）：$t,m,n\le 100$，$s\le 5\times 10^3$。
• 子任务二（$16$ 分）：$t\le 5\times 10^3$，$s\le 10^6$。
• 子任务三（$41$ 分）：无特殊限制。
• 子任务四（$29$ 分）：无特殊限制。另外，$s,c_j,d_k$ 不一定是偶数。