N = 21871933314112865467898746447162428269681974150519714528478475771703827782082086777378910931660851283137864486595246381663520526520406572392585716696740636321652635422330511478905871156104491051091699199328661682515139543764647633955554273153685714738637072846924125589482012883660900525811452130747478801714747134410380873103256687411673342117437796707225056047904754917357593353489909415225641961629027137870372460596260574307334099344500671701101013624827398256592554458862542282055436515336691300340663915126837728314682624857364309398500977847144537412681378537021206581518269710114878530997170114403219400927517


def main():
    with open('key.txt') as f:
        a = f.readlines()
        p = int(a[0])
        q = int(a[1])
        d = int(a[2])
    assert p * q == N
    assert d * 65537 % ((p - 1) * (q - 1)) == 1
    m = pow(1 << 1000, d, N)

    with open('users.txt', 'rb') as f:
        users = sorted(x for x in f.read().split(b'\n') if x != b'')

    h = 5381
    for s in users:
        for c in s:
            h = (h * 33 + c) % (1 << 64)

    x = (m + h) % (1 << 64)
    for _ in range(20):
        x = (x * 6364136223846793005 + 1) % (1 << 64)
        y = (x >> 32) % len(users)
        print(users[y].decode())
        del users[y]


main()
