Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

flows

graphs

*3100

No tag edit access

The problem statement has recently been changed. View the changes.

×
K. Projectors

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputThere 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

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

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.

Examples

Input

2 2 2 2 2 1 5 2 5 1 5 1 4 2 0 2 10 1 3 1 3

Output

YES 2 1 4 3 YES 2 1

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

Output

YES 1 2 1 NO YES 1

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/08/2023 05:53:36 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|