問題文
金貨の山が N 個あり、 i 番目の山には Ai 枚の金貨があります。
タドちゃんとコロちゃんはこれらを使ってゲームをします。ゲームの手順は以下の通りです。
- タドちゃんを先手、コロちゃんを後手とし、次の操作を交互に繰り返す。
- 操作:金貨の山のうち金貨が 1 枚以上残っているようなものを 1 つ選び、その山から 1 枚以上の金貨を取り除き、手に入れる。
- 全ての山から金貨が無くなり、これ以上操作が出来ない状態になったらゲームを終了する。
ゲームの勝敗は次のようにして決まります。
- 金貨を入手した枚数の合計が多いほうが勝ち
- 金貨を入手した枚数の合計が同じならば、最後に金貨を入手したほうが勝ち
両者最適に行動したとき、どちらが勝利するか求めてください。
制約
- 1≤N≤200000
- 1≤Ai≤109
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
出力
タドちゃんが勝利するならfirst
、コロちゃんが勝利するならsecond
と出力してください。
入力例1
出力例1
ゲームの進行例として、以下のようなものがあります。
- タドちゃんが 3 番目の山から金貨を 1 枚取る。
- コロちゃんが 2 番目の山から金貨を 4 枚取る。
- タドちゃんが 1 番目の山から金貨を 3 枚取る。
- 全ての山の金貨が 0 枚になったのでゲームを終了する。
両者とも入手したコインの枚数の合計は 4 枚ですが、最後に金貨を入手したのはタドちゃんなのでタドちゃんの勝ちとなります。
なお、この例において両者が最適な行動をとっているとは限りません。
入力例2
出力例2
タドちゃんは初手で金貨を全て入手出来るので、タドちゃんが勝ちます。