Sequence Sorting Queries

Time limit1sMemory limit128 MB

Summary
Given a sequence, each query sorts it, adds X to the elements at positions L through R, and sorts again; output the final sorted sequence.
Level

Medium6 of 10

Topics
Sorting, Implementation, Prefix sum, Greedy
Solved
No attempts yet

Problem

Jihun is playing with a sequence of NN numbers. He applies KK queries to it, in the order they are given.

A query LL RR XX is processed like this.

  1. Sort the sequence in ascending order and call the result A1,A2,…,ANA_1, A_2, \dots, A_N.
  2. Add XX to each of AL,AL+1,…,ARA_L, A_{L+1}, \dots, A_R.
  3. Sort the changed sequence in ascending order again.

Print the sequence after every query has been applied.

Input

The first line contains NN and KK, separated by a space. (1≤N≤100 0001 \le N \le 100\,000, 1≤K≤1 0001 \le K \le 1\,000)

The second line contains the NN integers of the sequence, separated by spaces. Each integer has absolute value at most 101810^{18}.

Each of the next KK lines contains one query LL RR XX. (1≤L≤R≤N1 \le L \le R \le N, ∣X∣≤109|X| \le 10^9)

Output

Print the sequence after every query has been applied, in ascending order, on one line. Put exactly one space between two adjacent numbers.

Examples7

  1. Example 1

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

  2. Example 2

    Input
    1 1
-1000000000000000000
1 1 -1000000000
    Expected output
    -1000000001000000000

  3. Example 3

    Input
    5 1
5 -3 0 12 -7
2 4 0
    Expected output
    -7 -3 0 5 12

  4. Example 4

    Input
    8 2
4 4 4 4 4 4 4 4
1 4 -2
5 8 3
    Expected output
    2 2 2 2 7 7 7 7

  5. Example 5

    Input
    6 2
-5 -1 0 3 8 100
1 6 -1000000000
1 6 1000000000
    Expected output
    -5 -1 0 3 8 100

  6. Example 6

    Input
    3 1000
1000000000000000000 999999999999999999 999999999999999998
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
    Expected output
    1000000999999999998 1000000999999999999 1000001000000000000

  7. Example 7

    Input
    12 10
-5 -1 -14 5 10 -11 -15 -16 -19 5 15 -2
1 4 1
5 7 -7
5 8 -7
11 12 1
4 6 1
5 10 -7
10 11 9
9 10 -1
4 11 1
2 10 1
    Expected output
    -22 -20 -20 -18 -17 -16 -15 -13 -1 8 17 20