for i in ls:
    a = [ [k, j] for k, j in dct.items() if j == i]
    if len(a) == 1:
        print(a[0][0], a[0][1])
    else:
        a.sort()
        for i in a:
            print(i[0],i[1])