대통령 K는 N×N 격자에 패턴을 디자인하려고 합니다. 각 셀은 정수로 표현되는 색상으로 칠해집니다. i번째 행(1 ≤ i ≤ N)과 j번째 열(1 ≤ j ≤ N)의 셀을 (i, j)로 표기합니다.

현재, 첫 번째 행과 첫 번째 열의 셀들은 이미 칠해져 있습니다. 구체적으로, 모든 1 ≤ i ≤ N에 대해 셀 (i, 1)은 색상 Aᵢ로, 모든 1 ≤ j ≤ N에 대해 셀 (1, j)은 색상 Bⱼ로 칠해져 있으며, A₁ = B₁입니다.

나머지 미칠해진 셀들은 다음 절차에 따라 차례대로 칠합니다.

• i = 2, 3, …, N에 대해, i번째 행의 셀들을 다음과 같이 칠합니다:

◦ j = 2, 3, …, N에 대해, 셀 (i, j)는 아래 두 값 중 더 큰 값으로 칠합니다.

셀 (i − 1, j)의 색상
* 셀 (i, j − 1)의 색상
(만약 두 색상이 동일하면 그 색상으로 칠합니다.)
최종적으로 모든 N²개의 셀이 칠해진 후, 대통령 K는 가장 많이 칠해진 색상이 무엇이며, 그 색상이 몇 개의 셀에 칠해졌는지 알고자 합니다. 만약 여러 색상이 같은 최대 빈도를 보이면, 그 중 색상 번호가 가장 큰 것을 출력합니다.

[제한]

Grid Coloring timer 1s memory 1024MB

Grid Coloring 1s 1024MB