提示: 欢迎访问OurACM平台。
Problem 1613 Hero's talent

Accept: 57    Submit: 333
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

The hero always has extraordinary abilities, of course, the hero's skills are more from their talent, such as strength, will, magic, life, and so on.

Oaiei certainly will not be convinced and he wants to make a comparison with the hero's abilities.

Assuming that the comparisons are N, and we make a numerical estimate for the N comparison places. For example, the hero’s strength is 100 and oaiei’s strength is 80.

If comparing with the same ability, oaiei may be worse than the hero, he thought a good idea: oaiei just want to know that the longest common subsequence between he and the hero.

Now given the N comparisons between oaiei and the hero, can you help oaiei to find out the longest common subsequence?

Input

There are multiple tests.

For each test, the first line is an integer N(1<=N<=100000), denoting that the comparisons number. The second line are N different integers Ai(|Ai|<=100000,i=1,2,…,N), denoting that the hero’s abilities values. The third line are N different integers Bi(|Bi|<=100000,i=1,2,…,N), denoting the oaiei’s abilities values.

Output

For each test, you should output two line. The first line is the length of the longest common subsequence, and the second line is the longest common subsequence(We guarantee that there are only one answer to the question).

Sample Input

4 1 2 3 5 1 2 -2 3

Sample Output

3 1 2 3

Source

FOJ月赛-2008年6月 -- Heroes Happen Here

Submit  Back  Status  Discuss