You are given a row x column integer grid. Find the length of the longest strictly increasing path in the grid.

From any cell, you may move only to its immediate left, right, up, or down neighbor. Diagonal movement is not allowed, and you cannot go outside the grid.

In addition to the maximum length, also return one longest strictly increasing path, and return all strictly increasing paths.

The grid is provided as List<String> gridLines, where each string represents one row and the numbers in that row are separated by commas.

A path is written in the following format:
(rowIndex,colIndex)=value -> (rowIndex,colIndex)=value -> ...

A path is strictly increasing if every next value in the path is greater than the value before it.

Method Signatures

int getLongestPathLength(List<String> gridLines)

• Returns the number of cells in the longest strictly increasing path.

String getOneLongestPath(List<String> gridLines)

• Returns one longest strictly increasing path.
• If multiple longest paths exist, return the lexicographically smallest path string.

List<String> getAllStrictlyIncreasingPaths(List<String> gridLines)

• Returns all strictly increasing paths.
• Each returned path must contain at least one cell.
• Return the paths in lexicographically increasing order of the full path strings.

Input Format

• gridLines.size() == row
• Each string in gridLines represents one grid row, such as "8,8,3"
• All row strings must have the same number of comma-separated integers
• If each row has column integers, then the grid size is row x column

Rules

• From cell (x, y), the only valid neighboring cells are (x - 1, y), (x + 1, y), (x, y - 1), and (x, y + 1), if they are inside the grid.
• You may move to a neighboring cell only if its value is strictly greater than the current cell value.
• Diagonal moves are not allowed.
• Wrap-around moves are not allowed.
• A path consisting of exactly one cell is also a valid strictly increasing path.

Constraints

• 1 ≤ row ≤ 200
• 1 ≤ column ≤ 200
• 0 ≤ grid[i][j] ≤ 2^20
• Each row string contains only non-negative integers separated by commas
• No row string is empty
• For test cases that call getAllStrictlyIncreasingPaths, the total number of valid strictly increasing paths will be small enough to fit in memory and output limits

Examples

Example 1

Example 2

Example 3

Example 4