Διανομή γλυκών (candies)

Η θεία Khong ετοιμάζει ~n~ κουτιά με γλυκά για τους μαθητές ενός σχολείου. Τα κουτιά είναι αριθμημένα από ~0~ έως ~n~ - ~1~ και αρχικά είναι άδεια. Το ~i~-οστό κουτί ( ~0~ ~\le~ ~i~ ~\le~ ~n~ - ~1~) χωράει ~c~[~i~] γλυκά.

Η θεία Khong αφιερώνει ~q~ ημέρες για την προετοιμασία των κουτιών. Την ~j~-οστή ημέρα (~0 \le j \le q - 1~), εκτελεί μια ενέργεια που καθορίζεται από τρείς ακέραιους ~l~[~j~], ~r~[~j~] και ~v~[~j~], όπου ~0 \le l[j] \le r[j] \le n - 1~ και ~v~[~j~] ~\ne~ ~0~. Για κάθε κουτί ~k~ για το οποίο ισχύει ~l[j] \le k \le r[j]~:

• Αν ~v[j] > 0~, η θεία Khong προσθέτει γλυκά στο κουτί ~k~, ένα-ένα, μέχρι να έχει προσθέσει ακριβώς ~v[j]~ γλυκά ή να γεμίσει το κουτί. Δηλαδη, αν το κουτί είχε προηγουμένως ~p~ γλυκά, μετά την ενέργεια αυτή θα έχει min~(c[k], p + v[j])~ γλυκά.

• Αν ~v[j] < 0~, η θεία αφαιρεί γλυκά από το κουτί ~k~, ένα-ένα, μέχρι να έχει αφαιρέσει ακριβώς -~v[j]~ γλυκά ή να αδειάσει το κουτί. Δηλαδή, αν το κουτί είχε προηγουμένως ~p~ γλυκά, μετά την ενέργεια αυτή θα έχει max(~0, p + v[j]~) γλυκά.

Βρείτε το πλήθος των γλυκών σε κάθε κουτί μετά από τις ~q~ ημέρες.

Λεπτομέρειες υλοποίησης

Πρέπει να υλοποιήσετε την παρακάτω συνάρτηση: int[] distribute_candies(int[] c, int[] l, int[] r, int[] v)

• ~c~: ένας πίνακας μήκους ~n~. Για ~0 \le i le n - 1~, το ~c[i]~ παριστάνει τη χωρητικότητα σε γλυκά του κουτιού ~i~.
• ~l~, ~r~ και ~v~: τρείς πίνακες μήκους ~q~. Την ~j~-οστή ημέρα, για ~0 \le j \le q - 1~, η θεία Khong εκτελεί μια ενέργεια που καθορίζεται από τους ακέραιους ~l[j]~, ~r[j]~ και ~v[j]~, όπως περιγράφεται παραπάνω.
• Η συνάρτηση αυτή θα πρέπει να επιστρέφει έναν πίνακα μήκους ~n~. Ας ονομάσουμε αυτόν τον πίνακα ~s~. Για ~0 \le i \le n - 1~, η τιμή του ~s[i]~ θα πρέπει να είναι το πλήθος των γλυκών στο κουτί ~i~ μετά από τις ~q~ ημέρες.

Παραδείγματα

Παράδειγμα 1

Έστω η ακόλουθη κλήση:

distribute_candies([10, 15, 13], [0, 0], [2, 1], [20, -11])

Αυτό σημαίνει ότι το κουτί ~0~ χωράει ~10~ γλυκά, το κουτί ~1~ χωράει ~15~ γλυκά, και το κουτί ~2~ χωράει ~13~ γλυκά.

Στο τέλος της ημέρας ~0~, το κουτί ~0~ έχει min(~c[0], 0 + v[0]~) = ~10~ γλυκά, το κουτί ~1~ έχει min(~c[1], 0 + v[0]~) = ~15~ γλυκά και το κουτί ~2~ έχει min(~c[2], 0 + v[0]~) = ~13~ γλυκά.

Στο τέλος της ημέρας ~1~, το κουτί ~0~ έχει max(~0, 10 + v[1]~) = ~0~ γλυκά, το κουτί ~1~ έχει max(~0, 15 + v[1]~) = ~4~ γλυκά. Εφόσον ~2 > r[1]~, δεν υπάρχει αλλαγή στο πλήθος των γλυκών του κουτιού ~2~. Το πλήθος των γλυκών σε κάθε κουτί στο τέλος κάθε ημέρας δίνεται παρακάτω:

Οπότε, η συνάρτηση θα πρέπει να επιστρέψει [~0, 4, 13~].

Περιορισμοί

• ~1 \le n \le 200\,000~
• ~1 \le q \le 200\,000~
• ~1 \le c[i] \le 10~ (για κάθε ~0 \le i \le n - 1~)
• ~0 \le l[j] \le r[j] \le n - 1~ (για κάθε ~0 \le j \le q - 1~)
• ~-10 \le v[j] \le 10~ , ~v[j] \ne 0~ (για κάθε ~0 \le j \le q - 1~)

Υποπροβλήματα

1. (~3~ βαθμοί) ~n, q \le 2\,000~
2. (~8~ βαθμοί) ~v[j] > 0~ (για κάθε ~0 \le j \le q - 1~)
3. (~27~ βαθμοί) ~c[0] = c[1]~ = ... = ~c[n - 1]~
4. (~29~ βαθμοί) ~l[j] = 0~ και ~r[j] = n - 1~ (για κάθε ~0 \le j \le q - 1~)
5. (~33~ βαθμοί) Χωρίς επιπλέον περιορισμούς.

Υποδειγματικός βαθμολογητής

Ο υποδειγματικός βαθμολογητής διαβάζει την είσοδο ως εξής:

• γραμμή ~1~: ~n~
• γραμμή ~2~: ~c[0] c[1]~ ... ~c[n - 1]~
• γραμμή ~3~: ~q~
• γραμμή ~4 + j ( 0 \le j \le q - 1~): ~l[j] r[j] v[j]~

Ο υποδειγματικός βαθμολογητής τυπώνει τις απαντήσεις ως εξής:

• γραμμή ~1~: ~s[0] s[1]~ ... ~s[n - 1]~