Gardened-Halved

건축가 제이크는 계절의 대비를 테마로 한 "반전의 정원"을 설계하고 있다. 제이크는 가로 $N$, 세로 $N$짜리 정사각형 모양 땅을 확보했다. 제이크가 확보한 땅의 왼쪽 아래 꼭짓점, 오른쪽 위 꼭짓점의 좌표는 각각 $(0, 0)$, $(N, N)$이다. 제이크는 땅을 $1 \times 1$ 크기의 격자 $N^2$개로 쪼개어서 각 격자에 식물을 심으려고 한다. 제이크가 격자 $(i, j)$에 식물을 심는다면 $(i, j)$가 왼쪽 아래 꼭짓점인 $1 \times 1$ 크기의 격자 영역에 식물이 가득 찬다.

우선 제이크는 자신이 원하는 대로 산책로를 만들었다. 산책로는 관람객들이 $(0, 0)$에서 시작해서 위쪽($(x, y) \rightarrow (x, y+1)$ 방향) 또는 오른쪽($(x, y) \rightarrow (x+1, y)$ 방향)으로 $1$만큼 총 $2 \times N$번 걸어서 $(N, N)$으로 갈 수 있도록 만들어졌다. 제이크는 산책로를 기준으로 왼쪽 위 방향에 있는 격자에는 개나리를, 오른쪽 아래 방향에 있는 격자에는 코스모스를 심었다. 결과적으로 산책로는 개나리가 있는 영역과 코스모스가 있는 영역 사이의 경계선이 된다.

아직 식물이 많이 자라지 않았기 때문에 제이크는 식물이 다 자랄 때까지 기다린 다음 늦여름에 정원을 개장하려고 한다. 여름이 되면 개나리와 코스모스가 무성히 자라서 산책로를 가려버린다. 여름에는 개나리와 코스모스를 구분하기 힘들기 때문에 단순 눈대중으로는 산책로를 복원하기 어렵다. 이에 따라 제이크는 처음에 산책로의 정보를 이용하여 정원에 나무를 심은 다음, 여름에 나무의 위치를 이용하여 산책로를 복원하려고 한다. 제이크는 개나리를 심는 격자에는 벚꽃을 심을 것이고 코스모스를 심는 격자에는 단풍나무를 심을 것이다.

제이크는 자신의 예술적 감각에 따라 나무를 정확히 $K$개만 심을 것이다. 제이크를 도와 산책로가 주어지면 산책로를 복원할 수 있도록 나무를 심을 위치를 계산하는 프로그램을 작성하여라.