Projectors
Contest: 2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 3100
Tags: flows, graphs

There are $$$n$$$ lectures and $$$m$$$ seminars to be conducted today at the Faculty of Approximate Sciences. The $$$i$$$-th lecture starts at $$$a_i$$$ and ends at $$$b_i$$$ (formally, time of the lecture spans an interval $$$[a_i, b_i)$$$, the right bound is exclusive). The $$$j$$$-th seminar starts at $$$p_j$$$ and ends at $$$q_j$$$ (similarly, time of the seminar spans an interval $$$[p_j, q_j)$$$, the right bound is exclusive).

There are $$$x$$$ HD-projectors numbered from $$$1$$$ to $$$x$$$ and $$$y$$$ ordinary projectors numbered from $$$x + 1$$$ to $$$x + y$$$ available at the faculty. Projectors should be distributed in such a way that:

- an HD-projector is used in each lecture;
- some projector (ordinary or HD) is used in each seminar;
- a projector (ordinary or HD) can only be used in one event at the same moment of time;
- if a projector is selected for an event, it is used there for the whole duration of the event;
- a projector can be reused in some following event, if it starts not earlier than current event finishes.

You are to find such distribution of projectors, if it exists.

Again, note that the right bound of the event's time range is not inclusive: if some event starts exactly when another event finishes, the projector can be reused (suppose that it is instantly transported to the location of the event).

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 300$$$) — the number of test cases.

Each test case starts with a line containing four integers $$$n, m, x, y$$$ ($$$0 \le n, m, x, y \le 300$$$; $$$n+m>0$$$, $$$x + y > 0$$$) — the number of lectures, the number of seminars, the number of HD projectors and the number of ordinary projectors, respectively.

The next $$$n$$$ lines describe lectures. Each line contains two integers $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i < b_i \le 10^6$$$) — the start time (inclusive) and finish time (exclusive) of the $$$i$$$-th lecture.

The next $$$m$$$ lines describe seminars. Each line contains two integers $$$p_j$$$, $$$q_j$$$ ($$$1 \le p_j < q_j \le 10^6$$$) — the start time (inclusive) and finish time (exclusive) of the $$$j$$$-th seminar.

Output format:
For each test case, print YES if it is possible to distribute projectors in order to meet all requirements, or NO otherwise.

In case of positive answer, output one additional line containing $$$n + m$$$ integers. The first $$$n$$$ integers should be not less than $$$1$$$ and not greater than $$$x$$$, and the $$$i$$$-th of them should be the index of HD projector used in the $$$i$$$-th lecture. The last $$$m$$$ integers should be not less than $$$1$$$ and not greater than $$$x + y$$$, and the $$$j$$$-th of them should be the index of projector used in the $$$j$$$-th seminar. If there are multiple answers, print any of them.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
2
2 2 2 2
1 5
2 5
1 5
1 4
2 0 2 10
1 3
1 3

Example output:
YES
2 1 4 3 
YES
2 1

Example input:
3
1 2 1 1
3 4
2 4
1 3
3 4 2 3
5 7
1 3
1 7
4 8
2 5
1 6
2 8
0 1 1 0
1 1000000

Example output:
YES
1 2 1 
NO
YES
1

Editorial: