피아의 아틀리에: 신비한 생명의 연금술사

피아는 "새로운 생명을 창조하는 연금술"을 연구하는 유명한 연금술사이다. 피아는 이 연금술로 수많은 생명을 창조하여 인류의 발전에 기여하고 있다. 하지만 빛의 속도로 달린다는 전설 속의 동물 "달토끼"만큼은 만들 수 없었다.

연금술은 미생물이 서식하고 있는 가마를 이용해 이루어진다. 이 미생물들이 특정한 규칙을 만족해야만 "신비한 생명의 힘"이 발현되어 새로운 생명을 창조할 수 있다. 만족하지 않는다면 가마의 뜨거운 온도 때문에 미생물의 기분이 나빠져 연금술을 할 수 없다. 그 규칙은 다음과 같다.

• 가마는 가로, 세로 모두 n칸인 격자 모양이다.
• 가마의 각 칸은 미생물 서식지이거나, 미생물 서식지가 아니다.
• $(i, j)$, $(i+1, j)$, $(i, j+1)$, $(i+1, j+1)$ 4개의 칸에 있는 미생물 서식지 수의 총합을 2로 나눈 나머지는 $c_{i,j}$와 같아야 한다. ($1 \le i, j \le n-1$; $0 \le c_{i,j} \le 1$)

특별한 생명을 창조하려면 특별한 조건을 만족해야 하며, 이를 "레시피"라고 한다. 레시피를 만족하지 않으면 좀비 같은 괴생명체가 만들어질 수 있기 때문에 매우 조심해야 한다. 피아가 만든 "달토끼 레시피"는 아래와 같은 $m$개의 조건을 만족해야 한다.

• 달토끼 레시피의 $i$번째 조건은 다음과 같다: "$s_i$일부터 $e_i$일까지 가마의 $(x_i, y_i)$칸은 항상 서식지이거나, 항상 서식지가 아니어야 한다." ($1 \le i \le m$)

피아는 자신이 만든 레시피대로 연금술을 시도했지만, 특정 시간에는 위의 조건을 모두 만족하는 서식지 배치가 존재하지 않아 실패하고 말았다. 피아는 레시피를 수정하기 전에 여러분에게 다음과 같은 내용을 의뢰했다: "연금술이 이루어지는 $T$일 각각에 대해, 달토끼 레시피를 포함한 모든 조건을 만족하는 미생물 서식지가 존재하는지 여부를 알려주세요."

피아의 달토끼 레시피가 성공적으로 완성될 수 있도록 피아를 도와주자.

첫 번째 줄에 가마의 크기 $n$과 조건의 수 $m$, 일 수 $T$가 주어진다. ($2 \le n \le 3\,000$, $1 \le m \le 10^5$, $1 \le T \le 10^5$)

두 번째 줄부터 $n-1$개의 줄에 $n-1$개의 정수 $c_{i,j}$가 공백 없이 주어진다. ($0 \le c_{i,j} \le 1$)

$n$번째 줄부터 $m$개의 줄에 걸쳐 조건의 정보가 5개의 수 $s_i$, $e_i$, $x_i$, $y_i$, $p_i$로 주어진다. ($1 \le s_i \le e_i \le T$; $1 \le x_i, y_i \le n$; $0 \le p_i \le 1$) 이는 $x_i$번째 행 $y_i$번째 열에 위치한 칸이, $s_i$일부터 $e_i$일까지, $p_i$가 0인 경우 미생물 서식지가 될 수 없는 경우를, $p_i$가 1인 경우 미생물 서식지가 되어야 하는 경우를 의미한다.

첫 번째 줄에 $T$개의 글자를 출력한다. $k$번째 글자로 $k$번째 날에 미생물이 열기를 이겨낼 수 있는 배치가 존재한다면 1, 아니면 0을 출력한다.