마비노기 색상표

NYPC 2019 · 예선

사람이 색을 볼 때는 눈에 존재하는 원추세포의 도움을 받는다. 원추세포에는 빨간색, 파란색, 초록색의 세 가지 빛에 반응하는 종류의 세포들이 있다. 각 종류의 세포들이 얼마나 신호를 발생시키느냐에 따라 사람은 색을 구별할 수 있다. 그래서, 컴퓨터에서 색을 표현할 때는, 빨간색, 파란색, 초록색의 섞인 비율을 사용하는 경우가 많다.

어떤 사람들은 원추세포 중 일부가 색을 잘 구분하지 못할 수 있다. 가장 흔한 경우는 빨간색 빛을 받아들이는 세포가 제대로 동작하지 않는 것이다. 이 경우 빨간색과 파란색이 섞여져 만들어진 보라색의 경우와 빨간색이 없이 파란색만 있는 경우를 잘 구분하지 못한다.

최근에 마비노기팀은 더욱 다양한 사람들에게 다가가고자 이런 경우에 속하는 사람들을 도와주기 위한 모드를 추가하려고 한다.

그리고 이 목적으로 사용될 수 있는 새로운 색상표를 만들려고 한다. 이 색상표에는 NN개의 색이 있고, 각 색은 파란색 빛의 세기를 나타내는 bb, 초록색 빛의 세기를 나타내는 gg로 표현된다. 각 빛의 세기는 00 이상 KK 미만이다. 두 색 (b1,g1)(b_1,g_1), (b2,g2)(b_2,g_2)의 거리는 (b1b2)2+(g1g2)2\sqrt{(b_1-b_2)^2+(g_1-g_2)^2} 이다. 즉, 거리가 가까울수록 구분이 잘 안 되고, 거리가 멀수록 구분이 잘 된다.

새로운 색상표는 모든 두 색의 거리 차이가 CC 이상이 되도록 만들어 색상의 구분이 잘 되게 하려고 한다. 새로운 색상표를 만들어주자!

입력 형식

첫째 줄에는 세 정수 NN, KK, CC가 공백으로 구분되어 주어진다. 이는 문제에 설명된 NN, KK, CC와 같으며, 데이터 별로 다음과 같이 주어진다.

데이터NNKKCC
112255 55
2255111177
3399111155
4488161677
551313212177
661616292999
773332323232
881313151555
993232252555
10102020292988

출력 형식

NN개의 줄을 출력한다. ii번째 줄에는 ii번째 색의 파란색 빛의 세기와 초록색 빛의 세기를 공백으로 구분하여 출력한다.

만약 가능한 답이 여러 가지인 경우 그중 아무거나 하나 출력한다.

예제

입력

3 3 1

출력

0 0 1 2 2 1

채점 방식

이 문제는 풀이 소스코드를 제출하지 않고, 각 테스트케이스의 입력데이터를 다운받아 알맞은 출력 파일을 만들어 출력 파일만을 제출하는 문제다.

문제 해결을 도와주는 시뮬레이터가 아래 미션에 대해 제공된다. 제공되는 시뮬레이터는 최신 버전의 크롬 브라우저에서 여는 것을 권장한다.

미션 1
미션 2
미션 3
미션 4
미션 5
미션 6
미션 7
미션 8
미션 9
미션 10

해설