== include(page="template/taskheader" task_id="pari") ==

Poveste şi cerinţă...

Se consideră un şir $S$ de $n$ numere întregi şi un alt şir de lungime $n$ format din cuvintele $par$, respectiv $impar$. Numerele din şir trebuie transformate conform regulilor de mai jos, astfel încât fiecare număr să devină de paritatea indicată:
 
* se alege o pereche de indici $(i, j)$ astfel încât $i$ şi $j$ să fie de parităţi diferite şi cel mai mare divizor comun al lor să fie mai mare sau egal cu un număr natural $d$ dat.
* numerelor $S{~i~}$ şi $S{~j~}$ li se adună un număr întreg oarecare.
 
h2. Cerinţă
 
Determinaţi calea de transformare a şirului dat conform operaţiilor din enunţ.

h2. Date de intrare

Fişierul de intrare $pari.in$ ...

Pe prima linie a fişierului de intrare $PARI.IN$ se află două numere naturale $n$ şi $d$, reprezentând numărul de elemente ale şirului $S$ şi valoarea minimă a celui mai mare divizor comun. Pe următoarele $n$ linii se găsesc câte un număr întreg, un spaţiu şi un cuvânt, cuvânt ce poate fi $par$, respectiv $impar$, reprezentând paritatea ce trebuie să o aibă numărul.

h2. Date de ieşire

În fişierul de ieşire $pari.out$ ...

În fişierul de ieşire $PARI.OUT$ se vor scrie pe câte un rând operaţiile aplicate asupra şirului. O operaţie este reprezentată de trei numere $i$, $j$, $k$, unde $i$ şi $j$ indică perechea de indici, iar $k$ valoarea care se adună la numerele din şir de pe poziţiile $i$ şi $j$. Cele trei numere se vor despărţi prin câte un spaţiu. Dacă nu există soluţie, în fişierul de ieşire se vor scrie trei numere $0$, despărţite prin câte un spaţiu.
 

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ n ≤ 1 000$
* $1 ≤ d ≤ 1 000$
* $1 ≤ S{~i~} ≤ 30 000, i = 1, 2, .., n$
* Se garantează că numărul total de perechi care se pot forma nu depăşeşte $10 000$.
* În cazul în care exisă mai multe soluţii se cere una singură.

h2. Exemplu
table(example). |_. pari.in |_. pari.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

| 5 1
8 par
10 par
7 par
6 impar
7 impar
| 3 4 -3
|

== include(page="template/taskfooter" task_id="pari") ==