G. The Chicken and the Egg
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

What came first, the chicken or the egg? This is one of life's biggest mysteries, but your friend Chris thinks he can solve it.

He hypothesizes that whichever came first should have had more time to evolve and should thus be faster.

To test this, he has made a maze. The maze can be represented as a directed graph with $$$n$$$ nodes and $$$m$$$ edges. Among these $$$n$$$ nodes, there are $$$a$$$ entrances and $$$b$$$ exits. Because chickens and eggs are shaped differently, they take $$$c_i$$$ and $$$e_i$$$ time to traverse edge $$$i$$$, respectively.

First, Chris will test a chicken. He will uniformly randomly pick an entrance to place the chicken and time how long it takes for the chicken to reach any exit. He will then similarly pick a random entrance for the egg and time it. He plans to let the chicken and egg study the maze beforehand so that they both take their respective fastest routes to any exit.

If a chicken or egg starts at a node that can't reach an exit, it can never finish. If they both never finish, it is a tie.

Knowing you are a mathematician, Chris wants to know who you think will win.

Input

The first line contains 4 space-separated integers $$$n$$$, $$$m$$$, $$$a$$$, and $$$b$$$ ($$$1 \leq n,m \leq 2 \cdot 10^5$$$, $$$1 \leq a, b \leq n$$$, $$$2 \leq a + b \leq n$$$) — the number of nodes, number of edges, the number of entrances, and the number of exits, respectively.

The following $$$m$$$ lines each contain four integers $$$u$$$, $$$v$$$, $$$c$$$, and $$$e$$$ ($$$1 \leq u, v \leq n$$$, $$$1 \leq c, e \leq 10^9$$$) – denoting a directed edge between nodes $$$u$$$ and $$$v$$$ that will take chickens and eggs time $$$c$$$ and $$$e$$$ to traverse, respectively.

The next line contains $$$a$$$ distinct space-separated integers $$$s_1, \dots, s_a$$$ ($$$1 \leq s_i \leq n$$$) – the nodes that are entrances.

The next line contains $$$b$$$ distinct space-separated integers $$$t_1, \dots, t_b$$$ ($$$1 \leq t_i \leq n$$$) – the nodes that are exits.

It is guaranteed that no node is both an entrance and an exit. There can be double edges.

Output

Output "chicken" if it is more likely for the chicken to win, "egg" if it is more likely for the egg to win, and "tie" if they have equal probability of winning.

Examples
Input
3 3 1 1
2 1 1 1
1 3 2 1
2 3 3 3
2
3
Output
egg
Input
5 6 3 2
1 2 1 2
1 3 3 1
2 3 2 2
1 4 1 10
3 4 3 2
3 5 1 3
1 2 3
4 5
Output
chicken
Input
4 2 2 2
1 3 2 1
2 4 1 2
1 2
3 4
Output
tie