Revisiting the earlier subsequence puzzle at full scale, Rafid now needs FAST answers (across many queries) for the maximum GCD of any increasing subsequence of a given length. Read N integers and Q queries, each giving K. For each query, print the maximum GCD achievable over any increasing subsequence of length exactly K (or -1 if impossible). This is the FULL version of Set 10 Q5 and mirrors the hardest problem ("GCD") from your real contest — for each divisor d from high to low, run LIS DP restricted to multiples of d, and combine answers for all K in one pass.
Input
Line1: N. Line2: N integers. Line3: Q. Next Q lines: K.
Output
Q lines: max GCD for that K, or -1.
Constraints
1 ≤ N,Q ≤ 3000, 1 ≤ a_i ≤ 3000
Sample Input
5 4 8 6 12 3 2 2 4
Sample Output
4 -1
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.