### PROBLEM LINKS

### DIFFICULTY

### EXPLANATION

Let **A 1 , A 2 , …, A[N]** be an array that we should restore. Consider the sequence of partial sums **S[k]=A1+…+A[k], 0<=k<=N**. In particular, **S[0]=0**. Clearly, conditions on array **A[]** mean that

**S[Y _{i}] - S[X_{i} - 1] = Z_{i}, 1 <= i <= M. & nbsp; (*)**

Let’s build a weighted graph on numbers **0, 1, …, N,** where for each triple **(Xi, Yi, Zi)** from the input we add edges from **Xi- 1** to **Yi** with weight **Zi** and from **Yi** to **Xi-1** with weight -Zi. We consider this graph as not-oriented when talk about connectivity but weights of edges depends on direction. Then if in some connected component of this graph we set value **S[v]** for some vertex **v**, all other values of **S[]** in this component can be restored by simple DFS using equalities (*). Namely, if we are in some vertex v and the value **S[v]** is known then for each neighbor u of **v** the value **S** must be equal to **S[v]+e[v]** where **e[v]** is the weight of the edge from **u** to **v**. So if it is not known we set **S** to this value and run DFS for it. Otherwise if it is known but not equal to this value the recipe can’t be restored. This leads to a simple algorithm for restoring array **S[]**. Then array A**[]** can be restored by formulas * A=S*-S[i-1], 1<=i<=N**. The total complexity is

**O(N+M)**.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.