**Замечание: Время на тест в этой задаче 8s, в четыре раза больше чем по умолчанию.**
У Фермера Джона есть большое квадратное поле из \((N+1)\times (N+1)\)
(\(1\le N\le 1500\)) ячеек. Пусть ячейка \((i, j)\) обозначает ячейку в \(i\)-ой строке
сверху, и в \(j\)-ом столбце слева. В каждой ячейке \((i, j)\) живёт по одной корове
(\(1 \le i, j \le N\)), и каждая ячейка содержит указатель или вправо или вниз.
Также каждая ячейка \((i, j)\) такая, что \(i=N+1\) или \(j=N+1\), кроме \((N+1, N+1)\),
содержит бак с коровьей едой. Каждый чан содержит еду различной цены. Чан в
ячейке \((i, j)\) стоит \(c_{i, j}\) (\(1 \le c_{i,j} \le 500\)).
Каждый день во время обеда ФД звонит в колокол и каждая корова движется по
направлениям указателей пока не достигнет чана с едой и затем есть из этого чана.
Затем все коровы возвращаются в исходные позиции к следующему дню.
Чтобы поддержать свой бюджет, ФД хочет узнать общую стоимость еды съедаемой
коровами каждый день. Однако, каждый день перед обедом корова в некоторой ячейке
\((i, j)\) меняет направление указателя "вправо" на "вниз" или наоборот.
Этот знак остаётся в таком направлении и в последующие дни, пока не будет перевёрнут
обратно позже.
Вам даны координаты указателя, который меняется каждый день. Выведите стоимость
каждого дня (всего \(Q\) дней, \(1 \le Q \le 1500\)).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) (
\(1 \le N \le 1500\)).
Следующие \(N+1\) строк описывают построчно решётку сверху вниз - изначальное
положение указателей стоимость \(c_{i, j}\) каждого чана.
Первые \(N\) строк содержат по \(N\) символов R или D (указывающих направление
вправо или вниз соответственно), затем следует цена \(c_{i, N+1}\).
\((N+1)\)-я строка содержит \(N\) цен \(c_{N+1, j}\).
Следующая строка содержит \(Q\) (\(1 \le Q \le 1500\)).
Затем следуют \(Q\) дополнительных строк, каждая содержит по два целых числа.
\(i\) и \(j\) (\(1 \le i, j \le N\)), которые представляют собой координаты ячеек,
в которых меняется указатель в соответствующий день.
ФОРМАТ ВЫВОДА (на экран / stdout):
\(Q+1\) строк: значение изначальной суммарной цены, за которым следует значение суммарной
цены после каждого изменения указателя.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
RR 1
DD 10
100 500
4
1 1
1 1
1 1
2 1
|
602
701
602
701
1501
|