VNOI Marathon 2009

Bắn bi

Trong những ngày hè rảnh rỗi, ktuan thường chơi bắn bi trên một bảng hình vuông gồm NxN ô vuông nhỏ. Trò chơi được thực hiện như sau:

• Ban đầu, ktuan đặt K vật cản vào K ô vuông của bảng.
• Sau đó, ktuan thực hiện lần lượt Q lượt chơi. Ở lượt chơi thứ i, ktuan lần lượt bắn D_i viên bi từ ngoài bảng vào một trong 4 đường biên của bảng. Kích thước của mỗi viên bi đúng bằng kích thước của một ô vuông nhỏ. Viên bi sẽ đi qua các ô thuộc cùng một hàng / cột cho đến khi đi ra ngoài bảng hoặc gặp một vật cản hay viên bi khác. Nếu có vật cản hay viên bi khác ở ngay ô đầu tiên thì viên bi đó không được đưa vào bảng.
• Ở mỗi lượt bắn, ktuan ghi lại tổng số ô mà các viên bi đã đi qua.

Bạn hãy viết chương trình mô phỏng lại trò chơi và với mỗi lượt bắn, in ra tổng số ô mà các viên bi của lượt bắn đó đã đi qua.

Dữ liệu

• Dòng đầu ghi 3 số N, K, Q.
• K dòng sau, mỗi dòng ghi một cặp số (u,v) thể hiện toạ độ (dòng, cột) của một vật cản.
• Q dòng sau, mỗi dòng ghi 4 giá trị c, D, u, v. Ký tự c có thể là 'L', 'R', 'T', hoặc 'B' cho biết viên bi được đưa vào từ biên trái, phải, trên hoặc dưới của bảng. (u,v) thể hiện toạ độ ô đầu tiên mà viên bi được đưa vào. Đây phải là một ô nằm trên biên của bảng ứng với ký tự c. D là số lượng viên bi sẽ bắn ở lượt chơi này.

Kết quả

• Với mỗi lượt chơi, in ra tổng số ô mà các viên bi của lượt đó đã đi qua

Ví dụ

Dữ liệu 
5 1 3
3 3
L 2 3 1
T 1 1 1
B 5 5 5

Kết quả
3
2
25

Giải thích

• Viên bi đầu tiên của lượt 1 sẽ đi qua 2 ô (3,1) và (3,2) trước ghi gặp vật cản ở ô (3,3)
• Viên bi tiếp theo của lượt 1 sẽ đi qua ô (3,1) trước khi gặp viên bi ở ô (3,2). Vậy tổng số ô bị đi qua ở lượt này là 3.
• Viên bi đầu tiên của lượt 2 sẽ đi qua 2 ô (1,1) và (2,1) trước khi gặp viên bi ở ô (3,1).
• Mỗi viên bi của lượt cuối cùng đều không gặp vật cản và sẽ đi ra ngoài bảng sau khi đi qua 5 ô.

Giới hạn

• N ≤ 50000, K ≤ 10, Q ≤ 100000
• Trong 1/3 số test, N và Q không vượt quá 1000.