Birthday Surprise

Farhan_meb Fun Contest
Limits 1s, 256 MB

Adnan bhai, Priyom dada and Shuvo bhai are the members of MU_Kheloars. They recently got graduated and did a lot for our ACM  family. Now it’s your turn to help them finding a good job. Their birthdays are very near and guess what? All the member's birthday is on the same day. What a coincidence, right?

We want to surprise them on their birthday. Since all three of them were born on the same day, they like only prime numbers  and they will only join an IT Firm if and only if it's rank is a prime number. If I tell you a secret about them, they like a girl! yeah  three of them want her so bad and her name is “Sokina Khatun”. For this reason, they want to join different company to impress her, which means if one joins a firm, two other won't join this firm.

In this problem, you will given an array of n elements and number of query q. In each query you will be given a range, the summation  of the range is an IT Firm's rank. So, if it is a prime number then we can gift this firm to any of them on their birthday. If we have enough firms  with prime rank, we can gift all three of them. If they get a job, the secret girl will be happy. So can you help them on behalf of ACM family of  our university?   

Input

You will be given nn (0n1050 ≤ n ≤ 10^5) on the first line which is the number of elements in the array. Then you will be given an array of nn elements, arrarr (0arr[i]1050 ≤ arr[i] ≤ 10^5) on the second line. And then in the next line, the number of queries qq (0q1050 ≤ q ≤ 10^5). For each query, you will be given ll and rr (1lrn1 ≤ l ≤ r ≤ n), the range.

Output

If we can gift only one of them, you have to print "Sokina Khatun will be very happy!" with a new line. If we can gift only two of them,  you have to print "Sokina Khatun will be very very happy!" with a new line. And if we can make all three of them happy, you have to  print "Sokina Khatun will be very very very happy!" with a new line. Else print "Adnan bhai, Priyom dada, Shuvo bhai will forever be single!"   

Samples

InputOutput
5 
1 3 4 7 2
3
1 2
2 3
3 5
Sokina Khatun will be very very happy!

In range [2, 3] we get (3 + 4) = 7, which is a prime number. In range [3, 5] we get (4 + 7 + 2) = 13, which is a prime number. So, we can make only two of them happy.

InputOutput
5
1 3 4 7 2
3
1 2
1 2
1 2
Adnan bhai, Priyom dada, Shuvo bhai will forever be single!

Prime number: a number that is divisible only by itself and 1.

Submit

Login to submit.

Statistics

71% Solution Ratio
Farhan_mebEarliest, Jul '19
BalchalFastest, 0.0s
emrul_muLightest, 524 kB
ShafahidShortest, 741B
Toph uses cookies. By continuing you agree to our Cookie Policy.