K. JajaScript
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ada and Grace have been friends for a long time, but there is one thing they have never been able to agree on: what makes a message funny.

To settle the argument once and for all, each of them created a collection of JajaScript rules. Each rule describes a pair of expressions that, when they appear in a message, contribute to its funniness score.

A rule consists of two non-empty strings $$$A$$$ and $$$B$$$, and an integer $$$P$$$, the funniness rating of the rule.

Suppose that $$$A$$$ occurs $$$x$$$ times in the message and $$$B$$$ occurs $$$y$$$ times. Then this rule contributes $$$x \cdot y \cdot P$$$ points to the owner's total score.

All occurrences are counted, including overlapping occurrences. For example, the string aa occurs three times in aaaa.

The score of Ada (respectively, Grace) is the sum of the contributions of all of her rules. Rules are considered independently: the same expression may appear in several rules, the same rule may appear more than once, and $$$A$$$ may be equal to $$$B$$$.

Given the message and both collections of rules, determine whose JajaScript score is greater.

Input

The first line contains a non-empty string $$$S$$$, the message.

The second line contains an integer $$$N$$$, the number of Ada's rules.

Each of the next $$$N$$$ lines contains two non-empty strings $$$A_i$$$, $$$B_i$$$, and an integer $$$P_i$$$, describing one of Ada's rules.

The next line contains an integer $$$M$$$, the number of Grace's rules.

Each of the next $$$M$$$ lines contains two non-empty strings $$$A_i$$$, $$$B_i$$$, and an integer $$$P_i$$$, describing one of Grace's rules.

All strings consist only of lowercase English letters ($$$a$$$–$$$z$$$).

The following constraints hold:

$$$1 \le |S| \le 10^6$$$

$$$1 \le N, M \le 2 \cdot 10^5$$$

$$$1 \le P_i \le 10$$$

The sum of the lengths of all strings $$$A_i$$$ and $$$B_i$$$ in Ada's and Grace's rules does not exceed $$$10^6$$$:

$$$\sum (|A_i| + |B_i|) \le 10^6$$$.

Output

If Ada's score is greater, print

Ada P

where $$$P$$$ is Ada's total score.

If Grace's score is greater, print

Grace P

where $$$P$$$ is Grace's total score.

If both scores are equal, print

Empate P

where $$$P$$$ is their common score.

The answer fits in a signed 64-bit integer.

Examples
Input
rrallrrll
2
rr ll 5
r all 2
2
rr ll 3
all r 4
Output
Empate 28
Input
aaaa
2
aa a 2
aaa aa 3
1
a aa 4
Output
Grace 48
Note

In the first example:

  • rr occurs $$$2$$$ times;
  • ll occurs $$$2$$$ times;
  • r occurs $$$4$$$ times;
  • all occurs $$$1$$$ time.

Therefore, Ada's score is

$$$(2\cdot2\cdot5)+(4\cdot1\cdot2)=28$$$,

while Grace's score is

$$$(2\cdot2\cdot3)+(1\cdot4\cdot4)=28$$$.

Thus, the result is Empate 28.

In the second example, overlapping occurrences are important. In aaaa:

  • a occurs $$$4$$$ times;
  • aa occurs $$$3$$$ times;
  • aaa occurs $$$2$$$ times.

Ada's score is

$$$(3\cdot4\cdot2)+(2\cdot3\cdot3)=42$$$,

while Grace's score is

$$$4\cdot3\cdot4=48$$$.

Therefore, Grace wins with a score of $$$48$$$.