题目描述

注意：此问题的时间限制为8s，是默认值的四倍。

农夫约翰有一块大正方形的田地，分成$(N+1)×(N+1) (1≤N≤1500)$ 网格。单元格$（i，j）$表示从顶部起第$i$行和从左侧起第$j$列中的单元格。每个单元格$（i，j）$中都有一头牛$(1≤i，j≤N)$，并且每个这样的单元格还包含指向右侧或下方的路标。此外，除了$（N+1，N+1）$之外，每个单元格$（i，j）$，使得$i＝N+1$或$j＝N+1$，包含一桶牛饲料。每个缸含有不同价格的奶牛饲料；$（i，j）$处的增值税成本为$ci,j（1 \leq ci,j \leq 500）$喂养每头牛。

每天晚饭时间，农夫约翰都会敲响晚餐钟，每头牛都会按照路标的指示走，直到到达一个大缸，然后再从大缸中进食。第二天，奶牛都会回到原来的位置。

为了维持他的预算，农夫约翰想知道每天喂养所有奶牛的总成本。然而，在每天晚饭前，奶牛在某个牢房里$（i，j）$

翻转其路标的方向（从右到下或反之亦然）。在接下来的几天里，路标也保持在这个方向上，除非稍后将其翻转回来。

给定每天翻转的路标坐标，输出每天的成本（总共Q天数，$1 \leq Q \leq 1500$）。

输入格式

第一行包含$N（1 \leq N \leq 1500）$。接下来的$N+1$行包含从上到下的网格行，包含路标的初始方向和成本$ci、j$ 每个缸的。这些行的第一个$N$包含一串方向$R$或$D$（分别表示向右或向下的路标），后跟成本$ci$​. 第$（N+1）$行包含成本$c N+1，j$

下一行包含$Q（1 \leq Q \leq 1500）$。

然后按照Q附加行，每行由两个整数$i和j（1 \leq i，j \leq N）$组成，这两个整数是其标志在相应日期翻转的单元格的坐标。

输出格式

$Q+1$行：总成本的原始值，后跟每次翻转后的总成本值。

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

602
701
602
701
1501

数据范围

输入2-4：$1 \leq N，Q \leq 50$

输入5-7：$1 \leq N，Q \leq 250$

输入2-10：每个单元格中的初始方向以及查询都是统一随机生成的。

输入11-15：无附加约束。