Longest Common Subsequence of Permutations

Given two permutations \(P_1\) and \(P_2\) of the numbers \(1,2,\ldots,n\), find one of their longest common subsequences (LCS). A common subsequence is a sequence that appears in both permutations (not necessarily contiguous) in the same order.

Hint: Since both \(P_1\) and \(P_2\) are permutations, one efficient method is to map each element of \(P_1\) to its index, transform \(P_2\) accordingly, and then compute the longest increasing subsequence (LIS) of the resulting sequence.

inputFormat

The input consists of three lines:

1. The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), representing the number of elements in the permutation.
2. The second line contains \(n\) space-separated integers representing the first permutation \(P_1\).
3. The third line contains \(n\) space-separated integers representing the second permutation \(P_2\).

outputFormat

Output a longest common subsequence of \(P_1\) and \(P_2\). The elements should be printed in order and separated by a single space. If there are multiple valid answers, printing any one of them is acceptable.

sample

5
3 1 2 5 4
1 3 2 5 4

3 2 5 4