RUN is a famous music box manufacturing club at KAIST (Rhythm Under Nature). RUN creates sophisticated music boxes that express various kinds of music in an emotional way, and also composes music tailored to clients' requests and turns them into music boxes.

This time, a total of $M$ clients have requested compositions from RUN. Each of them has made special requests, but they all commonly asked for music consisting of $N$ notes.

Normally, it would be standard to create $M$ different pieces of music satisfying each client's request. However, Junhwi, the president of RUN, found it too troublesome to create $M$ separate pieces. Therefore, he aims to compose only a single piece of music that satisfies as many clients as possible.

After analyzing the clients' requests, Junhwi managed to summarize them in a relatively simple form. Let the intensity of the $i$-th note in the music be represented by an integer $A_i$ such that $0 \le A_i \le 3$. Then, the requirement of the $i$-th client can be expressed as follows: for integers $1 \le x_i < y_i < z_i < w_i \le N$ and $0 \le k_i \le 3$, $A_{x_i} + A_{y_i} + A_{z_i} + A_{w_i} \equiv k_i \pmod{4}$.

Junhwi wants to compose a single piece of music that satisfies as many clients as possible. Specifically, he wants to construct a sequence of $N$ notes that satisfies the requests of at least $\left\lfloor \frac{M}{4} \right\rfloor$ clients. Although Junhwi has already determined the melody, he has not yet decided the intensity of each note. Help Junhwi determine the intensities so that at least $\left\lfloor \frac{M}{4} \right\rfloor$ clients are satisfied.

Constraints

• $4 \le N \le 100,000$
• $0 \le M \le 100,000$
• $1\le x_i<y_i<z_i<w_i\le N, 0\le k_i\le 3(1\le i\le M)$

Subtasks

1. (20 points) $M\le 7$

2. (20 points) $N\le 8, M\le 100$

3. (20 points) For all $i(1\le i\le M)$, $w_i=N$

4. (40 points) No additional constraints.

Input

The first line contains two nonnegative integers $N$ and $M$ separated by a space.

Each of the next $M$ lines contains five integers $x_i, y_i, z_i, w_i, k_i$ separated by spaces, representing the requirement of the $i$-th client.

Output

Output a single line containing $N$ integers $A_1, A_2, \cdots, A_N$ separated by spaces, where $A_i$ denotes the intensity of the $i$-th note. It is guaranteed that the valid output always exists.

Example

Example 1

Input

5 2
1 3 4 5 2
1 2 3 5 0

Output

0 0 0 0 0

Explanation

This output satisfies only the conditions of the second requirement. Note that in this example, $\lfloor \frac{2}{4} \rfloor = 0$, so any sequence of length $N$ whose elements are among $0, 1, 2,$ and $3$ is considered a valid answer.