피아의 아틀리에 ~신비한 생명의 연금술사~ timer 2s memory 512MB

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

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

• 가마는 가로, 세로 모두 n칸인 격자 모양이다.

• 가마의 각 칸은 미생물 서식지이거나, 미생물 서식지가 아니다.

• (i, j), (i+1, j), (i, j+1), (i+1, j+1) 4개의 칸에 있는 미생물 서식지 수의 총합을 2로 나눈 나머지는 c_{ij}와 같아야 한다. (1 ≤ i, j ≤ n-1; 0 ≤ c_{ij} ≤ 1)

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

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

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

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