Background

Day 2 Problem B.

This statement is translated from EGOI2021 railway.

Problem Description

There is a railway of length $s$ kilometers connecting Zurich and Lugano. The railway passes through the beautiful Alps, creating magnificent scenery along the journey. Since some mountain passes are too high for the railway, $t$ tunnels were built along the route. Tunnel $i$ starts at $a_i$ kilometers from Zurich and ends at $b_i$ kilometers. (So the length of tunnel $i$ is $b_i-a_i$.)

You are given a train timetable between the two cities. There are $m$ trains from Zurich to Lugano; train $j$ departs at minute $c_j$. There are $n$ trains from Lugano to Zurich; train $k$ departs at minute $d_k$. All trains in operation, regardless of direction and whether they are inside a tunnel, travel at a constant speed of $1$ kilometer per minute. There are no stations along the route, and trains do not stop at signals. Therefore, each train takes exactly $s$ minutes to reach its destination.

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

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

At any time, if two trains traveling in opposite directions meet outside a tunnel, they can always pass each other safely. This also includes the case where they meet exactly at an endpoint of a tunnel. However, if two trains traveling in opposite directions meet strictly$^\dagger$ inside a tunnel, a collision occurs.

Given the tunnel information and the train timetable, determine whether a collision will occur.

$^\dagger$Strictly: as stated in the original text (strictly).

Input Format

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

The second line contains $t$ integers $a_i$ — the start point of each tunnel.

The third line contains $t$ integers $b_i$ — the end point 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

Output one line containing a string YES or NO, indicating whether a collision will occur.

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

Hint

Sample $1$ Explanation

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

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

Sample $2$ Explanation

Two trains collide in the middle of the only tunnel.

Sample $3$ Explanation

Two trains meet near the Zurich end of the tunnel.

Sample $4$ Explanation

Two trains meet near the Lugano end of the tunnel.

Constraints

For all testdata, $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. In addition, $s,c_j,d_k$ are not necessarily even.

Translated by ChatGPT 5