module Main; // import BinaryHeap; // import BoolArray; import CPLib.Arithmetic; // import CPLib.Bipartite; // import CPLib.Bits; // import CPLib.Convolution; // import CPLib.DSegtree; // import CPLib.Graph; import CPLib.IO; // 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 HashMap; // import HashSet; facts_to_divisors_rec : Array (I64, I64) -> I64 -> Array I64 -> Array I64 = |facts, acm, divs| ( if facts.is_empty { divs.push_back(acm) }; let (p, e) = facts.@(facts.@size - 1); let facts = facts.pop_back; range(0, e+1).fold((acm, divs), |n, (acm, divs)| let divs = facts_to_divisors_rec(facts, acm, divs); let acm = acm * p; (acm, divs) ).@1 ); facts_to_divisors : Array (I64, I64) -> Array I64 = |facts| ( facts_to_divisors_rec(facts, 1, []) ); main : IO () = ( let n = *read_i; let m = *read_i; let k = *read_i; let op = *read_c; let bs = *read_is(m); let as = *read_is(n); let as = as.map(|x| x % k); let bs = bs.map(|x| x % k); let b_cnt = range(0, m).fold(HashMap::empty(m), |i, mp| let b = bs.@(i); match mp.find(b) { none() => mp.insert(b, 1), some(n) => mp.insert(b, n+1) } ); let ans = if op == '+' { range(0, n).map(|ai| let a = as.@(ai); let b = (k - a) % k; b_cnt.find_or(b, 0) ).sum } else { let rank : I64 -> I64 -> I64 = |p, n| ( if n == 0 { I64::maximum }; loop((n, 0), |(n, rk)| if n % p != 0 { rk.break }; let n = n / p; let rk = rk + 1; (n, rk).continue ) ); let ps = factorize(k); let div_cnt = range(0, m).fold(HashMap::empty(n), |bi, div_cnt| let b = bs.@(bi); let b_rks = ps.to_iter.map(|(p, e)| let rk = rank(p, b).min(e.i64); (p, rk)).to_array; let divs = facts_to_divisors(b_rks); divs.to_iter.fold(div_cnt, |d, div_cnt| match div_cnt.find(d) { none() => div_cnt.insert(d, 1), some(n) => div_cnt.insert(d, n+1) } ) ); as.to_iter.map(|a| let k = k / calc_gcd(k, a); div_cnt.find_or(k, 0) ).sum }; ans.to_string.println );