問題文

数式を表す記法に 逆ポーランド記法 がある． 本問題では， 1桁の整数 ( 0 から 9 ) や， 二項演算子 (加算 + , 減算 - , 乗算 * ) をトークンと呼び，トークンを連結した文字列で逆ポーランド記法の式を表す．
例えば， 逆ポーランド記法の式は 32-1+ のように書き，これは中置記法で書くと (3-2)+1 で計算結果は 2 である．
逆ポーランド記法の式を計算するための，関数のプログラムの擬似コードを次のように書いた．

calc(s)
{
    データ構造Xを空に初期化する

    for (i in [0 .. |s|-1])
    {
        if (s[i]は数である)
        {
            X.push(s[i])
        }
        else
        {
            r = X.pop()
            l = X.pop()
            lとrを演算子s[i]で計算した結果をaとする
            X.push(a)
        }
    }

    ans = X.pop()
    return ans
}

コード中のデータ構造 X がスタックならばこの関数は逆ポーランド記法の式を正しく計算するが，誤ってキューで作ってしまい正しい計算をすることができない． そこであなたは，入力する式を並び替えてキューで作ったプログラムに正しい答えを出力させることにした．

X をスタックで作ったコードをSプログラム， X をキューで作ったコードをQプログラムと呼ぶことにする．
逆ポーランド記法の式 A が与えられるので，次の条件を満たすような B を求めて出力せよ．

• B は A の並び替えである
• Qプログラムの入力に B を与えた時にQプログラムはエラーを出さない
• Sプログラムの入力に A を与えた時の出力とQプログラムの入力に B を与えた時の出力は等しい

A

B

入力例1

54-

出力例1

45-

入力 54- に対する正しい出力は 45- のただ一つだけである．

入力例2

321+-

出力例2

12+3-

入力 321+- をSプログラムに与えた時の計算を中置記法で書くと 3-(2+1) であり，Sプログラムの出力は 0 である．

入力例3

2

出力例3

2

数ひとつだけの文字列も正しい逆ポーランド記法の式である．

問題文

正整数 X を二進数で表したときに出現する 1 の個数を， X のビットカウントという．

与えられる正整数 N について， X と X + N のビットカウントが等しくなるような正整数 X は存在するだろうか?

存在するならばその最小値を，存在しないなら -1 を出力せよ．

T
N_1
:
N_T

入力例

3
10
20
30

出力例

10
20
2

16:38 入力例の三番目のケースに誤りがありましたので，修正しました．

問題文

ヘンゼルはビスケット，キャンディ，マシュマロの絵の書かれたタイルを使って平面上にお菓子の家を作る遊びをしている．

そこでグレーテルが，お菓子の家を使ったゲームを提案した．

ゲームの内容は以下のとおりである．

• まず，グレーテルがお菓子の家の大きさ N を指定する
• 次に，ヘンゼルは一辺の長さ N の正三角形状にタイルを並べ， お菓子の家を作り，下の図のように座標をつける．
  このとき，最下段はビスケットのタイルで土台を作り， それ以外の段はキャンディとマシュマロのタイルで構成する．
• グレーテルは，1 から N までがそれぞれ一度ずつ出現する 順列 σ を用意する．順列 σ の i 番目を σ_i で表すとする．
  なお，この順列 σ はヘンゼルには知られないようにする．
• グレーテルは，その順列 σ から，以下の規則にしたがってお菓子の家をシャッフルする．
  ただし，シャッフルする前の座標 (i, j) の位置のタイルを a[i,j] ， シャッフルした後の座標 (i, j) の位置のタイルを b[i,j] として表すものとする．
  • σ_i < σ_j のとき，b[i, j] = a[σ_j, σ_i]
  • σ_i ≥ σ_j のとき，b[i, j] = a[σ_i, σ_j]
• ヘンゼルはシャッフルされたお菓子の絵を見て，順列 σ の内容を推測する．
  推測通りであれば，ヘンゼルの勝ち，間違っていればグレーテルの勝ちである．

以上のゲームを複数回行う． この問題の目的は，ヘンゼル役のAIプログラムを作成し， ジャッジ側の用意したグレーテル役のAIプログラムと対戦をして， 全てのゲームに勝つことである．

入出力

初めの入力は以下の一行のみで与えられる．

N

N (6 \leq N \leq 200) はお菓子の家の大きさを表す整数である．

この入力の後に，解答プログラムはお菓子の家を表す文字列を， マシュマロを o ，キャンディを @ ， ビスケットを # として出力せよ． お菓子の家の上から i 段目を，長さ i の文字列 s_i として以下の形式で出力すること． 各行の先頭には空白を入れず横詰めで出力し，末尾には改行を出力せよ．

s_1
:
s_N

次に，シャッフル後のお菓子の家を表す文字列が同じ形式で与えられる． その後，順列 σ を空白区切りで以下のような形式で出力すること． 出力の後には改行を出力せよ．

σ_1 ... σ_N

この後，すぐに次のゲームがはじまり， 次のゲームのお菓子の家の大きさを表す整数が入力として与えられる． 全てのゲームが終了すると，お菓子の家の大きさを表す整数の代わりに 0 が入力として与えられるので，それを受け取ったら即座にプログラムを終了すること． なお，ひとつの入力で行われるゲームの回数は多くとも 10 回である．

各出力の後には，出力をフラッシュする必要があることに注意せよ．例えば C/C++ では

scanf("%d", &N);

としてお菓子の家のサイズNを受け取り， これに対して文字列sを

printf("%s\n", s); fflush(stdout);

と出力すればよい． グレーテル役のAIプログラムから与えられる入力は最後まで受け取ること．受け取らなかった場合，Time Limit Exceeded の結果が得られることがあるため，注意すること．

部分点

以下の制約を満たすデータセットに全て正解した場合は 3 点の部分点が与えられる．

• N = 6

入出力例

以下の入力例では N = 4 の場合について示しているが，このような入力は与えられないことに注意せよ．

  

    
手番
    
プログラムの出力
    
プログラムへの入力
    
説明
  
  

    
グレーテル
    

    
4
    
お菓子の家のサイズの指定
  
  

    
ヘンゼル
    
@
o@
@oo
####
    

    
お菓子の家の作成
  
  

    
グレーテル
    

    
@
o@
@oo
####
    
σを元にシャッフル
  
  

    
ヘンゼル
    
2 1 4 3
    

    
σの出力
  
  

    
グレーテル
    

    
4
    
お菓子の家のサイズの指定
  
  

    
ヘンゼル
    
@
o@
@oo
####
    

    
お菓子の家の作成
  
  

    
グレーテル
    

    
@
o@
@oo
####
    
σを元にシャッフル
  
  

    
ヘンゼル
    
1 2 3 4
    

    
σの出力
  
  

    
グレーテル
    

    
4
    
お菓子の家のサイズの指定
  
  

    
ヘンゼル
    
@
o@
oo@
####
    

    
お菓子の家の作成
  
  

    
グレーテル
    

    
@
@o
@oo
####
    
σを元にシャッフル
  
  

    
ヘンゼル
    
4 3 2 1
    

    
σの出力
  
  

    
グレーテル
    

    
0
    
全てのゲームが終了
  

問題文

頂点数 n の木があり，頂点 i (i = 1, ..., n) には正の整数 a_i が書かれている． q個の質問に答えよ.

各質問は3つの整数からなり， j 番目の質問は x_j, v_j, w_j で与えられる．
木の頂点 v_j から w_j への最短のパスの頂点に書かれている数 a_i で， x_j を順番に割った余りを出力せよ． 言い換えると，v_j から w_j への最短パスが p_1, ..., p_k (頂点数 k , p_1 = v_j, p_k = w_j ) であるとき， ((...((x_j % a_{p_1}) % a_{p_2}) ...) % a_{p_{k-1}} ) % a_{p_k} を出力せよ．

ただし x % y は x を y で割った余りを取る演算とする．

n q
a_1 ... a_n
b_1 c_1
:
b_{n-1} c_{n-1}
x_1 v_1  w_1
:
x_q v_q  w_q

入力例1

5 2
8 6 4 3 2
1 2
2 3
3 4
4 5
15 1 5
15 2 5

出力例1

1
0

入力例2

8 5
18 29 52 64 4 59 89 15
1 2
1 3
1 4
2 5
3 6
3 7
4 8
99 6 7
102 5 8
15 2 6
84 7 8
19 1 1

出力例2

40
2
15
14
1

問題文

テープに4001 個のセルが一列並んでおり、順に -2000 から 2000 の数が書かれている。 はじめに N 個のコインがそれぞれ 0 のセル以外の異なるセルに置かれている。 アリッサとベンはコインを1個づつ交互に動かすターン制ゲームを行う。

アリッサの先攻でゲームを始める。
自分のターンになったプレイヤーはテープに置かれているコインを1つ選ぶ。 そのコインをコインの置かれていない、別のセルに動かす。 ただしこのとき、 0 のセルに近づくように、 0 のセルを飛び越さないように動かさなければならない。
正確にはiのセルのコインを選んだ時は、次の条件を満たすjのセルに移動させることができる。

• i \geq 1 のとき、 0 \leq j \leq i-1を満たし、jのセルにはコインが置かれていない
• i \leq -1 のとき、 i+1 \leq j \leq 0を満たし、jのセルにはコインが置かれていない

ゲームの最初の状態として、N個のコインの置かれているセルA_1...A_Nが入力として与えられる。
アリッサがうまくプレイすればベンがどのように動かしても、アリッサが勝つ事ができるならば Alyssa と出力せよ。 そうでないならば Ben と出力せよ。

N
A_1 ... A_N

name

入力例1

1
5

出力例1

Alyssa

入力例2

2
-3 -4

出力例2

Ben

入力例3

4
-366 42 99 314

出力例3

Ben