007 - EEEEndless gamEEEE

問題

MMNMMさんはPlatypusくんと夏祭りで遊び、Platypusくんのことが気に入りました。
なので実は神社に憑いた妖怪であったMMNMMさんはPlatypusくんを神社にとらえようと、妖怪特有の不思議空間を使ってPlatypusくんとゲームをすることにしました。

ゲームはいくつかの石の山で行われて、それぞれのプレイヤーは自分のターンに1つの石の山に対して次の操作を一回だけすることができます。

・その山にある石の数を$N$、$N$の最小の素因数を$p$(ただし、$N=1$のとき$p=1$とする)として、その山から$1$個以上$p$個以下の石を取り除く。ただし、$K$個以上石を取ってはいけない。

最後の石を取った人が勝ちです。

ただし、MMNMMさんは妖怪なので、神通力を使ってズルをすることができます。
神通力を使うと、一つの石の山を選んで同じ山をもう一つ作ることができます。
Platypusくんは先手になることができましたが、MMNMMさんは一番最初に神通力を使うことができます。
二人ともが勝利に向かって最適な行動をするとき、Platypusくんはゲームに勝ってMMNMMさんから逃げることができるでしょうか。

入力

入力は以下の形式で与えられる。

$N\ K$
$A_1\ A_2\ \dots\ A_N$

一行目には、はじめにある山の個数である整数$N$と、一回に取ることができる石の最大の個数$K$が空白を区切りとして与えられる。 二行目には、それぞれの山にある石の個数$A_i\ (1\leqq i\leqq N)$が空白を区切りとして与えられる。

出力

二人が最適な行動をしたとき、Platypusくんがゲームに勝つことができるならば"ESCAPE"、できないならば"CAUGHT"と一行に出力しなさい。

制約

全ての入出力ケースについて以下を満たす。

• $1\leqq N\leqq10^5$
• $1\leqq A_i\leqq 10^6\quad(i=0,1,\dots,N)$
• $1\leqq K\leqq 10^6$

10点分の入出力ケースについて以下を満たす。

• $1\leqq A_i\leqq 2\times10^5\quad(i=0,1,\dots,N)$
• $1\leqq K\leqq 10^3$

入出力例

入力例1

3 5
3 3 4

出力例1

CAUGHT

たとえば、MMNMMが最初に4の山をもう一つ作ったら、3の山が二つ、4の山が二つできます。
それぞれの山のグループについてその中で対称な手(物まね戦略といいます)を打つことで、MMNMMが勝利します。

入力例2

3 2
1 4 7

出力例2

CAUGHT

入力例3

3 5
1 4 7

出力例3

ESCAPE

入力例4

10 7
9 10 3 5 5 9 1 8 5 3

出力例4

CAUGHT