Фермер Джон має велике квадратне поле з \((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\)).

Формат вхідних даних

Перший рядок містить \(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\)), які координатами комірок, у яких змінюється покажчик у цей день.

Формат вихідних даних

\(Q+1\) рядків: значення початкової сумарної ціни, за яким слідує значення сумарної ціни ціни після кожної зміни покажчика.

Приклад вхідних даних

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

Приклад вихідних даних

602
701
602
701
1501

Перед першою зміною покажчика ціни харчування корів у клітинах \((1, 1)\) і \((1, 2)\) по \(1\), ціна харчування корови в \((2, 1)\) дорівнює \(100\), а ціна харчування корови у \((2, 2)\) дорівнює \(500\). Сумарна ціна дорівнює \(602\). Після першої зміни покажчика у позиції

Після першої зміни напряму в \((1,1)\) з R на D, тепер харчування корови \((1, 1)\) коштує \(100\), решта залишиться без змін, тому загальна ціна стане \(701\). Другий та третій перевороти перемикають той самий знак назад і вперед. Після четвертого перевороту харчування корів \((1, 1)\) і \((2, 1)\) коштує по \(500\) і загальна ціна \(1501\).

ОЦІНЮВАННЯ:

• У тестах 2-4: \(1 \le N, Q \le 50\)
• У тестах 5-7: \(1 \le N, Q \le 250\)
• У тестах 2-10: Початковий напрямок у кожній комірці, а також запити згенеровані випадково рівномірно.
• У тестах 11-15: Немає додаткових обмежень.