The Barrow-Kings of Ossenmere Downs

The Wardens of Ossenmere Downs have opened the great barrow to re-inter its dead kings. The barrow has one straight row of burial niches, running from the west end to the east end, with exactly one niche for each king. The old rites say how the kings must lie relative to one another, and the barrow will not seal if any rite is broken. The Wardens' contract asks you to produce the burial order.

Write layBarrow(names, rites).

Arguments - names: a list of distinct king names. Each name is a non-empty string of lowercase letters a-z only. The list may be empty. - rites: a list of strings. Each string is exactly one of the following forms, with single spaces between the words. Here x and y are two *different* names from names: - "x before y": x lies in a niche somewhere west of y. They do not need to be neighbours. - "x beside y": x and y lie in neighbouring niches, in either order. - "x apart y": x and y do not lie in neighbouring niches. - "x first": x lies in the westernmost niche. - "x last": x lies in the easternmost niche.

Rites may repeat. They may also contradict one another.

Return

Return a list containing every name exactly once, ordered from the west end to the east end, such that every rite holds.

If more than one order satisfies every rite, return the one that comes first alphabetically. To compare two orders, find the first position at which they differ. The order whose name at that position is alphabetically earlier comes first.

If no order satisfies every rite, return an empty list. If names is empty, return an empty list.