408454: GYM103119 K Candy Ads

The Ingenious Candy Processing Company (ICPC) recently hits the market with a new kind of candy. The ICPC is planning to display $$$n$$$ advertisement posters on the screen at the center of the market, labeled by $$$1,2,\cdots,n$$$. The screen consists of multiple pixels, and each ad poster will occupy $$$w\times h$$$ pixels. Specifically, the $$$k$$$-th ad poster will occupy all the pixels $$$(i,j)$$$ such that $$$x_k\leq i\leq x_k+w-1$$$ and $$$y_k\leq j\leq y_k+h-1$$$ from the morning of the $$$l_k$$$-th day to the night of the $$$r_k$$$-th day.

Picture from Wikimedia Commons

You are a middleman in the market. Your job is to determine which ad posters to be accepted such that no two ad posters will occupy the same pixel at the same time. You are given extra $$$m$$$ requests from the ICPC, the $$$k$$$-th of which is that if both the $$$a_k$$$-th ad poster and the $$$b_k$$$-th ad poster are rejected, the ICPC will cancel the whole trade.

Please determine which ad posters to display such that the trade won't be canceled, or determine it is impossible.

The input contains only a single case.

The first line of the input contains three integers $$$n,w$$$ and $$$h$$$ ($$$1 \leq n \leq 50\,000$$$, $$$1\leq w,h\leq 2\,000$$$), denoting the number of ad posters and the size of each ad poster.

In the next $$$n$$$ lines, the $$$i$$$-th line $$$(1 \le i \le n)$$$ contains four integers $$$l_i,r_i,x_i$$$ and $$$y_i$$$ ($$$1\le l_i\leq r_i\leq 2\,000$$$, $$$1\leq x_i,y_i\leq 2\,000$$$), describing the $$$i$$$-th ad poster.

In the next line, there contains a single integer $$$m$$$ ($$$0\leq m\leq 100\,000$$$), denoting the number of requests.

In the next $$$m$$$ lines, the $$$i$$$-th line $$$(1 \le i \le m)$$$ contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1\leq a_i,b_i\leq n$$$, $$$a_i\neq b_i$$$), describing the $$$i$$$-th request.

If it is impossible to make such a trade, print a single line containing "No". Otherwise, print "Yes" in the first line, then print $$$n$$$ digits in the second line, denoting the solution you find. If the $$$i$$$-th ad poster is accepted, the $$$i$$$-th digit should be '1', and if it is rejected, the $$$i$$$-th digit should be '0'.

If there is more than one solution, any one of them will be accepted.

2 2 2
1 2 1 1
2 3 2 2
1
1 2

Yes
10

3 2 2
1 2 1 1
1 3 1 2
2 3 2 2
3
1 2
2 3
1 3

No