Bajtek and Bitek are world-class masters of the card game Magic Creatures. Tonight, an epic duel will take place to decide who will be granted the lifelong title of Grandmaster.

The rules of Magic Creatures are quite peculiar. Each player has $n$ different decks. The actual gameplay is preceded by a deck-selection phase. Starting with Bajtek, the players will take turns discarding one of their opponent's decks. When each player is left with only one deck, the much more exciting second and final phase of the game begins. Interestingly, the course of the second phase does not depend on the players' strategies or even on chance – for every potential pair of decks allowed into the final showdown, it is known in advance how it will end: with a win for Bajtek, a win for Bitek, or a draw.

Your task is to determine whether Bajtek has a winning strategy. We say that Bajtek has a winning strategy if he wins the final showdown when both players discard their opponent's decks optimally. If Bajtek does not have a winning strategy, you must determine whether he has at least a drawing strategy, meaning whether he can ensure that his rival does not receive the honorable title of Grandmaster, assuming both players act optimally.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 20$), representing the number of test cases.

The description of each test case begins with a line containing two integers $n$ and $m$ ($1 \le n \le 100\,000$, $0 \le m \le 200\,000$), representing the number of decks each player has and the number of pairs of decks whose selection for the second phase does not result in a draw, respectively. The decks of each player are numbered from $1$ to $n$. This is followed by $m$ lines of the form $a\ w\ b$, where ($1 \le a, b \le n$, $w \in \{<, >\}$). If $w = <$, this line means that Bajtek's deck $a$ loses to Bitek's deck $b$. If $w = >$, then Bajtek's deck $a$ wins against Bitek's deck $b$. For a given ordered pair $(a, b)$ of deck numbers (for Bajtek and Bitek, respectively), a line of the form $a\ w\ b$ appears in the description of a given test case at most once; if such a line does not appear at all, it means that the final showdown after choosing Bajtek's deck $a$ and Bitek's deck $b$ ends in a draw.

Output

For each test case, output one line in the order they appear in the input.

For each case, output WYGRANA if Bajtek has a winning strategy; REMIS if he does not have a winning strategy but has a drawing strategy; and PRZEGRANA in all other cases.

Examples

Input 1

3
5 5
5 > 5
1 > 5
3 > 5
4 > 5
2 > 5
2 2
1 > 1
1 > 2
1 1
1 < 1

Output 1

WYGRANA
REMIS
PRZEGRANA