Chess
Vasya recently discovered an old newspaper article about a unique chess match between two grandmasters. This game was played with experimental rules, leading to a different number of pieces and an unusual initial setup, though it still took place on a standard square chessboard. The traditional rules for moving and capturing pieces were maintained, and no new pieces were introduced during the game.
The newspaper included the board's configuration at a specific point in the match, along with the sequence of moves made by the players. Vasya wants to reconstruct the game on his board. He has already arranged the pieces according to the diagram and now needs to follow the recorded moves. Concerned about making errors, Vasya seeks your assistance. Your task is to write a program that identifies which piece makes each move.
Input
The first eight lines of the input file describe the chessboard's position at a certain moment in the game. Each line consists of eight characters. The symbols correspond to chess pieces as follows:
- Uppercase Latin letters represent white pieces, while lowercase letters represent black pieces. For instance, the white queen is denoted by "Q", and the black pawn by "p".
The ninth line of the input file contains an integer n, indicating the number of moves made (0 ≤ n ≤ 100000). Each of the following n lines describes one move, using four characters. The first two characters specify the starting position of the piece, and the last two characters specify the ending position. In each pair, the first character is a lowercase Latin letter a-h, representing columns 1-8. The second character is a digit from 1 to 8, where the digit i corresponds to the 9-i-th row in the input file.
Thus, the first character of the first line corresponds to position a8, and the seventh character of the sixth line corresponds to position g3.
Output
Output a single line, where the i-th character corresponds to the piece that made the i-th move.