URL Shortener

You are given the task of implementing a URL shortener service. The service should support two operations:

• shorten: Converts a long URL into a short URL. For the first occurrence of a long URL, the service generates a unique short URL, which is a string representation of a number. If the same long URL is shortened again, it returns the previously generated short URL.
• retrieve: Given a short URL, returns the original long URL if it exists, or None if it does not.

Formally, if we denote by \( i \) the order in which a unique URL arrives, then the assigned short URL is \( i \) (represented as a string). The service must process a sequence of operations provided from standard input.

inputFormat

The first line of input contains an integer \( n \) representing the number of operations. Each of the following \( n \) lines contains an operation and a URL (or a short URL) separated by a space.

Each operation is either "shorten" or "retrieve".

outputFormat

For each operation, output the result on a new line. For a "shorten" operation, output the generated short URL. For a "retrieve" operation, output the original long URL if it exists; otherwise, output "None".

## sample

5
shorten https://www.example.com
shorten https://medium.com/@someone/some-article
retrieve 1
shorten https://www.example.com
retrieve 2

1
2
https://www.example.com
1
https://medium.com/@someone/some-article

</p>