sclass RandomizerFromHistogram<A> implements IF0<A> {
  new LPair<A, Long> list;
  transient Random randomizer = defaultRandomizer();
  
  *(MultiSet<A> ms) {
    long sum = 0;
    for (A a : keys(ms)) {
      int val = ms.get(a);
      if (val == 0) continue;
      sum += val;
      list.add(pair(a, sum));
    }
  }
  
  public A get() {
    if (empty(list)) null;
    long val = randomLong(randomizer, last(list).b);
    int idx = generalizedBinarySearch2(list, p -> cmp((long) p.b, val));
    if (idx < 0) {
      //print("idx1: " + idx);
      idx = -idx-1;
    }
    //print("idx: " + idx);
    ret assertNotNull(pairA(_get(list, idx)));
  }
}