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).
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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 2 2 2
1 5
2 5
1 5
1 4
2 0 2 10
1 3
1 3
|
YES
2 1 4 3
YES
2 1
|
|
2
|
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
|
YES
1 2 1
NO
YES
1
|