#P18251. General Symmetry

General Symmetry

General Symmetry

给定一个由 mm 个整数组成的序列 S=[s1,s2,…,sm]S=[s_1,s_2,\ldots,s_m]。当且仅当对于所有 1≤i≤m1\le i\le m 都有

∣si−sm−i+1∣≤k,|s_i-s_{m-i+1}|\le k,

称 SS 为 kk 对称序列。

现在给你一个长度为 nn 的序列 A=[a1,a2,…,an]A=[a_1,a_2,\ldots,a_n]。对于每一个可能的中心,求以这个位置为中心的最长 kk 对称连续子段的长度。

这里,连续子段 [l,r][l,r] 的中心是 l+r2\frac{l+r}{2};中心既可以是整数,也可以是相邻两个整数的中点。

输入格式

第一行包含两个整数 n,kn,k,分别表示序列长度及参数 kk。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

第一行输出 nn 个整数,第 ii 个数表示以 ii 为中心的最长 kk 对称连续子段的长度。

第二行输出 n−1n-1 个整数,第 ii 个数表示以 i+0.5i+0.5 为中心的最长 kk 对称连续子段的长度。

若某个中心不存在满足条件的连续子段,则在相应位置输出 00。输出的是子段长度,而不是向一侧扩展的半径。

数据范围

  • 2≤n≤2×1052\le n\le 2\times10^5;
  • 0≤k≤1030\le k\le 10^3;
  • 1≤ai≤1031\le a_i\le 10^3。

输入只有一组数据。

样例 1

5 0
1 2 1 2 1
1 3 5 3 1
0 0 0 0

样例 2

5 1
1 2 1 3 1
1 3 5 3 1
2 2 0 0