Given n boolean variables and the result of m operations, calculate the maximum score you can get. The value of each variable only can be 0 or 1. The score is calculated by p rules. Each rule will be defined by five integers (i,x,j,y,w). It means that you can get w scores if the value of the i-th variable equal to x and the value of the j-th variable equal to y. Now, determine the value of each variable so that you can get the maximum score.
Input
There are multiple test cases. The first line of each case contains three integer n m p( 1 ≤ n,m ≤ 100 , 1 ≤ p ≤ 5000 ).
Then following m lines, each describe a result of an operation. The format of each line is : i [operation] j = x ( 1 ≤ i,j ≤ n , 0 ≤ x ≤ 1 ). It gives the result of the i-th variable and the j-th variable on the operation.
There are only three kinds of operation("and","xor","or") in the data. The next p lines give the rules using format : i x j y w( 1 ≤ i,j ≤ n , 0 ≤ x,y ≤ 1 , 0 ≤ w ≤ 50 ). Process to the end of file.
Output
Output one line for each case. That is the maximum score you can get. I guarantee that there is at least one solution can satisfy the m operations.
Sample Input
3 2 2
1 xor 2 = 1
1 and 3 = 0
1 1 2 0 1
3 1 3 1 10
Sample Output
10
