Terraced Vineyard

Medium · greedy

A vineyard is being built on a hillside as a row of n terraces, numbered 0 to n - 1 from left to right. Each terrace is built up to a whole-number height, and the plan must follow these rules:

terrace i must be at least lows[i] and at most highs[i] high, and
the heights of neighbouring terraces i and i + 1 may differ by at most gaps[i], so the vineyard can be walked without steep steps.

A plan that follows all the rules is valid. Return a list of n numbers, where entry i is the greatest height that terrace i can have in any valid plan (different terraces may reach their greatest height in different plans).

If there is no valid plan at all, return an empty list.

Examples

Example 1

Input: lows = [0, 0, 0, 0], highs = [5, 9, 3, 9], gaps = [2, 2, 2]

Output: [5, 5, 3, 5]

The upper limit of 3 on terrace 2 holds terraces 1 and 3 down to 5, and terrace 0 is limited by its own upper limit of 5.

Example 2

Input: lows = [8, 0], highs = [10, 2], gaps = [3]

Output: []

Terrace 0 must be at least 8, so terrace 1 must be at least 5. But terrace 1 can be at most 2.

Example 3

Input: lows = [2], highs = [7], gaps = []

Output: [7]

Constraints

1 <= n <= 10^4, where n is the length of lows and highs, and len(gaps) = n - 1
0 <= lows[i] <= highs[i] <= 10^6
0 <= gaps[i] <= 10^4