Upon arrival at an airport, passengers can pick up their luggage at a moving baggage carousel. The carousel rotates counterclockwise and is subdivided into compartments that each fit a single suitcase. First, the suitcases are transported from the aircraft to the baggage carousel by means of an automatic transport system. Afterwards, a porter drops the suitcases one by one on the carousel, always placing the next suitcase in the third empty compartment that passes by.

For example, suppose the porter has to drop five suitcases on a baggage carousel having eight compartments. For ease of reference, we have labeled the suitcases with the uppercase letters A, B, C, D and E, in the order the porter has to drop them on the carousel.

After the porter has dropped the last suitcase (E) on the baggage carousel, we get the following situation.

However, the carousel keeps spinning after all suitcases have been dropped, so that a few moments later the situation may look like this.

Assignment

In this assignment we represent a baggage carousel as a list. The compartments of the carousel correspond to the elements of the list. Each element that corresponds to a compartment containing a suitcase is assigned a single character string (the label of the suitcase). We assume that all suitcases on the carousel are labeled with a different character. Each element that corresponds to an empty compartment is assigned the value None.

The order of the elements in the list corresponds to the order of the compartments that pass by the position of the porter, until all compartments have passed him. For example, the carousel that corresponds to the middle figure in the introduction is represented by the list ['E', 'A', None, 'D', 'B', None, None, 'C']. That same carousel, but read from the situation in the bottom figure in the introduction, is represented by the list ['B', None, None, 'C', 'E', 'A', None, 'D']. These are two different lists that represent the same baggage carousel. You are asked to:

• Write a function baggageCarousel that takes two arguments: an integer $$c$$ that indicates the number of compartments of a baggage carousel, and a string whose characters correspond to the labels of a sequence of suitcases that must be dropped onto an empty carousel in the order in which the characters occur in the string. All characters in the string are different, and the number of characters is less than or equal to $$c$$. The function must return a list that represents the baggage carousel with $$c$$ compartments after all suitcases were dropped on the carousel by the porter. Keep in mind that the porter drops each suitcase in the third empty compartment that passes by. Make sure that the first element of the returned list corresponds to the compartment in which the last suitcase was dropped.

• Write a function rotated that takes two lists, each representing a baggage carousel. The function must return a Boolean value that indicates whether or not the given lists represent the same carousel. Two lists represent the same baggage carousel if they have an equal number of compartments, that are filled with the same bags in the same order. The only difference that may occur is that the compartments are read from a different starting position.

Example

>>> carousel(8, 'ABCDE')
['E', 'A', None, 'D', 'B', None, None, 'C']
>>> carousel(5, 'ABCDE')
['E', 'C', 'B', 'D', 'A']

>>> rotated(['E', 'A', None, 'D', 'B', None, None, 'C'], ['B', None, None, 'C', 'E', 'A', None, 'D'])
True
>>> rotated(['E', 'A', None, 'D', 'B', None, None, 'C'], ['B', None, None, 'A', 'E', 'C', None, 'D'])
False
>>> rotated(['E', 'A', None, 'D', 'B', None, None, 'C'], ['C', 'E', 'A', None, 'D', 'B'])
False