Fie un şir a[1], a[2], …, a[n] de numere naturale, unde n este impar. Avem la dispoziţie o singură operaţie admisă şi anume: putem aduna la două poziţii diferite din şir o aceeaşi valoare naturală nenulă.

Cerința

1. Să se verifice dacă șirul poate să aibă toate elementele egale după aplicarea unei singure operații.
2. Folosind de mai multe ori operaţia admisă, să se obţină șirul cu toate elementele egale, dar valoarea egală obţinută să nu depăşească dublul valorii maxime din şirul iniţial.

Date de intrare

Fișierul de intrare perechi2.in conține pe prima linie un număr natural C, pe a doua linie numărul n, iar pe linia a treia, separate prin câte un spațiu, valorile a[1], a[2], …, a[n].

Date de ieșire

Fișierul de ieșire perechi2.out va conține:

1. Dacă C=1, atunci se va rezolva doar prima cerință, deci se va afișa pe prima linie valoarea 0 dacă nu se pot obține în șir toate elementele egale, sau se vor afișa trei numere naturale i j v cu semnificația: la pozițiile i și j din șir se adaugă valoarea v și astfel toate elementele vectorului vor deveni egale.
2. Dacă C=2, atunci se va rezolva doar a doua cerință. Pe fiecare linie a fișierului de ieșire se vor afișa exact trei valori i j v cu semnificația: se adună valoarea v la a[i] și la a[j] (unde i și j sunt distincte și sunt cuprinse între 1 și n).

Restricții și precizări

• 5 ≤ n < 2000, n este impar
• 0 ≤ a[i] ≤ 100 000 000, pentru orice i=1..n
• Elementele șirului inițial nu sunt neapărat distincte, dar nu sunt nici toate egale
• Dacă există mai multe soluții, puteți afișa oricare dintre ele.
• Dacă numărul operațiilor aplicate este mai mic sau egal decât n, iar valoarea finală este de cel mult două ori cât maximul inițial și rezultatul aplicării operațiilor furnizează în șir aceeași valoare, atunci veți primi 100% din punctaj.
• Dacă numărul operațiilor este cuprins între n+1 și 2n, iar valoarea finală este de cel mult două ori cât maximul inițial și rezultatul aplicării operațiilor furnizează în șir aceeași valoare, atunci veți primi 70% din punctaj.
• Dacă numărul operațiilor este mai mare de 2n sau dacă valoarea finală depășește dublul valorii maxime inițiale, atunci veți primi 0 puncte. De asemenea, dacă în urma operațiilor aplicate nu se obține un șir cu aceeași valoare peste tot, sau dacă aplicați o operație în care pozițiile i și j nu sunt din intervalul 1..n, atunci de asemenea veți primi 0 puncte.
• Pentru teste valorând 20 de puncte vom avea C=1. Pentru restul testelor vom avea C=2, din care pentru 30 de puncte șirul va fi format din numere distincte cuprinse între 1 și n.

Exemplu 1

perechi2.in

1
5
8 2 8 8 2

perechi2.out

2 5 6

Explicație

C=1, deci se va rezolva doar prima cerință! Adunând valoarea 6 la pozițiile 2 și 5 se va obține șirul constant 8 8 8 8 8.

Exemplu 2

perechi2.in

2
5
8 5 6 3 10

perechi2.out

1 2 2
3 4 4
2 4 3

Explicație

C=2, deci se va rezolva doar a doua cerință! Valoarea maximă din șir este 10, deci valoarea finală trebuie să fie maximum 20. Trebuie efectuate cel mult 5 operații pentru 100 puncte.

• Aplicând operația 1 2 2, obținem șirul 10 7 6 3 10
• Aplicând operația 3 4 4, obținem șirul 10 7 10 7 10
• Aplicând operația 2 4 3, obținem șirul 10 10 10 10 10

Exemplu 3

perechi2.in

1
5
8 2 7 8 2

perechi2.out

0

Explicație

C=1, deci se va rezolva doar prima cerință! Nu se poate efectua o singură operație astfel încât toate elementele șirului să devină egale.

Exemplu 4

perechi2.in

2
3
1 2 3

perechi2.out

1 3 1
1 2 2

Explicație

C=2, deci se va rezolva doar a doua cerință! Valoarea maximă din șir este 3, deci valoarea finală trebuie să fie maximum 6. Trebuie efectuate cel mult 3 operații pentru 100 puncte.

• Aplicând operația 1 3 1, obținem șirul 2 2 4
• Aplicând operația 1 2 2, obținem șirul 4 4 4

#include <bits/stdc++.h>

using namespace std;

ifstream cin("perechi2.in");
ofstream cout("perechi2.out");

int n , cer , cnt;

struct poz
{
    int val , ind;
}a[2001];

int comp(poz a , poz b)
{
    return a.val < b.val;
}

int main()
{
    cin >> cer >> n;
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i].val , a[i].ind = i;
    sort(a + 1 , a + n + 1 , comp);
    if(cer == 1)
    {
        if(a[1].val == a[2].val && a[1].val < a[3].val)
        {
            for(int i = 4 ; i <= n ; i++)
                if(a[i].val != a[i - 1].val) cnt++;
            if(cnt == 0) cout << a[1].ind << " " << a[2].ind << " " << a[3].val - a[1].val;
        }
        else cout << 0;
    }
    else
    {
        int maxi = a[n].val;
        for(int i = 1 ; i < n ; i += 2)
        {
            int A = a[i].val , B = a[i + 1].val;
            a[i].val += (maxi - A);
            a[i + 1].val += (maxi - A);
            cout << a[i].ind << " " << a[i + 1].ind << " " << maxi - A << '\n';
            maxi = a[i + 1].val;
        }
        if(maxi - a[1].val != 0)
        cout << a[1].ind << " " << a[n].ind << " " << maxi - a[1].val << '\n';
        for(int i = 2 ; i < n - 1 ; i+=2)
            if(maxi - a[i].val != 0)
            cout << a[i].ind << " " << a[i + 1].ind << " " << maxi - a[i].val << '\n';
    }
}