For given integers N let’s consider the following single player game played with a box, N black and N white balls. Initially the box is empty and in one move the player can:

throw any ball not currently in the box into it
take out any ball currently in the box
if the box is empty, in one move he can put all \(2 \cdot N\) balls inside
if the box contains \(2 \cdot N\) balls, he can take away all of them in one move

Moreover, there are additional \(2 \cdot Q_v\) different valid moves given by \(Q_v\) rules and each single rule is given by 4 integers:

\(b, w, \delta_b, \delta_w\)

and means that if there are exactly b black balls and exactly w white balls in the box, then in one move the player can add/remove balls in such a way that after the move there are \(b + \delta_b\) black and \(w + \delta_w\) white balls in the box. In addition, the reverse operation is also a valid move, which means that if there are exactly \(b + \delta_b\) black and exactly \(w + \delta_w\) white balls in the box, the player can in one move add/remove balls in such a way that after the move there are exactly b black and exactly w white balls in the box.

Moreover, there are \(2 \cdot Q_f\) different forbidden moves given by \(Q_f\) rules and each such rule is given by 3 values:

\(b_f, w_f, c\)

where \(0 \leq b_f, w_f < N\) and denotes that if there are exactly \(b_f\) black and exactly \(w_f\) white balls in the box, the player cannot add to the box a ball of color c. In addition, the reverse operation is also a forbidden move, which means that for example if c is \(WHITE\) then the player cannot add a white ball to the box if there are exactly \(b_f\) black and exactly \(w_f\) white balls already there, and moreover, he cannot remove a white ball from the box if there are exactly \(b_f\) black and exactly \(w_f\) white balls already there.

Now let’s consider any valid state of the box during the game with exactly b black and w white balls inside. The evaluation of then box is then defined as \(b \cdot w\).

Next let’s consider a monkey playing the game forever. Monkey knows all the rules and makes only allowed moves. However, she doesn’t know what’s the best move in any situation, so she choses any of possible moves uniformly at random and performs it.

The goal of this problem is to find the greatest sum of evaluations of two boxes \(X, Y\) that can be produced during the game played by monkey, such that monkey can move from X to Y in a single move and she can move from Y to X in a single move also, and the expected number of moves the monkey will make in order to transform the box X to box Y and then back to X is an integer divisible by the number of all possible different moves monkey can make during the game. Two moves are the same if and only if they transform the same current state to the same state using the same operation including the same number of balls of every color.

If there are no two such boxes, then the answer is 1.

Constraints:

\(1 \leq N \leq 300\)
\(0 \leq Q_v \leq 100\)
\(0 \leq Q_f \leq 1000\)
\(0 < |\delta_b|, |\delta_w| < N\)
\(0 \leq b + \delta_b, w + \delta_w \leq N\)
for any \(0 \leq w, b \leq N\) the box containing b black and w white balls can be produces by a sequence of valid moves
c is either \(BLACK\) or \(WHITE\)
\(0 \leq b_f, w_f < N\)
all additional moves are unique and all of them are different than standard valid moves given at the beginning of the statement
all forbidden moves are unique
for a forbidden move the number of black balls in the box before and after the move cannot be both N
for a forbidden move the number of white balls in the box before and after the move cannot be both 0

Subtask 1 (10 pts):

\(N \leq 10\)

Subtask 2 (30 pts):

\(N \leq 50\)

Subtask 3 (60 pts):

\(N \leq 300\)

Input format:

In the first line there are three space separated integers \(N, Q_v, Q_f\) denoting the number of balls of each colors, the number of rules describing additional valid moves and the number of rules describing forbidden moves. Then \(Q_v\) lines follow and in each of them there are 4 space separated integers \(b, w, \delta_b, \delta_w\) denoting a rule describing two additional valid moves. After that \(Q_f\) lines follow and in each of them there are 3 space separated values \(b_f, w_f, c\) denoting a rule describing two forbidden moves.

Output format:

In a single line output one integer denoting the greatest sum of evaluations of two boxes \(X, Y\) during the game played by monkey, such that monkey can move from X to Y in a single move and she can move from Y to X in a single move also, and the expected number of moves the monkey will make in order to transform the box X to box Y and then back to X is an integer divisible by the number of all possible different moves monkey can make during the game. If there are any such boxes, print 1 in a single line.