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 = union { teban : I64, split : I64, choice : (I64, I64) }; impl State : Hash { hash : Main::State -> Std::U64 = |state| ( match state { teban(n) => ( combine_hash(0.u64, n.hash) ), split(n) => ( combine_hash(1.u64, n.hash) ), choice((n, m)) => ( combine_hash(n.u64, m.u64).combine_hash(2.u64) ) } ); } impl State : Eq { eq : Main::State -> Main::State -> Std::Bool = |lhs, rhs| ( match lhs { teban(n) => ( rhs.is_teban && n == rhs.as_teban ), split(n) => ( rhs.is_split && n == rhs.as_split ), choice((n, m)) => ( rhs.is_choice && (n, m) == rhs.as_choice ) } ); } transit : State -> Array State = |s| ( match s { teban(n) => ( if n == 1 { [] }; [split(n)] ), split(n) => ( range(1, n/2+1).fold([], |m, states| let s = choice((m, n-m)); states.push_back(s) ) ), choice((n, m)) => ( if n == m { [teban(n)] } else { [teban(n), teban(m)] } ), } ); grundy : State -> HashMap State I64 -> (I64, HashMap State I64) = |state, memo| ( match memo.find(state) { some(g) => (g, memo), none() => ( let nexts = transit(state); let (gs, memo) = nexts.to_iter.fold((HashSet::empty(nexts.@size), memo), |next, (gs, memo)| let (g, memo) = grundy(next, memo); let gs = gs.HashSet::insert(g); (gs, memo) ); let mex = count_up(0).filter(|n| !gs.contains(n)).get_first.as_some; let memo = memo.insert(state, mex); (mex, memo) ), } ); main : IO () = ( // let memo = HashMap::empty(1e5); // let memo = *range(1, 51).fold_m(memo, |n, memo| // let (g, memo) = grundy(teban(n), memo); // "g({}) = {}".printfln((n, g));; // memo.pure // ); let grundy : I64 -> I64 = |n| ( let m = n % 5; if m == 2 || m == 3 { 1 } else { 0 } ); let t = *read_i; range(0, t).fold_m((), |_, _| let n = *read_i; let as = *read_is(n); let g = as.to_iter.map(grundy).fold(0, bit_xor); let ans = if g == 0 { "Second" } else { "First" }; // "as = {}, g = {}, ans = {}".eprintfln((as, g, ans));; ans.println );; pure() );