Implement a host tracker: allocate(hostType) reserves and returns the hostname with the smallest free number for that type, from 1; deallocate(hostname) frees it for reuse.

Hostnames are a host type made of letters followed by a number, such as cache1 or cache2. Implement a tracker with two operations. allocate(hostType) reserves the free hostname of that type with the smallest number, counting from 1, and returns the full hostname. deallocate(hostname) releases that hostname so that it can be given out again; a deallocate for a hostname that is not currently allocated is a valid call and must be handled (it leaves that name free). The operations arrive as a list of strings, 'A <hostType>' for allocate and 'D <hostname>' for deallocate, and the output is the list of hostnames returned by the allocate calls, in order. There are at most 1,000 operations, and host numbers in deallocate requests do not exceed 999. Example: A cache, A cache, A queue, D cache1, A cache, A cache gives cache1, cache2, queue1, cache1, cache3.