Following Directions

Nông dân John quản lý một lưới $(N+1)\times (N+1)$. Mỗi ô $(i,j)$ với $1\le i,j\le N$ chứa một con bò và một biển chỉ hướng (sang phải R hoặc xuống dưới D). Các ô ở hàng dưới cùng và cột phải nhất (trừ góc) chứa máng thức ăn với chi phí cho trước.

Mỗi ngày, các con bò đi theo biển chỉ hướng cho đến khi gặp máng thức ăn. Trước mỗi ngày cho ăn, một biển chỉ hướng bị đổi chiều. Tính tổng chi phí cho ăn ban đầu và sau mỗi lần đổi.

Dữ liệu vào

• Dòng đầu: số nguyên $N$ ($1\le N\le 1500$)
• $N$ dòng tiếp: xâu $N$ ký tự (R hoặc D) và chi phí máng ở cột phải nhất
• Dòng tiếp: $N$ chi phí máng ở hàng dưới cùng
• Dòng tiếp: số nguyên $Q$ ($1\le Q\le 1500$)
• $Q$ dòng tiếp: tọa độ $(i,j)$ của biển cần đổi

Dữ liệu ra

• $Q+1$ dòng: tổng chi phí ban đầu, sau đó chi phí sau mỗi lần đổi.

Ràng buộc

• $1\le N\le 1500$, $1\le Q\le 1500$
• $1\le$ chi phí $\le 500$
• Giới hạn thời gian: 8 giây

Ví dụ