Bessie is going on a hiking excursion! The trail that she is currently traversing consists of N checkpoints labeled 1…N (1≤N≤10^5).

There are K (1≤K≤10^5) tickets available for purchase. The i-th ticket can be purchased at checkpoint c_i (1≤c_i≤N) for price p_i (1≤pi≤10^9) and provides access to all of checkpoints [a_i,b_i] (1≤a_i≤b_i≤N). Before entering any checkpoint, Bessie must have purchased a ticket that allows access to that checkpoint. Once Bessie has access to a checkpoint, she may return to it at any point in the future. She may travel between two checkpoints to which she has access, regardless of whether their labels differ by 1 or not.

For each of i∈[1,N], output the minimum total price required to purchase access to both checkpoints 1 and N if Bessie initially has access to only checkpoint i. If it is impossible to do so, print −1 instead.

#5726 upload 1 done 1 how_to_reg 1

Tickets timer 1s memory 32MB

#5726

Tickets 1s 32MB