Conflict-free timetables: hints, no solution

A conference has several talks and a number of rooms numbered from 0. Talk i runs from minute starts[i] up to but not including minute ends[i]. Two talks clash when each starts before the other ends, so a talk that ends at minute m does not clash with one that starts at minute m. Clashing talks cannot share a room, but any number of non-clashing talks can.

Return every valid assignment of rooms to talks. An assignment is a list whose i-th entry is the room of talk i. List the assignments in ascending order, comparing them entry by entry from the first talk, so that [0, 1, 0] comes before [0, 1, 2]. If no assignment exists, return an empty list.

Examples

Input

starts = [1, 2, 5], ends = [4, 6, 8], rooms = 2

Output

[[0, 1, 0], [1, 0, 1]]

Note

Talks 0 and 1 clash, and so do talks 1 and 2, but talks 0 and 2 can share a room.

Input

starts = [0, 1], ends = [5, 3], rooms = 1

Output

[]

Note

The talks overlap and there is only one room.

Constraints

• 1 <= number of talks <= 14 and 1 <= rooms <= 6
• 0 <= starts[i] < ends[i] <= 1000
• The result has at most 300 assignments

Hint 1: a nudge

For any two talks, can you say quickly whether they may share a room? Which pairs need to be checked when you assign the next talk?

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