408484: GYM103149 B Railway

There is a railway between Zürich and Lugano of length $$$s$$$ kilometers. The railway crosses the beautiful Alps, resulting in a spectacular scenery during the ride. Since some passes are too high for the railway, there are $$$t$$$ tunnels on the track. The $$$i$$$-th of them starts $$$a_i$$$ kilometers from Zürich and ends $$$b_i$$$ kilometers from Zürich. (Thus, the length of the $$$i$$$-th tunnel is $$$b_i - a_i$$$.)

You have a timetable of the rail service between the two cities. There are $$$m$$$ services from Zürich to Lugano, the $$$j$$$-th of which departs at $$$c_j$$$ minutes, and $$$n$$$ services from Lugano to Zürich, the $$$k$$$-th of which departs at $$$d_k$$$ minutes. All trains operating on the track have a constant speed of 1 kilometer per minute, regardless of their direction and whether they are in a tunnel or not. There are no stations on the route, and the trains never stop at semaphores. Hence, each service arrives to its destination in exactly $$$s$$$ minutes.

The length of a train is negligible in comparison to the length of the railway, so in this problem please assume that each train is a point that moves along the railway.

Usually, the railway has two tracks: one in each direction. The only exception are the tunnels. Each tunnel has just a single track that can be used in either direction.

Whenever two trains going in the opposite directions meet outside a tunnel, they can pass each other safely. This includes trains meeting exactly at either end of a tunnel. On the other hand, if a pair of trains meets strictly inside a tunnel, there is a collision.

Given the description of the tunnels and the train services, determine whether there will be any collision.

The first line contains four space-separated integers $$$s$$$, $$$t$$$, $$$m$$$, $$$n$$$ ($$$1 \leq s \leq 1\,000\,000\,000$$$, $$$0 \leq t \leq 100\,000$$$, $$$0 \leq m, n \leq 2\,000$$$) – the length of the track, the number of tunnels, the number of services from Zürich and the number of services from Lugano, respectively.

The second line contains $$$t$$$ space-separated integers $$$a_i$$$ ($$$0 \leq a_i < s$$$) – the starting positions of the tunnels.

The third line contains $$$t$$$ space-separated integers $$$b_i$$$ ($$$0 < b_i \leq s$$$) – the ending positions of the tunnels.

For each $$$i$$$ between $$$1$$$ and $$$t$$$, $$$a_i < b_i$$$ holds. Additionally, for each $$$i$$$ between $$$1$$$ and $$$t-1$$$, $$$b_i < a_{i+1}$$$. (In other words, each tunnel has a positive length, the tunnels are pairwise disjoint, and they are given in increasing order of distance from Zürich.)

The fourth line contains $$$m$$$ space-separated integers $$$c_j$$$ ($$$0 \leq c_j \leq 1\,000\,000\,000$$$) – the starting times (in minutes) of the services starting in Zürich. The times are given in increasing order, that is, $$$c_j < c_{j+1}$$$ for all valid $$$j$$$.

The fifth line contains $$$n$$$ space-separated integers $$$d_k$$$ ($$$0 \leq d_k \leq 1\,000\,000\,000$$$) – the starting times (in minutes) of the services starting in Lugano. The times are given in increasing order, that is, $$$d_k < d_{k+1}$$$ for all valid $$$k$$$.

Output a single line, containing "YES" (quotes for clarity) if at least one crash occurs, or "NO" if all trains reach their destination safely.

In all subtasks except the last one, the value of $$$s$$$ and all $$$c_j$$$ and $$$d_k$$$ are even.

Subtask 1 (14 points): $$$t, m, n \leq 100$$$ and $$$s \leq 5\,000$$$.

Subtask 2 (16 points): $$$t \leq 5\,000$$$ and $$$s \leq 1\,000\,000$$$.

Subtask 3 (41 points): there are no further restrictions.

Subtask 4 (29 points): there are no further restrictions. Additionally, $$$s$$$, $$$c_j$$$ and $$$d_k$$$ are not necessarily even.

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

In the first example there are two tunnels on a track of length $$$100$$$ kilometers: one $$$20$$$ to $$$30$$$ kilometers from Zürich, the other $$$50$$$ to $$$60$$$ kilometers from Zürich. The only train coming from Zürich manages to avoid all the Lugano services as follows:

• the first is met $$$5$$$ kilometers from Zürich,
• the second is met halfway between the tunnels,
• the third is met $$$10$$$ kilometers from Lugano,
• the fourth starts long after the Zürich train had arrived at its destination.

In the second example the only two trains meet exactly in the middle of the only tunnel, resulting in a crash.

In the third example the two trains meet exactly at the end of the tunnel that is closer to Zürich. In the fourth example they meet exactly at the other end of the tunnel. Both cases are fine, the trains pass each other and reach their destination safely.