Red-Blue Matrix solution codeforces

Red-Blue Matrix solution codeforces

You are given a matrix, consisting of nn rows and mm columns. The ii-th cell of the jj-th row contains an integer aijaij.

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 kk (1k<m1≤k<m) and cut the colored matrix in such a way that the first kk columns become a separate matrix (the left matrix) and the last mkm−k columns become a separate matrix (the right matrix).

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

Red-Blue Matrix solution codeforces

  • 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

The first line contains a single integer tt (1t10001≤t≤1000) — the number of testcases.

Then the descriptions of tt testcases follow.

Red-Blue Matrix solution codeforces

The first line of each testcase contains two integers nn and mm (2n,m51052≤n,m≤5⋅105nm106n⋅m≤106) — the number of rows and the number of columns in the matrix, respectively.

The ii-th of the next nn lines contains mm integers ai1,ai2,,aimai1,ai2,…,aim (1aij1061≤aij≤106).

The sum of nmn⋅m over all testcases doesn’t exceed 106106.

Output

Red-Blue Matrix solution codeforces

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 nn characters: the ii-th character should be ‘R‘ if the ii-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 kk (1k<m1≤k<m) — the number of columns from the left that are cut.

Example
input

Copy

Red-Blue Matrix solution codeforces

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
output

Copy

Red-Blue Matrix solution codeforces

YES
BRBRB 1
NO
YES
RB 3
Note

The coloring and the cut for the first testcase:

Leave a Comment