This is the big one — Sabbir must combine everything: for a stream of sensor values, find for every possible subsequence length the maximum GCD achievable, precomputed efficiently for all lengths at once. Read N integers and Q queries, each giving K (1 ≤ K ≤ N). For each query print the maximum GCD achievable over any strictly increasing subsequence of length exactly K, or -1 if none exists. N and Q can be up to 10^5, and a_i up to 10^5 — you must precompute answers for ALL K from 1 to N in roughly O((N + maxA) log(maxA)) or similar, not per-query O(N^2). This is a direct rebuild of the hardest problem from your original contest.
Input
Line1: N. Line2: N integers. Line3: Q. Next Q lines: K.
Output
Q lines: answer for each K.
Constraints
1 ≤ N, Q ≤ 10^5, 1 ≤ a_i ≤ 10^5
Sample Input
6 4 8 6 12 3 16 3 2 3 5
Sample Output
4 4 -1
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.