Intersection of Two Arrays Preserving Order

Given two arrays of integers, compute their intersection while preserving the order in which elements first appear in the first array. Each element in the second array can be used at most as many times as it occurs in that array. Formally, let \(f_2(x)\) be the frequency of \(x\) in the second array. Then, for each element \(x\) in the first array, if \(f_2(x) > 0\), include \(x\) in the result and decrement \(f_2(x)\) by 1.

For example:

• If the first array is [1, 2, 2, 1] and the second is [2, 2], the intersection is [2, 2].
• If the first array is [4, 9, 5] and the second is [9, 4, 9, 8, 4], the intersection is [4, 9] (since 4 appears before 9 in the first array).

inputFormat

The input consists of two lines:

1. The first line contains space-separated integers representing the first array.
2. The second line contains space-separated integers representing the second array.

If an array is empty, its corresponding line will be empty.

outputFormat

Output a single line with the space-separated integers representing the intersection computed as specified. If there is no intersection, output an empty line.

1 2 2 1
2 2

2 2