codeforces 612A The Text Splitting(扩展欧几里得)

You are given the string s of length n and the numbers p, q. Split the string s to pieces of length p and q.

For example, the string "Hello" for p = 2, q = 3 can be split to the two strings "Hel" and "lo" or to the two strings "He" and "llo".

Note it is allowed to split the string s to the strings only of length p or to the strings only of length q (see the second sample test).

Input

The first line contains three positive integers n, p, q (1 ≤ p, q ≤ n ≤ 100).

The second line contains the string s consists of lowercase and uppercase latin letters and digits.

Output

If it's impossible to split the string s to the strings of length p and q print the only number "-1".

Otherwise in the first line print integer k — the number of strings in partition of s.

Each of the next k lines should contain the strings in partition. Each string should be of the length p or q. The string should be in order of their appearing in string s — from left to right.

If there are several solutions print any of them.

Sample test(s)

input

5 2 3
Hello

output

2
He
llo

input

10 9 5
Codeforces

output

2
Codef
orces

input

6 4 5
Privet

output

-1

input

8 1 1
abacabac

output

8
a
b
a
c
a
b
a
c

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 void exgcd(int a,int b,int& d,int& x,int& y)
 6 {
 7     if(!b)d=a,x=1,y=0;
 8     else exgcd(b,a%b,d,y,x),y-=x*(a/b);
 9 }
10 int main()
11 {
12     char s[105];
13     int n,p,q,d,x,y;
14     bool ok;
15     scanf("%d%d%d",&n,&p,&q);
16     scanf("%s",s);
17     int t=0;
18     if(n%p==0)
19     {
20         n/=p;
21         printf("%d
",n);
22         for(int i=0;i<n;i++)
23         {
24             for(int j=0;j<p;j++)
25                 printf("%c",s[t++]);
26             puts("");
27         }
28     }
29     else if(n%q==0)
30     {
31         n/=q;
32         printf("%d
",n);
33         for(int i=0;i<n;i++)
34         {
35             for(int j=0;j<q;j++)
36                 printf("%c",s[t++]);
37             puts("");
38         }
39     }
40     else
41     {
42         ok=1;
43         exgcd(p,q,d,x,y);
44         if(n%d!=0)
45         {
46             puts("-1");
47             return 0;
48         }
49         else
50         {
51             x*=n/d,y*=n/d;
52             int a=p/d,b=q/d;
53             int tx=x,ty=y;
54             while(x<0||y<0)
55             {
56                 x+=b;
57                 y-=a;
58                 if(tx*x<0&&ty*y<0)
59                 {
60                     while(x<0||y<0)
61                     {
62                         x-=b;
63                         y+=a;
64                         if(tx*x<0&&ty*y<0)
65                         {
66                             ok=0;
67                             break;
68                         }
69                     }
70                     break;
71                 }
72             }
73         }
74         if(ok)
75         {
76             printf("%d
",x+y);
77             for(int i=0;i<x;i++)
78             {
79                 for(int j=0;j<p;j++)
80                     printf("%c",s[t++]);
81                 puts("");
82             }
83             for(int i=0;i<y;i++)
84             {
85                 for(int j=0;j<q;j++)
86                     printf("%c",s[t++]);
87                 puts("");
88             }
89         }
90         else
91             puts("-1");
92     }
93     return 0;
94 }

codeforces 612A The Text Splitting(扩展欧几里得)

A. The Text Splitting