福到年到

Time Limit: 500 ms Memory Limit: 65536 KiB

Problem Description

 

         

     过年了,有 n个小朋友,参加了集五福活动,集训队辉姐姐"福"特别特别多,要给小朋友们送一些 "福" ,辉姐姐会发放m次,每次有三个参数 l , r , k ( 1 ≤ l ≤ r ≤ n ≤1e5 ,1 ≤ k ≤ 5,0<=m<=1e5) ,表示给区间 [l,r] 内的小朋友都发一个福 k(众所周知有5种“福”) ,那么问题来了,在经过辉姐姐这 m次操作之后,对于每一个小朋友,回答他接受的福中,出现次数最多的福是什么。如果有多个,输出编号最小的那个;如果他没有"福",输出 -1 。

Input

单组输入第一行输入 n ,m分别代表小朋友数与发放次数

接下来 m行每行 3 个整数分别代表 l ,r ,k。

Output

根据题目要求输出一行,n个数表示n个小朋友信息。

Sample Input

5 3
1 2 1
3 3 1
1 3 2

Sample Output

1 1 1 -1 -1

Hint

配图转自:https://twitter.com/yumu_uri/status/1079754707780935682

Source

Infiniti