15946번 - 피아의 아틀리에 ~신비한 생명의 연금술사~

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

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

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

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

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

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

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

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

두 번째 줄부터 n-1개의 줄에 n-1개의 정수 c_i,j가 공백 없이 주어진다. (0 ≤ c_i,j ≤ 1)

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

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