273. Game Po
time limit per test: 0.5
memory limit per test: 65536
In the eastern country Pon-pong there is a very popular game Po. Po is the game with stones of four different colors: blue, red, yellow and white. The game is played by four participants. Before the beginning all stones are randomly placed in a row in front of the participants, each player chooses one of the stone colors (all players should have different colors). After that the game process begins. Each of the players in a turn chooses two nearby stones and replaces them by the third one, but only if this change is permitted by the "List of Po Replacements". Replacement is possible if the stones in the row and in the "List of Po Replacements" are in the same order. The game is considered to be finished if it is impossible to perform any change on the stones row. If after the end of the game only one stone remains, the player who chose the color of the stone left is a winner. If there are multiple stones, then the game result is draw. The boy Sasha liked very much the game Po during his visit to Pon-pong. He noticed, that in some games the players with some color are doomed to loose before the beginning of the game (after the distribution of the colors between players, but before the first move). Sasha decided to choose only such color, that he will have some chance to win the game, i.e. there is some sequence of players' moves, that leads to Sasha's victory.
Each stone color is defined by one symbol: "b" -- blue, "r" -- red, "y" -- yellow and "w" -- white. The first line of the input file contains integer numbers B, R, Y and W (1 <= B,R,Y,W <= 16). The following B lines contain the rules of replacement of stones to the blue stone (one rule per line). Each rule is a pair of symbols without spaces, denoting the two stones which can be replaced by the blue one. The following R lines describe the rules of replacement to the red stone, Y lines --- to the yellow stone and W lines -- to the white stone. The last line contains from 1 to 200 symbols denoting stone colors -- the row of the stones before the beginning of the game.
Output the single line without spaces containing the list of colors, for which there is a chance to win the game (in any order). If it is impossible to win the game with any color, output "Nobody".
2 1 1 1
1 1 1 1
|Author:||Sergey V. Mironov, Alexander S. Ivanov
|Resource:||ACM ICPC 2004-2005, NEERC, Southern Subregional Contest
|Date:||Saratov, October 7, 2004
|Server time: 2017-10-18 22:33:39||Online Contester Team © 2002 - 2016. All rights reserved.|