Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3382
Luna Dial

Time Limit: 6 Seconds      Memory Limit: 65536 KB

Izayoi Sakuya (十六夜咲夜) is the chief maid at the Scarlet Devil Mansion. She has the ability to manipulate time, and always takes advantage of her ability to stop time when working. (If she cleans when time stopped, it won't raise dust.) She can also speed or slow time.

Time has two concepts: DateTime (an instant) and TimeSpan (time interval). Manipulations of time can be treat as some binary operations on Scale, TimeSpan and DateTime. For example, for "Scale * TimeSpan", time is speeded up when Scale > 1, and is slowed down when Scale < 1; "DateTime - DateTime" tells the TimeSpan of two instants; but expressions like "TimeSpan * TimeSpan" and "DateTime + DateTime" are meaningless.

Sakuya records some of her manipulations as plain text, but the record may be ambiguous. For example, in "8:37 + 1:11", the type of "8:37" and "1:11" may be TimeSpan or DateTime, so we can also write the record as expression "TimeSpan\DateTime + TimeSpan\DateTime". Here, \ means "or" and has the highest precedence. There are four possible interpretations for this expressions, but only "TimeSpan + TimeSpan" and "DateTime + TimeSpan" are valid, the former result type is "TimeSpan" and the latter result type is "DateTime". Given a mass of expressions of records, could you tell Sakuya the number of valid interpretations whose result type is a particular type?

Input

There are multiple test cases, process to the end of file. Each test case begins with a line containing 5 integers, 1 ≤ ntype ≤ 4, 1 ≤ nop ≤ 6, 1 ≤ neq 100, 1 ≤ nexpr ≤ 100, 1 ≤ m ≤ 1000000007, which are the number of following types, operators, equations and expressions and the modulus respectively.

Then ntype different lines, each line contain a type. A valid type contains only alphanumeric characters, and its length is between 1 and 80.

Then nop different lines, each line contain a operator, its precedence (an integer between 1 (high) and 100 (low)) and its associativity ("l" means left-to-right and "r" means right-to-left), separated by a blank. A valid operator contains only punctuations other than '(', ')' and '\', and its length is between 1 and 80. It's guaranteed that all operators with the same precedence has the same associativity.

Then neq lines, each line has format "result_type = left_hand_side_type operator right_hand_side_type", which means that the type of "left_hand_side_type operator right_hand_side_type" is "result_type". There are no conflicting or duplicate equations. But you cannot assume that commutative laws or associative laws hold.

Then nexpr lines, each line contains an expression. All expressions are valid and no longer than 100000. Any white-space characters may appear anywhere as long as they doesn't break types or operators into two part.

Each test case ends with an empty line.

Output

For each expression, first output the expression id (starts from 1 for each test case). Then ntype lines, each contains a type and the corresponding answer mod m, output these lines in the same order as input. Output an empty line after each test case. See sample for more details.

Sample Input

3 4 11 6 530605879
Scale
TimeSpan
DateTime
+ 6 l
- 6 l
* 5 l
/ 5 l
Scale = Scale + Scale
Scale = Scale - Scale
Scale = Scale * Scale
Scale = Scale / Scale
Scale = TimeSpan / TimeSpan
TimeSpan = Scale * TimeSpan
TimeSpan = TimeSpan / Scale
TimeSpan = TimeSpan + TimeSpan
TimeSpan = DateTime - DateTime
DateTime = DateTime + TimeSpan
DateTime = DateTime - TimeSpan
Scale\TimeSpan\TimeSpan\Scale\DateTime\Scale\TimeSpan\TimeSpan\Scale
(DateTime \ TimeSpan) + (DateTime \ TimeSpan)
Scale \ TimeSpan \ DateTime + Scale \ TimeSpan \ DateTime
Scale \ TimeSpan \ DateTime - Scale \ TimeSpan \ DateTime
Scale \ TimeSpan \ DateTime * Scale \ TimeSpan \ DateTime
Scale \ TimeSpan \ DateTime / Scale \ TimeSpan \ DateTime

Sample Output

#1:
Scale: 4
TimeSpan: 4
DateTime: 1
#2:
Scale: 0
TimeSpan: 1
DateTime: 1
#3:
Scale: 1
TimeSpan: 1
DateTime: 1
#4:
Scale: 1
TimeSpan: 1
DateTime: 1
#5:
Scale: 1
TimeSpan: 1
DateTime: 0
#6:
Scale: 2
TimeSpan: 1
DateTime: 0

References

上海アリス幻樂団

acm_x_touhou


Author: WU, Zejun
Source: ACM × Touhou
Contest: ZOJ Monthly, August 2010
Submit    Status