Supply

There is an area with $N$ military bases on a two-dimensional plane. The location of the $i$-th base is given by the coordinates $(X_i, Y_i)$. The supply unit responsible for this area wants to supply all the bases. The $i$-th base can receive supplies from day $A_i$ to day $B_i$, inclusive. Since there is an ongoing war, the supply unit must advance in the upper-right direction while maintaining a formation in which the troops as a whole move from the upper-left to the lower-right. Therefore, a day $V_i$ must be assigned to each base on which it will receive supplies such that all of the following conditions are satisfied.

• For all $i$, $A_i \le V_i \le B_i$.
• For all $i, j$, if $X_i < X_j$ and $Y_i < Y_j$, then $V_i < V_j$.
• For all $i, j$, if $i \neq j$, then $V_i \neq V_j$.

Given the locations of each base and the ranges of dates on which they can receive supplies, write a program to determine whether it is possible to supply all the bases while satisfying the conditions.

The example below shows a situation with 6 bases. Each point represents a base, and the range of dates on which it can receive supplies is given to the upper right of the point.

The figure below shows an example of assigning supply dates in the above example while satisfying all the conditions. The assigned date is shown to the lower right of each point. The curve in the figure shows possible positions of the formation of the supply unit between the 2nd and 3rd days.

• All given numbers are integers.
• $1 \le N \le 250\,000$
• $1 \le A_i \le B_i \le N$
• $1 \le X_i \le N$
• $1 \le Y_i \le N$
• All $X_i$ are distinct. In other words, if $i \neq j$, then $X_i \neq X_j$.
• All $Y_i$ are distinct. In other words, if $i \neq j$, then $Y_i \neq Y_j$.

1. (13 points) $N \le 10$.
2. (18 points) $N \le 2\,500$.
3. (22 points) $B_i = N$ for all $i$.
4. (47 points) No additional constraints.

The first line contains the number of bases $N$.

The next $N$ lines contain information about the bases. The $i$-th line contains four integers $X_i$, $Y_i$, $A_i$, and $B_i$, separated by spaces.

If it is possible to assign supply dates, print YES on the first line. On the next line, print the assigned dates in order of the base numbers, separated by spaces.

If it is impossible to assign supply dates, print NO on the first line.