hackercupai/hackercup huggingface dataset:
Tabitha is tired of tricky Hacker Cup problems, and is hosting a table flipping after-party for the finalists to let out some steam. Her party will be held with finalists distributed across \(T\) rooms.

A given room has \(N\) tables (numbered from \(1\) to \(N\)), with one finalist at each table. Each table \(i\) is represented as an axis-aligned rectangle of positive area on a 2D plane, with bottom-left vertex at \((X_i, Y_i)\), a width of \(W_i\), and a height of \(H_i\). No two tables overlap (intersect with positive area).

Finalists will take turns flipping their tables in one of the \(4\) cardinal directions by reflecting the rectangle across an edge. Table \(i\) must be flipped in direction \(D_i\) (`"U"` if the table is to be flipped over its upper edge, `"D"` for its lower edge, `"L"` for its left edge, or `"R"` for its right edge). Finalists must flip their tables one-by-one, i.e., no two tables may be flipped at the exact same time.

Every finalist knows which direction each table must be flipped, and do not wish to interfere with each other. Tabitha would like to know if there exists some permutation in which the tables can be flipped, such that at no time do any two tables overlap (intersect with positive area).

# Constraints

\(1 \le T \le 70\)
\(1 \le N \le 300{,}000\)
\(0 \le X_i, Y_i \le 500{,}000{,}000\)
\(1 \le W_i, H_i \le 500{,}000{,}000\)
\(D_i \in \{\)`"U"`, `"D"`, `"L"`, `"R"`\(\}\)

The sum of \(N\) across all test cases is at most \(3{,}000{,}000\).

# Input

Input begins with a single integer \(T\), the number of rooms. For each room, there is first a line containing a single integer \(N\). Then, \(N\) lines follow, the \(i\)th of which contains \(4\) space-separated integers, \(X_i\), \(Y_i\), \(W_i\), and \(H_i\), followed by a space-separated character \(D_i\).

# Output

For the \(i\)th room, print a line containing *"Case #i: "* followed by `"YES"` if there exists a permutation of tables as described above, or `"NO"` otherwise.

# Sample Explanation

In the first room, the two tables (along with their flipping directions) are arranged as follows:

{{PHOTO_ID:616805819746914|WIDTH:420}}

Flipping the left table first would result in it overlapping with the right table. On the other hand, if the right table is flipped first, then the left table can be validly flipped as well, leaving the tables looking as follows:

{{PHOTO_ID:382533823663612|WIDTH:420}}

In the second room, the left table is to be flipped to the right instead. No matter which order the tables are flipped in, they will overlap with one another at some point.

The third room is arranged as follows:

{{PHOTO_ID:462323098803710|WIDTH:420}}

No matter which order the tables are flipped in, they will touch but not overlap with one another.

The fourth room is arranged as follows, and has no valid table-flipping order:

{{PHOTO_ID:1268827100291056|WIDTH:320}}