m n
a_1 b_1
a_2 b_2
:
a_m b_m

• 1 ≦ m ≦ 300^2
• 1 ≦ n ≦ 10000
• 1 ≦ a_i ≦ 300
• 1 ≦ b_i ≦ 300
• i ≠ j ならば、 a_i ≠ a_j または b_i ≠ b_j

city_A
hour_0 hour_1 … hour_{23}
N
city_{1,1} time_{1,1} city_{1,2} time_{1,2}
city_{2,1} time_{2,1} city_{2,2} time_{2,2}
:
city_{N,1} time_{N,1} city_{N,2} time_{N,2}
city_B
time_B

• 1≦N≦20
• 都市の名前・時間の名前は大文字・小文字の英字からなる
• 都市の名前・時間の名前の文字列長は 20 以下
• 異なる都市が同じ名前を持つことはない
• 時間の名前は互いに異なる
• 時刻はhh:mmの形式で与えられる
• hhは00～23
• mmは00～59
• 情報の矛盾や不足は存在しないことが保証される

N
a_1
a_2
:
a_N

<有限小数> ::= <整数部> "." <\d+>
<循環小数> ::= <整数部> "." <\d*> "(" <\d+> ")"
<整数部>   ::= "0" | <[1-9]> <\d*>
<\d*>      ::= "" | <\d+>
<\d+>      ::= <[0-9]> <\d*>
<[0-9]>    ::= "0" | <[1-9]>
<[1-9]>    ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

• 1 ≦ N ≦ 300
• a_i の文字列長は 300 以下

n m r

• 状態を (x,y) で表す。x, y を「要素」と呼ぶ。
• 初期状態は、先攻後攻ともに (1,1) である。
• 各ターンでとれる「行動」は「選択」または「分割」のいずれかである。
• 先攻後攻交互に行動を繰り返し、(0,0) となったほうが負けとなる。
• 選択： 自分の 0 でない要素 x と相手の 0 でない要素 y を選び、選んだ相手の要素に x を「加算」し、x+y にする。このとき、以下のどちらかの加算ルール r を適用する。
• 加算ルール 0 ： x+y が n 以上になった場合は 0 になる。
• 加算ルール 1 ： x+y が n 以上になった場合は x+y-n になる。
• 分割： 一方の要素が 0、かつ、もう一方の要素 k が 2 以上ならば、「分割」を行うことができる。 a + b = k, a ≧ 1, b ≧ 1 となるような自然数 a, b を選び (a,b) とする。
• 分割は最大 m 回行うことができる。

• 2 ≦ n ≦ 16
• 0 ≦ m ≦ 2
• 0 ≦ r ≦ 1

1. 自分が勝ちになる手が存在するときはその手を選ぶ。自分が勝ちになる手が複数存在するときはその中からゲームが最短で終了するような手を選ぶ。
2. 自分が負けになる手しか存在しないとき、ゲームが最長で終了するような手を選ぶ。