{"raw_statement":[{"iden":"statement","content":"Dasha decided to have a rest after solving the problem _D_ and began to look photos from previous competitions.\n\nLet's call photos as the matrix with the size _n_ × _m_, which consists of lowercase English letters.\n\nSome _k_ photos especially interested her, because they can be received from photo-template by painting a rectangular area in a certain color. Let's call such photos special.\n\n<center>![image](https://espresso.codeforces.com/681f3b406fd1119f7690fc4fba9353f8e2edb6f5.png)</center>More formally the _i_\\-th special photo is received from the photo-template by replacing all characters on some rectangle with upper left corner of the cell with coordinates (_a__i_, _b__i_) and lower right corner in the cell with coordinates (_c__i_, _d__i_) to the symbol _e__i_.\n\nDasha asks you to find the special photo so that the total distance from it to all other special photos is minimum. And calculate this distance.\n\nDetermine the distance between two photos as the sum of distances between all corresponding letters. The distance between two letters is the difference module of their positions in the alphabet. For example, the distance between letters '_h_' and '_m_' equals |8 - 13| = 5, because the letter '_h_' is the 8-th in the alphabet, the letter '_m_' is the 13-th."},{"iden":"input","content":"The first line contains three integers _n_, _m_, _k_ (1 ≤ _n_, _m_ ≤ 103, 1 ≤ _k_ ≤ 3·105) — the number of strings in the photo-template, the number of columns and the number of special photos which are interesting for Dasha.\n\nThe next _n_ lines contains the string with _m_ length which consists of little Latin characters — the description of the photo-template.\n\nEach of the next _k_ lines contains the description of the special photo in the following format, \"_a__i_ _b__i_ _c__i_ _d__i_ _e__i_\" (1 ≤ _a__i_ ≤ _c__i_ ≤ _n_, 1 ≤ _b__i_ ≤ _d__i_ ≤ _m_), where (_a__i_, _b__i_) — is the coordinate of the upper left corner of the rectangle, (_c__i_, _d__i_) — is the description of the lower right corner, and _e__i_ — is the little Latin letter which replaces the photo-template in the described rectangle."},{"iden":"output","content":"In the only line print the minimum total distance from the found special photo to all other special photos."},{"iden":"examples","content":"Input\n\n3 3 2\naaa\naaa\naaa\n1 1 2 2 b\n2 2 3 3 c\n\nOutput\n\n10\n\nInput\n\n5 5 3\nabcde\neabcd\ndeabc\ncdeab\nbcdea\n1 1 3 4 f\n1 2 3 3 e\n1 3 3 4 i\n\nOutput\n\n59"},{"iden":"note","content":"In the first example the photos are following:\n\nbba    aaa\nbba    acc\naaa    acc\n\nThe distance between them is 10."}],"translated_statement":[{"iden":"statement","content":"Dasha 在解决完问题 #cf_span[D] 后决定休息一下，开始查看以前比赛的照片。\n\n我们将照片视为一个大小为 #cf_span[n × m] 的矩阵，由小写英文字母组成。\n\n某些 #cf_span[k] 张照片特别引起了她的兴趣，因为它们可以通过将矩形区域涂成某种颜色从照片模板中得到。我们称这样的照片为特殊照片。\n\n更正式地，第 #cf_span[i] 张特殊照片是通过将矩形区域内所有字符替换为符号 #cf_span[ei] 得到的，该矩形的左上角坐标为 #cf_span[(ai, bi)]，右下角坐标为 #cf_span[(ci, di)]。\n\nDasha 请你找出一张特殊照片，使得它到所有其他特殊照片的总距离最小，并计算这个距离。\n\n定义两张照片之间的距离为所有对应字母距离之和。两个字母之间的距离是它们在字母表中位置的差的绝对值。例如，字母 '_h_' 和 '_m_' 之间的距离为 #cf_span[|8 - 13| = 5]，因为 '_h_' 是字母表中的第 8 个字母，'_m_' 是第 13 个字母。\n\n第一行包含三个整数 #cf_span[n], #cf_span[m], #cf_span[k] #cf_span[(1 ≤ n, m ≤ 103, 1 ≤ k ≤ 3·105)] —— 分别表示照片模板的行数、列数和 Dasha 感兴趣的特殊照片数量。\n\n接下来的 #cf_span[n] 行每行包含一个长度为 #cf_span[m] 的字符串，由小写拉丁字符组成——表示照片模板的描述。\n\n接下来的 #cf_span[k] 行每行以格式 \"#cf_span[ai] #cf_span[bi] #cf_span[ci] #cf_span[di] #cf_span[ei]\" 描述一张特殊照片 #cf_span[(1 ≤ ai ≤ ci ≤ n, 1 ≤ bi ≤ di ≤ m)]，其中 #cf_span[(ai, bi)] 是矩形的左上角坐标，#cf_span[(ci, di)] 是右下角坐标，#cf_span[ei] 是用于替换模板中对应区域的小写拉丁字母。\n\n请在唯一一行中输出所找到的特殊照片到所有其他特殊照片的最小总距离。\n\n在第一个示例中，照片如下：\n\n它们之间的距离为 #cf_span[10]。\n"},{"iden":"input","content":"第一行包含三个整数 #cf_span[n], #cf_span[m], #cf_span[k] #cf_span[(1 ≤ n, m ≤ 103, 1 ≤ k ≤ 3·105)] —— 分别表示照片模板的行数、列数和 Dasha 感兴趣的特殊照片数量。接下来的 #cf_span[n] 行每行包含一个长度为 #cf_span[m] 的字符串，由小写拉丁字符组成——表示照片模板的描述。每行接下来的 #cf_span[k] 行以格式 \"#cf_span[ai] #cf_span[bi] #cf_span[ci] #cf_span[di] #cf_span[ei]\" 描述一张特殊照片 #cf_span[(1 ≤ ai ≤ ci ≤ n, 1 ≤ bi ≤ di ≤ m)]，其中 #cf_span[(ai, bi)] 是矩形的左上角坐标，#cf_span[(ci, di)] 是右下角坐标，#cf_span[ei] 是用于替换模板中对应区域的小写拉丁字母。"},{"iden":"output","content":"请在唯一一行中输出所找到的特殊照片到所有其他特殊照片的最小总距离。"},{"iden":"examples","content":"输入\n3 3 2\naaaaaaaaa\n1 1 2 2 b\n2 2 3 3 c\n输出\n10\n\n输入\n5 5 3\nabcde\neabcd\ndabcc\ndeabb\ncdea\n1 1 3 4 f\n1 2 3 3 e\n1 3 3 4 i\n输出\n59"},{"iden":"note","content":"在第一个示例中，照片如下：\nbba    aaa\nbba    acc\naaa    acc\n它们之间的距离为 #cf_span[10]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, m \\leq 10^3 $, $ 1 \\leq k \\leq 3 \\cdot 10^5 $.  \nLet $ T \\in \\Sigma^{n \\times m} $ be the photo-template, where $ \\Sigma = \\{a, b, \\dots, z\\} $ is the set of lowercase English letters.  \nFor each $ i \\in \\{1, \\dots, k\\} $, let $ P_i \\in \\Sigma^{n \\times m} $ be the $ i $-th special photo, obtained by replacing all entries in the rectangle $ [a_i, c_i] \\times [b_i, d_i] $ with letter $ e_i $, starting from template $ T $.\n\nLet $ f: \\Sigma \\to \\{1, 2, \\dots, 26\\} $ map each letter to its 1-based alphabetical position: $ f(c) = \\text{ord}(c) - \\text{ord}(a) + 1 $.\n\n**Distance Function**  \nFor two photos $ P, Q \\in \\Sigma^{n \\times m} $, define:  \n$$\nD(P, Q) = \\sum_{x=1}^{n} \\sum_{y=1}^{m} \\left| f(P[x][y]) - f(Q[x][y]) \\right|\n$$\n\n**Objective**  \nFind $ i^* \\in \\{1, \\dots, k\\} $ minimizing:  \n$$\n\\sum_{j=1}^{k} D(P_i, P_j)\n$$  \nand output the minimal total distance:  \n$$\n\\min_{i \\in \\{1, \\dots, k\\}} \\sum_{j=1}^{k} D(P_i, P_j)\n$$","simple_statement":null,"has_page_source":false}