408527: GYM103181 H Similarities

Bob is currently infatuated with arrays of numbers - so much that he wants to analyze every single pattern that he can. Namely, for a given pair of two arrays, Bob wants to see as many longest common subsequences as possible.

Formally, Bob will give you two arrays $$$a$$$, $$$b$$$, and $$$q$$$ queries. Each query will contain an integer $$$k_i$$$. You are asked to find, among all longest common subsequences ordered lexicographically, the $$$k_i^{th}$$$ one. If there are not at least $$$k_i$$$ such subsequences, the answer will be $$$-1$$$.

Note that two subsequences with the same elements are not necessarily identical. For two of them to be different, it is enough that they are obtained from different positions in the arrays, although the actual integers are the same.

The first line of input will contain two integers $$$N$$$, $$$M$$$, $$$Q$$$, denoting the length of the arrays of integers and the number of queries. Note that $$$1 \leq N, M, Q \leq 100$$$.

The next two lines of input will contain two arrays of integers $$$a_i$$$ ($$$1 \leq i \leq N$$$, $$$1 \leq a_i \leq 10^9$$$) and $$$b_j$$$ ($$$ 1 \leq j \leq M $$$, $$$1 \leq b_j \leq 10^9$$$) - the arrays that Bob is currently infatuated with.

The next $$$Q$$$ lines will each contain an integer $$$k_i$$$, ($$$1 \leq k_i \leq 10^{18}$$$), representing the number of the subsequence from the ordering that Bob wants to see.

Print, on $$$q$$$ lines, the answer to Bob's queries, in the order that they are given. Namely, print -1 if a $$$k^{th}$$$ lexicographically ordered longest common subsequence does not exist. Otherwise, print the $$$k^{th}$$$ subsequence.

20 16 10
6 96 56 9 20 96 26 45 23 22 59 96 64 1 1 15 17 1 16 17
26 20 56 6 45 96 9 96 64 96 59 22 23 5 6 4
1
2
3
4
5
6
7
8
9
10

6 96 9 96 22 
6 96 9 96 22 
6 96 9 96 23 
6 96 9 96 23 
6 96 9 96 59 
6 96 9 96 59 
6 96 9 96 64 
6 96 9 96 64 
6 96 9 96 96 
-1 

4 5 5
1 3 2 4
2 1 4 5 3
1
2
3
4
5

1 3 
1 4 
2 4 
-1 
-1