题目描述

约翰的农场可以看作一个 $(N+1)×(N+1)$的方格矩阵。

矩阵行从上到下编号 $1∼N+1$，列从左到右编号 $1∼N+1$。

第 $i$ 行第 $j$ 列的方格表示为 $(i,j)。$

满足 $1≤i,j≤N$ 的每个方格 $(i,j)$ 中都居住着一头奶牛，并且每个这样的方格中都有一个向右或向下的路标。

此外，除了 $(N+1,N=1)$ 之外的满足 $i=N+1$ 或 $j=N+1$ 的每个方格 $(i,j)$ 中都有一桶牛饲料，饲料成本为 $c_{i,j}$ 每头牛。

也就是说，每当有一头奶牛来到方格$(i,j)$ 处吃牛饲料，约翰就需要付出 $c_i$ 的成本。

每头奶牛每天只吃一顿饭，用餐时间在晚上。

每天晚餐时间，约翰都会敲响晚餐铃，奶牛们就会遵循路标指示不断前进，直到到达有牛饲料的方格，奶牛就会停下来进食。

所有奶牛在吃完饲料后，都会回到自己的住所休息。

为了维持预算，约翰想知道每天喂养所有奶牛的总成本。

然而，每天开始晚餐前，都会有一个单元格 $(i,j)$ 中的奶牛翻转其所在方格的路标方向（向右变向下，向下变向右）。

注意，每一天的路标翻转都会对后续天产生影响。

路标方向一旦改变，在接下来的日子里，除非在某一天它又被奶牛翻转回来，否则，它不会自己翻转回来。

一共有 $Q$ 天时间，给定每天翻转路标的单元格坐标，请你计算初始总成本以及每天的实际总成本。

输入格式

第一行包含整数 $N$。

接下来 $N+1$ 行，其中第 $i$ 行用来描述矩阵第 $i$ 行：

• 前 $N$ 行：首先包含一个长度为 $N$ 的由 R 和 D 组成字符串，其中的第 $j$ 个字符表示方格 $(i,j)$ 的路标方向（R 表示向右，D 表示向下），然后包含一个整数 $c_{i,N+1}$ 表示方格 $(i,N+1)$ 的饲料成本。
• 第 $N+1$ 行：包含 $N$ 个整数 $c_{N+1},c_{N+2}...c_{N+3}$，表示每个方格的饲料成本。

接下来一行包含整数 $Q$。

接下来 $Q$ 行，其中第 $i$ 行包含两个整数 $a_i,b_i$，表示第 $i$ 天晚饭前翻转路标的单元格坐标为$(a_i,b_i)$。

输出格式

共 $Q+1$ 行。

第一行输出初始总成本，即没有任何翻转的情况下每天的晚餐总成本。

接下来 $Q$ 行，其中第 $i$ 行输出第 $i$ 天的实际晚餐总成本。

2
RR 1
DD 10
100 500
4
1 1
1 1
1 1
2 1

602
701
602
701
1501

提示

$1≤N≤1500,$
$1≤c_i,j≤500,$
$1≤Q≤1500,$
$1≤a_i,b_i≤N。$

样例解释

初始时，方格 (1,1) 和 (1,2) 的奶牛饲养成本均为 1，方格 (2,1) 的奶牛饲养成本为 100，方格(2,2) 的奶牛饲养成本为 500，总成本为 602。

第一次翻转后，方格 (1,1) 处的路标方向从 R 变为 D，此时方格 (1,1) 处的奶牛饲养成本变为 100，其余保持不变，所以总成本变为 701。

第二次翻转后，矩阵变回初始状态，总成本为 602。

第三次翻转后，矩阵变为第一次翻转后状态，总成本为 701。

第四次翻转后，方格 (1,1) 和 (2,1) 的奶牛饲养成本均变为 500，总成本为 1501。