#YZ0002. 圣晶石之争

圣晶石之争

圣晶石之争

题目描述

"要开始争夺圣晶石了哦!" —— 某位蓝发使魔

圣杯深处沉睡着 nn 颗圣晶石。alice和bob都想把圣晶石据为己有,于是两人约定轮流从圣杯中取走圣晶石。圣杯的封印只回应 22 的幂:每回合,轮到的人必须从圣杯中取走恰好 2k2^k 颗圣晶石(kk 为非负整数,即 1,2,4,8,…1,2,4,8,\dots),不能不取,也不能取超过当前剩余数量的圣晶石。取走最后一颗圣晶石的人获胜。

假设alice和bob都绝顶聪明,每一步都采取对自己最有利的策略。alice先手。请你判断:本局是alice(先手)必胜,还是bob(后手)必胜?

注意:如果圣杯里一开始就没有圣晶石(n=0n=0),alice无法进行任何操作,直接判负。

输入格式

一行一个整数 nn,表示圣晶石的数量。 0≤n≤10180 \le n \le 10^{18}。

输出格式

一行一个字符串:若alice(先手)必胜,输出 First;否则输出 Second。

样例 1

1
First

样例 1 解释:alice取走 11 颗,取走最后一颗,获胜。

样例 2

3
Second

样例 2 解释:alice只能取 11 颗或 22 颗。

  • 若bob取 11 颗,剩下 22 颗,bob取 22 颗取完;
  • 若bob取 22 颗,剩下 11 颗,bob取 11 颗取完。

因此alice无论怎么取都无法获胜。

样例 3

0
Second

样例 3 解释:圣杯一开始就是空的。alice没有任何合法的取法,直接判负。

提示

数据范围

  • 0≤n≤10180 \le n \le 10^{18}。

请注意 nn 的规模:直接开一个大小为 nn 的数组递推会超出内存;可以从 nn 较小时的情况入手。