#P1281. 2023.05.13-春招-第一题-泡泡排序

2023.05.13-春招-第一题-泡泡排序

题目描述

塔子哥在冒泡排序算法基础上想出了一个泡泡排序算法。对于一个无重复元素的排列数组a1a_1,a2a_2 ,···,ana_n，塔子哥给定一个常数 kk ，每次交换只能选择交换距离为 kk 个位置的元素，塔子哥可以做无限次交换。但是他发现这样可能不能将数组排成有序的，所以他想知道可能得到的字典序最小的数组是多少。对于两个长度相同的数组，通常定义其字典序大小关系为从前往后第一个值不相同的位置的值大小关系。

输入描述

输入第一行为两个整数 nn , kk (1≤n,k≤1e5)(1 \leq n , k \leq 1e5) 。

输入第二行 nn 个正整数， 表示数组 aa , 保证给出的 a(1≤ai≤1e9)a(1 \leq a_i \leq 1e9) 是一个排列。

输出描述

输出一行 nn 个整数表示字典序最小的数组。

样例

输入

6 2
5 8 9 3 4 1

输出

4 1 5 3 9 8

知识点:*****

查看知识点以及同类型题目

Statistics