import std.conv, std.functional, std.range, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; } int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); } int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); } // a^-1 (mod m) long modInv(long a, long m) in { assert(m > 0, "modInv: m > 0 must hold"); } do { long b = m, x = 1, y = 0, t; for (; ; ) { t = a / b; a -= t * b; if (a == 0) { assert(b == 1 || b == -1, "modInv: gcd(a, m) != 1"); if (b == -1) y = -y; return (y < 0) ? (y + m) : y; } x -= t * y; t = b / a; b -= t * a; if (b == 0) { assert(a == 1 || a == -1, "modInv: gcd(a, m) != 1"); if (a == -1) x = -x; return (x < 0) ? (x + m) : x; } y -= t * x; } } // M: prime, G: primitive root class Fft(int M_, int G, int K) { import std.algorithm : reverse; import std.traits : isIntegral; alias M = M_; // 1, 1/4, 1/8, 3/8, 1/16, 5/16, 3/16, 7/16, ... int[] gs; this() { static assert(2 <= K && K <= 30, "Fft: 2 <= K <= 30 must hold"); static assert(!((M - 1) & ((1 << K) - 1)), "Fft: 2^K | M - 1 must hold"); gs = new int[1 << (K - 1)]; gs[0] = 1; long g2 = G, gg = 1; for (int e = (M - 1) >> K; e; e >>= 1) { if (e & 1) gg = (gg * g2) % M; g2 = (g2 * g2) % M; } gs[1 << (K - 2)] = cast(int)(gg); for (int l = 1 << (K - 2); l >= 2; l >>= 1) { gs[l >> 1] = cast(int)((cast(long)(gs[l]) * gs[l]) % M); } assert((cast(long)(gs[1]) * gs[1]) % M == M - 1, "Fft: g^(2^(K-1)) == -1 (mod M) must hold"); for (int l = 2; l <= 1 << (K - 2); l <<= 1) { foreach (i; 1 .. l) { gs[l + i] = cast(int)((cast(long)(gs[l]) * gs[i]) % M); } } } void fft(int[] xs) const { const n = cast(int)(xs.length); assert(!(n & (n - 1)), "Fft.fft: |xs| must be a power of two"); assert(n <= 1 << K, "Fft.fft: |xs| <= 2^K must hold"); for (int l = n; l >>= 1; ) { foreach (i; 0 .. (n >> 1) / l) { const(long) g = gs[i]; foreach (j; (i << 1) * l .. (i << 1 | 1) * l) { const t = cast(int)((g * xs[j + l]) % M); if ((xs[j + l] = xs[j] - t) < 0) xs[j + l] += M; if ((xs[j] += t) >= M) xs[j] -= M; } } } } void invFft(int[] xs) const { const n = cast(int)(xs.length); assert(!(n & (n - 1)), "Fft.invFft: |xs| must be a power of two"); assert(n <= 1 << K, "Fft.invFft: |xs| <= 2^K must hold"); for (int l = 1; l < n; l <<= 1) reverse(xs[l .. l << 1]); for (int l = 1; l < n; l <<= 1) { foreach (i; 0 .. (n >> 1) / l) { const(long) g = gs[i]; foreach (j; (i << 1) * l .. (i << 1 | 1) * l) { int t = cast(int)((g * (xs[j] - xs[j + l])) % M); if (t < 0) t += M; if ((xs[j] += xs[j + l]) >= M) xs[j] -= M; xs[j + l] = t; } } } } T[] convolute(T)(inout(T)[] as, inout(T)[] bs) const if (isIntegral!T) { const na = cast(int)(as.length), nb = cast(int)(bs.length); int n, invN = 1; for (n = 1; n < na + nb - 1; n <<= 1) { invN = ((invN & 1) ? (invN + M) : invN) >> 1; } auto xs = new int[n], ys = new int[n]; foreach (i; 0 .. na) if ((xs[i] = cast(int)(as[i] % M)) < 0) xs[i] += M; foreach (i; 0 .. nb) if ((ys[i] = cast(int)(bs[i] % M)) < 0) ys[i] += M; fft(xs); fft(ys); foreach (i; 0 .. n) { xs[i] = cast(int)((((cast(long)(xs[i]) * ys[i]) % M) * invN) % M); } invFft(xs); auto cs = new T[na + nb - 1]; foreach (i; 0 .. na + nb - 1) cs[i] = cast(T)(xs[i]); return cs; } /* ModInt!M[] convolute(inout(ModInt!M)[] as, inout(ModInt!M)[] bs) const { const na = cast(int)(as.length), nb = cast(int)(bs.length); int n, invN = 1; for (n = 1; n < na + nb - 1; n <<= 1) { invN = ((invN & 1) ? (invN + M) : invN) >> 1; } auto xs = new int[n], ys = new int[n]; foreach (i; 0 .. na) xs[i] = as[i].x; foreach (i; 0 .. nb) ys[i] = bs[i].x; fft(xs); fft(ys); foreach (i; 0 .. n) { xs[i] = cast(int)((((cast(long)(xs[i]) * ys[i]) % M) * invN) % M); } invFft(xs); auto cs = new ModInt!M[na + nb - 1]; foreach (i; 0 .. na + nb - 1) cs[i].x = xs[i]; return cs; } int[] convolute(int M1)(inout(ModInt!M1)[] as, inout(ModInt!M1)[] bs) const if (M != M1) { const na = cast(int)(as.length), nb = cast(int)(bs.length); int n, invN = 1; for (n = 1; n < na + nb - 1; n <<= 1) { invN = ((invN & 1) ? (invN + M) : invN) >> 1; } auto xs = new int[n], ys = new int[n]; foreach (i; 0 .. na) xs[i] = as[i].x; foreach (i; 0 .. nb) ys[i] = bs[i].x; fft(xs); fft(ys); foreach (i; 0 .. n) { xs[i] = cast(int)((((cast(long)(xs[i]) * ys[i]) % M) * invN) % M); } invFft(xs); return xs[0 .. na + nb - 1]; } */ } alias Fft0 = Fft!(998244353, 3, 20); // Fft3_0.M Fft3_1.M Fft3_2.M > 1.15 * 10^27, > 2^89.9 //* enum FFT_K = 20; alias Fft3_0 = Fft!(1045430273, 3, FFT_K); // 2^20 997 + 1 alias Fft3_1 = Fft!(1051721729, 6, FFT_K); // 2^20 1003 + 1 alias Fft3_2 = Fft!(1053818881, 7, FFT_K); // 2^20 1005 + 1 //*/ // Fft3_0.M Fft3_1.M Fft3_2.M > 5.95 * 10^25, > 2^85.6 /* enum FFT_K = 24; alias Fft3_0 = Fft!(167772161, 3, FFT_K); // 2^25 5 + 1 alias Fft3_1 = Fft!(469762049, 3, FFT_K); // 2^26 7 + 1 alias Fft3_2 = Fft!(754974721, 11, FFT_K); // 2^24 45 + 1 //*/ enum long FFT_INV01 = modInv(Fft3_0.M, Fft3_1.M); enum long FFT_INV012 = modInv(cast(long)(Fft3_0.M) * Fft3_1.M, Fft3_2.M); Fft3_0 FFT3_0; Fft3_1 FFT3_1; Fft3_2 FFT3_2; void initFft3() { FFT3_0 = new Fft3_0; FFT3_1 = new Fft3_1; FFT3_2 = new Fft3_2; } // for negative result, if (!(0 <= c && c < )) add MMM: // enum MMM = 1L * Fft3_0.M * Fft3_1.M * Fft3_2.M; long[] convolute(inout(long)[] as, inout(long)[] bs) { const cs0 = FFT3_0.convolute(as, bs); const cs1 = FFT3_1.convolute(as, bs); const cs2 = FFT3_2.convolute(as, bs); auto cs = new long[cs0.length]; foreach (i; 0 .. cs0.length) { long d0 = cs0[i] % Fft3_0.M; long d1 = (FFT_INV01 * (cs1[i] - d0)) % Fft3_1.M; if (d1 < 0) d1 += Fft3_1.M; long d2 = (FFT_INV012 * ((cs2[i] - d0 - Fft3_0.M * d1) % Fft3_2.M)) % Fft3_2.M; if (d2 < 0) d2 += Fft3_2.M; cs[i] = d0 + Fft3_0.M * d1 + (cast(long)(Fft3_0.M) * Fft3_1.M) * d2; } return cs; } void main() { initFft3; try { for (; ; ) { auto N = new int[4]; foreach (h; 0 .. 4) { N[h] = readInt(); } const S = readLong(); auto A = new long[][4]; foreach (h; 0 .. 4) { A[h] = new long[N[h]]; foreach (i; 0 .. N[h]) { A[h][i] = readLong(); } } alias Entry = Tuple!(long, "val", int, "i", int, "j"); Entry[] fs, gs; foreach (i; 0 .. N[0]) foreach (j; 0 .. N[1]) { fs ~= Entry(A[0][i] * A[1][j], i, j); } foreach (i; 0 .. N[2]) foreach (j; 0 .. N[3]) { gs ~= Entry(A[2][i] * A[3][j], i, j); } fs.sort; gs.sort; const fsLen = cast(int)(fs.length); const gsLen = cast(int)(gs.length); const int lbF = fs.lowerBound(Entry(0, int.min, int.min)); const int ubF = fs.upperBound(Entry(0, int.max, int.max)); const int lbG = gs.lowerBound(Entry(0, int.min, int.min)); const int ubG = gs.upperBound(Entry(0, int.max, int.max)); // <= t long calc(long t) { long ret; if (0 <= t) { ret += 1L * (ubF - lbF) * (gsLen - 0); ret += 1L * (fsLen - 0) * (ubG - lbG); ret -= 1L * (ubF - lbF) * (ubG - lbG); ret += 1L * (lbF - 0) * (gsLen - ubG); ret += 1L * (fsLen - ubF) * (lbG - 0); for (int i = lbF, j = 0; j < lbG; ++j) { for (; i > 0 && fs[i - 1].val * gs[j].val <= t; --i) {} ret += (lbF - i); } for (int i = ubF, j = gsLen; --j >= ubG; ) { for (; i < fsLen && fs[i].val * gs[j].val <= t; ++i) {} ret += (i - ubF); } } else { for (int i = 0, j = ubG; j < gsLen; ++j) { for (; i < lbF && fs[i].val * gs[j].val <= t; ++t) {} ret += (i - 0); } for (int i = fsLen, j = lbG; --j >= 0; ) { for (; i > ubF && fs[i - 1].val * gs[j - 1].val <= t; --i) {} ret += (fsLen - i); } } return ret; } long lo = -10L^^18, hi = +10L^^18; for (; lo + 1 < hi; ) { const mid = (lo + hi) / 2; ((calc(mid) >= S) ? hi : lo) = mid; } writeln(hi); if (hi == 0) { writefln("%s %s %s %s", A[0][fs[lbF].i], A[1][fs[lbF].j], A[2][gs[lbG].i], A[3][gs[lbG].j]); } else { foreach (ref g; gs) { if (g.val != 0 && hi % g.val == 0) { const tar = hi / g.val; const pos = fs.lowerBound(Entry(tar, int.min, int.min)); if (pos < fsLen && fs[pos].val == tar) { writefln("%s %s %s %s", A[0][fs[pos].i], A[1][fs[pos].j], A[2][g.i], A[3][g.j]); break; } } } } } } catch (EOFException e) { } }