RUN은 카이스트의 유명한 오르골 제작 동아리(Rhythm Under Nature)이다. RUN은 다양한 음악을 감성적으로 표현하는 고급스러운 오르골들을 만들며, 의뢰인의 요구에 맞는 음악을 작곡하여 오르골로 만들어주기도 한다.

이번에는 총 $M$명의 의뢰인이 RUN에 작곡을 요청하였다. 이들은 각자 특별한 요구를 하였으나, 공통적으로 총 $N$개의 음으로 구성된 음악을 요청하였다.

원래대로라면 각 의뢰인들의 요구에 알맞은 $M$개의 음악을 만드는 것이 일반적이지만, RUN의 회장인 준휘는 $M$개의 음악을 만드는 것은 너무나도 귀찮은 일이라고 생각하였다. 따라서 준휘는 단 한 개의 음악만을 만들어서 최대한 많은 의뢰인들이 만족하도록 하고자 한다.

각 의뢰인들의 요구를 분석한 결과, 준휘는 각 의뢰인들의 요구를 비교적 단순한 형태로 요약하는데에 성공하였다. 음악에서 $i$번째 음의 세기를 $0$ 이상 $3$ 이하의 정수 $A_i$와 같이 나타내자. 이때 $i$번째 의뢰인의 요구는 $1$이상 $N$ 이하의 정수 $x_i<y_i<z_i<w_i$과 $0$ 이상 $3$ 이하의 정수 $k_i$에 대해서 $A_{x_i}+A_{y_i}+A_{z_i}+A_{w_i}\equiv k_i\pmod 4$와 같이 나타난다.

준휘는 단 하나의 음악을 작곡하여 많은 의뢰인들의 요구를 충족시키고자 한다. 준휘는 적어도 $\left\lfloor \frac{M}{4} \right\rfloor$명의 의뢰인들의 요구를 만족하는, $N$개의 음으로 이루어진 음악을 작곡하고자 한다. 준휘는 음악의 멜로디는 결정하였으나 아직 각 음의 세기를 결정하지 못하였다. 준휘를 도와 각 음의 세기를 결정하여, 적어도 $\left\lfloor \frac{M}{4} \right\rfloor$명의 의뢰인을 만족시켜보자.

제약 조건

• $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)$

부분문제

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

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

3. (20점) 모든 $i(1\le i\le M)$에 대해, $w_i=N$

4. (40점) 추가 제약 조건 없음.

입력 형식

첫째 줄에 음이 아닌 두 정수 $N,M$이 공백으로 구분되어 주어진다.

이후 $M$개의 줄에 걸쳐, $i$번째 줄에는 다섯개의 정수 $x_i,y_i,z_i,w_i,k_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 의뢰인의 요구를 나타낸다.

출력 형식

하나의 줄에 걸쳐 $N$개의 정수 $A_1,A_2,\cdots, A_N$을 공백으로 구분하여 출력한다. 이는 음악의 $i$번째 음의 세기를 의미한다. 문제의 조건을 만족하는 출력이 적어도 하나 존재함이 보장된다.

예제

예제 1

입력

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

출력

0 0 0 0 0

설명

해당 출력은 $2$번째 요구의 조건만을 만족한다. 이 예제의 경우 $\lfloor \frac{2}{4} \rfloor=0$이므로, 원소가 $0,1,2,3$중 하나인 길이 $N$의 모든 수열이 올바른 답으로 간주됨에 유의하라.