##################################################################################################### ##### 畳み込み ##################################################################################################### """ O(N log N) """ def gcd_inv(a, b): a %= b if a == 0: return b, 0 s = b t = a m0 = 0 m1 = 1 while t: u = s // t s -= t * u m0 -= m1 * u s, t = t, s m0, m1 = m1, m0 if m0 < 0: m0 += b // s return s, m0 def crt(Rs,MODs): """ Find solution s.t. x = R1 (MOD1) x = R2 (MOD2) x = R3 (MOD3) . . up to MOD=MOD1*MOD2*MOD3*.... """ assert len(Rs)==len(MODs) n = len(Rs) r0 = 0 m0 = 1 for i in range(n): assert 1<=MODs[i] r1 =Rs[i]%MODs[i] m1 = MODs[i] if m0 < m1: r0, r1 = r1, r0 m0, m1 = m1, m0 if m0 % m1 == 0: if r0 % m1 != r1: return 0, 0 continue g, im = gcd_inv(m0, m1) u1 = m1 // g if (r1 - r0) % g: return 0, 0 x = (r1 - r0) // g * im % u1 r0 += x * m0 m0 *= u1 if (r0 < 0): r0 += m0 return r0, m0 def ntt(A, n): for i in range(n): m = 1<<(n-i-1) for s in range(1<>i, mod) for i in range(24)] inv_roots = [pow(root, mod-2, mod) for root in roots] B=[1]+[0]*L CNT=[] for i in range(N)[::-1]: A=[1]*(C[i]+1) B = convolution(B, A) B = B[:L+1] CNT.append(B[::]) CNT=CNT[:-1] CNT.reverse() S=[[0]*(L+2) for _ in range(N-1)] for k in range(N-1): for i in range(L+1): # 自由パラメタの個数 S[k][i+1]+=S[k][i]+CNT[k][i] tmp.append(S) S=[[0]*(L+2) for _ in range(N-1)] for k in range(N-1): for i in range(L+2): S[k][i]=crt((tmp[0][k][i],tmp[1][k][i],tmp[2][k][i]),MODs)[0] Q=int(input()) for _ in range(Q): k=int(input()) res=[] l=L for p in range(N-1): i=bisect_left(S[p],k+S[p][max(l-C[p],0)])-1 # 自由パラメタ i個からi+1個のどこか k-=S[p][i]-S[p][max(l-C[p],0)] # print(i,k,l-i) res.append(l-i) l=i res.append(l) for i in range(N): if res[i]<0: print(-1) break else: print(*res)