Perfect Harmony (Small)
InterviewTime limit5sMemory limit512 MB
Pick the smallest frequency between L and H that divides or is divided by every given frequency, or report NO.
- Level
Easy3 of 10
- Topics
- Number theory, Brute force
- Solved
- No attempts yet
Problem
Jeff plays in the great Atlantean orchestra. Every player has already decided which sound to play, and for simplicity each player plays exactly one sound. Two sounds are in harmony when the frequency of one of them divides the frequency of the other. That is a restrictive idea of harmony, but the Atlanteans are known to be conservative about music. The notes chosen by the other players are not necessarily in harmony with each other. Jeff wants his own note to improve the symphony, so he wants to choose a note that is in harmony with the notes of all the other players.
This sounds simple. All the frequencies are positive integers, so Jeff could play the note with frequency 1, or, from the other side, the least common multiple of all the other notes. Unfortunately Jeff's instrument covers only a limited range of notes. Decide whether Jeff can play a note that is in harmony with all the others.
Input
The first line contains the number of test cases . test cases follow, and each test case is described by two lines. The first line contains three integers , and , where is the number of other players and and are the lowest and the highest frequency Jeff's instrument can play. The second line contains the frequencies of the notes played by the other players.
Limits
- Every frequency is a positive integer no larger than 10000.
Output
For each test case, print one line in the form Case #x: y. Here is the case number starting from 1, and is either the string NO when Jeff cannot play an appropriate note, or a frequency he can play. When several frequencies work, print the lowest one.