Tuenti Challenge 7

Challenge 10 - Passwords

You have proudly worked for almost five years in a leading technological company. One day, you realized that the disk of your main employee authentication server was becoming full, and you started deleting some unnecessary stuff until you had enough space to install some videogames. However, five minutes later you were informed that the authentication had stopped working for all the company's employees.

After some investigation, you realize that you have accidentally deleted the whole password database from the disk, and that all its backups met the same fate every time you previously wanted to install more videogames.

Since you don't want anyone to discover that you've been using one of the company's most important servers to play videogames, you somehow need to rebuild the passwords. Thankfully, all those passwords were obtained from the password generation script and you have its source code downloaded, so maybe you can save yourself from being fired and from having to reinstall all your games on another company's server.

Once you download the password generation history, you realize that most of them were generated using older versions of the script. What's more, many users have their passwords regenerated. You know that a new version of the script was generated every day, with no exceptions, and that some of the commits might have been moved onto branches or even accidentally deleted.

But time is running out; can you find all the scripts and recover all the passwords?

Input

In the first line, an integer T indicates the number of cases.

Each case represents a user's password history, and is described by N+1 lines. The first line of each case contains the word U, corresponding to its userid, and the integer N, representing the number of entries that exist for that user. After that, N lines follow containing the string D, which represents the generation date in yyyy-mm-dd format and the integer C, representing the number of times that user password was changed on that date.

Output

For each case, a line starting with "Case #x: " followed by the most recent password for that user.

Limits

  • 1 ≤ N ≤ 1800
  • 1 ≤ C ≤ 10000
  • 2012/03/01 ≤ D ≤ 2017/01/31

Sample Input

3
aaaaaa 1
2017-01-31 1
abcdef 1
2017-01-31 2
xoajoj 2
2013-05-19 1
2016-08-20 1

Sample Output

Case #1: !i'M]7Yumu
Case #2: 1!_5yu3Ok1
Case #3: WSUmXS~*oR

Test your code

You can test your program against both the input provided in the test phase and the input provided in the submit phase. A nice output will tell you if your program got the right solution or not. You can try as many times as you want to. Be careful with extra whitespaces, the output should be exactly as described.

Test your program against the input provided in the test phase

Download test input

Program output:

Test your program against the input provided in the submit phase

Download input

Program output:

During the submit phase, in some problems, we might give your program harder inputs. As with the test token, a nice output will tell you if your program got the right solution or not. You can try as many times as you need.

In the actual contest you first need to solve the test phase before submitting the code, you must provide the source code used to solve the challenge and you can only submit once (once your solution is submitted you won't be able to amend it to fix issues or make it faster).

If you have any doubts, please check the info section.