MARBLE - A Marble Game

ktuan usually plays a marble game in a square table of NxN cells. The game proceeds as the following:

  • Initially, ktuan puts K obstacles into K cells of the table.
  • After that, ktuan makes Q turns. At the ith turn, ktuan flicks Di marbles from the outside of the board into one of the 4 sides of the board. The size of each marble fits perfectly into one cell.  The marble goes through the cells in the same row/column until it goes out of the board or it meets an obstacle or another marble. If there is an obstacle or another marble at the first position then the marble will not be placed on the board.
  • After each turn, ktuan records the total number of cells that the marbles in that turn passing through.

Write a program that simulates the game and for each turn, print the total number of cells that the marbles in that turn passing through.

Input

  • The first line contains three integers N, K, Q.
  • Each line in the next K lines contains a pair (u, v) representing the coordinates (row, column) of an obstacle.
  • Each line in the next Q lines contains 4 values c, D, u, v. The character c could be 'L', 'R', 'T', or 'B' depending on whether the marbles go from the left, right, top, or bottom of the board. (u, v) represents the initial coordinates of the marbles and it should be a boundary cell (corresponding to c). D is the number of marbles in the current turn.

Output

  • For each turn, print the total number of cells that the marbles passing through.

Example

Input 
5 1 3
3 3
L 2 3 1
T 1 1 1
B 5 5 5

Output
3
2
25

Output details

  • The first marble of the first turn will go through the two cells (3, 1) and (3, 2) before facing an obstacle at (3, 3).
  • The next marble of the first turn will go through the cell (3, 1) before facing another marble at (3, 2). Thus, the total number of cells passed through is 3.
  • The first marble of the second turn will pass through the two cells (1, 1) and (2, 1) before facing a marble at the cell (3, 1).
  • Each marble of the last turn will go out of the board as it doesn't tough obstacle or another marble. Thus, each marble will pass through 5 cells.

Constraints

  • N ≤ 50000, K ≤ 10, Q ≤ 100000
  • In 1/3 of the test cases, N and Q do not exceed 1000.


Được gửi lên bởi:Jimmy
Ngày:2009-07-17
Thời gian chạy:0.600s-2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:VNOI Marathon 2009
Round 2
Problem Setter: Khúc Anh Tuấn

hide comments
2020-03-23 17:32:19
không hiểu sao nộp toàn 0 điểm
2018-01-17 10:31:15
không hiểu sao để N*4 ko đc. cho lên N*8 lại được
2017-11-20 14:57:33


Last edit: 2017-11-20 14:58:04
2017-09-29 06:24:13
sao toàn ok không thế

2016-09-06 10:50:14
Liên hệ lấy code nè https://facebook.com/profile.php=75816879

Last edit: 2016-12-08 13:37:06
2016-09-06 10:49:46
Đừng dùng IT./.
2015-11-11 16:27:08 Prismatic
ai thắc mắc Di nhiu thì cứ để int64 :)) ban đầu bấn loạn tưởng Bigint
2015-06-25 18:57:29 The Flash
KHÔNG DÙNG CÂY IT , 60 ĐIỂM
2013-11-04 18:25:53 up!
Toan 0.ok :((
2012-10-15 03:27:06 Scammers
uc che, nop bai toan 0k
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.