Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Language:
Greatest Common Increasing Subsequence
 Time Limit: 10000MS Memory Limit: 65536K Total Submissions: 11855 Accepted: 3099 Case Time Limit: 2000MS Special Judge

Description

You are given two sequences of integer numbers. Write a program to determine their common increasing subsequence of maximal possible length.
Sequence S1 , S2 , . . . , SN of length N is called an increasing subsequence of a sequence A1 , A2 , . . . , AM of length M if there exist 1 <= i1 < i2 < . . . < iN <= M such that Sj = Aij for all 1 <= j <= N , and Sj < Sj+1 for all 1 <= j < N .

Input

Each sequence is described with M --- its length (1 <= M <= 500) and M integer numbers Ai (-231 <= Ai < 231 ) --- the sequence itself.

Output

On the first line of the output file print L --- the length of the greatest common increasing subsequence of both sequences. On the second line print the subsequence itself. If there are several possible answers, output any of them.

Sample Input

```5
1 4 2 5 -12
4
-12 1 2 4```

Sample Output

```2
1 4```

Source

Northeastern Europe 2003, Northern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]