Background

Special for beginners, ^_^

Description

n个学生排成一排，计算从左到右每连续k个人的身高的中位数。 如果k是偶数，取靠左的元素。

Format

Input

第一行一个整数T（不超过5），表示有T组数据。 后面每行一个n和k（不超过2e5），表示总人数和每个分组的人数。

Output

输出n-k+1个中位数，相邻两个数之间一个空格。每组数据换行。.

Samples

1
8 3
2 4 3 5 8 1 2 1

3 4 5 5 2 1 

Limitation

1s, 1024KiB for each test case.