철도역 위치 복원

철도 노선은 섬의 서쪽 끝에서 동쪽 끝까지 구간 $m$개로 이어져 있다. 구간에는 서쪽부터 차례로 $0$번, $1$번, ..., $m-1$번이 붙어 있다. 각 구간의 북쪽에는 서쪽으로만 달리는 단선 선로가, 남쪽에는 동쪽으로만 달리는 단선 선로가 있고, 두 선로 사이에 역이 하나 있을 수도 있다.

구간의 종류는 세 가지다. C형 구간에는 북쪽 선로에서 들어가 남쪽 선로로 나오는 역이 있다. D형 구간에는 남쪽 선로에서 들어가 북쪽 선로로 나오는 역이 있다. 빈 구간에는 역이 없다. 이웃한 두 구간의 선로는 연결기로 이어지며, 아래 그림에서 연결기는 회색 사각형이다.

그림의 노선은 구간 7개로 이루어진다. $1$번, $2$번, $3$번 구간은 C형이고 $5$번 구간은 D형이며, 나머지 구간은 비어 있다. 역은 4개이고 $0$번 역은 $2$번 구간에, $1$번 역은 $5$번 구간에, $2$번 역은 $3$번 구간에, $3$번 역은 $1$번 구간에 있다.

노선에는 역이 $n$개 있고 $0$번부터 $n-1$번까지 번호가 붙어 있다. 어느 역에서 출발하든 선로를 따라 다른 모든 역에 갈 수 있다. 한 역에서 다른 역으로 가는 경로는 여러 가지이므로, 두 역 사이의 거리는 경로가 지나는 연결기 개수의 최솟값으로 정한다. 그림에서 $0$번 역에서 $2$번 역으로 가는 최단 경로는 구간 2, 3, 4, 5, 4, 3을 차례로 지나고 연결기 5개를 지나므로, 두 역 사이의 거리는 $5$이다.

정전이 한 번 있고 나서 노선을 관리하는 컴퓨터는 각 역이 몇 번 구간에 있는지와 그 구간의 종류를 모두 잃어버렸다. 남은 단서는 $0$번 역이 있는 구간의 번호뿐이고, 이 구간은 항상 C형이다. 대신 컴퓨터는 모든 역 쌍 사이의 거리를 다시 잴 수 있다. 거리 표와 $0$번 역의 구간 번호로 모든 역의 구간 번호와 구간 종류를 복원하라.

첫째 줄에 역의 개수 $n$과 $0$번 역이 있는 구간의 번호 $f$가 공백 하나로 구분되어 주어진다. 이어지는 $n$개 줄에 거리 표가 주어진다. 그중 $i$번째 줄의 $j$번째 수는 $i-1$번 역과 $j-1$번 역 사이의 거리다.

• $2 \le n \le 100$
• $0 \le f < 10^9$
• 모든 역의 구간 번호는 $0$ 이상 $10^9$ 미만이고, 한 구간에 역은 최대 하나 있다.
• 거리 표는 대칭이고 대각선 값은 모두 $0$이다.
• 입력은 위 조건을 모두 만족하는 노선에서 만들어진다. 그런 노선의 역 배치는 하나뿐이다.

$n$개 줄을 출력한다. $i$번째 줄에는 $i-1$번 역이 있는 구간의 번호와 그 구간의 종류를 공백 하나로 구분해 출력한다. 종류는 C형이면 C, D형이면 D로 쓴다.