CSES - Jättipizza
  • Time limit: 2.00 s
  • Memory limit: 512 MB

Sukukokouksen jälkeen Uolevin sukulaiset menevät tänä vuonna pizzeriaan. He tilaavat yhden jättipizzan, josta riittää syötävää kaikille. Ongelmana on kuitenkin, että kaikki eivät pidä samoista täytteistä.

Ennen pizzan tilausta Uolevi järjesti äänestyksen, jossa sukulaiset pystyivät vaikuttamaan pizzan täytteisiin. Jokaisella sukulaisella oli käytettävissä kaksi ääntä muotoa "täyte x on hyvää/pahaa".

Tehtäväsi on valita pizzan täytteet niin, että jokainen sukulainen on tyytyväinen. Sukulainen on tyytyväinen, jos pizzaan tulee jokin täyte, josta hän pitää, tai jos pizzaan ei tule jotain täytettä, josta hän ei pidä.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: täytteiden määrä ja sukulaisten määrä. Täytteet on numeroitu kokonaisluvuin 1,2,\ldots,n.

Sitten syötteessä on m riviä, joista jokainen kertoo, miten tietty sukulainen äänesti. Rivi muodostuu kahdesta äänestä, joissa on ensin merkki + (hyvää) tai - (pahaa) ja sitten täytteen numero.

Tuloste

Ohjelmasi tulee tulostaa yksi mahdollinen tapa valita täytteet. Jos täyte tulee pizzaan, sen kohdalle kuuluu merkki +, ja muuten merkki -.

Jos kaikkia tyydyttävä täytteiden valinta ei ole mahdollista, ohjelmasi tulee tulostaa vain QAQ.

Rajat

  • 1 \le n \le 5 \cdot 10^4
  • 1 \le m \le 5 \cdot 10^4

Esimerkki

Syöte:

4 3
+ 1 + 2
+ 4 - 1
- 1 - 2

Tuloste:

- + + +

Selitys: Pizzaan valitaan täytteet 2, 3 ja 4. Sukulainen 1 on tyytyväinen, koska hän pitää täytteestä 2. Sukulainen 2 on tyytyväinen, koska hän sekä pitää täytteestä 4 että inhoaa täytettä 1. Sukulainen 3 on tyytyväinen, koska hän inhoaa täytettä 1.