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 : Array I64, split : (Array I64, I64), choice : (Array I64, 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((ns, n, m)) => ( combine_hash(2.u64, (ns, (n, m)).hash) ) } ); } impl State : Eq { eq : Main::State -> Main::State -> Std::Bool = |lhs, rhs| ( match lhs { teban(x) => ( rhs.is_teban && x == rhs.as_teban ), split(x) => ( rhs.is_split && x == rhs.as_split ), choice(x) => ( rhs.is_choice && x == rhs.as_choice ) } ); } remove : I64 -> Array a -> Array a = |i, xs| ( xs.get_sub(0, i) + xs.get_sub(i+1, xs.@size) ); move : State -> Array State = |s| ( match s { teban(ns) => ( range(0, ns.@size).map(|i| let n = ns[i].iget; let ns = ns.remove(i); State::split((ns, n)) ).to_array ), split((ns, n)) => ( range(1, n/2+1).fold([], |m, states| let s = choice((ns, m, n-m)); states.push_back(s) ) ), choice((ns, n, m)) => ( let insert = |n, ns : Array _| ( if n == 1 { ns }; ns.push_back(n).sort ); if n == m { [teban(ns.insert(n))] } else { [teban(ns.insert(n)), teban(ns.insert(m))] } ), } ); // grundy : State -> HashMap State I64 -> (I64, HashMap State I64) = |state, memo| ( // match memo.find(state) { // some(g) => (g, memo), // none() => ( // let nexts = state.move; // 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) // ), // } // ); wins : State -> HashMap State Bool -> (Bool, HashMap State Bool) = |state, memo| ( match memo.find(state) { some(g) => (g, memo), none() => ( let nexts = state.move; let (any_loose, memo) = nexts.to_iter.loop_iter((false, memo), |next, (any_loose, memo)| let (wins, memo) = wins(next, memo); let any_loose = any_loose || !wins; if any_loose { (true, memo).break }; (any_loose, memo).continue ); let wins = any_loose; let memo = memo.insert(state, wins); (wins, memo) ), } ); main : IO () = ( // let calc_g : I64 -> I64 = |n| ( // let m = n % 5; // if m == 2 { 1 }; // if m == 3 { 2 }; // 0 // ); // let memo = *range(1, 3e1+1).fold_m(memo, |n, memo| // let memo = *range(1, 3e1+1).fold_m(memo, |m, memo| // let (g, memo) = grundy(teban([3, n, m]), memo); // // "g([{}, {}]) = {}, ".eprintf((n.right_aligned_to(2), m.right_aligned_to(2), g));; // "{}, ".eprintf((if g == 0 { "S" } else { " " }, ));; // memo.pure // ); // "".eprintfln(());; // memo.pure // ); let t = *read_i; let memo = HashMap::empty(1e5); range(0, t).fold_m(memo, |_, memo| let n = *read_i; let as = *read_is(n); let as = as.to_iter.map(|n| if n >= 4 { (n-4) % 5 + 4 } else { n } ).filter(|n| n != 1).to_array; let (wins, memo) = wins(teban(as), memo); let ans = if wins { "First" } else { "Second" }; ans.println;; memo.pure );; pure() );