Invert a One-to-One Dictionary

Summary

Create the inverse of a mapping: values become keys and keys become values (as lists) to handle duplicate values.

Problem statement

Given a dictionary where multiple keys may map to the same value, invert the mapping so that each value becomes a key mapping to a list of original keys. Preserve the order of original keys as they appear during iteration of the input dictionary. Return the inverted dictionary. Values in the input are guaranteed to be hashable.

Task

Write a function that inverts a dictionary by turning each original value into a key and collecting all original keys that mapped to it into a list, preserving original key order.

Examples

Input format

A dictionary with hashable values.

Output format

A dictionary where each value from the input is a key and maps to a list of original keys.

Constraints

Input values are hashable. If input is empty, return an empty dictionary. Preserve original key order for lists.

Samples