该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师负责统计学校的每日出勤人数。为了分析出勤情况，徐老师想知道每个连续$k$天时间段内的最高出勤人数。

具体来说，给定$n$天的出勤记录，对于每个以第$i$天结尾的连续$k$天时间段（如果不足$k$天则从第$1$天开始），输出该时间段内的最高出勤人数。

Format

Input

第一行一个正整数$T(1 \leq T \leq 10)$，表示测试组数。

对于每组测试，第一行两个正整数$n, k(1 \leq k \leq n \leq 10^5)$，分别表示总天数和时间段长度。

第二行$n$个整数$a_i(1 \leq a_i \leq 10^9)$，表示每天的出勤人数。

Output

对于每组测试，输出一行$n$个整数，表示每个以第$i$天结尾的时间段内的最高出勤人数，用空格分隔。

Samples

1
8 3
100 350 80 500 300 600 700 200

100 350 350 500 500 600 700 700

Limitation

1s, 1024KiB for each test case.