問題
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$
- $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