{"raw_statement":[{"iden":"statement","content":"Tomas never buys neither sugar nor salt (these are the only seasonings he use) from a shop — he makes his own. For that purpose he has Sugar-n-Salt-O-Matic. It's a special machine which produces sugar and salt, and does that simultaneously.\n\nThe Sugar-n-Salt-O-Matic is a pretty simple machine. There are some holes distributed on a plane, which are used to drop grains of seasoning. Below is a single cup which can move in any of the four directions (north, south, east or west) and be placed under any of the holes with coordinates (x, y) (0 ≤ x, y ≤ 100). At a specific time t from the hole a single grain of sugar or salt is dropped. If at that moment the cup is below the hole, the grain will fall into the cup.\n\nThere are some issues regarding this machine. At the beginning (at the time t = 0) the cup can be placed under any of the holes, but per single unit of time it can only move from current hole to the adjacent one (respecting the 4 directions movement), or stay in the same place. Also at the same time there might be multiple holes dropping grains of seasoning. This makes some of the sugar and/or salt fall onto the ground.\n\nObviously, the sugar is ruined even if a single grain of salt falls into the cup, and vice versa. Tomas wants only pure sugar and pure salt. Luckily, he can take the cup away at any moment of time.\n\nTomas must decide if he should collect sugar or salt. Given the number of holes and the timings of seasoning production find the maximum number of grains of sugar ant the maximum number of grains of salt Tomas can collect.\n\nThe first line contains the number of test cases _T_ (T ≤ 20). \n\nIn the first line of every test case there is an integer _m_ (1 ≤ m ≤ 103) – the number of grains of seasoning dropped. \n\nIn the following _m_ lines there are integer values of _t_, _x_, _y_ and _q_ (1 ≤ t ≤ 100, 0 ≤ x, y ≤ 100) – the time of the dropping, the coordinates of the hole and the type of the seasoning dropped (single lowercase character, \"_u_\" (without quotation mark) for s*U*gar and \"_a_\" for s*A*lt) — sorted in increasing order. \n\n*Note*: it is guaranteed that all triples of _t_, _x_ and _y_ are pairwise distinct. \n\nFor each test case output one line containing “_Case #tc: sugar salt_”, where _tc_ is the number of the test case (starting from 1), _sugar_ is the maximum number of sugar grains collected and _salt_ is the maximum number of salt grains collected.\n\n"},{"iden":"input","content":"The first line contains the number of test cases _T_ (T ≤ 20). In the first line of every test case there is an integer _m_ (1 ≤ m ≤ 103) – the number of grains of seasoning dropped. In the following _m_ lines there are integer values of _t_, _x_, _y_ and _q_ (1 ≤ t ≤ 100, 0 ≤ x, y ≤ 100) – the time of the dropping, the coordinates of the hole and the type of the seasoning dropped (single lowercase character, \"_u_\" (without quotation mark) for s*U*gar and \"_a_\" for s*A*lt) — sorted in increasing order. *Note*: it is guaranteed that all triples of _t_, _x_ and _y_ are pairwise distinct. "},{"iden":"output","content":"For each test case output one line containing “_Case #tc: sugar salt_”, where _tc_ is the number of the test case (starting from 1), _sugar_ is the maximum number of sugar grains collected and _salt_ is the maximum number of salt grains collected."},{"iden":"examples","content":"Input251 1 1 a2 1 2 u3 1 2 u3 1 3 a4 2 2 u51 0 0 a1 0 1 a1 1 0 a1 1 1 a2 0 0 uOutputCase #1: 3 1Case #2: 0 1"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ X, Y \\in \\mathbb{R}^+ $ denote the dimensions of the rectangular room with corners at $ (0,0) $ and $ (X,Y) $.  \n- Let $ N \\in \\mathbb{Z}_{\\geq 0} $ be the number of rectangular glass cases.  \n- For each $ i \\in \\{1, \\dots, N\\} $, let the $ i $-th glass case be defined by its axis-aligned bounding box with lower-left corner $ (X1_i, Y1_i) $ and upper-right corner $ (X2_i, Y2_i) $, where $ 0 \\leq X1_i < X2_i \\leq X $ and $ 0 \\leq Y1_i < Y2_i \\leq Y $.  \n- Let the four CCTV cameras be located at the four corners of the room: $ C_1 = (0,0) $, $ C_2 = (X,0) $, $ C_3 = (X,Y) $, $ C_4 = (0,Y) $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 20 $  \n2. For each test case:  \n   - $ 0 \\leq N \\leq 100 $  \n   - All coordinates are real numbers satisfying $ 0 \\leq X1_i < X2_i \\leq X \\leq 10^4 $, $ 0 \\leq Y1_i < Y2_i \\leq Y \\leq 10^4 $  \n   - Glass cases do not overlap (but may share edges).  \n\n**Objective**  \nFor each CCTV camera $ C_j $ ($ j \\in \\{1,2,3,4\\} $), compute the visible (track-able) region within the room $ [0,X] \\times [0,Y] $, defined as the set of points $ p \\in [0,X] \\times [0,Y] $ such that the line segment $ \\overline{C_j p} $ does not intersect the interior of any glass case.  \nCompute the total visible area as the union of the visible regions from all four cameras.  \nOutput the total track-able area.","simple_statement":"Calculate the total area visible to 4 CCTV cameras placed at the corners of a rectangular room, where rectangular glass cases block the view.","has_page_source":false}