思考题 about cheating

Lottery Cheating

Let's have some lottery!
In this lottery system, a number string S and an array of integers A is predetermined. It is known that |A|=|S| and let's define A_0=0.
Each user chooses a number string T(|T|=|S|). The amount of money he will get equals to A_{\sum^{|T|}_{i=1}[S_i=T_i]}. That is to say, it depends on the number of identical digits of S and T.
For example, if A=[1,10,100] and S="019"
if T="000" you will get 1 yuan
if T="011" or "119" you will get 10 yuan
if T="019" you will get 100 yuan
if T="888" you will get 0 yuan sadly
But as a bussinessman, you want to do some cheats. You are given the users' chosen numbers Ts and the sequence A, find such a string S that you need to pay the least money. Print the string.

Example

Input 1
A={1,10,100}
Ts={"110","512","777"}
Output 1
999
Explain 1
The total money you need to pay is 0. Hooray!
Input 1
A={1,10,100,1000,10000}
Ts={"12345","23456","34567","45678","56789","67890","78901","89012","90123","01234"}
Output 1
11111
Explain 1
The total money you need to pay is 1+0+0+0+0+0+1+1+1+1=5

Constriants

Subtask 1(20%):For each 1\leq i,j\leq |S|, A_i-A_{i-1}=A_j-A_{j-1}
Subtask 2(20%): For each 1\leq i,j\leq |S|,A_i=A_j
Subtask 3(20%):|S|\times |Ts|\leq 2000
Subtask 4(40%):|S|\times |Ts|\leq 100000.For each 1\leq i\leq j\leq |S|, A_i\leq A_j

No cheating!