問題文
T 個のテストケースが与えられるので、それぞれについて答えてください。
正整数 K と、長さ N の整数列 A=(A1,A2,…,AN) が与えられます。
各 i=1,2,…,N について、以下で定める Li を求めてください。
整数列 B を B=(B1,B2,…,BN−i+1)=(Ai,Ai+1,…,AN) と定義します。
K 個の整数 C1,C2,…,CK を自由に選び、B の各項に対して、次の操作を同時に 1 度だけ行います。
- Bj←Bj+C((j−1) mod K)+1
C1,C2,…,CK を適切に選んで操作を行うことで、操作後の B の先頭 L 項と A の先頭 L 項を一致させることができるような整数 L (0≤L≤N−i+1) の最大値を Li とします。
なお、K 個の整数 C1,C2,…,CK は、i ごとに独立して選ぶことができます。
制約
- 1≤T≤103
- 1≤K≤N≤2×105
- −109≤Ai≤109
- すべてのテストケースにおける N の総和は 2×105 以下
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
各テストケース caset (1≤t≤T) は以下の形式で与えられる。
出力
T 行出力せよ。
t 行目には t 番目のテストケースについて、L1 L2…LN をこの順に空白区切りで出力せよ。
サンプル 1
入力
出力
i=1 の場合、C1=C2=0 を選ぶことで、A と B の先頭 8 項を一致させることができます。よって L1=8 です。
i=2 の場合、C1=−3,C2=1 を選ぶことで、A と B の先頭 2 項を一致させることができます。また、先頭 3 項以上を一致させることはできないため、 L2=2 です。