Quarantine can be very boring. To help pass the time, you've decided to watch piddddgy and deruikong play a game. The game is played on a directed acyclic graph with ~N~ nodes numbered from ~1~ to ~N~ and ~M~ edges each coloured red, orange, yellow, green, blue, indigo, or violet. To start the game, a token is placed on node ~1~, then piddddgy and deruikong take alternating turns with piddddgy starting first. A move consists of a player selecting the token and moving it along an edge to an adjacent node. The game ends when the token has visited all the colours on the graph, or it is impossible to make a move. The winner is then the last player who moved the token.

Assuming both piddddgy and deruikong play optimally, who is the winner of the game?

Input Specification

The first line of input will contain two space-separated integers, ~N~ and ~M~.

The next ~M~ lines that follow will each contain two integers, ~u_i~ and ~v_i~, followed by a single character ~C~. This describes that there is a directed edge from ~u_i~ to ~v_i~ with colour ~C~.

Output Specification

Output the winner of the game, either piddddgy or deruikong.

Constraints

~2 \le N \le 10^5~

~1 \le M \le 10^6~

~C \in \{\text{r, o, y, g, b, i, v}\}~

It is not guaranteed that all edges are distinct.

Sample Input 1

4 4
1 2 r
1 2 b
2 3 r
3 4 r

Sample Output 1

piddddgy

Explanation for Sample 1

The optimal game is played as follows:

Turn ~1~: piddddgy moves the token on the red edge from ~1~ to ~2~.

Turn ~2~: deruikong moves the token on the red edge from ~2~ to ~3~.

Turn ~3~: piddddgy moves the token on the red edge from ~3~ to ~4~.

The game ends with piddddgy making the last move.

Sample Input 2

4 4
1 2 b
1 2 b
2 3 r
3 4 r

Sample Output 2

deruikong

Explanation for Sample 2

The optimal game is played as follows:

Turn ~1~: piddddgy moves the token on the blue edge from ~1~ to ~2~.

Turn ~2~: deruikong moves the token on the red edge from ~2~ to ~3~.

The game ends because the token visited every colour on the graph with deruikong making the last move.