设 $S = [s_1, s_2, \dots, s_m]$ 为一个包含 $m$ 个整数的序列。当且仅当对于所有整数 $i$ ($1 \le i \le m$)，满足 $|s_i - s_{m-i+1}| \le k$ 时，称序列 $S$ 为 $k$-对称序列。

给定一个长度为 $n$ 的序列 $A = [a_1, a_2, \dots, a_n]$。你的任务是求出以每个位置为中心的最长 $k$-对称连续子序列的长度。假设对应的连续子序列的下标范围为 $[l, r]$，则其中心为 $\frac{l+r}{2}$。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($2 \le n \le 2 \times 10^5$, $0 \le k \le 10^3$)，分别表示序列 $A$ 的长度和参数 $k$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^3$)，表示序列 $A$。

输出格式

第一行输出 $n$ 个整数，第 $i$ 个整数 ($1 \le i \le n$) 表示以 $i$ 为中心的最长 $k$-对称连续子序列的长度。

第二行输出 $n-1$ 个整数，第 $i$ 个整数 ($1 \le i < n$) 表示以 $(i + 0.5)$ 为中心的最长 $k$-对称连续子序列的长度。

注意，如果对于某个固定的中心找不到符合条件的子序列，请输出 “0”。

样例

样例输入 1

5 0
1 2 1 2 1

样例输出 1

1 3 5 3 1
0 0 0 0

样例输入 2

5 1
1 2 1 3 1

样例输出 2

1 3 5 3 1
2 2 0 0