For the first subtask, the intended solution was brute force.

Time Complexity: ~\mathcal O(NQ)~

For the second subtask, we can precompute ~f(x)~ for all ~x~ in the range ~[K, K+5000]~.

Then, we can create a lazy segment tree of bitsets of size ~5001~, of which the ~i^\text{th}~ bit (~0~ indexed) of each bitset stores whether an element with value ~i+K~ exists in either of its two children (or itself if it is a leaf node). For a query, we can handle it how it would normally be handled, except when joining two bitsets, we bitwise or them together. When performing lazy propagation on a node, we can bitshift the bitset left or right depending on the lazy value (right if the lazy value is less than ~0~, and left if it is greater than ~0~).

Time Complexity: ~\mathcal O(\frac{5000Q\log N}{\text{bitset constant}} + 5000K)~

For the third subtask, we can use some mathematical insight. Using Wilson's theorem, the function ~f(x)~ reduces to ~x~ if ~x~ is prime, or ~-1~ otherwise. To precompute ~f(x)~, we can use a segmented sieve to generate the primes in the range ~[K, K+5000]~. The rest is the same as subtask 2.

An alternative method of precomputing ~f(x)~ is to run the Miller-Rabin primality test for all ~x~ in the range ~[K, K+5000]~.

Time Complexity: ~\mathcal O(\frac{5000Q\log N}{\text{bitset constant}} + \sqrt K \log \log \sqrt K)~ or ~\mathcal O(\frac{5000Q\log N}{\text{bitset constant}} + 5000 \log^3 K)~