Rekonstruisati niz ako su poznate sume elemenata nekih njegovih podnizova uzastopnih elemenata. Pri tom treba poštovati sledeća ograničenja:

• Svi elementi niza moraju biti celi brojevi, po apsolutnoj vrednosti ne veći od 10⁹.
• Za maksimalan broj poena, svi elementi niza moraju biti pozitivni. Ukoliko se u nizu nađe broj koji je manji ili jednak od 0, dobijate 40% poena na tom primeru.

Uvek će postojati bar jedno rešenje sa svim pozitivnim brojevima. Ukoliko postoji više rešenja, možete ispisati bilo koje.

Ulaz.

(Ulazni podaci se učitavaju iz datoteke podnizovi.in.) U ulaznoj datoteci se u prvom redu nalaze dva broja N i Q (1 ≤ N ≤ 1000, Q ≤ N(N -1)/2), broj elementata niza, i broj poznatih suma podnizova. U sledećih Q redova se nalaze po tri broja L, R i S koja označavaju da je suma od L-tog do R-tog elementa u nizu (uključujući ova dva elementa) jednaka S (1 ≤ L < R ≤ N, 1 ≤ S ≤ 10¹²).

Izlaz.

(Izlazni podaci se ispisuju u datoteku podnizovi.out.) Ispisati rekonstruisan niz u jednom redu izlazne datoteke. Elemente odvojiti jednim razmakom.

Primer 1.

5 3
1 3 9
3 4 10
1 5 100

3 1 5 5 86

Objašnjenje. Poznato je da je suma prvog, drugog i trećeg elementa niza jednaka 9, suma trećeg i četvrtog jednaka 10 i suma svih elemenata jednaka 100. Jedan od nizova sa celo- brojnim pozitivnim članovima koji zadovoljava ovo je 3 1 5 5 86 (3 + 1 + 5 = 9, 5 + 5 = 10, 3 + 1 + 5 + 5 + 86 = 100).

Napomena.
U 40% test primera je 1 ≤ N ≤ 100.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <cstring>

using namespace std;

#define sz size()
#define pb push_back
#define len length()
#define clr clear()
#define FOR(i,a,b) for(i=a;i<b;i++)
#define FORR(i,n) for(i=0;i<n;i++)
#define is_digit(c) ('0'<=(c) && (c)<='9')

#define eps 0.0000001
#define PI  3.14159265359
#define inf 1999888777

long long n,px,x[1555],r[1555],u[15555],v[15555],w[15555],z[1555],pz[1555],d[1555],pocx[1555];
vector<long long> adj[1555],adjw[1555];

void dfs(long long t) {

    long long i,l,y,w;

    l = adj[t].sz;
    for(i=0; i<l; i++) {
        y = adj[t][i];
        w = adjw[t][i];
        if (x[y] == -1) {
            r[y] = r[t] + w;
            x[y] = px;
            dfs(y);
        }
    }

}

int main() {

    FILE *ff = fopen("podnizovi.in", "r"), *gg = fopen("podnizovi.out", "w");

    long long q,i,s,m,g,j,pu,pv,pw,raz,left,right;

    fscanf(ff,"%lld%lld", &n, &q);

    n++;
    for(i=0; i<n; i++) {
        adj[i].clr;
        r[i] = 0;
        x[i] = -1;
    }

    for(i=0; i<q; i++) {
        fscanf(ff,"%lld%lld%lld", &left, &right, &s);

        adj[right].pb(left-1);
        adjw[right].pb(-s);

        adj[left-1].pb(right);
        adjw[left-1].pb(s);
    }

    m = 0;
    for(i=0; i<n; i++) if (x[i] == -1) {

        r[i] = 0;
        x[i] = i;
        px = i;
        m++;
        z[i] = m;
        pz[m] = i;

        dfs(i);
    }

    g = 0;
    for(i=1; i<n; i++) {
        v[g] = z[ x[i-1] ];
        u[g] = z[ x[i] ];
        w[g] = r[i] - r[i-1] - 1;

        //pxi > pxi-1 => pxi >= pxi-1   =>
        //Pxi - Pxi-1 < 10^9
        //Zx_i + r_i - Zx_i-1 - r_i-1 < 10^9
        //Zx_i - Zx_i-1 <= 10^9 - r_i + r_i-1 - 1

        if (u[g] == v[g]) {
            continue;
        }
       
        g++;

        u[g] = z[ x[i-1] ];
        v[g] = z[ x[i] ];
        w[g] = 1000000000 + r[i-1] - r[i];
        g++;
    }

    for(i=1; i<=m; i++) {
        u[g] = 0;
        v[g] = i;
        w[g] = 0;
        g++;

        d[i] = inf;
    }

    d[0] = 0;

    for(i=0; i<=m; i++) {
        for(j=0; j<g; j++) {
            pu = u[j];
            pv = v[j];
            pw = w[j];
            if ( d[pv] > d[pu] + pw ) {
                d[pv] = d[pu] + pw;
            }
        }
    }

    raz = d[1];
    for(i=1; i<=m; i++) {
        pocx[pz[i]] = d[i] - raz;
    }

    for(i=1; i<n; i++) {
        fprintf(gg,"%lld ", (pocx[x[i]] + r[i]) - (pocx[x[i-1]] + r[i-1]));
    }
    fprintf(gg,"\n");

    fclose(ff); fclose(gg);

    return 0;
}