Smallest sufficient tier: hints, no solution

A cloud console lists the memory capacities of its instance tiers in gigabytes, sorted from smallest to largest. The list may contain the same capacity more than once because several families share sizes.

Given a list of workload demands in gigabytes, answer each demand with the smallest capacity in the table that is at least as large as it. If even the largest tier is too small, or the table is empty, that answer is -1. Return the answers in the order the demands were given.

The table is long and every demand is looked up against the same table, so aim for logarithmic time per demand rather than scanning every tier each time.

Examples

Input

capacities = [2, 4, 8, 16, 32], demands = [5, 8, 33]

Output

[8, 8, -1]

Note

5 needs the 8, an exact match counts, and no tier reaches 33.

Input

capacities = [2, 4, 8], demands = [9, 1]

Output

[-1, 2]

Note

Each demand is answered on its own.

Constraints

• 0 <= capacities.length <= 100000
• capacities is sorted ascending and may contain duplicates
• 1 <= capacities[i] <= 200000
• 0 <= demands.length <= 2000; 0 <= demands[j] <= 1000000

Hint 1: a nudge

If you look at one capacity in the middle of the table, does the answer lie to its left or to its right, or is it the answer itself?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing