Diamants P75018

Un príncep molt ric té $n$ diamants. Cada diamant $1 \le i \le 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^8$) i el nombre $n$ de diamants (un natural entre 1 i $10^5$) en aquest ordre. Després vénen $n$ naturals entre 1 i $10^8$ 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.