K. Projectors
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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

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