// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
 
int binSearchInd(vector<long> population, int randInd) {
    int low = 0;
    int high = population.size();
 
    while (low <= high) {
        int mid = (low + high)/2;
        if ((mid==0 && population[mid] >= randInd) || (population[mid-1] < randInd && population[mid] >= randInd)) {//out of ind
            return mid;
        } else if (population[mid] < randInd) {
            low = mid + 1;
        } else {
            high = mid-1;
        }
 
    }
    return -1;
}    
 
string randCity(vector<string> cities, vector<long> population) {
    vector<long> preSum;
    preSum.push_back(population[0]);
 
    int size = population.size();
 
    for (int i = 1; i < size; i++) {
        preSum.push_back(preSum.back() + population[i]);
    }
 
    int randInd = 1 + rand() % (preSum.back());
 
 
    int cityInd = binSearchInd(preSum, randInd);
    cout<<rand()<<" "<<randInd<<" "<<cityInd<<endl;
    return cities[cityInd];
}
 
int main() {
    // Write C++ code here
    vector<string> cities = {"A", "B", "C", "D"};
    vector<long> population = {5, 4, 2, 6};
    cout<<randCity(cities, population)<<endl;
 
    return 0;
}
 
 

Ly8gT25saW5lIEMrKyBjb21waWxlciB0byBydW4gQysrIHByb2dyYW0gb25saW5lCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGJpblNlYXJjaEluZCh2ZWN0b3I8bG9uZz4gcG9wdWxhdGlvbiwgaW50IHJhbmRJbmQpIHsKICAgIGludCBsb3cgPSAwOwogICAgaW50IGhpZ2ggPSBwb3B1bGF0aW9uLnNpemUoKTsKICAgIAogICAgd2hpbGUgKGxvdyA8PSBoaWdoKSB7CiAgICAgICAgaW50IG1pZCA9IChsb3cgKyBoaWdoKS8yOwogICAgICAgIGlmICgobWlkPT0wICYmIHBvcHVsYXRpb25bbWlkXSA+PSByYW5kSW5kKSB8fCAocG9wdWxhdGlvblttaWQtMV0gPCByYW5kSW5kICYmIHBvcHVsYXRpb25bbWlkXSA+PSByYW5kSW5kKSkgey8vb3V0IG9mIGluZAogICAgICAgICAgICByZXR1cm4gbWlkOwogICAgICAgIH0gZWxzZSBpZiAocG9wdWxhdGlvblttaWRdIDwgcmFuZEluZCkgewogICAgICAgICAgICBsb3cgPSBtaWQgKyAxOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIGhpZ2ggPSBtaWQtMTsKICAgICAgICB9CiAgICAgICAgCiAgICB9CiAgICByZXR1cm4gLTE7Cn0gICAgCiAgICAKc3RyaW5nIHJhbmRDaXR5KHZlY3RvcjxzdHJpbmc+IGNpdGllcywgdmVjdG9yPGxvbmc+IHBvcHVsYXRpb24pIHsKICAgIHZlY3Rvcjxsb25nPiBwcmVTdW07CiAgICBwcmVTdW0ucHVzaF9iYWNrKHBvcHVsYXRpb25bMF0pOwogICAgCiAgICBpbnQgc2l6ZSA9IHBvcHVsYXRpb24uc2l6ZSgpOwogICAgCiAgICBmb3IgKGludCBpID0gMTsgaSA8IHNpemU7IGkrKykgewogICAgICAgIHByZVN1bS5wdXNoX2JhY2socHJlU3VtLmJhY2soKSArIHBvcHVsYXRpb25baV0pOwogICAgfQogICAgCiAgICBpbnQgcmFuZEluZCA9IDEgKyByYW5kKCkgJSAocHJlU3VtLmJhY2soKSk7CiAgICAKICAgIAogICAgaW50IGNpdHlJbmQgPSBiaW5TZWFyY2hJbmQocHJlU3VtLCByYW5kSW5kKTsKICAgIGNvdXQ8PHJhbmQoKTw8IiAiPDxyYW5kSW5kPDwiICI8PGNpdHlJbmQ8PGVuZGw7CiAgICByZXR1cm4gY2l0aWVzW2NpdHlJbmRdOwp9CgppbnQgbWFpbigpIHsKICAgIC8vIFdyaXRlIEMrKyBjb2RlIGhlcmUKICAgIHZlY3RvcjxzdHJpbmc+IGNpdGllcyA9IHsiQSIsICJCIiwgIkMiLCAiRCJ9OwogICAgdmVjdG9yPGxvbmc+IHBvcHVsYXRpb24gPSB7NSwgNCwgMiwgNn07CiAgICBjb3V0PDxyYW5kQ2l0eShjaXRpZXMsIHBvcHVsYXRpb24pPDxlbmRsOwoKICAgIHJldHVybiAwOwp9Cgo=

MTAKYWJhCmdlZWtzZm9yZ2Vla3MKZ2Vla3Nmb3JnZWVrcwpnZWVrc2ZvcmdlZWtzCmdlZWtzZm9yZ2Vla3MKZ2Vla3Nmb3JnZWVrcwpnZWVrc2ZvcmdlZWtzCmdlZWtzZm9yZ2Vla3MKZ2Vla3Nmb3JnZWVrcwpnZWVrc2ZvcmdlZWtz

10
aba
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks