题目大意：有n个点和m根水管，每根水管用来单向地流躺液体的，是否能做到每根水管流入量要等于流出量，使得m根水管组成一个循环体，并满足第i根水管流量在[Li,Ri]范围内？如果有输出一个流量方案。

The terrorist group leaded by a well known international terrorist Ben Bladen is buliding a nuclear reactor to produce plutonium for the nuclear bomb they are planning to create. Being the wicked computer genius of this group, you are responsible for developing the cooling system for the reactor.

The cooling system of the reactor consists of the number of pipes that special cooling liquid flows by. Pipes are connected at special points, called nodes, each pipe has the starting node and the end point. The liquid must flow by the pipe from its start point to its end point and not in the opposite direction.

Let the nodes be numbered from 1 to N. The cooling system must be designed so that the liquid is circulating by the pipes and the amount of the liquid coming to each node (in the unit of time) is equal to the amount of liquid leaving the node. That is, if we designate the amount of liquid going by the pipe from i-th node to j-th as f_ij, (put f_ij = 0 if there is no pipe from node i to node j), for each i the following condition must hold:

f_i,1+f_i,2+…+f_i,N = f_1,i+f_2,i+…+f_N,iEach pipe has some finite capacity, therefore for each i and j connected by the pipe must be f_ij <= c_ij where cij is the capacity of the pipe. To provide sufficient cooling, the amount of the liquid flowing by the pipe going from i-th to j-th nodes must be at least l_ij, thus it must be f_ij >= l_ij.

Given cij and l_ij for all pipes, find the amount f_ij, satisfying the conditions specified above.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Input

The first line of the input file contains the number N (1 <= N <= 200) – the number of nodes and and M – the number of pipes. The following M lines contain four integer number each – i, j, lij and cij each. There is at most one pipe connecting any two nodes and 0 <= l_ij <= c_ij <= 10^5 for all pipes. No pipe connects a node to itself. If there is a pipe from i-th node to j-th, there is no pipe from j-th node to i-th.

Output

On the first line of the output file print YES if there is the way to carry out reactor cooling and NO if there is none. In the first case M integers must follow, k-th number being the amount of liquid flowing by the k-th pipe. Pipes are numbered as they are given in the input file.

Sample Input

2
4 6
1 2 1 2
2 3 1 2
3 4 1 2
4 1 1 2
1 3 1 2
4 2 1 2
4 6
1 2 1 3
2 3 1 3
3 4 1 3
4 1 1 3
1 3 1 3
4 2 1 3

Sample Input

NO
YES
1
2
3
2
1
1

解题思路

这是有上下界的网络流，与网络最大流的区别是多了个下界，无源点、汇点。在求网络流的时候，上界是一定满足的，因为能流（不超过上界）才流过去，如何满足下界呢？统计一下每个点最少流入量和最少流出量，建立一个超级源点S，分别向每个点流入他们的最少流入量，建立一个超级汇点T，每个点分别向T流出最少流出量，这样就保证每个点至少流入流出多少了，解决了下界问题，原来的有向边如果流量在[x,y]范围内，那么就建立一条流量为y-x的有向边（相当于流量x已经流了）。就这样，从S点往T点求网络最大流，如果最大流等于各点流入量之和（或者各点流出量之和），也即满足在流量平衡的情况下满足下界和上界，那就就有解，其中一个解（可行流）就是每条边的流量为反向边的流量（自由流）加上原来正向边的下界（必须流）。

如a向b至少流c，至多流d，那么S→b为c，a→T为c，a→b为d-c，如果S能够流c到T，也就说明b能够通过其他边流c到a，相当于a能流c到b了。由于一个点可能有很多出边、入边，我们可以先统计每个点最少的流入量和流出量，各点流入量之和必定等于各点流出量之和，因为有一个下界x，那么ru[b]+=x、chu[a]+=x，最终他们的和一定相等。a到b有边而且a到c右边，那么a的至少有2个流出下界，即建2条a到T的有向边，两条边可以合并成一条，容量为两个下界之和，故统计好最少流入量、最少流出量再建边，相当于把起点终点相同的边合并到一起而已。

S能流到T，说明下界满足，那怎么找可行流呢？对于每一条边，除了必须要流的（下界），还有可以流的，如果反向边有流量，说明该边流出了流量——自由流，其总流量为自由流流量加上下界流量。

程序实现

如果a到b有下界x，c到a有下界y，对于a来说，需要建立a到T容量为x的边，S到a容量为y的边，显然可以有S→a→T，如果x大，那就只需要建立S到a容量为x-y的边，因为y我们可以提前流了；同理，如果y到，我们只需要建立a到T容量为y-x的边。这样可以减少图中的边，跑网络流可以稍微快一点点。实现也不麻烦，只记录进入每个点的流量，如果流量为正，说明需要流入，那就建立S到a的边；如果流量为负，说明需要流入负值即流出，建立a到T的边。