For the marquee hardest problem, Wasif combines two classic ideas into one: querying both the max GCD of a length-K increasing subsequence, and the max pairwise-difference sum for a size-X team, all in a single problem. Given N integers, answer Q queries of two types: type 1 "K" — print the maximum GCD over any increasing subsequence of length K (as in Set 18 Q5); type 2 "X" — print the maximum sum of pairwise |differences| for a chosen team of size X (as in Set 15 Q3). This directly recreates having to solve BOTH of your original contest's hardest problems (H and J) under one time budget.
Input
Line1: N. Line2: N integers. Line3: Q. Next Q lines: "1 K" or "2 X".
Output
Q lines: the requested answer per query.
Constraints
1 ≤ N,Q ≤ 10^5, 1 ≤ a_i ≤ 10^5
Sample Input
5 4 8 6 12 3 2 1 3 2 2
Sample Output
4 9
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.