Diamants P75018

Un príncep molt ric té n diamants. Cada diamant 1 ≤ i ≤ n té un cert valor v_i. La tradició mana que, abans de casar-s’hi, el príncep faci un regal de valor exactament V a la seva princesa. El príncep vol regalar-li exactament dos dels seus diamants, però no sap com decidir ràpidament si pot fer-ho o no. Podeu ajudar aquest tanoca?

Per exemple, si n=6 i el valor dels diamants és 5, 8, 6, 2, 6, 20, llavors és possible fer un regal de valor V=10 (8+2) o bé un regal de valor V=12 (6+6), però no és possible fer un regal de valor V=9.

Entrada

L’entrada consisteix diversos casos. Cada cas comença amb el valor V del regal (un natural entre 1 i 10⁸) i el nombre n de diamants (un natural entre 1 i 10⁵) en aquest ordre. Després vénen n naturals entre 1 i 10⁸ indicant el valor de cada diamant. Un cas amb V = n = 0 marca el final de l’entrada.

Sortida

Per a cada cas, escriviu una línia amb “married” o bé “single” segons si el príncep pot fer el regal o no.