SOJ ONLINE JUDGE

문제 170

직사각형 문자열 비교

내 상태
미제출
난이도
170번 문제 난이도 보기
Gold I
출제자
rlatjwls7882
시간 제한
2000 ms
메모리 제한
1024 MB
170번 문제 태그 보기
문자열해싱

알파벳 소문자로 이루어진 $N$행 $M$열의 격자가 주어진다. 행과 열의 번호는 각각 $1$부터 $N$, $1$부터 $M$까지이다.

두 직사각형 영역이 같은지 묻는 $Q$개의 질의에 답해 보자. 두 영역의 행 수와 열 수가 각각 같고, 대응하는 모든 칸의 문자가 같으면 같은 영역이다.

각 영역은 왼쪽 위 칸과 오른쪽 아래 칸의 행·열 번호로 주어지며, 두 칸을 모두 포함한다. 영역을 회전하거나 뒤집어서 비교하지 않는다.

입력

첫 번째 줄에 세 정수 $N$, $M$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N, M \le 2\,000; N \cdot M \le 10^6; 1 \le Q \le 200\,000)$

두 번째 줄부터 $N$개의 줄에 걸쳐 알파벳 소문자로 이루어진 길이가 $M$인 문자열이 주어진다. $i$번째 문자열은 격자의 $i$번째 행이다.

그다음 줄부터 $Q$개의 줄에 걸쳐 두 영역의 왼쪽 위 칸과 오른쪽 아래 칸의 행·열 번호를 나타내는 여덟 정수 $x_1$, $y_1$, $x_2$, $y_2$, $u_1$, $v_1$, $u_2$, $v_2$가 공백으로 구분되어 주어진다. $(1 \le x_1 \le x_2 \le N; 1 \le y_1 \le y_2 \le M; 1 \le u_1 \le u_2 \le N; 1 \le v_1 \le v_2 \le M)$

첫 번째 영역의 왼쪽 위 칸은 $(x_1, y_1)$, 오른쪽 아래 칸은 $(x_2, y_2)$이며, 두 번째 영역의 왼쪽 위 칸은 $(u_1, v_1)$, 오른쪽 아래 칸은 $(u_2, v_2)$이다.

출력

각 질의에 대해 두 영역이 같다면 Yes를, 그렇지 않다면 No를 질의가 주어진 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

3 4 4
abab
abab
baba
1 1 1 2 1 3 1 4
1 1 2 2 2 1 3 2
1 1 1 2 1 1 2 1
1 1 3 4 1 1 3 4

예제 출력 1

Yes
No
No
Yes

예제 입력 2

1 1 1
z
1 1 1 1 1 1 1 1

예제 출력 2

Yes

제출

편집기에서 나가려면 Esc를 누른 뒤 Tab 또는 Shift와 Tab을 누르세요.