Number Box

Statement

You are given a positive integer [[n]] and a [[n*n]] grid where the square at the <<i>>-th row from the top and <<j>>-th column from the left has a digit <<d(i, j)>> written on it. Assume that the upper and lower edges of this grid are connected, as well as the left and right edges. Takahashi will first choose one of the following four directions: up, down, left, right. Then, he will start on a square of his choice and repeat moving one square in the chosen direction [[n−1]] times. In this process, Takahashi visits [[n]] squares. Find the <<greatest possible value of the integer>> that is formed by using the digits written on the squares in the same order as visited by him. `Example: 3 744 533 697` The solution is <<976>>, obtained as follows: start at (2, 1) -> (right) (2, 2) -> (right) (2, 0).

Input description

<<Line 1:>> An integer [[n]]. <<Next [[n]] lines:>> A string of [[n]] digits

Output description

An <<integer>> representing the highest value that Takahashi can achieve.

Constraints

1 ≤ [[n]] ≤ 10 0 ≤ <<d(i, j)>> ≤ 9

Game modes

Test cases

Example (N = 3) Test

Input

3 744 533 697

Output

976

N = 3 Validator

Input

3 662 635 807

Output

870

N = 2 Test

Input

2 70 08

Output

N = 2 Validator

Input

2 24 15

Output

N = 4 (Atcoder test) Test

Input

4 1161 1119 7111 1811

Output

9111

N = 4 Validator

Input

4 5161 6667 3004 9494

Output

9660

N = 10 (Atcoder test) Test

Input

10 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111

Output

1111111111

N = 10 Validator

Input

10 9999999999 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111

Output

9999999999

Final (N = 10) Test

Input

10 2391862821 9037983536 2139839392 5896672665 3008877263 5959600631 2242106277 1254567628 6191759746 7689475927

Output

9895450933

Final (N = 10) VAL Validator

Input

10 3510549429 0053665349 1943497433 4502406071 7702417082 0929536554 5162744541 8095718245 1780009182 0966570879

Output

9993124152

Edge case (GIVE ME AN INTEGER) Test

Input

5 00000 00000 00000 00000 00000

Output

Edge case Validator

Input

3 000 000 000

Output

Solution language

Solution

Stub generator input