401576: GYM100495 H Sugar and Salt

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.

The 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.

There 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.

Obviously, 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.

Tomas 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.

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 ≤ 10³) – 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 sUgar and "a" for sAlt) — sorted in increasing order.

Note: it is guaranteed that all triples of t, x and y are pairwise distinct.

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.

2
5
1 1 1 a
2 1 2 u
3 1 2 u
3 1 3 a
4 2 2 u
5
1 0 0 a
1 0 1 a
1 1 0 a
1 1 1 a
2 0 0 u

Case #1: 3 1
Case #2: 0 1