The median of a sequence is the element in the middle of the sequence after it is sorted. For a sequence with even size, the median is the average of the two middle elements of the sequence after sorting. For example, for a sequence $A = [1, 3, 3, 5, 4, 7, 11]$, the median is equal to $4$, and for $A = [2, 3, 4, 5]$, the median is equal to $(3+4)/2 = 3.5$.
Fulu is a famous programmer in his country. He wrote the following program (given in pseudocode) for finding the median in a sequence $A$ with length $N$:
read(N)
read(A[0], A[1], ..., A[N-1])
sort(A)
# simultaneously remove elements A[K] and A[N mod K] from the array A
# the order of the remaining N-2 elements is unchanged
remove(A[K], A[N mod K])
return A[(N-2)/2] # integer division
The program takes an integer $K$ as a parameter. Fulu can choose this integer arbitrarily between $1$ and $N-1$ inclusive.
Little Lima, Fulu's friend, thinks Fulu's program is wrong (as always). As finding one counterexample would be an easy task for Lima (he has already found the sequence $A = [34, 23, 35, 514]$, which is a counterexample for any $K \le 3$), Lima decided to make hacking more interesting. Fulu should give him four parameters $S, K, m, M$ (in addition to $N$) and Lima should find the lexicographically smallest proper sequence $A$ with length $N$ as a counterexample.
We say that a sequence $A$ with length $N$ ($0$-indexed) is proper if it satisfies the following conditions:
- it contains only positive integers
- $A_0 + A_1 +A_2 + \dots + A_{N-1} = S$
- $m \le A_i \le M$ for each $0 \le i < N$
- the number returned by Fulu's program, ran with the given parameter $K$, is different from the correct median of the sequence $A$
Can you help Lima find the lexicographically smallest counterexample or determine that Fulu's program works perfectly for the given parameters?
-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains five space-separated integers $N$, $S$, $K$, $m$ and $M$.
-----Output-----
For each test case, if there is no proper sequence, print a single line containing the integer $-1$; otherwise, print a single line containing $N$ space-separated integers — the lexicographically smallest proper sequence.
-----Constraints-----
- $1 \le T \le 8$
- $3 \le N \le 10^5$
- $1 \le K \le N-1$
- $1 \le S \le 10^9$
- $1 \le m \le M \le S$
-----Example Input-----
2
3 6 1 1 5
4 4 2 1 3
-----Example Output-----
1 1 4
-1
-----Explanation-----
Example case 1: For the sequence $A = [1, 1, 4]$, it is already sorted, so the program would just remove the first two elements ($K=1$, $N\%K=0$) and return the only remaining element $4$. Obviously, the median of the original sequence is $1$. It can be shown that there is no lexicographically smaller proper sequence.
Example case 2: The only possible sequence is $A = [1, 1, 1, 1]$, which is not proper, since Fulu's program will give the correct answer $1$ for it.
# cook your dish here
import numpy as np
import sys

def findSeq(n, s, k, m, M):
    midInd = n // 2
    seqs = []
    for ind in range(midInd + 2, midInd - 3, -1):
        if ind >= n or ind < 0:
            continue     
        seq = genBestSeq(n, ind, m, M, s)
        if seq is not -1 and testSeq(k, seq):
            seqs.append(list(seq))
    if len(seqs) == 0:
        return -1
    return min(seqs)

#def findSeq(n, s, k, m, M):
#    midInd = n // 2
#    if k <= midInd: #and (n % 2 == 1 or s < m * midInd + M * (n - midInd)):
#        return genBestSeq(n, midInd + 1, m, M, s) 
#    elif k > midInd + 1 and n % 2 == 1:
#        return -1
#    return genBestSeq(n, midInd, m, M, s)

def genBestSeq(n, diffInd, m, M, s):
    #inc = M - m - 1
    arr = np.full((n,), m)
    arr[diffInd:] += 1
    #remainder = s - np.sum(arr)
    #if remainder < 0:
    #    return -1

    #nFull, remainder = divmod(remainder, inc)
    #if nFull > n or (nFull == n and remainder > 0):
    #    return -1

    #addingInd = n - nFull -1
    #arr[addingInd + 1:] += inc
    #arr[addingInd] += remainder
    #return arr
    s = s - np.sum(arr)
    if s < 0:
        return -1
    inc = M - m - 1
    ind = n - 1
    while (ind >= 0):
        z = min(inc, s)
        arr[ind] += z
        s -= z
        ind -= 1
    if s != 0:
        return -1
    return arr

def testSeq(k, seq):
    seq = sorted(seq)
    n = len(seq)
    if n % 2 == 1:
        median = seq[n // 2]
    else:
        median = (seq[n // 2 - 1] + seq[n // 2]) / 2
    seq.pop(n % k)
    seq.pop(k - 1)
    return (median != seq[(n - 2) // 2]) 
    

def __starting_point():
    nCases = int(input())
    answers = []
    #ks = []
    for i in range(nCases):
        #nums = [int(val) for val in input().split()]
        #ks.append(nums[2])
        #answers.append(findSeq(*nums))
        answers.append(findSeq(*(int(val) for val in input().split())))
        ans = answers[-1]
        if not isinstance(ans, int):
            print(*ans, sep=' ')
        else:
            print(ans)
    #for i, ans in enumerate(answers):

    #for ans in answers:
    #    if isinstance(ans, np.ndarray):
    #        print(*ans, sep=' ')
    #    else:
    #        print(ans)

__starting_point()
# cook your dish here
import numpy as np
import sys

def findSeq(n, s, k, m, M):
    midInd = n // 2
    seqs = []
    for ind in range(midInd + 2, midInd - 3, -1):
        if ind >= n or ind < 0:
            continue     
        seq = genBestSeq(n, ind, m, M, s)
        if seq is not -1 and testSeq(k, seq):
            seqs.append(list(seq))
    if len(seqs) == 0:
        return -1
    return min(seqs)

#def findSeq(n, s, k, m, M):
#    midInd = n // 2
#    if k <= midInd: #and (n % 2 == 1 or s < m * midInd + M * (n - midInd)):
#        return genBestSeq(n, midInd + 1, m, M, s) 
#    elif k > midInd + 1 and n % 2 == 1:
#        return -1
#    return genBestSeq(n, midInd, m, M, s)

def genBestSeq(n, diffInd, m, M, s):
    #inc = M - m - 1
    arr = np.full((n,), m)
    arr[diffInd:] += 1
    #remainder = s - np.sum(arr)
    #if remainder < 0:
    #    return -1

    #nFull, remainder = divmod(remainder, inc)
    #if nFull > n or (nFull == n and remainder > 0):
    #    return -1

    #addingInd = n - nFull -1
    #arr[addingInd + 1:] += inc
    #arr[addingInd] += remainder
    #return arr
    s = s - np.sum(arr)
    if s < 0:
        return -1
    inc = M - m - 1
    ind = n - 1
    while (ind >= 0):
        z = min(inc, s)
        arr[ind] += z
        s -= z
        ind -= 1
    if s != 0:
        return -1
    return arr

def testSeq(k, seq):
    seq = sorted(seq)
    n = len(seq)
    if n % 2 == 1:
        median = seq[n // 2]
    else:
        median = (seq[n // 2 - 1] + seq[n // 2]) / 2
    seq.pop(n % k)
    seq.pop(k - 1)
    return (median != seq[(n - 2) // 2]) 
    

def __starting_point():
    nCases = int(input())
    answers = []
    #ks = []
    for i in range(nCases):
        #nums = [int(val) for val in input().split()]
        #ks.append(nums[2])
        #answers.append(findSeq(*nums))
        answers.append(findSeq(*(int(val) for val in input().split())))
        ans = answers[-1]
        if not isinstance(ans, int):
            print(*ans, sep=' ')
        else:
            print(ans)
    #for i, ans in enumerate(answers):

    #for ans in answers:
    #    if isinstance(ans, np.ndarray):
    #        print(*ans, sep=' ')
    #    else:
    #        print(ans)

__starting_point()