10_D. LCIS_10172
This problem differs from one which was on the online contest.

The sequence a1, a2, ..., an is called increasing, if ai < ai + 1 for i < n.

The sequence s1, s2, ..., sk is called the subsequence of the sequence a1, a2, ..., an, if there exist such a set of indexes 1 ≤ i1 < i2 < ... < ik ≤ n that aij = sj. In other words, the sequence s can be derived from the sequence a by crossing out some elements.

You are given two sequences of integer numbers. You are to find their longest common increasing subsequence, i.e. an increasing sequence of maximum length that is the subsequence of both sequences.

Input

The first line contains an integer n (1 ≤ n ≤ 500) — the length of the first sequence. The second line contains n space-separated integers from the range [0, 109] — elements of the first sequence. The third line contains an integer m (1 ≤ m ≤ 500) — the length of the second sequence. The fourth line contains m space-separated integers from the range [0, 109] — elements of the second sequence.

Output

In the first line output k — the length of the longest common increasing subsequence. In the second line output the subsequence itself. Separate the elements with a space. If there are several solutions, output any.

Examples

Input

7
2 3 1 6 5 4 6
4
1 3 5 6


Output

3
3 5 6 


Input

5
1 2 0 2 1
3
1 0 1


Output

2
0 1 
#!/usr/bin/python

import fileinput

lines =[ line for line in fileinput.input() ]

n = int(lines[0])
a = map(int, lines[1].split(" "))
m = int(lines[2])
b = map(int, lines[3].split(" "))

f = [ [0 for j in range(0, m)] for i in range(0, n) ]
p = [ -1 for i in range(0, m) ] 

for j in range(0, m):
    f[0][j] = 1 if a[0] == b[j] else 0

for i in range(1, n):
    idx = -1
    lastmax = 0
    for j in range(0, m):
        if a[i] != b[j]:
            f[i][j] = f[i - 1][j]
            if a[i] > b[j] and f[i - 1][j] > lastmax:
                lastmax = f[i - 1][j]
                idx = j
        else:
            if idx == -1:
                f[i][j] = 1
                p[j] = -1
            else:
                f[i][j] = f[i - 1][idx] + 1
                p[j] = idx

result = 0
ptr = -1
for j in range(0, m):
    if result < f[n - 1][j]:
        result = f[n - 1][j]
        ptr = j

print result

arr = [ 0 for i in range(0, result) ]
while ptr > -1:
    result -= 1
    arr[result] = b[ptr]
    ptr = p[ptr]

for i in arr:
    print i,
print

5
1 2 0 2 1
3
1 0 1
 7
2 3 1 6 5 4 6
4
1 3 5 6
 9
7 4 4 5 0 6 5 4 10
4
5 2 10 9
 13
55 160 86 99 92 148 81 36 216 191 214 127 44
85
92 12 64 21 221 225 119 243 147 47 244 112 212 237 209 121 81 239 43 104 3 254 52 13 1 210 28 18 199 75 251 146 77 28 253 211 50 35 42 160 157 104 155 37 241 78 42 190 150 228 193 96 190 178 232 65 231 186 1 123 212 126 239 22 214 186 245 249 66 234 57 78 173 229 185 23 240 91 127 177 240 105 77 208 86
 8
0 4 10 6 7 2 8 5
7
0 4 6 7 7 0 8
 94
100 161 99 102 209 51 5 188 217 53 121 5 233 55 25 156 136 195 243 157 110 202 136 151 86 171 253 38 126 40 27 76 60 119 222 52 134 104 184 146 133 220 88 108 246 61 215 184 181 134 223 164 41 193 232 217 38 192 226 91 81 99 204 232 178 4 187 61 160 255 121 142 191 114 114 181 226 49 86 55 252 169 59 190 246 93 21 22 17 18 120 88 93 144
30
61 51 176 38 119 33 100 185 103 84 161 166 103 227 43 200 127 53 52 89 19 215 76 254 110 30 239 247 11 182
 53
135 168 160 123 6 250 251 158 245 184 206 35 189 64 138 12 69 21 112 198 165 211 109 40 192 98 236 216 255 98 136 38 67 79 25 196 216 64 134 124 102 232 229 102 179 138 111 123 2 93 25 162 57
57
64 143 41 144 73 26 11 17 224 209 167 162 129 39 102 224 254 45 120 2 138 213 139 133 169 54 7 143 242 118 155 189 100 185 145 168 248 131 83 216 142 180 225 35 226 202 8 15 200 192 75 140 191 189 75 116 202
 10
62914292 123971042 784965687 324817892 379711365 394545872 813282270 822333477 865397146 437913515
9
297835672 62914292 123971042 324817892 379711365 394545872 813282270 822333477 865397146
 7
4 2 4 3 10 3 6
9
7 5 2 3 0 1 6 1 4
 10
0 1 2 3 4 5 6 7 8 9
10
0 1 2 3 4 5 6 7 8 9
 83
95 164 123 111 177 71 38 225 103 59 210 209 117 139 115 140 66 21 39 84 14 227 0 43 90 233 96 98 232 237 108 139 55 220 14 225 134 39 68 167 193 125 86 216 87 14 94 75 255 24 165 98 177 191 239 123 98 90 29 52 155 231 187 90 180 1 31 237 167 145 242 115 61 190 47 41 61 206 191 248 126 196 26
49
234 134 9 207 37 95 116 239 105 197 191 15 151 249 156 235 17 161 197 199 87 78 191 188 44 151 179 238 72 29 228 157 174 99 190 114 95 185 160 168 58 216 131 151 233 204 213 87 76
 3
37 49 24
3
33 5 70
 2
6 10
3
6 3 3
 8
7 8 6 6 8 10 3 3
5
7 4 10 8 7
 13
0 46 104 116 63 118 158 16 221 222 136 245 223
9
0 46 104 116 118 158 221 222 245
 9
7 0 1 2 6 0 10 3 5
4
8 4 0 3
 10
130077811 57466561 335978192 71385678 434259735 454136111 482887469 530031703 688581885 809880630
8
373627898 57466561 71385678 434259735 454136111 482887469 530031703 809880630
 15
10 4 7 7 10 1 4 9 1 10 9 6 8 8 2
2
0 4
 3
48875076 71023491 76538219
3
48875076 71023491 76538219
 2
5 2
4
8 8 0 4
 16
8 8 6 7 10 0 10 1 7 6 6 0 4 2 6 7
12
9 3 8 4 10 3 9 8 3 7 10 4
 3
6379263 55134355 76061584
3
6379263 55134355 76061584
 1
7
10
1 8 8 10 9 10 4 6 0 5
 23
174 172 196 135 91 174 208 92 132 53 202 118 5 244 161 140 71 21 185 56 60 195 217
17
38 218 120 77 22 214 164 194 79 195 36 167 42 89 201 80 11
 13
34 38 51 57 73 125 147 158 160 178 188 198 235
15
34 38 51 57 73 125 147 158 160 178 255 67 188 198 235
 8
2 3 4 5 6 8 9 5
9
2 2 3 4 5 6 6 8 9
 10
7 10 1 2 1 7 1 5 9 9
9
6 2 5 6 7 7 5 5 2
 6
3 5 4 6 8 1
10
3 3 0 5 4 0 10 5 6 8
 17
364396044 90653796 82853043 311258337 326557522 362475139 415783272 428510002 840021181 469284863 541444887 650535473 649258258 750028895 791368777 808443140 959785237
13
82853043 311258337 326557522 362475139 415783272 428510002 469284863 541444887 649258258 750028895 791368777 808443140 959785237
 17
25 29 37 207 122 189 118 42 54 95 154 160 162 225 228 237 248
19
25 29 248 37 147 209 42 54 255 95 154 160 162 225 228 237 73 248 10
 1
7
2
7 9
 3
1 3 9
10
8 0 10 5 7 0 3 1 2 4
 5
6621317 78540394 52064998 89150480 53659440
3
78540394 46008538 839195
 20
7 17 24 27 36 45 62 92 93 94 98 112 114 138 143 156 173 199 204 207
20
7 17 24 27 36 45 62 92 93 94 98 112 114 138 143 156 173 199 204 207
 4
3 4 9 1
7
5 3 8 9 10 2 1
 2
34665180 51128665
5
71074966 34665180 47089728 44119345 51128665
 17
12 17 39 156 100 177 188 129 14 142 45 144 243 151 158 194 245
16
125 12 17 199 65 39 100 185 129 194 142 144 62 92 158 194
 9
7 4 4 5 0 6 5 4 10
4
5 0 10 9
 13
55 160 86 99 92 148 81 36 216 191 214 127 44
85
92 12 64 21 221 225 119 243 147 47 244 112 103 237 209 121 81 239 43 104 3 254 52 13 1 210 28 18 199 75 251 146 77 28 253 211 50 35 42 160 157 104 155 37 241 78 42 190 150 228 193 96 190 178 232 65 231 186 1 123 212 126 239 22 214 186 245 249 66 234 57 78 173 229 185 23 240 91 127 177 240 105 77 208 86
 8
0 0 10 6 7 2 8 5
7
0 4 6 7 7 0 8
 94
100 161 99 102 209 51 5 188 217 53 121 5 233 55 25 156 136 195 243 157 110 202 136 151 86 171 253 38 126 40 27 76 60 119 222 52 134 104 184 146 133 220 88 108 246 61 215 184 181 134 223 164 41 193 232 217 38 192 226 91 81 99 204 232 178 4 187 61 160 255 121 142 191 114 114 181 329 49 86 55 252 169 59 190 246 93 21 22 17 18 120 88 93 144
30
61 51 176 38 119 33 100 185 103 84 161 166 103 227 43 200 127 53 52 89 19 215 76 254 110 30 239 247 11 182
 53
135 168 160 123 6 250 251 158 245 184 206 35 119 64 138 12 69 21 112 198 165 211 109 40 192 98 236 216 255 98 136 38 67 79 25 196 216 64 134 124 102 232 229 102 179 138 111 123 2 93 25 162 57
57
64 143 41 144 73 26 11 17 224 209 167 162 129 39 102 224 254 45 120 2 138 213 139 133 169 54 7 143 242 118 155 189 100 185 145 168 248 131 83 216 142 180 225 35 226 202 8 15 200 192 75 140 191 189 75 116 202
 10
62914292 123971042 784965687 324817892 379711365 394545872 813282270 822333477 865397146 437913515
9
297835672 62914292 123971042 324817892 199337131 394545872 813282270 822333477 865397146
 7
4 2 4 3 10 3 6
9
7 5 3 3 0 1 6 1 4
 10
0 1 2 3 4 5 6 7 8 9
10
0 1 2 3 4 3 6 7 8 9
 83
95 164 123 111 177 71 38 225 103 59 210 209 117 139 115 140 66 21 39 84 14 227 0 43 90 233 96 98 232 237 108 139 55 220 14 225 134 39 68 167 193 125 86 216 87 14 94 75 255 24 165 98 177 191 239 123 12 90 29 52 155 231 187 90 180 1 31 237 167 145 242 115 61 190 47 41 61 206 191 248 126 196 26
49
234 134 9 207 37 95 116 239 105 197 191 15 151 249 156 235 17 161 197 199 87 78 191 188 44 151 179 238 72 29 228 157 174 99 190 114 95 185 160 168 58 216 131 151 233 204 213 87 76
 3
37 49 24
3
47 5 70
 8
7 8 6 6 8 10 4 3
5
7 4 10 8 7
 13
-1 46 104 116 63 118 158 16 221 222 136 245 223
9
0 46 104 116 118 158 221 222 245
 9
11 0 1 2 6 0 10 3 5
4
8 4 0 3
 10
130077811 57466561 335978192 71385678 434259735 454136111 482887469 530031703 688581885 809880630
8
373627898 57466561 71385678 649062669 454136111 482887469 530031703 809880630
 3
29302524 71023491 76538219
3
48875076 71023491 76538219
 16
8 8 6 7 10 0 10 1 7 6 6 0 4 2 5 7
12
9 3 8 4 10 3 9 8 3 7 10 4
 3
6379263 55134355 76061584
3
998185 55134355 76061584
 23
174 172 196 135 91 174 208 92 132 53 202 118 5 244 161 140 71 21 38 56 60 195 217
17
38 218 120 77 22 214 164 194 79 195 36 167 42 89 201 80 11
 13
34 38 51 57 73 125 147 158 160 178 188 198 235
15
34 38 6 57 73 125 147 158 160 178 255 67 188 198 235
 8
2 3 4 5 6 8 9 5
9
2 2 3 4 5 9 6 8 9
 10
7 10 1 2 1 7 1 5 9 9
9
6 2 5 6 6 7 5 5 2
 6
3 5 4 6 8 1
10
0 3 0 5 4 0 10 5 6 8
 17
25 29 37 207 122 189 118 42 54 95 154 160 162 225 228 237 248
19
25 29 248 37 147 209 42 54 90 95 154 160 162 225 228 237 73 248 10
 3
1 3 9
10
8 0 10 5 7 1 3 1 2 4
 20
7 17 24 27 36 45 62 92 93 94 98 112 114 138 143 156 173 199 204 207
20
7 17 24 27 36 45 62 92 93 94 175 112 114 138 143 156 173 199 204 207
 4
3 8 9 1
7
5 3 8 9 10 2 1
 2
41667422 51128665
5
71074966 34665180 47089728 44119345 51128665
 17
12 17 39 156 100 177 188 129 14 142 45 144 243 151 158 194 245
16
125 12 17 199 65 39 110 185 129 194 142 144 62 92 158 194
 5
0 2 0 2 1
3
1 0 1
 7
2 3 1 6 5 4 6
4
0 3 5 6
 9
7 4 4 5 0 6 5 4 5
4
5 0 10 9
 8
0 0 10 6 7 2 0 5
7
0 4 6 7 7 0 8
 10
62914292 123971042 784965687 324817892 379711365 394545872 813282270 822333477 865397146 437913515
9
297835672 62914292 123971042 324817892 199337131 394545872 813282270 237345896 865397146
 10
0 1 2 3 4 5 6 9 8 9
10
0 1 2 3 4 3 6 7 8 9
 8
7 8 6 6 8 10 4 3
5
14 4 10 8 7
 13
-1 46 104 116 63 118 158 16 221 222 136 245 223
9
0 46 104 116 118 181 221 222 245
 10
130077811 57466561 335978192 71385678 434259735 454136111 482887469 530031703 688581885 809880630
8
373627898 57466561 71385678 649062669 454136111 482887469 699463267 809880630
 13
34 38 51 57 73 125 235 158 160 178 188 198 235
15
34 38 6 57 73 125 147 158 160 178 255 67 188 198 235
 8
2 3 4 5 6 8 2 5
9
2 2 3 4 5 9 6 8 9
 6
3 5 4 6 8 1
10
0 3 0 5 4 0 10 5 0 8
 2
1 10
3
6 3 3
 15
10 4 7 7 10 1 4 9 1 10 9 6 8 8 2
2
0 5
 2
5 2
4
8 8 0 8
 1
7
10
1 8 8 10 9 10 8 6 0 5
 1
6
2
7 9
 5
6621317 78540394 52064998 89150480 53659440
3
58374366 46008538 839195
 13
55 160 86 99 92 148 81 36 216 191 214 127 44
85
92 12 64 21 221 225 119 243 147 47 244 112 103 237 209 121 81 239 43 104 3 254 52 13 1 210 28 18 199 75 251 146 77 28 253 211 50 35 42 160 157 104 155 37 241 78 41 190 150 228 193 96 190 178 232 65 231 186 1 123 212 126 239 22 214 186 245 249 66 234 57 78 173 229 185 23 240 91 127 177 240 105 77 208 86
 94
100 161 99 102 209 51 5 188 217 53 121 5 233 55 25 156 136 195 243 157 110 202 136 151 86 171 253 38 126 40 27 76 60 119 222 52 134 104 184 146 133 220 88 108 246 61 215 184 181 134 223 164 41 193 232 217 38 192 226 91 81 99 204 232 178 4 187 61 160 255 121 142 191 114 114 181 329 49 86 55 252 169 59 190 246 93 21 22 17 17 120 88 93 144
30
61 51 176 38 119 33 100 185 103 84 161 166 103 227 43 200 127 53 52 89 19 215 76 254 110 30 239 247 11 182
 53
135 168 160 123 6 250 251 158 245 184 206 35 119 64 138 12 69 21 112 198 165 211 109 40 192 98 236 216 255 98 136 38 67 79 25 196 216 64 134 124 102 232 229 102 179 138 111 123 2 93 25 162 57
57
64 143 41 144 73 26 11 17 224 209 167 162 129 37 102 224 254 45 120 2 138 213 139 133 169 54 7 143 242 118 155 189 100 185 145 168 248 131 83 216 142 180 225 35 226 202 8 15 200 192 75 140 191 189 75 116 202
 7
4 2 4 3 7 3 6
9
7 5 3 3 0 1 6 1 4
 83
95 164 123 111 177 71 38 225 103 59 210 209 117 139 115 140 66 21 39 84 14 227 0 43 90 233 96 98 232 237 108 139 55 220 14 225 134 39 68 167 193 125 86 216 87 14 94 75 255 24 165 98 177 191 239 123 12 90 29 52 155 231 187 90 180 1 31 237 167 145 242 115 61 190 47 41 61 206 191 248 126 196 26
49
234 134 9 207 37 95 116 239 105 197 191 15 151 249 156 235 17 161 197 199 87 78 191 188 44 151 179 238 72 29 228 157 174 99 190 114 95 185 160 168 58 216 136 151 233 204 213 87 76
 3
37 49 24
3
47 8 70
 2
2 10
3
6 3 3
 9
11 0 1 2 6 0 10 3 5
4
8 1 0 3
 15
10 4 7 2 10 1 4 9 1 10 9 6 8 8 2
2
0 5
 3
3820512 71023491 76538219
3
48875076 71023491 76538219
 2
5 2
4
9 8 0 8
 16
8 8 6 7 10 0 10 0 7 6 6 0 4 2 5 7
12
9 3 8 4 10 3 9 8 3 7 10 4
 3
4924680 55134355 76061584
3
998185 55134355 76061584
 1
7
10
2 8 8 10 9 10 8 6 0 5
 23
174 172 196 135 91 60 208 92 132 53 202 118 5 244 161 140 71 21 38 56 60 195 217
17
38 218 120 77 22 214 164 194 79 195 36 167 42 89 201 80 11
 10
7 10 1 2 1 7 1 5 17 9
9
6 2 5 6 6 7 5 5 2
 17
25 29 37 207 122 189 85 42 54 95 154 160 162 225 228 237 248
19
25 29 248 37 147 209 42 54 90 95 154 160 162 225 228 237 73 248 10
 1
6
2
7 16

2
0 1 
 3
1 5 6 
 2
5 10 
 2
92 214 
 5
0 4 6 7 8 
 3
51 119 215 
 3
64 102 138 
 8
62914292 123971042 324817892 379711365 394545872 813282270 822333477 865397146 
 3
2 3 6 
 10
0 1 2 3 4 5 6 7 8 9 
 2
134 239 
 0

 1
6 
 2
7 10 
 9
0 46 104 116 118 158 221 222 245 
 2
0 3 
 7
57466561 71385678 434259735 454136111 482887469 530031703 809880630 
 1
4 
 3
48875076 71023491 76538219 
 0

 2
8 10 
 3
6379263 55134355 76061584 
 0

 1
195 
 13
34 38 51 57 73 125 147 158 160 178 188 198 235 
 7
2 3 4 5 6 8 9 
 2
2 5 
 4
3 5 6 8 
 13
82853043 311258337 326557522 362475139 415783272 428510002 469284863 541444887 649258258 750028895 791368777 808443140 959785237 
 13
25 29 37 42 54 95 154 160 162 225 228 237 248 
 1
7 
 1
3 
 1
78540394 
 20
7 17 24 27 36 45 62 92 93 94 98 112 114 138 143 156 173 199 204 207 
 2
3 9 
 2
34665180 51128665 
 9
12 17 39 100 129 142 144 158 194 
 2
5 10 
 2
92 214 
 4
0 6 7 8 
 3
51 119 215 
 3
64 102 138 
 7
62914292 123971042 324817892 394545872 813282270 822333477 865397146 
 2
3 6 
 9
0 1 2 3 4 6 7 8 9 
 2
134 239 
 0

 2
7 10 
 8
46 104 116 118 158 221 222 245 
 2
0 3 
 6
57466561 71385678 454136111 482887469 530031703 809880630 
 2
71023491 76538219 
 2
8 10 
 2
55134355 76061584 
 2
38 195 
 12
34 38 57 73 125 147 158 160 178 188 198 235 
 7
2 3 4 5 6 8 9 
 2
2 5 
 4
3 5 6 8 
 13
25 29 37 42 54 95 154 160 162 225 228 237 248 
 2
1 3 
 19
7 17 24 27 36 45 62 92 93 94 112 114 138 143 156 173 199 204 207 
 3
3 8 9 
 1
51128665 
 8
12 17 39 129 142 144 158 194 
 2
0 1 
 3
3 5 6 
 1
5 
 3
0 6 7 
 6
62914292 123971042 324817892 394545872 813282270 865397146 
 8
0 1 2 3 4 6 8 9 
 1
4 
 7
46 104 116 118 221 222 245 
 5
57466561 71385678 454136111 482887469 809880630 
 11
34 38 57 73 125 158 160 178 188 198 235 
 6
2 3 4 5 6 8 
 3
3 5 8 
 0

 0

 0

 0

 0

 0

 2
92 214 
 3
51 119 215 
 3
64 102 138 
 2
3 6 
 2
134 239 
 0

 0

 2
1 3 
 0

 2
71023491 76538219 
 0

 2
8 10 
 2
55134355 76061584 
 0

 2
38 195 
 2
2 5 
 13
25 29 37 42 54 95 154 160 162 225 228 237 248 
 0

