LRU Caching

When accessing large amounts of data is deemed too slow, a common speed-up technique is to keep a small amount of the data in a more accessible location known as a cache. The first time a particular piece of data is accessed, the slow method must be used. However, the data is then stored in the cache so that the next time you need it you can access it much more quickly. For example, a database system may keep data cached in memory so that it doesn't have to read the hard drive, or a web browser might keep a cache of web pages on the local machine so that it doesn't have to download them over the network.

In general, a cache is much too small to hold all the data you might possibly need, so at some point you have to remove something from the cache in order to make room for new data. The goal is to retain those items that are more likely to be retrieved again soon. This requires a sensible algorithm for selecting what to remove. One simple but effective algorithm is the Least Recently Used, or LRU, algorithm. When performing LRU caching, you always throw out the data that was accessed least recently.

As an example, imagine a cache that can hold up to five pieces of data. Suppose we access three pieces of data — A, B, and C. As we access each one, we store it in the cache, so at this point we have three pieces of data in the cache and two empty spots (Figure 1). Now suppose we access D and E. They are added to the cache as well, filling it up. Next suppose we access A again. A is already in the cache, so the cache's contents do not change; however, this access still counts as a use, making A the most recently used. Now if we access F, we have to throw something out to make room for it. At this point B has been used least recently, so we throw it out and replace it with F (Figure 2). If we now access B again, it is exactly like the first time we accessed it: we retrieve it and store it in the cache, throwing out the least recently used data — this time C — to make room for it.

Figure 1: Cache after A, B, C	Figure 2: Cache after A, B, C, D, E, A, F

Your task is to take a sequence of data accesses and simulate an LRU cache. When requested, output the contents of the cache, ordered from least recently used to most recently used.

The input is a series of data sets, one per line. Each data set consists of an integer N and a string of two or more characters. The integer N is the size of the cache for that data set ($1 \le N \le 26$). The string consists solely of uppercase letters and exclamation marks. An uppercase letter represents an access to that particular piece of data. An exclamation mark represents a request to print the current contents of the cache.

For example, the sequence ABC!DEAF!B! means: access A, B, and C (in that order), print the contents of the cache, access D, E, A, and F (in that order), print the contents of the cache, access B, and again print the contents of the cache.

Each sequence always begins with an uppercase letter and contains at least one exclamation mark.

The end of the input is signaled by a line containing only the number 0.

For each data set, output the line "Simulation S", where S is 1 for the first data set, 2 for the second data set, and so on. Then, for each exclamation mark in the data set, output the contents of the cache on one line as a sequence of characters representing the pieces of data currently held. The characters are ordered from least recently used to most recently used, with the least recently used first. Output only the letters that are in the cache; if the cache is not full, you simply have fewer characters to output (do not print any blank spaces). Because each sequence always begins with an uppercase letter, you will never be asked to output a completely empty cache.