SAS003 - Apoorv Loves Primes

Given two arrays A and B of size n and x. Apoorv is given an empty array P. He has to fill the array according to the following conditions:

for each i in range (0 to x-1) {
    if b[i] is negative
        (insert the subarray from A[abs(B[i]] to A[n-1] in P at the end)
    else
        (insert the subarray from A[0]to A[B[i]] in P at the end)
}

Since Apoorv loves Prime numbers He wants to know the Kth prime number in P after the above operation is completed.

So given q queries Apoorv has to report the kth prime number in it. If kth prime doesn't exist print -1.

Note: Both A and B are 0 indexed. abs stands for absolute value.

Constraints:

1<=n<=100000

1<=x<=100000

1<=A[i]<=1000000

0<=abs(B[i])<=n-1

1<=q<=10000

1<=k<=10000000000

Input

First line will contain n size of A.

Second line will contain n space separated integers denoting A[i].

Third line will contain x denoting size of B.

Fourth line will containĀ x space separated integers denoting B[i].

Fifth line will contain q denoting number of queries.

Sixth line will contain q space separated integers denoting k.

Output

Print q lines denoting output for each query.

Example

Input:
3
2 3 4
1
2
3
1 2 3

Output:
2
3
-1
Explanation:

P is [2,3,4] so for k=1 answer is 2, for k=2 answer is 3, for k=3 answer=-1 because 3rd prime number doesn't exist.


Added by:sas1905
Date:2018-06-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Other Contest.

hide comments
2019-06-06 10:06:06 Sushovan Sen
@sas1905 Can you please tell where my solution is failing?

Last edit: 2019-06-06 10:14:07
2018-06-18 14:09:51
Nice One SAS!!
2018-06-09 22:07:35
Mehmet, try this:
10
2 3 4 5 8 10 11 12 13 14
5
2 -1 -2 1 3
15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Output (onelined to save space):
2 3 3 5 11 13 5 11 13 2 3 2 3 5 -1
2018-06-09 18:04:28 mehmetin
We have to find kth prime in array p according to insertion order or according to index of ordered primes?

Re: You just need to find the kth prime present in array P after processing all B[i] for i 0 to x-1 and completing all the steps.

Last edit: 2018-06-09 21:36:47
2018-06-06 23:57:38
Is it meant to be solvable with Python, Sasmit? My mem use is quite disturbing but the non-O(1)-answers approach will TLE for sure. Please increase the limit slightly if I'm following the right path.

RE:Thanks for the typos they are corrected.I have increased the time limit to 2s from 1s but I have checked your code for 10s as well it is getting timed out.I think approach is not the same as intended.

[NG]: I misjudged the worst case performance for each algo. The other one flies! Bonus: AC in pure Python also possible. Very nice problem, thank you.

RE:Thank you for attempting and liking the problem..:)

Last edit: 2018-06-10 09:20:51
2018-06-06 14:18:37
Two comments: the code in the statement would probably look better pre-formatted. The constraints on B[i] are actually 0 <= abs(B[i]) <= n-1.

RE:Done.Thanks for pointing out.

Last edit: 2018-06-06 19:22:31
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.