{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eRikka\u0027s birthday is on June 12th. The story of this problem happens on that day.\u003cbr\u003e\u003cbr\u003eToday is Rikka\u0027s 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.\u003cbr\u003e\u003cbr\u003eFor 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 $i$th cut is a ray starting from $(x_i,y_i)$ while the direction is $D_i$. There are four possible directions: L, passes $(x_i-1,y_i)$; R, passes $(x_i+1,y_i)$; U, passes $(x_i,y_i+1)$; D, passes $(x_i,y_i-1)$.\u003cbr\u003e\u003cbr\u003eTake advantage of the infinite power of Tyrant\u0027s 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.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains a single integer $T(1 \\leq T \\leq 100)$, the number of the test cases.\u003cbr\u003e\u003cbr\u003eFor each test case, the first line contains three positive integers $n,m,K(1 \\leq n,m \\leq 10^9, 1 \\leq K \\leq 10^5)$, which represents the shape of the cake and the number of instructions on the grimoire. \u003cbr\u003e\u003cbr\u003eThen $K$ lines follow, the $i$th line contains two integers $x_i,y_i(1 \\leq x_i \u0026lt; n, 1 \\leq y_i \u0026lt;m)$ and a char $D_i \\in \\{$\u0027L\u0027,\u0027R\u0027,\u0027U\u0027,\u0027D\u0027$\\}$, which describes the $i$th cut.\u003cbr\u003e\u003cbr\u003eThe input guarantees that there are no more than $5$ test cases with $K \u0026gt; 1000$, and no two cuts share the same $x$ coordinate or $y$ coordinate, i.e., $\\forall 1 \\leq i \u0026lt; j \\leq K$, $x_i \\neq x_j$ and $y_i \\neq y_j$."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output a single line with a single integer, the number of pieces of the cake.\u003cbr\u003e\u003cbr\u003e\u003cdiv style\u003d\"font-family:Times New Roman;font-size:14px;background-color:F4FBFF;border:#B7CBFF 1px dashed;padding:6px\"\u003e\u003cdiv style\u003d\"font-family:Arial;font-weight:bold;color:#7CA9ED;border-bottom:#B7CBFF 1px dashed\"\u003e\u003ci\u003eHint\u003c/i\u003e\u003c/div\u003e\u003cbr\u003eThe left image and the right image show the results of the first and the second test case in the sample input respectively. Clearly, the answer to the first test case is $3$ while the second one is $5$.\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/d0472a2cdfb4bc02b2dedace2f3e44a5?v\u003d1713713664\"\u003e\u003c/center\u003e\u003cbr\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n4 4 3\r\n1 1 U\r\n2 2 L\r\n3 3 L\r\n5 5 4\r\n1 2 R\r\n3 1 U\r\n4 3 L\r\n2 4 D\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}