SPOJ.com - Problem SUFFIX

SUFFIX - Suffixes

#number-theory

Find the smallest natural number X such that, if we write X in bases B₁, B₂ ... B_N, we get strings with suffixes S₁, S₂ ... S_N, respectively.

The possible digits are 0123456789ABCDEFG ... XYZ, with values 0..35. Of course, the number written in base B consists only of the digits with values between 0 and B - 1.

Input

In the first line of input there is an integer N (1 ≤ N ≤ 10) from the task description.

In k^th of the next N lines there is an integer B_k (2 ≤ B_k ≤ 36) and a suffix S_k from the task description.

The given bases will be pairwise distinct. Also, the product of the powers B_k ^ length(S_k) will be less than 10¹⁸.

Output

Print the required X, written in base 10.

Example

Input:
3
5 22
11 A2
18 4

Output:
112

Input:
5
2 110
32 E
25 M3
28 2
7 2

Output:
53678

Submit solution!

hide comments



	Adrian Satja Kurdija: 2015-05-23 12:23:35 @Szymon: try this one 3 9 71 29 H 16 2F14
	Szymon: 2015-05-20 17:02:47 @Adrian can you give me more tests? have no idea why SIGFPE occures, my code answers properly for both imputs from example and this provided by you in comments...
	Adrian Satja Kurdija: 2015-04-30 12:09:25 @tarunsingal: Yes, it is the right direction. In order to find the intersection of arithmetic progressions, use [spoiler removed]. Last edit: 2015-12-21 07:34:01
	tarunsingal: 2015-04-21 06:30:56 Hi Adrian, I am trying to formulate this problem as follows: Each (b,s) pair can be represented as an arithmetic series. If we can find an arithmetic series, if it exists, which contains terms common to all n arithmetic series( as there are n (b,s) pairs) then first term of this series will be required output. Do you think I am thinking in right direction? Or can you suggest some direction? Tarun.
	Adrian Satja Kurdija: 2015-04-16 13:09:15 @tarunsingal: 560093690230
	tarunsingal: 2015-04-16 05:47:09 Thanks Adrian for test vector. Can you also provide its output value?
	Adrian Satja Kurdija: 2015-04-15 15:23:51 @tarunsingal: try this one 5 9 737 20 BA 19 25 31 5G 23 5
	tarunsingal: 2015-04-15 11:33:46 My solution is exceeding time limit. Can you provide some test case which may help me reproduce this issue on my local machine?
	Adrian Satja Kurdija: 2015-04-07 19:23:17 @Pradd: Everything is fine. 22 is a suffix of 422 and 4 is a suffix of 64.
	Pradd: 2015-04-07 12:08:28 There appears to be some mistakes in the first test case. 112 in Base 5 gives 422 not 22 and 112 in base 18 gives 64 not 4.

Submit solution!

Added by:	Adrian Satja Kurdija
Date:	2015-04-05
Time limit:	0.100s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64 JS-MONKEY
Resource:	Own problem.