LCS3 - Long Common Subsequence

Given a main sequence of N (1 <= N <= 1000000) numbers range from 0 to 10000 and several other sequence of M (0 <= M <= 5) numbers, you have to compute the Longest Common Subsequence of this sequence with the main sequence.

Input

First line of the input will be N the number of elements of the main sequence. After that line there will be N numbers in one or more lines. Each of this number will be between 0 to 10000 (inclusive). Then there will be Q (1 <= Q <= 5000) the number of query. Then following Q lines will be queries. In each query, start with a number M (0 <= M <= 5), followed by M numbers also between 0 to 10000 (inclusive).

Output

For each query first print the number of elements in the longest common subsequence of the main and query sequences. Then print the subsequence. If there is more then one then print the lexicographically smallest.

Example

Input:
10
5 1 4 3 2 6 5 5 0 7
5
1 5
1 10
4 5 0 4 7
5 4 1 2 3 5
5 2 6 5 0 7

Output:
1 5
0
3 5 0 7
3 1 2 5
5 2 6 5 0 7
Huge Test Case (almost 5MB)

Added by:Muhammad Ridowan
Date:2011-07-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own. Thanks msh_shiplu and zobayer for alternate

hide comments
2015-06-03 23:53:41 Addy
:)atlast my dream of an AC at one go comes true
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.