题目描述

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

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

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

现在给定初始序列 $A[1 \sim n]$（保证 $A$ 是排列，即 $1 \sim n$ 每个数恰好出现一次）和 $m$ 个询问 $q[1, 2, \ldots, m]$（保证 $q[i] < q[i + 1]$），请你依次输出第 $q[i]$ 趟之后的序列 $A$。

输入格式

第一行 2 个整数 $n, m$。

第二行 $n$ 个整数 $A[1 \sim n]$，保证 $A$ 是排列。

第三行 $m$ 个整数 $q[1 \sim m]$，保证 $q[i] < q[i + 1]$。

输出格式

输出 $m$ 行，第 $i$ 行包含 $n$ 个整数代表第 $q[i]$ 趟之后的序列 $A$。

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 \leq n \leq 10^5, 1 \leq m \leq 10, 1 \leq A[i] \leq n, 1 \leq q[i] < q[i + 1] < n$，保证 $A$ 是排列。

• 对于测试点 1~8：$n \leq 10$；
• 对于测试点 9~13：$n \leq 2000$；
• 对于测试点 14~20：$n \leq 10^5$；