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
fuadul_hasan: 2022-04-28 16:23:35

nice one.. it took me 3h to solve but give me so much fun.
i use segtree lazy

ayush_shaz: 2022-04-21 08:04:48

It can also be done in n+q using heap.

mahbubkuet08: 2022-02-01 10:19:24

This is an offline query problem. Using segment trees will be overkill. Solved using DSU.

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

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


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