ural One-two, One-two 2

One-two, One-two 2

Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u

Description

A year ago the famous gangster Vito Maretti woke up in the morning and realized that he was bored of robbing banks of round sums. And for the last year he has been taking from banks sums that have only digits 1 and 2 in their decimal notation. After each robbery, Vito divides the money between N members of his gang. Your task is to determine the minimal stolen sum which is a multiple of N.

Input

The input contains the number N (1 ≤ N ≤ 10 ⁶).

Output

Output the minimal number which is a multiple of N and whose decimal notation contains only digits 1 and 2. If it contains more than 30 digits or if there are no such numbers, then output "Impossible".

Sample Input

input	output
5	Impossible
8	112

AC代码：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define N 5000002
 5 using namespace std;
 6 int n;         
 7 struct Node{
 8     int dig,mod;
 9     int f;//模拟指针，指向数组的下一个元素 
10 }nod[N];
11 
12 int l,r;
13 bool vis[N];
14 int ret;
15 
16 void BFS(){
17     while(l<r){
18         int tmod1=(nod[l].mod*10+1)%n;
19         int tmod2=(nod[l].mod*10+2)%n;
20         if(!vis[tmod1]){
21           vis[tmod1]=1;
22             r++;
23             nod[r].mod=tmod1;   
24             nod[r].dig=1;
25             nod[r].f=l;
26             if(tmod1==0){ret=r;return ;}
27         }
28         if(!vis[tmod2]){
29           vis[tmod2]=1;
30             r++;
31             nod[r].mod=tmod2;
32             nod[r].dig=2;
33             nod[r].f=l;
34             if(tmod2==0){ret=r;return ;}
35         }
36 
37         l++;
38 
39     }
40 }
41 
42 void out(int x)
43 {
44     if(x>0)out(nod[x].f);
45     else if(x==0)return;
46     cout<<nod[x].dig;
47 }
48 
49 void first()
50 {
51    nod[1].dig=1;
52    nod[1].f=0;
53    nod[1].mod=1;
54    nod[2].dig=2;
55    nod[2].f=0;
56    nod[2].mod=2;
57 }
58 
59 int main()
60 {
61     while(cin>>n)
62     {
63         if(n==1||n==2){
64             cout<<n<<endl;
65             continue;
66         }
67         first();
68         
69         l=1;r=2;ret=0;
70         memset(vis,0,sizeof(vis));
71         vis[1]=vis[2]=1;
72        
73         BFS();
74         if(ret==0){
75             cout<<"Impossible"<<endl;
76             continue;
77         }
78         out(ret);
79         cout<<endl;
80     }
81     return 0;
82 }