Bay switchers: hints, no solution

Trucks arriving at a warehouse are logged as events. Event i says that the truck with plate number plates[i] pulled into the loading bay numbered bays[i]. A truck can arrive many times in a day and may use any bay each time.

Dispatch wants to know which trucks keep changing bays. Given the two parallel arrays and an integer k, return the plate numbers of every truck that used strictly more than k distinct bays, sorted ascending, each plate once. Using the same bay again does not add to a truck's count. Return an empty list if no truck qualifies.

Examples

Input

plates = [5, 8, 5, 8, 5, 9, 8], bays = [1, 2, 3, 2, 1, 4, 7], k = 1

Output

[5, 8]

Note

Plate 5 used bays 1 and 3, plate 8 used bays 2 and 7, and plate 9 used only bay 4.

Input

plates = [4, 4, 2], bays = [1, 1, 1], k = 0

Output

[2, 4]

Note

With k = 0 any truck that arrived at all qualifies.

Input

plates = [6, 6, 6], bays = [1, 2, 3], k = 3

Output

[]

Note

Plate 6 used three distinct bays, which is not more than 3.

Constraints

• plates.length == bays.length, 0 <= length <= 140000
• 1 <= plates[i] <= 1000000, 1 <= bays[i] <= 100000
• 0 <= k <= 140000

Hint 1: a nudge

For a single plate, what would you want to be able to list after reading all the events?

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