I問題 - Hyper Janken(easy)

実行時間制限: 2sec / メモリ制限: 1024MB

問題文

C氏はじゃんけんを一般化しようとしました。

与えられる整数\(n\)に対して、整数\(p, q\)を引数とする二変数関数\(g\)を次のように定めます。

ただし、自然数\(n, m\)に対して\(n \% m\)は「\(n\)を\(m\)で割った余り」を表します。

実数\(x\)に対して\(\lceil x \rceil\)は「\(x\)以上である最小の整数」を表します。

\(Q\)個の解読されたクエリ\(X,Y\)が暗号化されて与えられるので、次の規則に基づいて解読されたクエリを順に処理してください。

与えられる長さ \(m\) の数列 \(A\)に対して、

1. \(X \leq i, j, k < Y, \: i \neq j, \: j \neq k, \: i \neq k\) を満たすある整数の組 \((i, j, k)\) が存在して \(g(A_i, A_j) = g(A_j, A_k) = g(A_k, A_i) \neq 0\) が成り立つ。
2. \(X \leq i, j < Y, \: i \neq j\)を満たす\((i, \, j)\) の組が存在しない。

1,2のいずれかを満たすとき Aiko と出力し、どちらも満たさないとき Shoubu Ari と出力してください。

まず、\(g(p, q)\)の返り値は\(p, q\)のうちどちらのほうが強い手かを返します。

\(p\)と\(q\)が同じ強さ(同じ値)ならば0を、\(p\)が\(q\)より弱ければ1を、\(p\)が\(q\)より強ければ2を返します。

例として、\(N=1\)のとき、0をグー、1をチョキ、2をパーに対応させて考えてみると、\(g(0, 0)=0, \quad g(0, 1)=2, \quad g(0, 2)=1\)となることがわかります。

これをもとにクエリの処理の条件を考えると、

• 条件1は三つ巴になっている手があることを表します。

  例えばグー、チョキ、パーの3つの手が出たとき、\(g(0, 1)=g(1, 2)=g(2, 0)=2\)となり、三つ巴となります。

• 条件2はすべての手(の強さ)が同じであることを表します。

暗号化されたクエリは\(V_i,W_i \; (1 \leq i \leq Q)\)で与えられます。

\(i \; (1 \leq i \leq Q)\)番目の解読されたクエリについて、

1. \(i-1\)番目の解読されたクエリの処理でAikoと出力したとき、

   \(X=\min((V_i-V_{i-1})\% m,(W_i-W_{i-1})\% m)\)

   \(Y=\max((V_i-V_{i-1})\% m,(W_i-W_{i-1})\% m)+1\)

   となる。

2. \(i-1\)番目の解読されたクエリの処理でShoubu Ariと出力したとき、

   \(X=\min((V_i+V_{i-1})\% m,(W_i+W_{i-1})\% m)\)

   \(Y=\max((V_i+V_{i-1})\% m,(W_i+W_{i-1})\% m)+1\)

   となる。

ただし、自然数\(n,m\)に対して\(n \% m\)は「\(n\)を\(m\)で割った余り」を表します。

整数\(a,b\)に対して\(\min(a,b)\)は\(a,b\)のうち大きくない方、\(\max(a,b)\)は\(a,b\)のうち小さくない方とします。

ただし、0番目の暗号化されたクエリは\(V_0=W_0=0\)とします。

制約

• \(1 \leq n \leq 10^9\)
• \(1 \leq m, Q \leq 2 \times 10^5\)
• \(0 \leq V_i, W_i < m\)
• \(0 \leq A_i < 2n + 1 \quad (0 \leq i < m)\)
• 入力はすべて整数で与えられる。

入力

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

n m
A_0 A_1 ... A_{m-1}
Q
query1
query2
...
queryQ

各クエリ\(query_i\)は以下の形式で与えられる。

V_i W_i

出力

クエリごとにAikoまたはShobu Ariのうち正しい方を標準出力にそれぞれ1行で出力してください。

入力例1

3 6
2 2 2 4 0 6
3
0 2
3 3
3 2

出力例1

Aiko
Shoubu Ari
Aiko

1つ目のクエリでは \(g(2, 2) = 0\)です。 2つ目のクエリでは 条件を満たすような組は存在しません。 3つ目のクエリでは \((i, j, k ) = (0, 3, 5 )\)とすると \(g(2, 4) = g(4, 6) = g(6, 2) = 2\)です。