시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (언어별 추가 시간 없음) 512 MB 30 8 7 25.000%

문제

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

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

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

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

3 5 9
01
10
1 5 1 1 1
2 6 1 3 0
3 7 2 2 1
4 8 3 1 0
5 9 3 3 0

예제 출력 1

111101111