Problem Background

Day 2 Problem B.

The problem statement is translated from EGOI2021 railway.

Problem Description

There is a railway connecting Zurich and Lugano with a length of $s$ kilometers. The railway passes through the beautiful Alps, creating spectacular scenery during the journey. Due to some mountain passes being too high for the railway, $t$ tunnels have been cut along the route. The $i$-th tunnel starts at $a_i$ kilometers from Zurich and ends at $b_i$ kilometers. (Thus, the length of the $i$-th tunnel is $b_i - a_i$.)

You have a timetable for trains between the two cities. There are $m$ trains from Zurich to Lugano, with the $j$-th train departing at $c_j$ minutes; and $n$ trains from Lugano to Zurich, with the $k$-th train departing at $d_k$ minutes. All trains in operation, regardless of their direction or whether they are in a tunnel, maintain a constant speed of $1$ kilometer per minute. There are no stations on the route, and trains do not stop at signals. Therefore, each train exactly takes $s$ minutes to reach the destination.

Compared to the length of the railway, the length of the trains can be ignored, so assume each train is a point moving along the railway in this problem.

Normally, the railway has two tracks: one for each direction. The only exception is tunnels. Each tunnel has only one track and can be traversed in either direction.

At any time, when two trains traveling in opposite directions meet outside a tunnel, they can always safely pass each other. This includes trains meeting exactly at the endpoints of a tunnel. On the other hand, if two trains traveling in opposite directions strictly meet inside a tunnel, a collision will occur.

Given the information about the tunnels and the train timetable, determine if a collision will occur.

Input Format

The first line contains four integers $s, t, m, n$ — the length of the railway, the number of tunnels, the number of trains departing from Zurich and Lugano, respectively.

The second line contains $t$ integers $a_i$ — the starting points of each tunnel.

The third line contains $t$ integers $b_i$ — the ending points of each tunnel.

The fourth line contains $m$ integers $c_j$ — the departure times from Zurich.

The fifth line contains $n$ integers $d_k$ — the departure times from Lugano.

Output Format

A single line containing a string YES or NO, indicating whether a collision will occur.

Sample Input and Output

Input Sample #1

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

Output Sample #1

NO

Input Sample #2

1000 1 1 1
600
700
100
400

Output Sample #2

YES

Input Sample #3

1000 1 1 1
600
700
100
300

Output Sample #3

NO

Input Sample #4

1000 1 1 1
600
700
100
500

Output Sample #4

NO

Notes

Sample 1 Explanation

On a railway of length $100$ kilometers, there are two tunnels: one between $20\sim 30$ kilometers from Zurich and another between $50\sim 60$ kilometers. The only train departing from Zurich avoids all trains departing from Lugano as follows:

• Meets the first train at $5$ kilometers from Zurich.
• Meets the second train between the two tunnels.
• Meets the third train at $10$ kilometers from Lugano.
• The fourth train departs long after this train has arrived.

Sample 2 Explanation

The two trains collide in the middle of the only tunnel.

Sample 3 Explanation

The two trains meet at the Zurich end of the tunnel.

Sample 4 Explanation

The two trains meet at the Lugano end of the tunnel.

Data Range

For all data, $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}$.

In the first three subtasks, it is guaranteed that $s, c_j, d_k$ are all even.

• Subtask 1 (14 points): $t, m, n \le 100$, $s \le 5 \times 10^3$.
• Subtask 2 (16 points): $t \le 5 \times 10^3$, $s \le 10^6$.
• Subtask 3 (41 points): No additional constraints.
• Subtask 4 (29 points): No additional constraints. Additionally, $s, c_j, d_k$ are not necessarily even.

见题面 Input 部分

见题面 Output 部分