local mfl = math.floor local TranFFT = {} TranFFT.initialize = function(self) self.size = 18 -- 2^18 self.n = 262144 -- 1007681537: prime, -- 1007681537 % 262144 = 1 self.mod = 1007681537 -- (6161^262144) % mod = 1 self.w = 6161 -- (1007677693 * 262144) % mod = 1 self.ninv = 1007677693 -- (534835031 * 6161) % mod = 1 self.winv = 534835031 self.p2 = {1} for i = 2, self.size do self.p2[i] = self.p2[i - 1] * 2 end self.binv = {} for i = 1, self.n do local y, z = 0, i - 1 for j = 1, self.size do y = y + (z % 2) * self.p2[self.size + 1 - j] z = mfl(z / 2) end self.binv[i] = y + 1 end self.wmul = {1} for i = 2, self.n do self.wmul[i] = self:mul(self.wmul[i - 1], self.w) end self.winvmul = {1} for i = 2, self.n do self.winvmul[i] = self:mul(self.winvmul[i - 1], self.winv) end end -- (44893^2) % 1007681537 = 18375 -- 1007681537 = 22446 * 44893 + rem(13259) -- x0, y0 <= 44892 -- x1, y1 <= 22446 -- max(x1y1*18375+(x1y0+x0y1)*44893+x0y0) < 10^14 TranFFT.mul = function(self, x, y) local x0, y0 = x % 44893, y % 44893 local x1, y1 = mfl(x / 44893), mfl(y / 44893) return (x1 * y1 * 18375 + (x1 * y0 + x0 * y1) * 44893 + x0 * y0) % self.mod end TranFFT.add = function(self, x, y) return (x + y) % self.mod end TranFFT.fft_common = function(self, ary, wmul) local ret = {} for i = 1, self.n do ret[i] = ary[self.binv[i]] end for i = 1, self.size do local step_size = self.p2[i] local step_count = self.p2[self.size + 1 - i] for istep = 1, step_count do local ofst = (istep - 1) * step_size * 2 for j = 1, step_size do local a1, a2 = ret[ofst + j], ret[ofst + step_size + j] ret[ofst + j] = self:add(a1, self:mul(a2, wmul[1 + (j - 1) * step_count])) ret[ofst + step_size + j] = self:add(a1, self:mul(a2, wmul[1 + (j + step_size - 1) * step_count])) end end end return ret end TranFFT.fft = function(self, ary) return self:fft_common(ary, self.wmul) end TranFFT.ifft = function(self, ary) local ret = self:fft_common(ary, self.winvmul) for i = 1, self.n do ret[i] = self:mul(ret[i], self.ninv) end return ret end TranFFT:initialize() local a, b = {}, {} for i = 1, TranFFT.n do a[i] = 0 b[i] = 0 end local x, y, n = io.read("*n", "*n", "*n") for i = 1, x do local tmp = io.read("*n") a[tmp] = 1 end for i = 1, y do local tmp = io.read("*n") b[100001 - tmp] = 1 end local q = io.read("*n") local at = TranFFT:fft(a) local bt = TranFFT:fft(b) for i = 1, TranFFT.n do at[i] = TranFFT:mul(at[i], bt[i]) end local c = TranFFT:ifft(at) for i = 0, q - 1 do print(c[100000 + i]) end