Game of Generals

While we already have some chess-related games, we don't yet have any task involving the game in full. Implementation of such a game is expected to be somewhat complex but allowing to enjoy various small tricks and improvements - and should be adequate to skills of everyone who already have tried other (smaller) positional games at this website.

We are going to split the work in two steps to better cope with the aforementioned complexity - the first problem (this one) will help to verify implementation of rules (i.e. building possible move list for arbitrary position), while the second will challenge your skill in implementing best move search algorithm (e.g. playing and winning the game itself).

Here comes the first part (the next being Shogi Engine).

As a weak attempt against using modern "intelligent" code-generation tools, we are not going to play standard chess. Let here be a few changes:

• we'll play "Japanese Chess" or Shogi - which literally translates to "General's Game"
• idea of shuffling the initial setup (thanks to R.Fischer) is employed - both sides have the same but randomized arrangement of pieces
• moreover, we'll pick pieces from the slightly non-standard set (but those which existed at some larger historical Shogi variants)

The second point will relieve programmer from the necessity of building an "opening book" by the way.

The first will introduce us to curious world of this exceptionally extravagant derivative of historical chess game. Let's look at it closer.

Shogi principles

Both western chess and Shogi evolved from some common predecessor, perhaps "Shatranj", but it was quite a long way.

Doubtless the most unusual feature of Shogi is this: Pieces are not distinguished by color, only by direction from which follows that captured piece could be later dropped back into the game to play on captor's side. For example, if Blacks capture the opponent's rook with bishop and then the bishop is taken by opponent's pawn, then Blacks now have rook in the "pocket" while Whites have the bishop in the pocket. These pieces could be reintroduced into the game, to any empty square - this counts for a move and is called "drop".

Look at the picture above - here is a standard Shogi board (9 by 9, without typical "checkered" pattern of squares) - and the "wedge-shaped" flat pieces, distinguished by neat Japanese calligraphy.

Pieces are flat for the reason - in most Shogi variants not only pawns, but almost all other pieces do promote when reaching the far side of the board. Promotion is achieved by flipping the piece - on the other side it bears another mark, typically in red.

Another notable difference is that Shogi pieces on average are weaker than western ones. Many of them have a range of 1 cell, i.e. they are weaker than King.

The further description of our specific variant should be enough to solve the task, but you are encouraged to read more about Shogi in the wiki article (and perhaps try playing it a bit - online or with friends and relatives).

Our Shogi Variant

The game of shogi is infamous for having quite a number of variants, so we are not inventing something extraordinary here. We'll just use small board and some pieces from variants "Tai-shogi" and "Taikyoku-shogi" (these are quite large). The motivation for small board is that due to "drop" moves game search tree could be very large for computer algorithm.

So we use 6 by 6 board and the following setup:

• the second row for each opponent has six pawns
• the first row has other pieces - King is always among them, but others are picked randomly from the set of G, S, C, Y, R, X, V, H - and randomly placed at the row

Opponent's "armies" have symmetry, but not of "mirror" kind (as in western chess) - rather "180-degree rotational".

In shogi the first player (called Sente) is described as Black in translations while the other (called Gote) is white. We'll use capital letters for "blacks" and small letters for "whites". Below here is an initial position for some randomly-set game and with the first move made by one of black pawns:

 y k c v s r        |  moves of the pieces:
 p p p p p p        |
 - - - - - -        |  * * *    * * *    * * *    * * * 
 - - P - - -        |  * K *    * G *    - S -    - C -
 P P - P P P        |  * * *    - * -    * - *    - * -
 R S V C K Y        |
                    |  * - *    * - *    - * -    - * -
                    |  - Y -    - X -    - R -    - P -
                    |  - * -    * - *    * - *    - - -
                    |
                    |  - - - - -      - - * - -
                    |  - - * - -      - - * - -   * * *
                    |  * * H * *      - * V * -   * T *
                    |  - - * - -      - - * - -   - * -
                    |  - - - - -      - - * - -

The pieces king (K), gold general (G), silver general (S) and pawn (P) are found in standard Shogi. They only can move to one of adjacent cells, according to the patterns above (star means valid move). So King has 8 moves, Gold has 6, Silver has 5 and Pawn only 1 (and so pawns can't build "pawn chains" as in western chess).

Pieces copper general (C), tile general (Y), sword cat (X), and old rat (R) are found in larger variants - but in other regards follow the principles of those mentioned above, just with different patterns (letters Y and X are chosen as mnemonics of the respective patterns while R could be thought of the reversal of Y).

The two "ranging" pieces are vertical mover (V) and horizontal mover (H) - they could move unlimited number of squares vertically or horizontally but also can shift one cell in the orthogonal direction.

The pattern for piece tokin (T) is also presented, the same as for Gold - we haven't mentioned it yet, because it is not the separate piece, rather the promoted version of the pawn.

In our variant the pawns are the only pieces which promote - and they do it obligatory on reaching the last row (and becoming tokin).

When piece is captured it becomes unpromoted - hence when it is "dropped" back into the game, it is, in our case, simple pawn, not tokin.

Standard Shogi have limitation on pawn drops - they are not allowed to be dropped to the same "file" (vertical column of squares) where another pawn of the same player already is. And they couldn't be dropped to the last row as they won't be able to promote. We do not respect both of these rules, so pawns could be dropped everywhere, as other pieces. The third limitation - pawn couldn't be dropped to deliver immediate checkmate - is so rare that we also ignore it for our simplified variant.

The game is won by capturing the opponent's King.

Problem Statement

Given the initial setup and a sequence of moves, you are to print out how many valid moves there are after each move. No need to print it for the initial position itself - due to absence of knights only pawns can move and this makes 6 available moves always.

Input data the first line contains initial setup in the SFEN notation - it's an adaptation of the popular western chess "FEN" notation for Shogi.
Next lines contain moves, one move per line, described by four numbers. Details of the format are below. The sequence ends with 0 0 0 0 (not a valid move).

SFEN format has all rows (ranks) of the board concatenated into single line with slashes /. Empty squares are denoted by digits, each meaning specified amount of empty spaces (in a row). Then after the space follows the letter b or w - which side is to move. After one more space pocketed pieces are enumerated. However in this problem we always start with blacks to move and no pieces are pocketed yet.

Move is specified in a form of 4 digits, specifying Y1, X1, Y2, X2 where "X" mean the "file" and "Y" means the "rank" of the coordinate - and the first pair is for starting cell, the second for the target cell of a move.

Drops have ! (exclamation mark) in place of Y1 and the piece letter in place of Y2

Answer should simply contain space-separated numbers - counts of available moves after each next move.

Example

input:
ykcvsr/pppppp/6/6/PPPPPP/RSVCKY b
2 6 3 6
5 5 4 5
2 4 3 4
6 5 5 5
2 3 3 3
6 4 6 5
3 3 4 3
5 6 4 6
3 6 4 6
4 5 3 5
2 5 3 5
5 4 4 4
3 4 4 4
5 3 4 3
! P 5 6
0 0 0 0

answer:
6 7 7 9 9 12 10 13 10 26 10 30 10 32 27

This example starts with the board shown above, where rules are explained, though the first move is different (rightmost pawn). After the first move of blacks opponent still has just 6 pawn moves available, but after his response blacks have 7 opportunities (six for pawns and one for king. Position after this sequence of moves should be like this:

ykc1vr/pp2sP/2pP1P/4P1/PP4/RSVCKY w PPp