You have a log where every update to a record is appended as a new line. When the same id appears more than once, the later line has overwritten the earlier one.

Implement deduplicate(records), which collapses this list down to one line per id.

Input

records = [
    {"id": 1, "value": 10},
    {"id": 2, "value": 20},
    {"id": 1, "value": 30},
]

• Each record is a dictionary and always has an id key.
• Keys other than id are free-form and may differ between records.
• An id may be an integer or a string.

Output

Return the cleaned-up list of records.

deduplicate(records)
# [{"id": 1, "value": 30}, {"id": 2, "value": 20}]

Two things must hold at the same time.

1. When an id repeats, only the last record for it survives.
2. The surviving records are ordered by where that id first appeared.

In the example id=1 appears twice. The value that survives is the later one, 30. Its position, however, is the front, because that is where id=1 first appeared. So id=1 comes before id=2 in the result.

Where the two conditions collide

Satisfying just one of them is easy.

Walking backwards and keeping each id the first time you see it gives the right values but reverses the order. Walking forwards and keeping each id the first time you see it gives the right order but stale values.

A property of Python dictionaries gets you both at once. Store records keyed by id: assigning to a key that already exists replaces the value, but leaves that key sitting where it was first inserted.

Things to watch

1. Even if an id appears three or more times, only the last one survives.
2. You may return the same dictionary objects that were in the input. No copying is needed.
3. If there are no duplicates at all, return everything in the input order.
4. Empty input returns an empty list.

Implement deduplicate(records).