Zer is a programmer who has a friend named Nir. Nir always shows off how great EEE is. One day Nir came to Zer with a EEE'ish problem. Nir gave Zer a circuit. The circuit has N nodes and M wires where each wire connects two different nodes. Moreover, a wire that connects node U to node V can only pass electricity from U to V but not vice-versa, that means the wires are uni-directed.
Nir gave Zer a list of these wires detailing which wire connects which nodes. There are also a lower bound and an upper bound for each wire describing the minimum amount of electricity that must pass through the wire and the maximum amount of electricity that can pass through the wire, respectively. Also, according to KCL (Kirchhoff's Circuit Law), the net amount of electricity entering a node must be equal to the net amount of electricity exiting that node.
Zer has to give a valid configuration for the problem Nir gives. He has to tell the amount of electricity flowing through each wire such that all the above constraints are satisfied. As a good problem solver, your help would be highly appreciated by Zer.
Input
The input starts with two integers N and M, the number of nodes and the number of wires respectively.
Each of the next M lines contains four integers U, V, L, H, stating that a wire connects node U and V such that electricity can pass from U to V and the amount of electricity must be at least L and at most H.
It is guaranteed that no two wires will have exactly the same U and V i.e. there will be at most one wire that allows electricity to pass from a node U to another node V.
Constraints:
1 ≤ N ≤ 100
For each wire,
1 ≤ U, V ≤ N
U != V
0 ≤ L ≤ H ≤ 106
Output
If no valid configuration exists, print NO in a single line.
Otherwise, print YES followed by M lines. Each line should contain the amount of electricity flowing through each wire in the same order as given in input.
If multiple valid configurations exist, print any of them in such a case.
Samples
| Input | Output |
|---|---|
3 3 1 2 1 2 2 3 0 3 3 1 2 6 | YES 2 2 2 |
| Input | Output |
|---|---|
3 3 1 2 1 2 2 3 0 3 3 1 4 5 | NO |
| Input | Output |
|---|---|
4 5 1 2 1 2 2 3 0 3 3 1 2 6 3 4 1 1 4 3 1 1 | YES 2 2 2 1 1 |
