Guessing Answers

Time limit1sMemory limit1024 MB

Summary

Given the correct answers and the set of problems guessed correctly, build an answer sequence where consecutive answers differ and exactly the listed problems are correct.

Level: Medium6 of 10
Topics: Greedy, Implementation, Array, Brute force
Solved: No attempts yet

Problem

Yunee did not study for the final exam. So Yunee decided to guess the answers to all problems in the final exam. The final exam consists of $N$ single choice questions numbered from $1$ to $N$ , each with a choice of $1$ to $5$ .

Yunee gets anxious when the answers to two successive problems are the same. So Yunee always selects an answer different from the answer to the previous problem (except for the first problem). After submitting the answers, Yunee received the grading result, which stated whether each answer was correct.

Given the correct answers to all problems and the $M$ problems that Yunee guessed correctly, reconstruct a possible sequence of Yunee's answers. It is guaranteed that at least one such sequence exists for each input.

Input

The first line contains two integers $N$ and $M$ $(1 \leq N \leq 100,000, 1\leq M \leq N)$ . $N$ is the total number of problems. $M$ is the number of problems that Yunee guessed correctly.

The second line contains $N$ integers from $1$ to $5$ . The $i$ -th integer represents the correct answer to the $i$ -th problem.

The third line contains $M$ distinct integers from $1$ to $N$ . They represent the $M$ problems that Yunee guessed correctly.

Output

Output a possible sequence of Yunee's answers. Each number should be separated by a blank.

Examples2

Example 1
Input
```
4 2
1 1 2 3
1 4
```
Expected output
```
1 5 4 3
```
Example 2
Input
```
3 2
1 2 3
1 3
```
Expected output
```
1 4 3
```