Nông dân John có một trang trại lưới ô vuông kích thước \((N + 1) \times (N + 1)\) (\(1 \le N \le 1500\)). Ô \((i, j)\) đại diện cho ô ở hàng \(i\) từ trên xuống và cột \(j\) từ trái sang. Có một con bò sống ở mỗi ô \((i, j)\) với \(1 \le i, j \le N\), mỗi ô như vậy cũng chứa một biển hiệu hướng sang phải hoặc xuống dưới. Mỗi ô \((i, j)\) thỏa mãn \(i = N + 1\) hoặc \(j = N + 1\), ngoại trừ \((N + 1, N + 1)\), chứa một bể thức ăn cho bò. Mỗi bể chứa thức ăn có giá khác nhau, bể ở ô \((i, j)\) có giá \(c_{i, j}\) (\(1 \le c_{i, j} \le 500\)) để cho một con bò ăn.

Mỗi ngày vào giờ ăn tối, nông dân John rung chuông ăn tối, và mỗi con bò sẽ đi theo biển hiệu cho đến khi chúng đi đến một bể thức ăn, và ăn thức ăn ở bể đó. Sau đó, các con bò quay trở về chỗ ban đầu vào ngày tiếp theo.

Để quản lý chi phí, nông dân John muốn biết tổng chi phí để cho tất cả bò ăn mỗi ngày. Tuy nhiên, vào mỗi ngày, trước trời tối, con bò ở một ô \((i, j)\) nào đó lật ngược hướng của biển hiệu của nó (sang phải thành xuống dưới và ngược lại). Biển hiệu sẽ hướng về hướng này cho những ngày tiếp theo, trừ khi nó được lật lại một lần nữa.

Bạn được cho tọa độ của biển hiệu bị lật trong mỗi ngày, in ra chi phí cho mỗi ngày (tổng có \(Q\) ngày, \(1 \le Q \le 1500\)).

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 1500\)).
• \(N + 1\) dòng tiếp theo chứa các hàng của lưới từ trên xuống dưới, chứa hướng ban đầu của các biển hiệu và chi phí \(c_{i, j}\) của mỗi bể. \(N\) dòng đầu tiên chứa một xâu \(N\) chứa hướng R hoặc D (biểu diễn chỉ hướng sang phải hoặc xuống dưới), theo sau đó là chi phí \(c_{i, N + 1}\). Dòng thứ \(N + 1\) chứa \(N\) chi phí \(c_{N + 1, j}\).
• Dòng tiếp theo chứa \(Q\) (\(1 \le Q \le 1500\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i\) và \(j\) (\(1 \le i, j \le N\)), tọa độ của ô mà biển hiệu bị lật trong ngày tương ứng.

Output

• \(Q + 1\) dòng, chi phí ban đầu và theo sau là chi phi sau mỗi lần lật biển.

Scoring

• Subtask 1: \(1 \le N, Q, \le 50\)
• Subtask 2: \(1 \le N, Q \le 250\)
• Subtask 3: Các hướng ban đầu của các biển hiệu được sinh ngẫu nhiên.
• Subtask 4: Không có ràng buộc gì thêm

Example

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

602
701
602
701
1501