Sole-source parts: hints, no solution

A purchasing team holds one catalogue per supplier. Each catalogue is a list of part numbers the supplier can deliver. A catalogue may be empty, and a supplier sometimes lists the same part number more than once.

A part is sole-source if exactly one supplier offers it, however many times that supplier lists it. Given all the catalogues, return the part numbers that are sole-source, sorted ascending, each once. Return an empty list if there are none.

Examples

Input

catalogues = [[4, 7, 9], [7, 2], [9, 4, 5]]

Output

[2, 5]

Note

Part 2 only appears in the second catalogue and part 5 only in the third; 4, 7 and 9 each have two suppliers.

Input

catalogues = [[1, 1, 1], [2]]

Output

[1, 2]

Note

A part listed three times by one supplier still has a single supplier.

Input

catalogues = [[3, 3], [3]]

Output

[]

Note

Part 3 is offered by both suppliers.

Constraints

• 0 <= catalogues.length <= 60, each catalogue has 0 to 4800 part numbers
• 1 <= part <= 100000
• Return parts sorted ascending

Hint 1: a nudge

For one part number, what do you need to know about the catalogues to decide if it qualifies?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing