$K$ Integers

시간 제한2초메모리 제한512 MB

요약

문자열과 인덱스 수열 t가 주어질 때, t에 대응하는 문자들을 부분수열로 포함하면서 사전순으로 가장 작은 문자열의 부분수열을 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 문자열, 구현
정답자: 아직 제출이 없습니다

문제

You are given a string $s$ of length $n$ .

A sequence of integers $t$ is an index sequence if $1 \leq t\_1 < t\_2 < \ldots < t\_k \leq n$ , where $k$ is the length of $t$ .

A string corresponding to an index sequence $t$ is the the following string: $s\_{t\_1} s\_{t\_2} \ldots s\_{t\_k}$ . Note that it is always a subsequence of $s$ .

You are given an index sequence. Find the lexicographically smallest string which corresponds to some index sequence which contains the given one as a subsequence.

입력

The first line contains the string $s$ consisting of $n$ ( $1 \leq n \leq 5 \cdot 10^5$ ) lowercase English letters.

The second line contains a single integer $k$ ( $1 \leq k \leq n$ ), length of $t$ .

The third line contains $k$ integers $t\_i$ ( $1 \leq t\_i \leq n$ ). $t$ is an index sequence.

출력

Print a single string --- the answer to the problem.

예제8

예제 1
입력
```
links
2
3 4
```
예상 출력
```
ink
```
예제 2
입력
```
abacaba
2
4 6
```
예상 출력
```
aacab
```
예제 3
입력
```
pepega
2
2 6
```
예상 출력
```
ea
```
예제 4
입력
```
gaypride
2
6 7
```
예상 출력
```
aid
```
예제 5
입력
```
pogchamp
3
1 2 3
```
예상 출력
```
pog
```
예제 6
입력
```
frankerz
1
8
```
예상 출력
```
aerz
```
예제 7
입력
```
blessrng
8
1 2 3 4 5 6 7 8
```
예상 출력
```
blessrng
```
예제 8
입력
```
residentsleeper
4
1 3 7 15
```
예상 출력
```
resdeneeer
```