Description

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每趟找出第 i 小的元素（也就是 A[i∼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∼n] （保证 A 是排列，即 1∼n 每个数恰好出现一次）和 m 个询问q[1,2,…,m]（保证 q[i]<q[i+1]），请你依次输出第 q[i] 趟之后的序 列 A。

Format

Input

输入格式 第一行2个整数 n,m 第二行 n 个整数 A[1∼n]，保证 A 是排列 第三行 m个整数 q[1∼m]，保证 q[i]<q[i+1]

Output

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

Samples

5 4 
3 4 1 5 2 
1 2 3 4


```output1
1 4 3 5 2 
1 2 3 5 4 
1 2 3 5 4 
1 2 3 4 5

```input2
6 3 
6 4 2 3 1 5 
1 3 5

```output2
1 4 2 3 6 5 
1 2 3 4 6 5 
1 2 3 4 5 6


# Limitation
提示
对于所有数据，满足 1≤n≤〖10〗^5,1≤m≤10,1≤A[i]≤n,1≤q[i]<q[i+1]<n，保证A是排列。
对于测试点1~8：n≤10
对于测试点9~13：n≤2000 
对于测试点14~20：n≤〖10〗^5