Submit | All submissions | Best solutions | Back to list |
NITK07 - THE INDIAN OCEAN |
Salim is a part of THE INDIAN OCEAN BAND. Each musician of the band has already decided what sound will he play (for the sake of simplicity we assume each musician plays only one sound). We say two sounds are in harmony if the frequency of any one of them divides the frequency of the other (that's a pretty restrictive idea of harmony, but THE INDIAN OCEANS are known to be very conservative in music). Salim knows that the notes played by other players are not necessarily in harmony with each other. He wants his own note to improve the music, so he wants to choose his note so that it is in harmony with the notes all the other musicians play.
Now, this sounds simple (as all the frequencies are positive integers, it would be enough for Salim to play the note with frequency 1, or, from the other side, the Least Common Multiple of all the other notes), but unfortunately Salim's instrument has only a limited range of notes available. Help Salim find out if playing a note harmonious with all others is possible.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case is described by two lines. The first contains three numbers: N, L and H, denoting the number of other players, the lowest and the highest note Salim's instrument can play respectively. The second line contains N integers denoting the frequencies of notes played by the other players.
1 ≤ T ≤ 40.
1 ≤ N ≤ 104.
1 ≤ L ≤ H ≤ 1016.
All the frequencies are no larger than 1016.
Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is either the string "NO" (if Salim cannot play an appropriate note), or a possible frequency. If there are multiple frequencies Salim could play, output the lowest one.
Example
Input: 3 3 2 100 3 5 7 4 8 16 1 20 5 2 2 5 10000000000000000 9999999999999606 9999999999999822 Output: Case #1: NO Case #2: 10 Case #3: 6
Added by: | Gaurav Jain |
Date: | 2013-09-26 |
Time limit: | 1s-60s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |