Difference Basics

Points 100 1.0s 256M

You are given a sequence of nonnegative integers \(a_1, a_2, \ldots, a_N\) of length \(N\).

There are \(Q\) operations. The \(i\)-th operation is described by three positive integers \(L_i, R_i, b_i\) and adds \(b_i\) to every element in the range \([L_i, R_i]\).

After performing all operations, output the final sequence \(a\).

Input

The first line contains two integers \(N\) and \(Q\).

The second line contains \(N\) nonnegative integers \(a_1, a_2, \ldots, a_N\).

Each of the next \(Q\) lines contains three integers \(L_i, R_i, b_i\), describing one operation.

Constraints

  • \(1 \le N, Q \le 2 \times 10^5\)
  • \(0 \le a_i \le 10^4\)
  • \(1 \le b_i \le 10^4\)
  • \(1 \le L_i \le R_i \le N\)

Output

Output a single line containing \(N\) integers: the sequence \(a\) after applying all \(Q\) operations.

Scoring

There are two subtasks. Each subtask contains multiple test cases, and you earn the subtask's score only if you solve all of its tests.

  • Subtask \(1\) (60 points): \(a_i = 0\) for all \(i\).
  • Subtask \(2\) (40 points): no additional constraints.

Sample Input 1

5 3
0 0 0 0 0
1 4 2
2 3 1
3 5 4

Sample Output 1

2 3 7 6 4

Sample Input 2

4 2
2 0 4 8
1 3 1
3 4 1

Sample Output 2

3 1 6 9

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.