스도쿠

$N \times N$ 행과 $N \times N$ 열로 이루어진 빈 표가 주어진다. 토니는 표에 수를 $M$번 쓴다. 먼저 칸을 하나 고른 뒤 다음과 같이 한다.

• 칸이 비어 있으면 그 칸에 수를 쓴다.
• 칸에 이미 수가 있으면 기존 수를 지우고, 빈 칸에 수를 쓴다.

쓰는 수는 1 이상 $N \times N$ 이하의 자연수다.

표가 올바르려면 각 행, 각 열, 각 특수 정사각형에 모든 수가 정확히 한 번씩 들어 있어야 하고, 빈 칸이 없어야 한다. 즉 모든 칸에 수가 쓰여 있어야 한다.

특수 정사각형은 다음과 같이 정의한다. 첫 번째 특수 정사각형은 처음 $N$개 행과 처음 $N$개 열이 만나는 칸이다. 두 번째 특수 정사각형은 처음 $N$개 행과 두 번째 $N$개 열이 만나는 칸이다. 세 번째 이후도 같은 방식으로 이어진다.

그림은 $N=3$인 표를 보여준다. 굵은 선으로 된 9칸짜리 정사각형이 특수 정사각형이다.

수를 쓸 때마다 표가 올바른지 아닌지 출력하라.

첫 줄에 자연수 $N$과 $M$이 주어진다 ($2 \le N \le 60$, $1 \le M \le 1000000$).

다음 $M$개 줄에는 자연수 $A$, $B$, $C$가 주어진다 ($1 \le A, B, C \le N \times N$). 이는 토니가 $A$행 $B$열의 칸에 수 $C$를 썼다는 뜻이다.

$M$개 줄에 출력한다. $i$번째 쓰기를 마친 뒤 표가 올바르면 1을, 올바르지 않으면 0을 출력한다.

두 번째 예제에서 첫 번째, 두 번째, 세 번째 쓰기를 마친 뒤의 표 상태이다. 세 번째 쓰기가 첫 번째 쓰기를 지웠다는 점에 주목하라.