human
Consider placing N flags on a line. Flags are numbered through 1 to N.

Flag i can be placed on the coordinate X_i or Y_i. For any two different flags, the distance between them should be at least D.

Decide whether it is possible to place all N flags. If it is possible, print such a configulation.

Constraints

* 1 \leq N \leq 1000
* 0 \leq D \leq 10^9
* 0 \leq X_i < Y_i \leq 10^9
* All values in Input are integer.

Input

Input is given from Standard Input in the following format:

N D
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Print `No` if it is impossible to place N flags.

If it is possible, print `Yes` first. After that, print N lines. i-th line of them should contain the coodinate of flag i.

Examples

Input

3 2
1 4
2 5
0 6

Output

Yes
4
2
0

Input

3 3
1 4
2 5
0 6

Output

No
Using python3 can you solve the prior task?

Can you provide a Python code to print `No` if it is impossible to place N flags?
assistant
#Here is Python code to print `No` if it is impossible to place N flags.

class Two_SAT:
    """2-SATを定義する.

    """

    #入力定義
    def __init__(self,variable=[]):
        self.variable=set(variable)

        self.clause_number=0
        self.variable_number=len(variable)

        self.adjacent_out={(v,b):set() for v in variable for b in [True,False]} #出近傍(vが始点)
        self.adjacent_in={(v,b):set() for v in variable for b in [True,False]} #入近傍(vが終点)
        #※ (X,False)が not Xに対応

    #変数の追加
    def add_variable(self,*adder):
        """変数を加える.

        adder(可変長):加える変数の名前
        """
        for v in adder:
            if v not in self.variable:
                self.adjacent_in[(v,True)]=set()
                self.adjacent_in[(v,False)]=set()
                self.adjacent_out[(v,True)]=set()
                self.adjacent_out[(v,False)]=set()

                self.variable_number+=1
                self.variable.add(v)

    #節の追加
    def add_clause(self,X,F,Y,G):
        """(X=F) or (Y=G) という節を加える.

        X,Y:変数の名前
        F,G:真偽値(True or False)
        """

        assert isinstance(F,bool),"Fが真偽値ではない"
        assert isinstance(G,bool),"Gが真偽値ではない"

        for v in [X,Y]:
            if v not in self.variable:
                self.add_variable(v)

        if (Y,G) not in self.adjacent_out[(X,not F)]:
            self.clause_number+=1

            #(X,not F)→(Y,G)を追加
            self.adjacent_out[(X,not F)].add((Y,G))
            self.adjacent_in[(Y,G)].add((X,not F))

            #(Y,not G) → (X,F)を追加
            self.adjacent_out[(Y,not G)].add((X,F))
            self.adjacent_in[(X,F)].add((Y,not G))

    #節を除く
    def remove_edge(self,X,F,Y,G):
        pass

    #変数を除く
    def remove_vertex(self,*vertexes):
        pass

    #変数が存在するか否か
    def variable_exist(self,v):
        """変数 X が存在するか?

        X,Y:変数の名前
        """
        return v in self.variable

    #グラフに節が存在するか否か
    def clause_exist(self,X,F,Y,G):
        """(X=F) or (Y=G) という節が存在するか?

        X,Y:変数の名前
        F,G:真偽値(True or False)
        """
        if not(self.variable_exist(X) and self.variable_exist(Y)):
...