CLFLARR  COLORFUL ARRAY
You have been given an array of n unpainted elements. By unpainted, we mean that each element initially has a value of 0. You have to process q queries of the form l r c, in which you paint all the elements of the array from index l to index r with color c. Assume that, each new color currently being applied to an element overrides its previous color. Output the color of each element after all the queries have been processed.
Note: The problem is guaranteed to be solved using C or C++ programming language.
Input
The first line of input consists of two integers n and q. Next q lines consists of 3 integers l, r and c denoting the starting index, ending index and the color respectively.
 1 <= n <= 200000
 1 <= q <= 200000
 1 <= l <= r <= n
 1 <= c <= 1 000 000 000
Output
Output the final color of each element starting from index 1 on a new line.
Example
Input 4 3 1 3 2 2 4 6 2 3 7
Output: 2 7 7 6
Input 10 5 3 9 13 1 4 9 2 10 14 2 7 10 6 9 44
Output 9 10 10 10 10 44 44 44 44 14
hide comments
anil_1:
20210922 18:21:52
Can someone tell me how to do it using DSU. 

kumar_sunny:
20210402 08:59:01
No need to use DSU..just an optimistation on array...basically implementation based problem. 

dpw4112001:
20210212 11:59:52
its passing N^2 . TC are not strong 

amrit5:
20210119 01:33:30
Hello all, I'm a faggot. Last edit: 20210119 09:16:07 

nikhil_kmtnk:
20210116 10:09:55
This problem can also be solved using sets of C++ STL. Using lower_bound() and upper_bound() function this problem can be easily solved. 

aman_bedi:
20200828 12:53:30
Segment tree with lazy propogation can take time but dsu make it superfast


gnomegeek:
20200805 01:43:29
AC in one go. SegTree with Lazy. 

sarthak_19:
20200709 19:49:59
Nice problem on DSU. Can be solved using segment trees too 

shameek:
20200625 08:16:54
a beginner can benefit a lot from ths question!!


shikhar2402_:
20200529 18:40:24
please someone tell my mistake 
Added by:  No_idea 
Date:  20190321 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Competitive Programming Community 