Sort by Relative Order
Given a list of N integers, A, and another list of M distinct integers, B, sort the elements of A such that: 1. All elements in A that are present in B appear first, in the same relative order as they appear in B. 2. All elements in A that are not present in B appear next, in increasing order. Print the sorted list.
Input
The first line contains two integers N and M (1 <= N, M <= 200000). The second line contains N integers, A_1, A_2, ..., A_N (-10^9 <= A_i <= 10^9). The third line contains M distinct integers, B_1, B_2, ..., B_M (-10^9 <= B_i <= 10^9).
Output
Print the N integers of the sorted list A on a single line, separated by spaces.
Constraints
1 <= N, M <= 200000. -10^9 <= A_i, B_i <= 10^9. All elements in B are distinct.
Example 1
5 3 2 8 2 5 4 2 4 5
2 2 4 5 8
Elements 2, 5, 4 from A are in B. Their relative order in B is 2, 4, 5. So they appear first. The remaining element 8 is appended sorted. Result: 2 2 4 5 8.
Example 2
6 2 10 20 30 40 50 60 60 10
60 10 20 30 40 50
Elements 10 and 60 from A are in B. Their relative order in B is 60, 10. So they appear first. The remaining elements 20, 30, 40, 50 are appended sorted. Result: 60 10 20 30 40 50.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 3 2 8 2 5 4 2 4 5
6 2 10 20 30 40 50 60 60 10