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)); } uint xrand() { static uint x = 314159265, y = 358979323, z = 846264338, w = 327950288; uint t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8; } enum N = 30; enum EPS = 1e-10L; enum MIN_P = 8000.0L; enum LIM_E = cast(int)(floor((MIN_P / (N - 1))^^2)); enum M = 5 * 10^^5; void main() { alias Entry = Tuple!(real, "r", int[], "es"); auto ps = new Entry[M]; auto qs = new Entry[M]; foreach (i; 0 .. M) { ps[i].r = 0.0L; ps[i].es = new int[N / 2 - 1]; foreach (k; 0 .. N / 2 - 1) { const e = cast(int)(xrand() % (LIM_E + 1)); ps[i].r += sqrt(cast(real)(e)); ps[i].es[k] = e; } ps[i].r -= floor(ps[i].r); } foreach (i; 0 .. M) { qs[i].r = 0.0L; qs[i].es = new int[N - N / 2]; foreach (k; 0 .. N - N / 2) { const e = cast(int)(xrand() % (LIM_E + 1)); qs[i].r += sqrt(cast(real)(e)); qs[i].es[k] = e; } qs[i].r -= floor(qs[i].r); } ps.sort; qs.sort; try { for (; ; ) { const numCases = readInt(); foreach (caseId; 0 .. numCases) { const P = readReal(); foreach (i; 0 .. M) { real r = P - EPS - ps[i].r; r -= floor(r); const j = qs.lowerBound(Entry(r, null)); if (j < M && qs[j].r <= r + EPS) { auto ans = [0] ~ ps[i].es ~ qs[j].es; real p = P; foreach (k; 1 .. N) { p -= sqrt(cast(real)(ans[k])); } ans[0] = (cast(int)(p + 0.5L))^^2; write(N); foreach (k; 0 .. N) { write(" ", ans[k]); } writeln(); debug { real sum = 0.0L; foreach (k; 0 .. N) { sum += sqrt(cast(real)(ans[k])); } writefln("%.15f %.15f", sum, sum - P); } goto found; } } assert(false, format("FAIL: P = %.15f", P)); found: } } } catch (EOFException e) { } }