#!/usr/bin/env python# -*- coding=utf8 -*-import sysimport osimport random#input split 1565 #>>> 3000000/1565.0#1916.932907348243#2000K = 2000pool = []idxs = range(K)i = 0for line in sys.stdin:    line = line.strip()    if i < K:        pool.append(line)        i += 1    else:        p_i = 1.0 / i        if random.random() < p_i:            idx = random.choice(idxs)            pool[idx] = line        i += 1print os.linesep.join(pool)