問題

$X$ 桁の整数 $N$ 個 $A_1, A_2, ..., A_N$ と整数 $K$ が与えられ ahri と teemo が3万円の松茸を賭けて以下のゲームをします。

1. 最初の発言者を ahri として以下を繰り返します。
2. 手番になった発言者は $N$ 個の整数 $A_i$ のうち $K$ 個の整数を選び、好きなように並べて新たな $XK$ 桁の整数を作ります。例えば 3個の整数 $31, 41, 59$ のうち 2個の整数を好きなように並べると新たな4桁の整数 $4159, 3159, 3141, 5941, 5931, 4131$ を作ることができます。このとき $A_i = A_j (i \neq j)$ は選べますが $A_i = A_j (i = j)$ は選べません。
3. 新たな $XK$ 桁の整数のうち $X$ 桁の 33...33 で割り切れる整数を1つ答えます。ただし、過去に誰かが発言した整数は答えられません。答えられる整数がなければ、その時点で手番の発言者は負けになります。
4. 手番の発言者を交代して2と3を繰り返します。

このゲームを ahri の先手で始めて互いに最善の行動を取ったとき、どちらがゲームに勝って松茸を食べられるか答えてください。

2021/08/02 14:00 サンプル4を追加しました。

2021/08/02 23:30 想定解のバグが原因でテストケース18が間違っていたため修正しました。

制約

• $1 \leqq X, N, K \leqq 14$
• $10^{X-1} \leqq A_i \leqq 10^{X} - 1$
• $K \leqq N$
• 入力は整数

入力

$X \ N \ K$

$A_1 \ A_2 \ ... \ A_N$

出力

ahri がゲームに勝つなら "ahri" を出力してください。

teemo がゲームに勝つなら "teemo" を出力してください。

なお、最後に整数を答えられなかった者を負けとし、最後に整数を答えられた者は勝ちとします。

サンプル

2 4 2
23 98 56 43

teemo

4個の整数 $A_1, ..., A_4$ から2個選んで並べると新たな4桁の整数を12個作ることができます。

そののうち33で割り切れるのは $2343, \ 4323, \ 4356, \ 5643$ の4個です。

ahri が $2343$ teemo が $4323$ ahri が $4356$ teemo が $5643$ を発言すると次に ahri は整数を答えられないので teemo が勝ちます。

2 5 3
64 11 64 37 99

ahri

5個の整数 $A_1, ..., A_5$ から3個選んで並べると新たな6桁の整数を33個作ることができます。

そのうち33で割り切れるのは $376464, \ 643764, \ 646437$ の3個です。

ahri が $376464$ teemo が $643764$ ahri が $646437$ を発言すると次に teemo は整数を答えられないので ahri が勝ちます。

$A_i$ には同じ整数が含まれることもあり、 $A_i = A_j (i = j)$ は選べませんが、 $A_i = A_j (i \neq j)$ は選べることに注意してください。

3 10 2
123 410 456 922 789 151 848 151 666 666

ahri

333で割り切れる6桁の整数は5個作れるので、互いに最善の行動を取ると ahri が勝ちます。

3 2 2
333 333

ahri

並べ方は2通りありますが、333で割り切れるのは $333333$ の1個なので ahri が発言して teemo が負けます。