시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)2933100.000%

문제

MatKor는 2022년 1학기 활동과 여름에 열린 <제1회 MatKor Cup:2022 Summer>를 토대로 2학기 사이버국방학과 동아리로 인준되었다. 이제 MatKor는 동아리 부원을 공개적으로 모집하고 세미나와 프로젝트 등 다양한 활동을 시작하였다.

또 다른 사이버국방학과 동아리인 AlKor는 MatKor를 견제하려 한다. 이를 알아챈 MatKor의 회장인 창호는 스테가노그래피(Steganography)를 이용해 정보를 숨기려고 한다.

스테가노그래피는 사진이나 메시지 등 어떤 정보에 다른 데이터를 몰래 숨기는 기법을 의미한다. 스테가노그래피와 관련된 자세한 내용은 아래 노트를 통해 스테가노그래피가 무엇인지 한 번 읽어보도록 하자. 구체적으로 창호가 개발한 스테가노그래피 기법은 2차원 좌표평면의 격자점의 색깔을 이용해 정보를 숨기는 것으로, 처음에는 모든 격자점이 색깔 $0$으로 칠해져 있다. 창호는 다음 두 가지 은닉과 검사 행동을 할 수 있다.

  • 은닉: 주어진 점 하나를 주어진 색깔로 색칠한다.
  • 검사: 주어진 두 2차원 구간에 색칠된 패턴이 동일한지 판단한다. 두 2차원 구간 $\left[ x_1,x_1+w \right]\times\left[ y_1,y_1+h \right]$와 $\left[ x_2,x_2+w \right]\times\left[ y_2,y_2+h \right]$에 색칠된 패턴이 동일하다는 것은, 모든 정수 $0\le i\le w$, $0\le j\le h$에 대해 $(x_1+i,y_1+j)$의 색깔과 $(x_2+i,y_2+j)$의 색깔이 동일하다는 것을 의미한다.

검사 행동이 주어졌을 때 창호를 도와 주어진 두 2차원 구간에 색칠된 패턴이 동일한지 판단해 보자.

입력

첫 번째 줄에 창호가 시행하는 행동의 수 $Q(1\le Q\le 10^5)$가 주어진다.

두 번째 줄부터 $Q$개의 줄에 걸쳐 창호가 시행하는 행동이 다음과 같은 형식으로 주어진다.

  • 은닉 행동의 경우 1 $x$ $y$ $c$의 형식으로 주어진다. 이는 점 $(x,y)$를 색깔 $c$로 색칠함을 의미한다.
  • 검사 행동의 경우 2 $x_{1}$ $y_{1}$ $x_{2}$ $y_{2}$ $w$ $h$의 형식으로 주어진다. 이는 두 2차원 구간 $\left[ x_1,x_1+w \right]\times\left[ y_1,y_1+h \right]$와 $\left[ x_2,x_2+w \right]\times\left[ y_2,y_2+h \right]$에 색칠된 패턴이 동일한지 판단해야 함을 의미한다.
  • 모든 입력은 $-10^{9}$ 이상, $10^{9}$ 이하의 정수이며, $w$와 $h$의 경우 음이 아닌 정수이다.

검사 행동이 한 번 이상 주어진다.

출력

첫 번째 줄부터 $2$번 쿼리가 주어졌을 때, 두 2차원 구간에 색칠된 패턴이 동일하면 1, 아니면 0을 한 줄에 한 개씩 출력한다.

서브태스크

번호배점제한
131

은닉 행동의 모든 $c$는 서로 다르게 주어진다.

233

은닉 행동에서 $y=0$

336

추가적인 제한 조건 없음

예제 입력 1

3
1 1 1 1
1 3 1 1
2 1 1 3 1 1 1

예제 출력 1

1

검사 행동은 다음과 같다.

예제 입력 2

9
1 2 3 4
1 3 4 5
1 4 5 4
1 12 13 4
1 13 14 5
1 14 15 4
2 2 3 3 4 1 1
2 2 3 12 13 2 2
2 100 100 100 100 100 100

예제 출력 2

0
1
1

첫 번째와 두 번째 검사 행동은 다음과 같다.

노트

스테가노그래피는 숨겨야 할 데이터를 또 다른 데이터에 넣어 은폐하는 기술이다. 주로 사진, 동영상, 음악 등에 아주 미세한 변화를 주어 데이터를 넣게 되며, 무심코 지나치면 인지할 수 없지만 실제로는 이미지의 픽셀이나 오디오의 진동수 등을 미세하게 조정하여 기존과 다른 부분이 존재하기 때문에, 은폐가 정교하지 않다면 은폐했다는 사실을 눈치챌 수 있다. 암호는 데이터 자체를 읽지 못하게 만드는 반면, 스테가노그래피는 단순히 숨기는 기법으로, 스테가노그래피의 일종으로 여러 줄로 이루어진 문장의 첫 글자를 읽으면 숨겨진 뜻이 나타나는 세로드립 역시 스테가노그래피라 할 수 있다.

실제로 MatKor에서 진행한 <제6회 고려대학교 MatKor Cup : 2025 Winter>의 본 대회 유의사항 탭의 사진이나, <제1회 MatDegy Cup>의 문제에서 스테가노그래피를 통해 정보를 은닉해 참여자들이 숨겨진 문제를 찾게 한 적이 있다. 간단한 스테가노그래피는 누구나 쉽게 숨기고 해독할 수 있도록 공개되어 있는 도구들이 많으며, 단순히 구글에 스테가노그래피 복호화나 암호화와 관련된 검색만 하면 무료로 도구를 사용할 수 있다.

채점 및 기타 정보

  • 예제는 채점하지 않는다.