codeforces 1079B Personalized Cup

题目描述：

At many competitions that have a word «cup» in its official name the winner is presented with an actual cup. This time the organizers of one unusual programming competition have decided to please the winner even more and to add a nameplate to the cup with the handle of the winner.

The nameplate is to be rectangular and the text on it will be printed as a table of several rows and columns. Having some measurements done, the organizers have found out that the number aa of rows cannot be greater than 55 while the number bb of columns cannot exceed 2020. Every cell of the table will contain either an asterisk («*») or a letter of user's handle.

Furthermore, the organizers want the rows of the table to be uniform, which means that the number of asterisks used in different rows should differ by at most one (i.e. you can't have two asterisks in the first row and none in the second). The main goal, however, is to obtain the winner's handle precisely when reading the table from top to bottom and from left to right in every row (skipping asterisks).

The organizers want for the nameplate to have as few rows as possible and among all valid tables with the minimum number of rows they want to choose the one that has the minimum number of columns.

The winner is not yet determined so your task is to write a program that, given a certain handle, generates the necessary table.

Input

The only line contains one string ss (1≤|s|≤1001≤|s|≤100), comprised of uppercase and lowercase Latin letters,  — the handle of the winner.

Output

In the first line output the minimum number aa of rows in the table and the minimum number bb of columns in an optimal table with rows.

The following aa lines should contain bb characters each  — any valid table.

 

Examples

input

tourist  

output

1 7 tourist

input

MyNameIsLifeIAmForeverByYourSideMyNameIsLife

output

3 15 MyNameIsLifeIAm ForeverByYourSi deMyNameIsL*ife

题目大意就是给定一个字符串，要求切割成行不大于5，列不大于20的子串，且要求每个子串的长度必须相同，不同可以补*，但是不同行“*”的个数最多相差一个。

先求出该字符串应该分成多少行，然后根据行号求出还多出多少字符，再对多出的字符进行均匀分配。

#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAX = 109; char a[MAX]; int len[25]; int main() { while(~scanf("%s", a)) { int lena = strlen(a); int col = 0, row; for(int i = 1; i <= 5; i++) { if(lena / i < 20) { row = i; break; } if(lena / i == 20 && lena % i == 0) { row = i; break; } } col = lena / row; int yu = lena % row; int l = yu / row; int yy = yu % row; int ll = 0; for(int i = 0; i < row; i++) { len[i] += l; len[i] += col; if(i < yy) len[i] ++; } ll = len[0]; int i, j = 0, st; printf("%d %d\n", row, ll); for(i = 0; i < row; i++) { st = j; if(len[i] < ll) { for(int k = 0; k < ll - len[i]; k++) printf("*"); } for(j = st; j < len[i] + st; j++) printf("%c", a[j]); printf("\n"); } memset(a, '\0', sizeof(a)); memset(len, 0, sizeof(len)); } return 0; }