Diamonds P75018


Statement
 

pdf   zip

html

A very rich prince has exactly n diamonds. Each diamond 1 ≤ in has a certain value vi. Tradition says that, before getting married, the prince has to give a present of value exactly V to his princess. The prince wants to give her exactly two of his diamonds, but he does not know how to decide quickly if he can do it or not. Can you help to this stupid?

For instance, if n=6 and the value of the diamonds is 5, 8, 6, 2, 6, 20, then it is possible to give a present of value V=10 (8+2) or a present of value V=12 (6+6), but it is impossible to give a present of value V=9.

Input

Input consists of several cases. Each case begins with the gift value V (a natural number between 1 and 108) and the number n of diamonds (a natural number between 1 and 105) in this order. Then come n natural numbers between 1 and 108 indicating the value of each diamond. A case with V = n = 0 marks the end of the input.

Output

For each case, print a line with “married” or “single” depending on whether the prince can give the present or not.

Public test cases
  • Input

    12 6
    5 8 6 2 6 20
    9 6
    5 8 6 2 6 20
    0 0
    

    Output

    married
    single
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan Spanish
    Official solutions
    C++
    User solutions
    C++ Java