A Tale of Peter, Paul and Mary P52993

MOCW (Massive Online Collaborative Writing) is not only a recent Internet success, but it is also really trendy, as well as a potentially profitable business for IT start-ups. The site recently published the book A Tale of Peter, Paul and Mary, written by 200 registered users, and reported a record of several million euro earnings from its sales in the first month.

In MOCW, registered users write independent passages, which are ranked by other users. From that, each passage is assigned an economical value. Eventually, the site chooses a sequence of passages as the final book, and sets its price to the sum of prices of the passages.

Because of this writing process, the style of MOCW books has nothing to do with that of traditional books. Anyone who read A Tale of Peter, Paul and Mary remembers the memorable passages of Peter’s struggle for love: How Peter leaves his job as a consultant to join an amateur pétanque team after meeting Mary, engaged to the evil Petankemeister Paul, and how, following a breathtaking plot including Saracen and Mongol fleet attacks, the Ark of the Covenant, dragon Smaug, a Vatican conspiracy and Chuck Norris, at last Peter manages to beat Paul at the final of the Pétanque World Championship, save the world and free Mary—who has completely fallen for him—from his rival, who has taken her as a hostage after commanding a Martian invasion to the Earth.

Unfortunately, for the consistency of the story, many other memorable passages had to be discarded, because Paul could not die in all the 183 ways that the writers had imagined. So the editors were strict in the fact that once a character was dead, he could not appear in the story any more. Moreover, time consistency was important: two passages could not happen at the same time, and there should be no time gaps in which nothing was happening.

After the success of A Tale of Peter, Paul and Mary, the board of wants to devise an automatic system for building the final books out of the available passages. The idea is (as usual) to find the plot that will give the highest priced book, but without forgetting about story consistency. Will the IT crowd of manage to do it, or will be a one-hit wonder of online publishing?

Input

Input consists of several cases. Every case begins with three natural numbers giving the time span of the story 1 ≤ T ≤ 100, the number of characters 1 ≤ C ≤ 100, and the number of passages 1 ≤ P ≤ 10⁴. The end of the input is signaled by three zeros.

Next come the information for each of the P passages: its start time s_i, its end time e_i, its price 0 ≤ p_i ≤ 10⁶, and a string of length C with the alive or dead status of each character: the jth character is ‘L’ or ‘+’ according to whether the jth character is alive or dead in that passage. Assume 0 ≤ s_i < e_i ≤ T.

Output

For every case, if a consistent plot can be found, print “Good, $”, followed by the highest price that can be achieved. Otherwise, print “Bad”. A plot is consistent if every moment from 0 to T is covered by exactly one passage, and if no character that is dead in a passage is alive in a later passage.

Observation

The private test cases for this problem were generated at random.