module Main; import CPLib.IO; import Hash::{combine_hash, Hash, Hash::hash}; import HashMap; // import BinaryHeap; // import BoolArray; // import CPLib.Arithmetic; // import CPLib.Bipartite; // import CPLib.Bits; // import CPLib.Convolution; // import CPLib.DSegtree; // import CPLib.Graph; // import CPLib.LDSegtree; // import CPLib.LSegtree; // import CPLib.MaxFlow; // import CPLib.Memoize; // import CPLib.MinCostFlow; // import CPLib.Misc; // import CPLib.Monoid; // import CPLib.Segtree; // import CPLib.String; // import CPLib.Trait; // import CPLib.TwoSat; // import CPLib.UnionFind; // import CPLib.ZP; import HashSet; type State = struct { teban : I64, }; impl State : Hash { hash : Main::State -> Std::U64 = |state| ( state.@teban.hash ); } impl State : Eq { eq : Main::State -> Main::State -> Std::Bool = |lhs, rhs| ( lhs.@teban == rhs.@teban ); } // move : State -> Array State = |s| ( // let n = s.@teban; // if n == 1 { [] }; // let gs = range(1, n/2+1).fold([], |m, gs| // // ); // ); grundy : I64 -> HashMap I64 I64 -> (I64, HashMap I64 I64) = |n, memo| ( match memo.find(n) { some(g) => (g, memo), none() => ( if n == 1 { (0, memo) }; let (gss, memo) = range(1, n/2+1).fold(([], memo), |m, (gss, memo)| let a = m; let b = n - m; let gs = HashSet::empty(2); let (ga, memo) = grundy(a, memo); let (gb, memo) = grundy(b, memo); let gs = gs.HashSet::insert(ga).HashSet::insert(gb); let gss = gss.push_back(gs); (gss, memo) ); let mex = count_up(0).filter(|g| gss.to_iter.check_any(|gs| !gs.contains(g)) ).get_first.as_some; let memo = memo.insert(n, mex); (mex, memo) ), } ); main : IO () = ( let calc_g : I64 -> I64 = |n| ( if n == 2 { 1 }; if n == 3 { 2 }; if n <= 6 { 0 }; let m = n % 5; if m == 2 { 1 }; if m == 3 { 1 }; 0 ); // let memo = HashMap::empty(1e5); // let memo = *range(1, 1e2+1).fold_m(memo, |n, memo| // let (g, memo) = grundy(n, memo); // // "g({}) = {}".eprintfln((n, g,));; // assert_eq(|_|"g != calc_g", g, calc_g(n));; // memo.pure // ); let t = *read_i; range(0, t).fold_m((), |_, _| let n = *read_i; let as = *read_is(n); let g = as.to_iter.map(calc_g).fold(0, bit_xor); let ans = if g != 0 { "First" } else { "Second" }; ans.println );; pure() );