Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
ACM ICPC 2018 World Finals
Language:
Putin-chess
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 133 Accepted: 25 Special Judge

Description

Visitors of the site dni.ru are offered to play "Putin-chess" – a game that is a combination of chess and the well-known computer game "Lines". Here is a simplified version of the game.

There are several chess pieces (except pawns) on a standard chessboard. They are placed disregarding the usual chess rules, but each square may contain no more than one piece. A player can make a standard chess move with any piece (of any color) to any free square. The object is to align five or more pieces of the same color side by side in a vertical, horizontal or diagonal line. Several lines can be formed with one move. After the move, all pieces in all formed lines are removed from the board. Moves not resulting in line formation are not allowed. The game goes on until the player cannot move.

The task is to determine maximal number of pieces that can be removed from the board according to these rules.

Input

The first line contains the number of white and black pieces. The numbers are separated by one or more spaces. Each following line contains the description of one piece (upper-case Latin letters R, Q, K, B, C for king "rex", queen, knight, bishop, or castle) and the initial location of the piece in the standard chess notation (the lower left-hand square has notation a1, the upper right-hand – h8). At first the white pieces are described, then the black ones. It is guaranteed that the initial configuration contains no lines that could be removed.

Output

The first line contains two numbers: the number of pieces removed and the number of moves. The numbers should be separated by one or more spaces. Each following line describes one move. It contains the description of a piece (in the same format as in the input file), the character '‑' and the notation of the square to which the piece is moved.

If the task has several solutions it is sufficient to give only one of them.

Sample Input

```5 0
Rb1
Kc1
Ke3
Re1
Rf1```

Sample Output

```5 1
Ke3-d1```

Source

Northeastern Europe 2003, Western Subregion

[Submit]   [Go Back]   [Status]   [Discuss]