Longest Playlist Without Consecutive Same Genre

You are given a list of n songs along with their corresponding genres. Your task is to construct the longest possible playlist (a sequence of song names) such that no two consecutive songs share the same genre. When multiple songs are available that satisfy the condition, you must choose the one with the lexicographically smallest name. The playlist is constructed by repeatedly selecting an eligible song and removing it from the list.

Input Format: The first line contains an integer \(n\) representing the number of songs. The second line contains \(n\) space-separated song names. The third line contains \(n\) space-separated genres corresponding to each song.

Output Format: Output a single line containing the playlist, which is the space-separated list of selected song names. If it isn’t possible to add any new song (because all remaining songs have the same genre as the last selected one), then the process terminates.

Note: To ensure determinism, when choosing among multiple valid songs, always pick the one with the smallest lexicographical order.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains an integer (n) representing the number of songs.
2. The second line contains (n) space-separated strings, each being a unique song name.
3. The third line contains (n) space-separated strings, where the (i)-th string is the genre of the (i)-th song.

outputFormat

Output to standard output (stdout) a single line containing the playlist: a sequence of song names separated by a single space. This playlist is the longest possible such that no two consecutive songs share the same genre, and when choices are available, the song with the smallest lexicographical name is chosen.## sample

7
song1 song2 song3 song4 song5 song6 song7
rock jazz pop rock pop jazz pop

song1 song2 song3 song4 song5 song6 song7