Santa’s Gift Delivery Optimization

On Christmas Eve, Santa starts at coordinate 0 and enters a city with N houses located along a straight road at positions \(X_1, X_2, \dots, X_N\). Each house \(i\) is characterized by two values:

• \(H_i \in \{0,1\}\): if \(H_i = 0\) the house contains an elf holding a gift of value \(V_i\); if \(H_i = 1\) the house contains a child waiting for a gift with minimum acceptable value \(V_i\).
• \(X_i\): the coordinate of the \(i\)th house along the road. The houses are numbered from 1 to \(N\) in increasing order of \(X_i\).

Santa considers N scenarios. In the \(i\)th scenario, he follows this route:

1. Start at coordinate 0 with an empty gift bag.
2. Move to the right until reaching house \(i\) (at \(X_i\)). During this forward journey:
1. Whenever he passes an elf house (with \(H=0\)) that he has not visited before, he picks up the gift (adding it to his bag).
2. Whenever he passes a child house (with \(H=1\)) and the child has not received a gift, he may deliver a gift from his bag. However, a gift can only be given if its value is at least the child’s minimum requirement \(V_i\) and if the gift was already picked up (i.e. the house with the gift appears before the child in the route if delivered during the forward pass).
3. After reaching house \(i\), Santa turns around and moves to the left until he reaches some coordinate \(X_{\text{left}}\) (with \(X_{\text{left}} \le X_i\)). On his leftward (backward) journey, he visits only the houses whose coordinates are in the interval \([X_{\text{left}}, X_i]\). During this backward pass, he may deliver gifts to any child house he visits (regardless of the order, because by then all gifts have been collected in the forward pass). Note that a child house visited in the forward pass may be skipped in delivery if it is more advantageous to wait for the backward pass; however, child houses that do not appear on the backward pass (i.e. those with coordinate less than \(X_{\text{left}}\)) must receive their gift during the forward pass if at all.

The total distance traveled in the \(i\)th scenario is defined as \(D_i = 2X_i - X_{\text{left}}\). The objective is to deliver all gifts from elf houses (each elf’s gift must be given to some child, and each child can receive at most one gift) while minimizing \(D_i\). If it is impossible to deliver every gift (either because some elf house is never reached or because there isn’t a valid delivery assignment), then \(D_i\) is defined to be \(-1\). Note that if there are elf houses located beyond house \(i\), Santa cannot pick up those gifts and the scenario is automatically impossible.

Input constraints: The houses are given in order of increasing \(X_i\). All formulas are rendered in \(\LaTeX\) format.

inputFormat

The first line contains a single integer \(N\) (the number of houses and scenarios). Each of the next \(N\) lines contains three integers \(X_i\), \(H_i\) and \(V_i\), describing the coordinate of the \(i\)th house, the type of the house (0 for an elf, 1 for a child), and the gift value (or required minimum value), respectively.

outputFormat

Output \(N\) lines. The \(i\)th line should contain the minimum distance \(D_i\) required in the \(i\)th scenario, or \(-1\) if it is impossible to deliver every gift from the elf houses.

sample

3
1 0 5
2 1 3
3 1 6

-1
2
3