大学のプログラミングコンテストでボツになった自作問題です. 重要な問題だと思うのでみなさんといてみてください！

Description

非決定性有限オートマトン(NFA)とは、処理の実行による状態の遷移を記述するための概念で、形式言語を扱う際にも多く用いられる重要なものです。NFAは次の五つから構成されます： $Q$ ：状態全体の集合、 $\Sigma$ ：入力記号全体の集合、 $\delta$ ：状態遷移関数、 $q_0$ ：初期状態、 $F$ ：受理状態全体の集合( $Q$ の部分集合)

状態遷移関数 $\delta$ は現在の状態と入力記号を受け取ると次に移動する状態の候補を返す関数です。ある入力記号n文字の列 $w$ をNFAが受け取ると次のように動作します：・開始時の状態は初期状態です。入力記号列の1文字目と現在の状態(初期状態)を読み込んで、状態遷移関数の持つ、次に移動する状態の候補のうちのどれか1つの状態に移動します。次に移動する状態の候補が1つもないとき、エラーとして動作を強制終了します。
・次に、入力記号列の2文字目と現在の状態を読みこんで、状態遷移関数の持つ、次に移動する状態の候補のうちのどれか1つの状態に移動します。次に移動する状態の候補が1つもないとき、エラーとして動作を強制終了します。
・・・
・入力記号の列のn文字目と現在の状態を読みこんで、状態遷移関数の持つ、次に移動する状態の候補のうちのどれか1つの状態に移動します。次に移動する状態の候補が1つもないとき、エラーとして動作を強制終了します。エラーにならずにここまできた場合、n回目の移動先を最終状態とします。

動作の結果として最終状態が $F$ の要素となるような状態遷移の選び方が1つでもあるとき、NFAは入力記号列を受理する(Accept)といい、そうでないとき拒絶する(Reject)といいます。状態遷移の選び方をどのようにしてもエラーとなるときは、拒絶されます。

NFAの構成と入力記号列が与えられるので、入力記号列がNFAに受理されるか、拒絶されるかを判定してください。

Constraints

Input

1つの入力ファイルは複数のテストケースからなる。

入力ファイルの最初の1行目にはテストケースの個数 $T$ が記される( $1 \leq T \leq 100$ )。

2行目以降には、 $T$ 個のテストケースが記述されており、各テストケースは次の形式で表される。

$|Q|~ |\Sigma|~q_0$
$F$
$\delta_{00} ~ ~ ~ ~\delta_{01} ~ ~ \cdots ~ ~\delta_{0, |Q|-1}$
$\delta_{10} ~ ~ ~ ~ \delta_{11} ~ ~ \cdots ~ ~ \delta_{1, |Q|-1}$
$\vdots ~ ~ ~ ~ ~ ~\vdots ~ ~ ~ ~ \ddots ~ ~ ~ ~ \vdots$
$\delta_{|\Sigma|-1, 0} ~\delta_{|\Sigma|-1, 1} ~ ~ \cdots ~ ~ \delta_{|\Sigma| -1, |Q|-1}$
$w$

・ $Q$ は $0$ 以上 $|Q|$ 未満の整数全体、 $\Sigma$ は $0$ 以上 $|\Sigma|$ 未満の整数全体で表す。
・ $q_0$ は初期状態で $Q$ の要素、すなわち $0$ 以上 $|Q|$ 未満の整数。
・ $F$ は $Q$ の部分集合, すなわち $Q$ の要素が多くとも1度ずつのみ出現する数字列であって、各桁の数字は受理状態1つを表す。
・ $\delta_{a, q}$ は、入力記号 $a$ を状態 $q$ で読み込んだ時に次に移動する状態の候補で、 $Q$ の要素が多くとも1度ずつのみ出現する数字列または-1である。各桁の数字は次に移動する状態の候補1つを表すが、-1のときには次に移動する状態の候補が1つもないことを意味する。
・ $w$ は入力記号列で、 $\Sigma$ の要素1文字以上70文字以下からなる数字列である。

Output

各テストケースに対して、入力記号列がNFAに受理される場合は'Accept'、拒絶される場合は'Reject'と1行ずつ出力せよ。

Sample Input

3
2 2 0
1
01 1
-1 1
0111
10 1 0
9
012345678 -1 -1 -1 -1 -1 -1 -1 -1 -1
000000000
10 1 0
789
0123456789 123456789 23456789 3456789 456789 56789 6789 789 89 9
000000000

Sample Output

Accept
Reject
Accept

・1つ目のテストケースでは、0->0と状態を移動してしまうと次でエラーになりますが、0->1->1->1->1と状態を移動すれば受理状態を終了状態にできるので、受理されます。

・2つ目のテストケースでは、8文字目まで状態0に留まって9文字目で状態0から8までのいずれかに移動する以外はエラーとなります。状態0から8まではどれも受理状態ではないので、拒絶されます。

・3つ目のテストケースでは、うまく状態遷移していけばどの状態も最終状態となりうるので、受理状態7、8、を最終状態とする状態遷移の方法も存在します。よって、受理されます。

気まぐれエンジニア日記

ひよっこエンジニアの雑記

NFAエミュレータ