You are an adventurer who has travelled far and wide to meet the elusive Sphinx - and obtain its treasures for yourself. After many days of journeying you uncover the Sphinx's riddle.

I guard ~n~ hidden relics. Each pair of relics is bound by truths... or lies. Use my clues to determine their values - or prove that I deceive you.

Each relic has an unknown integer value. You are given information regarding the values of these relics, and you need to determine if the information is contradictory and the Sphinx is deceiving you, the information is insufficient (i.e. there could be multiple valid assignments), or if there is a single valid assignment, in which case you can obtain the Sphinx's riches.

Input

The first line contains 2 integers ~n\ m~ (~1 \leq n,m \leq 10^5~). ~n~ represents the number of relics, and ~m~ represents the number of clues you are given.

The next ~m~ lines each contain a clue of the form

u v w t

• ~u,v~: indices of two relics (1 indexed) - ~1 \leq u,v \leq n~
• ~w~: an integer - ~-10^9 \leq w \leq 10^9~
• ~t~: either 0 or 1

If ~t = 0~, the statement means ~value_u+value_v=w~. If ~t = 1~, the statement means ~value_u-value_v=w~.

Output

Determine if the constraints given by the clues lead to a contradiction, multiple possible assignments, or a single unique assignment.

• If the information is inconsistent, output contradiction.
• If the information is insufficient (i.e. there are multiple valid assignments), output insufficient.
• If there is exactly one valid assignment, output the values of all relics in order on a single line. It is possible for the values to be negative.

Clarifications

• We note that all relics have integer values, so if a set of clues would assign a relic a non-integer value you should output contradiction. I.e. ~v_1+v_2=0~ and ~v_1-v_2=1~ will assign ~v_1=\frac{1}{2}~, which is impossible.
• You might be able to determine that there is definitely insufficient information, but later on find a contradiction. In this case, you should print contradiction. I.e., if there is both insufficient and contradiction, contradiction should take precedence.

Example

Input 1

3 3
1 2 5 1
2 3 3 1
1 3 20 1

Output 1

contradiction

We are told

• ~v_1 - v_2 = 5~
• ~v_2 - v_3 = 3~ This implies that ~v_1-v_3=8~. However, we are given ~v_1-v_3=20~, so the Sphinx is playing a cruel trick on us.

Input 2

3 3
1 2 5 1
2 3 3 1
1 3 8 0

Output 2

8 3 0

We know

• ~v_1 - v_2 = 5~
• ~v_2 - v_3 = 3~
• ~v_1 + v_3 = 8~ The first two tell us that ~v_1-v_3 = 8~. This and the third clue tell us that ~v_1=8~. We can then deduce that ~v_2=3~, and ~v_3=0~.

Input 3

3 2
1 2 5 1
2 3 3 1

Output 3

insufficient

We know

• ~v_1 - v_2 = 5~
• ~v_2 - v_3 = 3~ This tells us ~v_1-v_3=8~, but this provides infinite possible assignments, so there is insufficient information to tell the values of the relics.

Input 4

1 1
1 1 3 1

Output 4

contradiction

The sole clue tells us that ~v_1-v_1=3~, but this is clearly impossible as ~v_1-v_1=0~ for any ~v_1~.

Input 5

3 2
1 2 5 0
3 3 1 1

Output 5

contradiction

Although there is insufficient information to fix 1 and 2, and you can figure that out first, the second clue also contains a contradiction: ~3-3=1~, and this takes precedence.