You are given a sequence $a_1, a_2, \dots, a_n$ of length $n$, where each element is a positive integer in the range $[1, 10^9]$.

You are provided with $m$ pieces of information. Each piece of information is given as $i, j, k, x$, which means the sequence satisfies the condition $a_i+a_j+a_k-\max(a_i, a_j, a_k)-\min(a_i, a_j, a_k)=x$.

Construct a sequence that satisfies these conditions.

Input

The first line contains two positive integers $n$ and $m$.

The next $m$ lines each contain four positive integers $i, j, k, x$, representing a piece of information.

Output

If no solution exists, output NO on the first line.

If a solution exists, output YES on the first line. On the second line, output $n$ positive integers $a_1, a_2, \dots, a_n$ representing the constructed sequence $a$. You must ensure that each $a_i$ is a positive integer in the range $[1, 10^9]$.

Examples

Input 1

6 4
1 3 4 2
1 2 5 6
3 6 6 7
2 4 5 3

Output 1

YES
6 8 2 2 3 7

Input 2

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

Output 2

NO

Constraints

For all data, $1\leq n, m\leq 10^5$, $1\leq i, j, k\leq n$, $1\leq x\leq 10^9$.

• Subtask 1 (20 points): $n, m\leq 10$.
• Subtask 2 (10 points): $m=\binom{n}{3}$, and for any piece of information, $i\neq j, j\neq k, k\neq i$. For any set $\{i, j, k\}$ satisfying the condition, it appears exactly once in the information.
• Subtask 3 (30 points): $n, m\leq 1000$.
• Subtask 4 (40 points): No special restrictions.