C. Battle
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Siri is playing a two-player mini-game, and he called Dagu to play the game with him.

The whole game flow is as follows: $$$n$$$ piles of stones will be randomly generated at the beginning of the game, and there are $$$a_i$$$ stones in the $$$i$$$ th pile. At the same time, the players will set a lucky number $$$p$$$. The two players then take turns to perform the following operation: choose a pile and remove some stones from the pile. The number of stones removed each time must be a non-negative integer power of the lucky number. That is, the number of stones that both players can remove each time is a set as $$$\{1,p,p^2...\}$$$. Specially, if $$$p=1$$$ , both player can only remove one stone each time. Like many games, whenever a player cannot perform any operation, that player loses.

Siri, as the king of mini-games, wants to humiliate Dagu, but he is busy falling in love with his girlfriend, so he found you and wanted to know if he would win ultimately, when Siri goes first and both players play optimally?

Input

The first line contains two integers $$$n,p$$$ $$$(1\le n\le 3\times 10^5,1\le p\le 10^{18})$$$ — $$$n$$$ is the number of piles, and $$$p$$$ is the lucky number, whose significance is described in the title.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(1\le a_i\le 10^{18})$$$ — $$$a_i$$$ is the number of stones in the $$$i$$$ th pile.

Output

Output one line. If Siri can win, output "GOOD", otherwise output "BAD" (without quotes).

Examples
Input
1 1
2
Output
BAD
Input
1 4
5
Output
BAD
Input
2 3
4 5
Output
GOOD