Problem 3052 --Rikka with Cake

3052: Rikka with Cake

正确率: $66.67\%$ 下一题

Time Limit	$3$ 秒/Second(s)	Memory Limit	$512$ 兆字节/Megabyte(s)
提交总数	$3$	正确数量	$2$
裁判形式	标准裁判/Standard Judge	我的状态	尚未尝试
难度		分类标签

Description

Rikka's birthday is on June 12th. The story of this problem happens on that day.

Today is Rikka's birthday. Yuta prepares a big cake for her: the shape of this cake is a rectangular of

n centimeters times

m centimeters. With the guidance of a grimoire, Rikka is going to cut the cake.

For simplicity, Rikka firstly builds a Cartesian coordinate system on the cake: the coordinate of the left bottom corner is

(0,0) while that of the right top corner is

(n,m). There are

K instructions on the grimoire: The

ith cut is a ray starting from

(xi,yi) while the direction is

Di. There are four possible directions: L, passes

(xi−1,yi); R, passes

(xi+1,yi); U, passes

(xi,yi+1); D, passes

(xi,yi−1).

Take advantage of the infinite power of Tyrant's Eye, Rikka finishes all the instructions quickly. Now she wants to count the number of pieces of the cake. However, since a huge number of cuts have been done, the number of pieces can be very large. Therefore, Rikka wants you to finish this task

Input

The first line of the input contains a single integer

T(1≤T≤100), the number of the test cases.
For each test case, the first line contains three positive integers

n,m,K(1≤n,m≤109,1≤K≤105), which represents the shape of the cake and the number of instructions on the grimoire.
Then

K lines follow, the

ith line contains two integers

xi,yi(1≤xi<n,1≤yi<m) and a char

Di∈{'L','R','U','D'

}, which describes the

ith cut.
The input guarantees that there are no more than

5 test cases with

K>1000, and no two cuts share the same

x coordinate or

y coordinate, i.e.,

∀1≤i<j≤K,

xi≠xj and

yi≠yj.

Output

For each test case, output a single line with a single integer, the number of pieces of the cake.

Sample Input复制

Sample Output复制

3
5

本题记录	用户（点击查看用户）	运行号（点击购买题解）	时间
算法最快[$295 $ms]	intLSY	500378	2019-10-20 15:37:00
内存最少[$0 $KB]	淡意的温柔	588055	2020-05-27 09:43:01
第一AC	intLSY	500378	2019-10-20 15:37:00
第一挑战	intLSY	500366	2019-10-20 15:31:28

赛题来源/所属竞赛 2019 Multi-University Training Contest 9 N/A

竞赛编号	竞赛名称	竞赛时间	访问比赛