I. Geometry Dash
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bessie is playing a Geometry Dash level that takes place on an infinite 2D grid. The level contains $$$n$$$ objects, with no two at the same position. Bessie starts and ends the level at the first object, which is always a green orb.

Bessie always faces one of the four cardinal directions: up, down, left or right. At the end of every second, she moves exactly one unit in her current direction.

There are three types of objects. When Bessie enters a cell containing an object, her direction may change based on the object type:

  • Green orb: Bessie can change her direction to any of the four cardinal directions.
  • Blue pad: Bessie's direction is immediately reversed (e.g., if she was moving right, she now moves left).
  • Purple pad: Bessie's direction is set to the direction of the purple pad.

If Bessie enters a cell without an object, she continues moving in her current direction. Bessie can visit a cell any number of times.

Help Bessie determine the maximum number of distinct cells she can visit such that she starts and ends at the first object, or output $$$0$$$ if she can never return to the first object.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. For each test case:

The first line contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), the number of objects.

Each of the next $$$n$$$ lines describes an object:

  • 1 $$$x$$$ $$$y$$$: A green orb at $$$(x, y)$$$.
  • 2 $$$x$$$ $$$y$$$: A blue pad at $$$(x, y)$$$.
  • 3 $$$x$$$ $$$y$$$ $$$d$$$: A purple pad at $$$(x, y)$$$ with direction $$$d \in \{U, L, D, R\}$$$.

The characters U, L, D, and R represent the directions up, left, down, and right respectively.

For each test case, it is guaranteed that all $$$(x, y)$$$ are distinct and $$$|x|, |y| \le 10^9$$$. The first object is always a green orb.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

—–

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-4$$$ have an answer that is at most $$$25$$$.

Tests $$$5-20$$$ satisfy no additional constraints.

Output

Output a single integer — the maximum number of distinct cells Bessie can visit and return to the starting cell, or $$$0$$$ is she cannot return.

Example
Input
2
9
1 0 0
1 -1 -1
1 -1 1
1 1 -1
2 -1 0
3 0 -1 R
3 1 0 L
3 0 1 L
3 1 1 D
1
1 1 1
Output
5
0
Note

—

Problem Idea: AksLolCoding

Problem Preparation: AksLolCoding

Occurrences: Novice I, Advanced E