Reading Croatian Numbers

Time limit1sMemory limit128 MB

Summary

Given a letter and index N, find the N-th positive integer (up to 10^12) whose Croatian number reading starts with that letter, following specific rules about leading digits and place values.

Level: Hard8 of 10
Topics: Math, Binary search, Simulation, Implementation
Solved: No attempts yet

Problem

The table below summarizes the first word used when reading positive integers in Croatian. Numbers are read in groups of three digits from the right. If the leading digit of the highest place is not 1, the reading begins with that digit's word. If it is 1, that 1 is usually omitted and the word for the place value is read first. The exceptions are the number 1 itself, which is read as jedan, and numbers whose highest three-digit group is from 11 to 19, which begin with the corresponding word in the table. For example, 40 begins with četiri, 705 with sedam, 150 with sto, 1 500 with tisuću, and 15 000 with petnaest.

1	jedan	10	deset	1xx	sto
2	dva	11	jedanaest	1xxx	tisuću
3	tri	12	dvanaest	1xxxx	deset tisuća
4	četiri	13	trinaest	1xxxxx	sto tisuća
5	pet	14	četrnaest	1xxxxxx	milijun
6	šest	15	petnaest	1xxxxxxx	deset milijuna
7	sedam	16	šesnaest	1xxxxxxxx	sto milijuna
8	osam	17	sedamnaest	1xxxxxxxxx	milijarda
9	devet	18	osamnaest	1xxxxxxxxxx	deset milijardi
		19	devetnaest	1xxxxxxxxxxx	sto milijardi

For a given uppercase letter, list all positive integers whose Croatian reading starts with that letter in increasing order. For example, the sequence for P starts 5, 15, 50, 51, 52, ..., 59, 500, 501, ...

Find the N-th number in the sequence for the given letter.

Input

The input contains a letter L and an integer N separated by a space. L is one of D, J, M, O, P, S, and T.

The answer is guaranteed not to exceed 10^12.

Output

Print the N-th number in the sequence.

Examples3

Example 1
Input
```
S 1
```
Expected output
```
7
```
Example 2
Input
```
P 13
```
Expected output
```
500
```
Example 3
Input
```
M 1000006
```
Expected output
```
1000000005
```