Let's define a *duke* as a chess figure that is only allowed to move 1 cell up, down, left or right.
Let's consider a large chess board of size 1000000×1000000. Both rows and columns are numbered from "000000" to "999999".
A cell is labeled as "(<Column number>, <Row number>)" (quotes for clarity), where <Column number> and <Row number> each contain exactly six digits. For example, "(499999, 000000)" and "(500000, 000000)" are the two cells in the middle of the bottom row.
A duke is placed on a chessboard in the cell **initPosition**.
Let's describe a duke's path as a space-separated list of cells visited by the duke. For example, "(444444, 600000) (444445, 600000) (444445, 599999)" is a path consisting of two moves. The first move is one cell to the right and the second move is one cell down.
A path is called simple if it contains no repeated cells.
Consider the lexicographically greatest simple path of a duke starting in **initPosition**. Return the last cell of this path in the same format as **initPosition**. |