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?
You will be given $n$ ($0 ≤ n ≤ 10^5$) on the first line which is the number of elements in the array. Then you will be given an array of $n$ elements, $arr$ ($0 ≤ arr[i] ≤ 10^5$) on the second line. And then in the next line, the number of queries $q$ ($0 ≤ q ≤ 10^5$). For each query, you will be given $l$ and $r$ ($1 ≤ l ≤ r ≤ n$), the range.
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!"
Input | Output |
---|---|
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. |
Input | Output |
---|---|
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.