题目描述

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每趟找出第 $𝑖$ 小的元素（也就是 $𝐴[𝑖 ∼ 𝑛]$ 中最小的元素），然后将这个元素与数组第 $𝑖$ 个位置上的元素 $𝐴[𝑖]$ 交换；在 $𝑛 − 1$ 趟之后序列 $𝐴$ 变为升序。

例如 $𝐴 = [3,4,1,5,2]$：

• 第 $1$ 趟交换 $𝐴[1], 𝐴[3]$，序列变为 $[1,4,3,5,2]$ • 第 $2$ 趟交换 $𝐴[2], 𝐴[5]$，序列变为 $[1,2,3,5,4]$ • 第 $3$ 趟交换 $𝐴[3], 𝐴[3]$，序列不变 • 第 $4$ 趟交换 $𝐴[4], 𝐴[5]$，序列变为 $[1,2,3,4,5]$

现在给定初始序列 $𝐴[1 ∼ 𝑛]$ （保证 $𝐴$ 是排列，即 $1 ∼ 𝑛$ 每个数恰好出现一次）和 $𝑚$ 个询问 $𝑞[1,2, . . . , 𝑚]$（保证 $𝑞[𝑖] < 𝑞[𝑖 + 1]$），请你依次输出第 $𝑞[𝑖]$ 趟之后的序列。

输入格式

第一行 $2$ 个整数 $𝑛, 𝑚$。

第二行 $𝑛$ 个整数 $𝐴[1 ∼ 𝑛]$，保证 $𝐴$ 是排列。

第三行 $𝑚$ 个整数 $𝑞[1 ∼ 𝑚]$，保证 $𝑞[𝑖] < 𝑞[𝑖 + 1]$

输出格式

输出 $𝑚$ 行，第 $𝑖$ 行包含 $𝑛$ 个整数代表第 $𝑞[𝑖]$ 趟之后的序列 $𝐴$。

5 4
3 4 1 5 2
1 2 3 4

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

6 3
6 4 2 3 1 5
1 3 5

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

提示

对于所有数据，满足 $1 ≤ 𝑛 ≤ 10^5, 1 ≤ 𝑚 ≤ 10,1 ≤ 𝐴[𝑖] ≤ 𝑛, 1 ≤ 𝑞[𝑖] < 𝑞[𝑖 + 1] < 𝑛$，保证 $𝐴$ 是排列。

对于测试点 $1 \sim 8$：$𝑛 ≤ 10$

对于测试点 $9\sim13$：$𝑛 ≤ 2000$

对于测试点 $14\sim20$：$𝑛 ≤ 10^5$