题目描述

题目译自 European Girls' Olympiad in Informatics 2021 Day2 T2. Railway

苏黎世和卢加诺之间有一条全长 $s$ 公里的铁路。这条铁路穿越壮丽的阿尔卑斯山脉，沿途风景美不胜收。由于一些山口太高，铁路无法通过，因此轨道上有 $t$ 个隧道。第 $i$ 个隧道从苏黎世起 $a_i$ 公里处开始，到 $b_i$ 公里处结束。（因此，第 $i$ 个隧道的长度为 $b_i - a_i$。）

你拿到了一份两城之间的铁路服务时刻表。从苏黎世到卢加诺有 $m$ 趟列车，第 $j$ 趟在 $c_j$ 分钟时发车；从卢加诺到苏黎世有 $n$ 趟列车，第 $k$ 趟在 $d_k$ 分钟时发车。所有列车无论方向或是否在隧道内，均以恒定速度 $1$ 公里/分钟行驶。途中没有车站，列车也不会在信号灯处停靠。因此，每趟列车都将在正好 $s$ 分钟后抵达目的地。

相较于铁路的长度，列车的长度可以忽略不计，因此在本题中，请假设每列列车是一个沿铁路移动的点。

通常，铁路有双向轨道：每个方向各一条。唯一的例外是隧道，每个隧道只有一条可双向使用的单轨。

当两列反向行驶的列车在隧道外相遇时，它们可以安全通过，包括恰好在隧道两端相遇的情况。然而，如果两列列车在隧道内部（严格来说）相遇，就会发生碰撞。

给定隧道和列车服务的描述，你需要判断是否会发生任何碰撞。

输入格式

第一行包含四个用空格分隔的整数 $s,t,m,n$ $(1 \leq s \leq 10^9, 0 \leq t \leq 100000, 0 \leq m, n \leq 2000)$，分别表示铁路长度、隧道数量、从苏黎世出发的列车数量和从卢加诺出发的列车数量。

第二行包含 $t$ 个用空格分隔的整数 $a_i$ $(0 \leq a_i < s)$，表示每个隧道的起始位置。

第三行包含 $t$ 个用空格分隔的整数 $b_i$ $(0 < b_i \leq s)$，表示每个隧道的结束位置。

对于每个 $i$ $(1 \leq i \leq t)$，保证 $a_i < b_i$。此外，对于每个 $i$ $(1 \leq i \leq t-1)$，$b_i < a_{i+1}$。（换句话说，每个隧道长度为正，隧道互不相交，且按距苏黎世的距离递增排序。）

第四行包含 $m$ 个用空格分隔的整数 $c_j$ $(0 \leq c_j \leq 10^9)$，表示从苏黎世出发的列车发车时间（分钟）。时间按递增顺序给出，即对于所有有效的 $j$，$c_j < c_{j+1}$。

第五行包含 $n$ 个用空格分隔的整数 $d_k$ $(0 \leq d_k \leq 10^9)$，表示从卢加诺出发的列车发车时间（分钟）。时间按递增顺序给出，即对于所有有效的 $k$，$d_k < d_{k+1}$。

输出格式

输出一行，如果至少发生一次碰撞，输出 YES；如果所有列车都能安全到达目的地，输出 NO。

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

NO

铁路全长 $100$ 公里，有两个隧道：一个从苏黎世起 $20$ 公里到 $30$ 公里，另一个从 $50$ 公里到 $60$ 公里。唯一从苏黎世出发的列车成功避开了所有从卢加诺出发的列车，具体如下：

• 与第一趟列车在距苏黎世 $5$ 公里处相遇。
• 与第二趟列车在两隧道之间的中点相遇。
• 与第三趟列车在距卢加诺 $10$ 公里处相遇。
• 第四趟列车在苏黎世列车到达目的地很久后才发车。

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

两列列车恰好在另一端的隧道端点相遇。这两种情况均安全，列车可以互相通过并安全到达目的地。

数据范围与提示

除最后一个子任务外，$s$ 以及所有 $c_j$ 和 $d_k$ 均为偶数。

详细子任务附加限制及分值如下表所示。