题目背景

冒泡排序，这个曾经风靡一时的排序算法，却因为其 (O(n^2)) 的复杂度，在各种竞赛中被冷落，只能在角落里默默流泪。不甘心的她决定踏上“超进化”的旅程，希望通过优化自己，赢得更多关注。

题目描述

在传统的冒泡排序中，我们有以下代码：

int cnt = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n - 1; j++) {
        if (a[j] > a[j + 1]) {
            swap(a[j], a[j + 1]);
        }
        ++cnt;
    }
}

显然，在排序完成时，cnt来到了n(n-1)。

然而，超进化后的冒泡排序有了新的想法：她想知道，在cnt达到特定值k的时候，排序是否已经完成，或者至少能看看此时的数组状态是什么样的。于是，她向你发出了求助：希望你能帮忙输出在 cnt = k 时的数组状态。

形式化的表述，她会给你一个数列a,并提出T组询问，每组询问一个k,你需要输出当cnt = k时，当前的数组状态。

输入格式

• 第1行，一个数字n，表示数组长度

• 第2行，n个数字a1,a2,...,an(-10^8 ≤ ai ≤ 10^8)，表示初始数组状态

• 第3行，一个数字T，表示询问组数

• 第4~T+3行，一个数字k，表示询问的比较次数

输出格式

对于每组询问，输出超进化冒泡排序在 cnt = k 时的数组状态，每个数字之间用空格分隔。

示例

input

5
4 3 1 2 5
6
1
2
3
4
5
6

output

3 4 1 2 5
3 1 4 2 5
3 1 2 4 5
3 1 2 4 5
1 3 2 4 5
1 2 3 4 5

数据范围

• 对于 40% 的数据点，满足 2 ≤ n ≤ 10000
• 对于 100% 的数据点，满足 2 ≤ n ≤ 200000
• 对于所有的数据点，保证 T ≤ 10, 1 ≤ k ≤ n(n-1)

限制

• 每个测试的时间限制：1s

• 每个测试的内存限制：512 MB