You are producing a song with ~n~ tones, and you must assign an integer intensity to each tone, forming an array ~a~ of length ~n~ (1-indexed). Your label gives you ~q~ constraints you must satisfy, detailing the musical preferences of your audience.

Each constraint is a tuple ~(t,l,r,v)~, where ~t~ is either atmost or atleast, ~1 \leq l \leq r \leq n~, and ~v~ is an integer.

• If ~t=~atmost, then every tone in the segment must satisfy ~a_i \leq v~ for all ~i\in[l,r]~.
• If ~t=~atleast, then every tone in the segment must satisfy ~a_i \geq v~ for all ~i\in[l,r]~.

If there exists such an array, output any one of them. Otherwise, report that it is impossible. All array elements you output must be in the range ~[-10^9, 10^9]~ (otherwise you would blow out your speakers from the volume).

Input

The first line contains two integers ~n~ and ~q~ ~(1 \leq n,q \leq 1000)~ representing the amount of tones in the song and the amount of constraints from your label.

Each of the next ~q~ lines contains a constraint in the form t l r v, where ~t~ is either atmost or atleast, ~1 \leq l \leq r \leq n~, and ~v~ is an integer ~(-10^9 \leq v \leq 10^9)~.

Output

If a valid array exists, on a single line print ~n~ integers ~a_1, a_2, \dots, a_n~ ~(-10^9 \leq a_i \leq 10^9)~ satisfying all constraints.

If no valid array exists, print NO.

Example

Input 1

5 3
atleast 1 3 2
atmost 2 5 7
atleast 4 5 0

Output 1

2 2 2 0 0

There are many possible outputs. For instance, here are some more valid arrays:

• 2 5 5 2 2
• 5 5 5 5 5

Input 2

3 3
atleast 1 2 5
atmost 2 3 3
atleast 3 3 4

Output 2

NO

The constraints on positions ~2~ and ~3~ are contradictory, so there are no valid arrays.