Random Pick with Weight

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the i-th index.

You need to implement the function pickIndex() which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking index i is w[i] / sum(w).

For testing purposes, you receive w and an array of targets (each in range [1, sum(w)]). For each target, return the index that would be selected by binary searching the prefix sum array.

Examples

Example 1:

Input: w = [1, 3], targets = [1, 2, 3, 4]

Output: [0, 1, 1, 1]

Explanation: Prefix sums = [1, 4]. Target 1 → index 0, targets 2–4 → index 1.

Example 2:

Input: w = [3, 1, 2, 4], targets = [3, 4, 5, 10]

Output: [0, 1, 2, 3]

Explanation: Prefix sums = [3, 4, 6, 10].

Constraints

• 1 <= w.length <= 10^4
• 1 <= w[i] <= 10^5
• 1 <= targets[i] <= sum(w)