from __future__ import division, print_function

import sys
from csv import DictReader
from math import exp, log, sqrt
import random
from datetime import date
from stats import RunningStatistics
import multiprocessing
from os.path import dirname, join

# from sklearn.utils.murmurhash import murmurhash3_bytes_s32
import mmh3

def murmur3(x):
    # return hash(x)
    return mmh3.hash(x)

def quickSelect(seq, k):
    # this part is the same as quick sort
    len_seq = len(seq)
    if len_seq < 2: return seq

    ipivot = len_seq // 2
    pivot = seq[ipivot]

    smallerList = [x for i,x in enumerate(seq) if x <= pivot and  i != ipivot]

    # here starts the different part
    m = len(smallerList)
    if k == m:
        return pivot
    elif k < m: