Red-Blue Matrix
Contest: Educational Codeforces Round 116 (Rated for Div. 2)
Difficulty rating: 2400
Tags: brute force, constructive algorithms, implementation, sortings

You are given a matrix, consisting of $$$n$$$ rows and $$$m$$$ columns. The $$$j$$$-th cell of the $$$i$$$-th row contains an integer $$$a_{ij}$$$.

First, you have to color each row of the matrix either red or blue in such a way that at least one row is colored red and at least one row is colored blue.

Then, you have to choose an integer $$$k$$$ ($$$1 \le k < m$$$) and cut the colored matrix in such a way that the first $$$k$$$ columns become a separate matrix (the left matrix) and the last $$$m-k$$$ columns become a separate matrix (the right matrix).

The coloring and the cut are called perfect if two properties hold:

- every red cell in the left matrix contains an integer greater than every blue cell in the left matrix;
- every blue cell in the right matrix contains an integer greater than every red cell in the right matrix.

Find any perfect coloring and cut, or report that there are none.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

Then the descriptions of $$$t$$$ testcases follow.

The first line of each testcase contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 5 \cdot 10^5$$$; $$$n \cdot m \le 10^6$$$) — the number of rows and the number of columns in the matrix, respectively.

The $$$i$$$-th of the next $$$n$$$ lines contains $$$m$$$ integers $$$a_{i1}, a_{i2}, \dots, a_{im}$$$ ($$$1 \le a_{ij} \le 10^6$$$).

The sum of $$$n \cdot m$$$ over all testcases doesn't exceed $$$10^6$$$.

Output format:
For each testcase print an answer. If there are no perfect colorings and cuts in the matrix, then print "NO".

Otherwise, first, print "YES". Then a string, consisting of $$$n$$$ characters: the $$$i$$$-th character should be 'R' if the $$$i$$$-th row is colored red and 'B' if it's colored blue. The string should contain at least one 'R' and at least one 'B'. Finally, print an integer $$$k$$$ ($$$1 \le k < m$$$) — the number of columns from the left that are cut.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
The coloring and the cut for the first testcase:

Example input:
3
5 5
1 5 8 8 7
5 2 1 4 3
1 6 9 7 5
9 3 3 3 2
1 7 9 9 8
3 3
8 9 8
1 5 3
7 5 7
2 6
3 3 3 2 2 2
1 1 1 4 4 4

Example output:
YES
BRBRB 1
NO
YES
RB 3

Editorial:
Imagine you fixed some cut and then colored one row red. Which rows can now be colored red or blue so that the condition on the left matrix is satisfied? If the row has at least one number greater or equal than the numbers in the red row, then the row must be red. Otherwise, it can be either red or blue.
However, imagine a weaker condition. Let's look only at the first cell in each row. Sort the rows by the first cell in them. Similarly, if a row is colored red, all the rows that are further in the sorted order should also be red, because they already have a greater or equal number in them.
It implies that after you sort the rows, the only possible colorings are: color some prefix of the rows in blue and the remaining suffix in red.
So there are $$$n$$$ possible colorings and $$$m$$$ possible cuts. If we learn to check if they are perfect in $$$O(1)$$$, we can get the solution in $$$O(nm)$$$.
Turns out, the condition "all numbers in the submatrix should be greater than all numbers in the other submatrix" is the same as "the minimum in the first submatrix should be greater than the maximum in the second submatrix".
Thus, you can first precalculate prefix and suffix minimums and maximums and check a coloring and a cut in $$$O(1)$$$.
Overall complexity: $$$O(n \log n + nm)$$$ per testcase.