Uolevilla ja Maijalla on n omenaa. Tiedät jokaisen omenan painon ja haluat jakaa omenat mahdollisimman tasaisesti.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: omenoiden määrä.

Seuraavalla rivillä on n kokonaislukua p_1,p_2,\ldots,p_n: kunkin omenan paino.

On olemassa ainakin yksi tapa jakaa omenat niin, että Uolevin ja Maijan saamien omenoiden yhteispainot ovat samat.

Tuloste

Ohjelmasi tulee tulostaa jokaisesta omenasta, meneekö se Uoleville (1) vai Maijalle (2).

Esimerkki

Syöte:

3
4 9 5

Tuloste:

1 2 1

Rajat

• 1 \le n \le 100
• 1 \le p_i \le 10^9

Pisteytys

Ohjelmasi saa jokaisesta testistä pisteitä \max(\lfloor 100-10 \cdot log_{10}(d+1) \rfloor,0), missä d on Uolevin ja Maijan saamien omenoiden yhteispainojen ero.

Tehtävän pistemäärä on testien pistemäärien keskiarvo.