Tickets#11228
Bessie is going on a hiking excursion! The trail that she is currently traversing consists of checkpoints labeled ...
There are tickets available for purchase. The -th ticket can be purchased at checkpoint c_i for price p_i and provides access to all of checkpoints [a_i, b_i]. 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.
For each of ∈ [, ], output the minimum total price required to purchase access to both checkpoints and if Bessie initially has access to only checkpoint . If it is impossible to do so, print instead.
The first line contains ( ≤ ≤ 10^5) and ( ≤ ≤ 10^5).
Each of the next lines contains four integers c_i ( ≤ c_i ≤ ), p_i ( ≤ p_i ≤ 10^9), a_i and b_i ( ≤ a_i ≤ b_i ≤ ) for each ( ≤ ≤ ).
Print lines, one for each checkpoint.
Esempio 1
If Bessie starts at checkpoint = , then the only way for Bessie to purchase access to checkpoints and is as follows:
- Purchase the first ticket at checkpoint , giving Bessie access to checkpoints and . - Purchase the third ticket at checkpoint , giving Bessie access to checkpoint . - Return to checkpoint and purchase the second ticket, giving Bessie access to checkpoints and . - Purchase the fourth ticket at checkpoint , giving Bessie access to checkpoint .