B4171 [BCSP-X 2024 6 月小学高年级组] 选择排序

选择排序（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$。

对于所有数据，满足 $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$；