Problem Statement

You are given positive integers $N$ and $L$, and a sequence of positive integers $A = (A_{1}, A_{2}, \dots , A_{N})$ of length $N$.

For each $i = 1, 2, \dots , N$, answer the following question:

Determine if there exists a sequence of $L$ non-negative integers $B = (B_{1}, B_{2}, \dots, B_{L})$ such that $\displaystyle \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = A_{i}$. If it exists, find the minimum value of $\max(B)$ for such a sequence $B$.

Constraints

• $1 \leq N \leq 2 \times 10^{5}$
• $2 \leq L \leq 2 \times 10^{5}$
• $1 \leq A_{i} \leq 2 \times 10^{5}$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N L
A_{1} A_{2} \cdots A_{N}

Output

Print $N$ lines. The $k$-th line should contain -1 if no sequence $B$ satisfies the condition for $i=k$; otherwise, it should contain the minimum value of $\max(B)$ for such a sequence $B$.