链接: https://cses.fi/problemset/task/3294

板块: Additional Problems I

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你的任务是构造一个由 $n$ 个整数组成的数组 $x_1,x_2,\dots,x_n$。

该数组必须满足 $m$ 个形如 $(l,r,s)$ 的约束：和 $x_l + x_{l+1} + \dots + x_r$ 必须等于 $s$。

输入

第一行包含两个整数 $n$ 和 $m$：数组的长度和约束的数量。

接下来的 $m$ 行每行包含三个整数 $l$、$r$ 和 $s$：约束的描述。

输出

如果存在解，在第一行输出 YES。

在第二行，输出 $n$ 个整数 $x_1, x_2,\dots, x_n$：数组的内容。数组的所有元素必须满足 $-10^{15} \le x_i \le 10^{15}$，且数组必须满足所有给定的约束。你可以输出任意有效解。

如果不存在解，只输出 NO。

数据范围

$1 \le n \le 5000$ $0 \le m \le 2 \cdot 10^5$ $1 \le l \le r \le n$ $-10^9 \le s \le 10^9$

样例输入

5 3
1 3 3
3 5 3
4 4 -1

样例输出

YES
0 2 1 -1 3