Under construction

Still being built. Things may change

Taesang's Training Camp Life

Interview

Time limit1sMemory limit512 MB

Summary
Apply M range updates that add a signed value to each cell in a range, then print every final cell height.
Level

Easy3 of 10

Topics
Prefix sum, Array, Implementation
Solved
No attempts yet

Problem

Taesang enlisted at the Nonsan training camp on May 14, 2020, and made a serious mistake during his first firearms training: he lost the gas regulator. Because of this, the instructors began to glare at him. They give Taesang the job of moving dirt on the parade ground and plan to discipline him if he fails to do it properly.

The parade ground consists of N cells in a row, each with a height, numbered 1, 2, 3, ..., N from the first cell onward. There are M instructors in total, and each instructor orders Taesang to either cover or dig out dirt by a height of k over the cells from a to b. Dirt can be obtained in unlimited amounts from the nearby mountains, so it never runs out.

Taesang realized that carrying out each instructor's order separately leads to inefficient work, such as digging out cells that another instructor's order had already covered with dirt. So he plans to gather all the instructors' orders, compute the final height of each parade ground cell in advance, and do the work all at once.

For poor Taesang, find the height of each parade ground cell after carrying out all of the instructors' orders.

Input

The first line gives the size of the parade ground N and the number of instructors M.

The second line gives the heights Hi of the parade ground cells in order, N of them.

From the third line onward, M lines give each instructor's order.

Each instructor's order consists of three integers a, b, k.

  • If k ≥ 0, dirt must be covered so that the height of each cell from a to b increases by |k|.
  • If k < 0, dirt must be dug out so that the height of each cell from a to b decreases by |k|.

Output

After carrying out all the orders, print the height of each parade ground cell, separated by spaces.

Constraints

  • 1 ≤ N ≤ 100,000

  • 1 ≤ M ≤ 100,000

  • -10,000 ≤ Hi ≤ 10,000

  • N, M, and Hi are integers

  • Each instructor's order

    • 1 ≤ a ≤ b ≤ N
    • |k| ≤ 100

Examples1

  1. Example 1

    Input
    10 3
1 2 3 4 5 -1 -2 -3 -4 -5
1 5 -3
6 10 5
2 7 2
    Expected output
    -2 1 2 3 4 6 5 2 1 0