CLFLARR - COLORFUL ARRAY

no tags 

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: 2021-09-22 18:21:52

Can someone tell me how to do it using DSU.

kumar_sunny: 2021-04-02 08:59:01

No need to use DSU..just an optimistation on array...basically implementation based problem.

dpw4112001: 2021-02-12 11:59:52

its passing N^2 . TC are not strong

amrit5: 2021-01-19 01:33:30

Hello all, I'm a faggot.

Last edit: 2021-01-19 09:16:07
nikhil_kmtnk: 2021-01-16 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: 2020-08-28 12:53:30

Segment tree with lazy propogation can take time but dsu make it superfast

gnomegeek: 2020-08-05 01:43:29

AC in one go. SegTree with Lazy.

sarthak_19: 2020-07-09 19:49:59

Nice problem on DSU. Can be solved using segment trees too

shameek: 2020-06-25 08:16:54

a beginner can benefit a lot from ths question!!
method 1 - segemnt trees + lazy update
method 2 - process query in reverse order and keep an additional array next which points to the next unpainted block
method 3 - do the same thing above but use DSU i.e. merge(i, i+1) and merge based on one with higher value of parent. i think 3 might be more efficient than 2 as the latter uses path compression along the way

Last edit: 2020-06-25 11:17:57
shikhar2402_: 2020-05-29 18:40:24

please someone tell my mistake


Added by:No_idea
Date:2019-03-21
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Competitive Programming Community