문제 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