Problem 59: Feasible Flow with Lower Bounds

Problem Statement: Given a flow network with lower and upper bounds on each edge, decide if there exists a feasible flow that satisfies all edges' requirements and compute one if it exists.

Input

The first line contains n and m, the number of nodes and edges. Each of the next m lines contains four integers u, v, l, and c, where l is the lower bound and c is the capacity (upper bound). The last line contains two integers s and t, the source and sink.

Output

If a feasible flow exists, print "YES" followed by a possible flow on each edge in order. Otherwise, print "NO".

Examples


Input:
4 5
1 2 1 5
1 3 0 4
2 3 1 3
2 4 0 2
3 4 2 5
1 4

Output:
YES
1
0
1
0
2

Solution Explanation

Convert the network using flow adjustments by subtracting the lower bound from each edge and then checking if a circulation exists that meets the deficits. Then add back the lower bounds to obtain the feasible flow.

Solution in C++


                [ a solution will be implemented when possible]