a067. 編輯器選取框

題目描述

文字編輯器可以把一份固定的文件排成 R 列、每列 C 個字母。校稿員經常用滑鼠框選文件的一小塊區域，再問編輯器：這個選取範圍內，指定的字母總共出現了幾次？框選可能只涵蓋一格，也可能一次選到整份文件。

每筆查詢提供左上角 (r1, c1)、右下角 (r2, c2) 和目標字母 x。從第 r1 列到第 r2 列、第 c1 行到第 c2 行，包含四周邊界，都是這次要計算的位置。即使某個字母在選取框中重複出現，也要按每個格子各算一次。

校稿員只會查詢，不會修改文件；因此所有查詢都依據最初那張字母方格。因為查詢數量可能很多，請依輸入順序把每筆結果各輸出一行，不要只回覆最後一次的答案。

輸入格式

第一行 R C，接著 R 行字母方格；下一行為查詢數 Q；每筆查詢為 r1 c1 r2 c2 x，座標從 1 開始，x 是大寫英文字母。

限制

• 1 ≤ R, C ≤ 300；1 ≤ Q ≤ 20000
• 1 ≤ r1 ≤ r2 ≤ R、1 ≤ c1 ≤ c2 ≤ C；方格只含大寫英文字母

輸出格式

每筆查詢各輸出一行整數。

範例1

範例輸入：

2 3
ABC
ABA
3
1 1 2 3 A
2 2 2 3 B
1 2 1 2 C

範例輸出：

3
1
0

整個方格有三個 A；第二筆選到最後一列的 B、A，只有一個 B；第三筆只選第一列第二行的 B，因此沒有 C。

範例2

範例輸入：

1 1
Z
2
1 1 1 1 Z
1 1 1 1 A

範例輸出：

1
0

查詢同一個單格選取框，指定的字母不同，答案也不同。