Programmers Should Learn Theory of Computation
By Matheus Pimenta, UnB 
Brazil
By Matheus Pimenta, UnB Brazil
During his adventure in Imaginationland, Alan Leopold "Butters" Stotch Turing invented his famous ice cream machine. You only have to say the flavor and the machine makes a delicious ice cream!
Image source: http://southpark.cc.com/avatar
At this moment, Butters is worried about one thing. He is capable of building his machine in many different ways; and he's doing experiments to decide which is the best. You decided to help him, because you're anxious for a vanilla ice cream. Given a description of a machine and a series of Q queries of flavors, Butters wants to know how many steps this machine takes to make the ice cream of each query.
An ice cream machine is a configuration with a state (an integer number), a string and a position in this string. For each configuration <state,string,position>, a step is generating a new configuration: the state is updated, the symbol at the current position is updated; and the current position is moved to an adjacent one (leftward, or rightward). If the command moves the position to a position beyond the limits of the string, a white space should be concatenated in the respective end of the string; and the position of the new configuration should point to this white space. The machine starts with the configuration <1,flavor,1>, where flavor is a string and the second 1 indicates the first position of this string. The machine halts when it reaches a configuration whose state is the integer S, as in "sorvete" (ice cream in portuguese).
The magical trick is that, for each configuration <state,string,position>, the Butters machine is capable of executing many different steps, so it can make the ice cream faster. Whenever the machine reaches a configuration that leads to multiple new configurations, the machine creates copies of itself, so each copy continues independently. There is a new copy for each new configuration. After creating copies for new configurations, the machine dies. If a particular configuration doesn't leads to any new configuration, it just dies. The process ends when any copy halts and finishes making the ice cream. It is guaranteed that some branch of the machine will halt and give the ice cream.
The input has several test cases and finishes with end of file.
The first line of a test case contains the integers N, S and Q, where 0 ≤ N ≤ 25 and 1 ≤ S,Q ≤ 10.
The next N lines describe the commands of the machine to be tested. Each line is in the format q a t b c, indicating that if a configuration is in the state q and the symbol at the current position is a, there must be a new configuration with state t, update the symbol at the current position to b and the current position should move in direction c, according the description of the statement. Note that 1 ≤ q,t ≤ S. The input a can be a lowercase letter, '0', or '~' followed by a non-empty string w, which may contain lowercase letters or '0'. In the third case, the command should be executed when the symbol at the current position do not occurs in w. The input b can be a lowercase letter, '0', or '*'. In the third case, the symbol at the current position should not be updated. The input c is either 'E' (of "esquerda", left in portuguese), or 'D' (of "direita", right in portuguese). The symbol '0' means a white space.
The next Q lines describe the queries. Each line is a string flavor of lowercase letters, with at least 1 and at most 20 letters.
For each query of each test case, print a line with the number of steps of the branch that produced the ice cream.
| Input Sample | Output Sample |
|
0 1 3 |
0 |