### Problem Statement

Almost every different government in the world has a different method of assigning license plates to vehicles. In any of these systems, it is possible to take all possible plates, arrange them in lexicographical order, and number them, where the first plate is 0, the second plate is 1, etc. Your local government has decided to do this with the license plates that it issues, and right before you leave to eat lunch, you have been assigned this daunting project. So that you can actually have a warm meal today, you have decided to write a program to do this for you.

You will be given a String format, containing the format of the local license plates. Each character of format will be either an uppercase letter ('A'-'Z'), a number ('0'-'9'), a space (' '), a dash ('-'), or the lowercase letters 'u', 'n', or 'a'. If the character is a 'u', it means that any uppercase letter can be used in that place. If the character is an 'n', it means that any number can be used in that place. If the character is an 'a', it means that any uppercase letter or number can be used in that place. If the character is not a lowercase letter, then the character in that spot must be the one used in format. For instance, if the format was "AB-una", then "AB-C52" and "AB-D3G" would be legal license plates, but "AC-D3G", "AB-111", and "AB-DEF" would not.

Given the format, you are to return the n-th earliest (0-indexed) license plate that can be formed in this system. If the n-th license plate cannot be formed using the given format, return an empty String. Note that numbers occur earlier lexicographically than letters (e.g., '4' comes before 'B').

### Definition

 Class: LicensePlate Method: getPlate Parameters: String, int Returns: String Method signature: String getPlate(String format, int n) (be sure your method is public)

### Constraints

-format will contain between 1 and 50 characters, inclusive.
-Each character of format will be an uppercase letter ('A'-'Z'), a number ('0'-'9'), a space (' '), a hyphen ('-'), or the lowercase letters 'a', 'n', or 'u'.
-n will be between 0 and 2^31-1, inclusive.

### Examples

0)

 `"ABu"` `2`
`Returns: "ABC"`
 The license plates in this format are "ABA", "ABB", "ABC", "ABD", etc. We return the 2nd (0-based) element in this list, which is "ABC".
1)

 `"ABn"` `2`
`Returns: "AB2"`
2)

 `"ABa"` `12`
`Returns: "ABC"`
 Remember that numbers come first in lexicographical order.
3)

 `"A BC"` `2`
`Returns: ""`
 There are only 1 possible license plate in this format ("ABC"), so we must return a blank plate.
4)

 `"una"` `8732`
`Returns: "Y2K"`
5)

 `"ABa DEuF-GHuJ KL-aMNaa5390u"` `1345876`
`Returns: "AB0  DEAF-GHBJ KL-3MNXW5390M"`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6823

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10655&pm=6823

connect4

#### Testers:

PabloGilberto , brett1479 , Olexiy

#### Problem categories:

Greedy, String Parsing