You are given an N x N chess board.

There are already N - 1 rooks placed on the board.

These rooks do not attack each other. More formally:

• no row contains more than one rook
• no column contains more than one rook

You need to place the Nth rook and return the position (i, j) where it should be placed.

You do not know where the existing rooks are located.

Instead, you are given a list of rectangle query results.

Each rectangle query result tells how many already placed rooks are inside a given inclusive rectangle.

The board uses 1-indexed coordinates.

RookPlacement(int n, List<String> rectangleQueries)

• Initializes the object with the board size and the given rectangle query results
• Each string in rectangleQueries is in the format "a,b,c,d,count"
• a and b are row boundaries, where a ≤ b
• c and d are column boundaries, where c ≤ d
• count is the number of already placed rooks inside rows a through b and columns c through d

String placeNthRook()

• Returns the answer as "i,j"
• i is the row index where the Nth rook should be placed
• j is the column index where the Nth rook should be placed

The constructor input is:

• n: the size of the board
• rectangleQueries: a list of rectangle query results

Each query result is given as a comma-separated string:

"a,b,c,d,count"

There are two useful types of rectangle queries:

• A row-range query has c = 1 and d = n. It counts rooks in rows a through b across all columns.
• A column-range query has a = 1 and b = n. It counts rooks in columns c through d across all rows.

The given rectangle queries are guaranteed to contain enough information to uniquely determine the missing row and the missing column.

Return a string in the format "i,j", where:

• i is the row of the missing rook position
• j is the column of the missing rook position

If multiple valid positions are possible, return the position with the smallest row index.
If there is still a tie, return the position with the smallest column index.

• 1 ≤ n ≤ 10^5
• 1 ≤ rectangleQueries.size() ≤ 2 * 10^5
• Each query string is in the format "a,b,c,d,count"
• 1 ≤ a ≤ b ≤ n
• 1 ≤ c ≤ d ≤ n
• 0 ≤ count ≤ n - 1
• Every query is either a row-range query or a column-range query
• Exactly n - 1 rooks are already placed on the board
• No two existing rooks share the same row
• No two existing rooks share the same column
• The given rectangle queries are consistent with one valid board configuration
• The given rectangle queries are sufficient to uniquely identify the missing row and missing column
• The given rectangle queries are consistent with at least one valid board configuration
• If multiple missing rows or missing columns are possible, return the lexicographically smallest valid position "i,j"
• The board is 1-indexed

Because there are n - 1 non-attacking rooks on an n x n board:

• exactly one row does not contain a rook
• exactly one column does not contain a rook
• the answer is the intersection of that row and that column

For a row-range query covering rows a through b:

• if the missing row is inside this range, then the count is b - a
• if the missing row is outside this range, then the count is b - a + 1

For a column-range query covering columns c through d:

• if the missing column is inside this range, then the count is d - c
• if the missing column is outside this range, then the count is d - c + 1

Input:
RookPlacement(n = 3, rectangleQueries = List.of("1,1,1,3,0", "1,3,1,1,0"))
placeNthRook()

Output:
"1,1"

Explanation:
Query "1,1,1,3,0" means rows 1 through 1 across all columns contain 0 rooks.
Therefore, row 1 is the missing row.

Query "1,3,1,1,0" means columns 1 through 1 across all rows contain 0 rooks.
Therefore, column 1 is the missing column.

The new rook should be placed at (1,1).

Input:
RookPlacement(n = 4, rectangleQueries = List.of("1,2,1,4,2", "3,4,1,4,1", "3,3,1,4,1", "1,4,1,2,2", "1,4,3,4,1", "1,4,3,3,1"))
placeNthRook()

Output:
"4,4"

Explanation:
Query "1,2,1,4,2" means rows 1 to 2 contain 2 rooks, so both rows are occupied.
Query "3,4,1,4,1" means rows 3 to 4 contain only 1 rook, so one of these rows is missing.
Query "3,3,1,4,1" means row 3 contains 1 rook.
Therefore, row 4 is missing.

Query "1,4,1,2,2" means columns 1 to 2 contain 2 rooks, so both columns are occupied.
Query "1,4,3,4,1" means columns 3 to 4 contain only 1 rook, so one of these columns is missing.
Query "1,4,3,3,1" means column 3 contains 1 rook.
Therefore, column 4 is missing.

The new rook should be placed at (4,4).

Input:
RookPlacement(n = 5, rectangleQueries = List.of("1,3,1,5,2", "1,2,1,5,2", "1,5,1,3,3", "1,5,4,5,1", "1,5,4,4,0"))
placeNthRook()

Output:
"3,4"

Explanation:
Query "1,3,1,5,2" means rows 1 to 3 contain only 2 rooks, so one of these rows is missing.
Query "1,2,1,5,2" means rows 1 to 2 contain 2 rooks, so rows 1 and 2 are occupied.
Therefore, row 3 is missing.

Query "1,5,1,3,3" means columns 1 to 3 contain 3 rooks, so columns 1, 2, and 3 are occupied.
Query "1,5,4,5,1" means columns 4 to 5 contain only 1 rook, so one of these columns is missing.
Query "1,5,4,4,0" means column 4 contains 0 rooks.
Therefore, column 4 is missing.

The new rook should be placed at (3,4).

Input:
RookPlacement(n = 1, rectangleQueries = List.of("1,1,1,1,0"))
placeNthRook()

Output:
"1,1"

Explanation:
There are 0 rooks already placed on a 1 x 1 board.
Therefore, the only possible position for the new rook is (1,1).