Rail Station Recovery

Time limit3sMemory limit512 MB

Summary

Recover every station's block number and C or D type from the all-pairs shortest-route distances and station 0's block.

Level: Hard9 of 10
Topics: Graph, Sorting, Math
Solved: No attempts yet

Problem

A railway line runs from the western end of the island to the eastern end and consists of $m$ blocks. The blocks are numbered $0$ , $1$ , ..., $m-1$ from the west. Each block has a one way westbound track on its north side, a one way eastbound track on its south side, and possibly one station between the two tracks.

A block has one of three types. A type C block holds a station that you enter from the northern track and leave onto the southern track. A type D block holds a station that you enter from the southern track and leave onto the northern track. An empty block has no station. The tracks of two neighboring blocks are joined by a connector. In the figure below the connectors are the gray rectangles.

The line in the figure has 7 blocks. Blocks $1$ , $2$ and $3$ are type C, block $5$ is type D, and the other blocks are empty. It has 4 stations: station $0$ sits in block $2$ , station $1$ in block $5$ , station $2$ in block $3$ , and station $3$ in block $1$ .

The line has $n$ stations, numbered $0$ to $n-1$ . From every station you can reach every other station along the tracks. Several routes join one station to another, so the distance between two stations is the smallest number of connectors a route passes. In the figure the shortest route from station 0 to station 2 runs through blocks 2, 3, 4, 5, 4, 3 and passes 5 connectors, so the distance between those two stations is $5$ .

After a power outage the computer that manages the line lost the block number and the block type of every station. The only clue left is the block number of station $0$ , and that block is always type C. The computer can still measure the distance between every pair of stations. Recover the block number and the block type of every station from the distance table and the block number of station $0$ .

Input

The first line has the number of stations $n$ and the block number $f$ of station $0$ , separated by a space. Each of the next $n$ lines holds one row of the distance table. The $j$ -th number on the $i$ -th of those lines is the distance between station $i-1$ and station $j-1$ .

$2 \le n \le 100$
$0 \le f < 10^9$
Every station has a block number that is at least $0$ and less than $10^9$ , and a block holds at most one station.
The distance table is symmetric and every diagonal entry is $0$ .
The input comes from a line that meets all of the conditions above, and only one arrangement of stations produces it.

Output

Print $n$ lines. The $i$ -th line holds the block number of station $i-1$ and the type of that block, separated by a single space. Write C for a type C block and D for a type D block.

Examples4

Example 1

Input

Expected output

2 C
5 D
3 C
1 C

Example 2
Input
```
2 0
0 1
1 0
```
Expected output
```
0 C
1 D
```

Example 3

Input

Expected output

3 C
9 D
0 C
4 D
7 C

Example 4
Input
```
3 5
0 7 1
7 0 6
1 6 0
```
Expected output
```
5 C
0 C
6 D
```