Full menus: hints, no solution

A caterer offers a set menu made of several courses served in a fixed order. For every course there is a list of dishes to choose from, and a guest picks exactly one dish per course. All dish names within one course are different.

Given the list of courses, each a list of dish names, return every possible menu. A menu is the list of chosen dishes, one per course, in course order. Produce the menus in this order: compare two menus from the first course onward, and the menu whose dish appears earlier in that course's list comes first. If there are no courses, or any course has no dishes, no menu can be formed and the result is an empty list.

Examples

Input

courses = [["soup", "salad"], ["curry", "pasta"]]

Output

[["soup", "curry"], ["soup", "pasta"], ["salad", "curry"], ["salad", "pasta"]]

Note

Each soup or salad choice is combined with each main, with the first course changing slowest.

Input

courses = [["tea"], ["cake", "pie", "scone"]]

Output

[["tea", "cake"], ["tea", "pie"], ["tea", "scone"]]

Note

One tea, three possible bakes.

Constraints

• 0 <= number of courses <= 6
• 0 <= dishes in a course <= 6
• The result has at most 100 menus
• Dish names are non-empty lowercase words

Hint 1: a nudge

If you had to write the menus out by hand, how would you make sure you never miss one and never repeat one?

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