def top_sentences(query, sentences, idfs, n):
    """
    Given a `query` (a set of words), `sentences` (a dictionary mapping
    sentences to a list of their words), and `idfs` (a dictionary mapping words
    to their IDF values), return a list of the `n` top sentences that match
    the query, ranked according to idf. If there are ties, preference should
    be given to sentences that have a higher query term density.
    """
    result = []
    for sentence in sentences:
        idf = 0
        total_words_found = 0
        for word in query:
            if word in sentences[sentence]:
                total_words_found += 1
                idf += idfs[word]
        density = float(total_words_found) / len(sentences[sentence])
        result.append((sentence, idf, density))
    result.sort(key=lambda x: (x[1], x[2]), reverse=True)
    return [x[0] for x in result[:n]]