27879번 - 누적 합과 쿼리 서브태스크

크기가 \(n\) x \(n\)인 문자형 \(2\)차원 배열 \(A\)가 주어진다. 배열 \(A\)의 원소는 \(A[1][1],\ A[1][2],\ …,\ A[n][n]\)이다. 배열 \(A\)의 원소의 값은 알파벳 'a' 또는 'b'이다. 배열 \(A\)의 모든 원소의 초깃값은 입력으로 주어진다. 배열 \(A\)에 대한 \(q\)개의 질의가 저장된 질의 목록 \(Q\)가 주어진다. 질의 목록 \(Q\)에 저장된 \(q\)개의 질의는 아래와 같은 유형이다.

• \(i_1\ j_1\ i_2\ j_2\ s\) : \(i_1,\ j_1,\ i_2,\ j_2\)는 양의 정수이고 \(s\)는 알파벳 'a' 또는 'b'로 구성된 길이가 \(2\)인 문자열이다. \(i_1\ \le\ i_3\ \le\ i_4\ \le\ i_2,\ j_1\ \le\ j_3\ \le\ j_4\ \le\ j_2\)이고 배열 \(A\)의 원소 \(A[i_3][j_3]\)와 \(A[i_4][j_4]\)를 순서대로 이어 붙인 문자열이 문자열 \(s\)와 일치하는 \(((i_3,\ j_3),\ (i_4,\ j_4))\) 순서쌍의 개수를 출력한다. 단, \(A[i_3][j_3]\)와 \(A[i_4][j_4]\)는 가로 또는 세로 방향으로 인접해있다. 가로로 인접한 경우는 \(i_3=i_4,\ j_3+1=j_4\)이고 세로로 인접한 경우는 \(i_3+1=i_4,\ j_3=j_4\)이다.

질의 목록 \(Q\)에 저장된 첫 번째 질의부터 \(q\)번째 질의까지 순서대로 처리하면서 질의 결과를 출력하자.

첫 번째 줄에 배열 \(A\)의 크기 \(n\)이 주어진다.

두 번째 줄부터 \(n\)개의 줄에 배열 \(A\)의 원소가 주어진다. \(i\)번째 줄의 \(j\)번째 문자는 배열 \(A\)의 \((i-1)\)번째 행 \((j-1)\)번째 열의 원소 \(A[i-1][j-1]\)을 나타낸다.

다음 줄에 질의의 수 \(q\)가 주어진다.

다음 \(q\)개의 줄에 질의 정보가 순서대로 주어진다. 한 줄에 하나의 질의 정보가 주어진다. 하나의 질의 정보는 \(i_1,\ j_1,\ i_2,\ j_2,\ s\)가 공백을 사이에 두고 순서대로 주어진다.

첫 번째 줄부터 \(q\)개의 줄에 질의 결과를 순서대로 출력한다. 한 줄에 하나의 질의 결과를 출력한다.

• \(1\ \le\ n\ \le\ 1,000\)
• \(A[i][j]\)는 알파벳 'a' 또는 'b'이다. \((1\ \le\ i,\ j\ \le\ n)\)
• \(1\ \le\ q\ \le\ 100,000\)
• \(1\ \le\ i_1\ \le\ i_2\ \le\ n\)
• \(1\ \le\ j_1\ \le\ j_2\ \le\ n\)
• \(s\)는 알파벳 'a' 또는 'b'로 구성된 길이가 \(2\)인 문자열이다.