Random Country Generator with Population Bias

Problem: Random Country Generator with Population Bias Given n countries and their population weights weight[i], implement a weighted random country generator so that each country is returned with probability proportional to its population over the total population. You need to support: Initialization with country names and population weights. Random selection: each call to pick_country() returns one country according to the weights. Analyze the time complexity of initialization and one random pick. For deterministic judging, the input provides several random values r, where 0 <= r < total_weight. For each r, return the country interval that contains it. In a real random generator, r can be generated uniformly at random. Input Format n country_1 weight_1 country_2 weight_2 ... country_n weight_n q r_1 r_2 ... r_q country_i is a country name without spaces. weight_i is a positive integer population weight. r_j is a floating-point number satisfying 0 <= r_j < sum(weight). Output Format For each query value r_j, output the selected country name, one per line. Constraints 1 <= n <= 10^5 1 <= weight_i <= 10^12 1 <= q <= 10^5 0 <= r_j < sum(weight_i) Example Input 3 USA 331 India 1380 Canada 38 5 0 330.999 331 1710.5 1711 Output USA USA India India Canada Explanation The prefix sums define these intervals: USA: [0, 331) India: [331, 1711) Canada: [1711, 1749) Therefore, r=331 falls into India's interval, and r=1711 falls into Canada's interval. Example Input 3 USA 331 India 1380 Canada 38 5 0 330.999 331 1710.5 1711 Output USA USA India India Canada