### Problem

One day Silence is interested in revolving the digits of a positive integer. In the revolving operation, he can put several last digits to the front of the integer. Of course, he can put all the digits to the front, so he will get the integer itself. For example, he can change 123 into 312, 231 and 123. Now he wanted to know how many different integers he can get that is less than the original integer, how many different integers he can get that is equal to the original integer and how many different integers he can get that is greater than the original integer. We will ensure that the original integer is positive and it has no leading zeros, but if we get an integer with some leading zeros by revolving the digits, we will regard the new integer as it has no leading zeros. For example, if the original integer is 104, we can get 410, 41 and 104.

### Code

```#include <bits/stdc++.h>
using namespace std;

const int maxn = 204800;
int fail[maxn], extend[maxn];
char s1[maxn], s2[maxn];

/**
* fail[i]: x[i...m-1]与x[0...m-1]的最长公共前缀
* extend[i]: y[i...n-1]与x[0...m-1]的最长公共前缀
*/
void pre_EKMP(char x[], int m, int fail[]) {
fail[0] = m;
int j = 0, k = 1;
while (j + 1 < m && x[j] == x[j + 1]) ++j;
fail[1] = j;
for (int i = 2; i < m; i++) {
int p = fail[k] + k - 1;
int L = fail[i-k];
if (i + L < p + 1) fail[i] = L;
else {
j = max(0, p - i + 1);
while (i + j < m && x[i+j] == x[j])j++;
fail[i] = j;
k = i;
}
}
}
void EKMP(char x[], int m, char y[], int n, int fail[], int extend[]) {
pre_EKMP(x, m, fail);
int j = 0, k = 0;
while (j < n && j < m && x[j] == y[j]) ++j;
extend[0] = j;
for (int i = 1; i < n; i++) {
int p = extend[k] + k - 1;
int L = fail[i-k];
if (i + L < p + 1) extend[i] = L;
else {
j = max(0, p - i + 1);
while (i + j < n && j < m && y[i+j] == x[j]) ++j;
extend[i] = j;
k = i;
}
}
}

void getFail(const char *P, int *f, int len) {
f[0] = f[1] = 0;
for(int i = 1; i < len; ++i) {
int j = f[i];
while(j && P[i] != P[j]) j = f[j];
f[i+1] = P[i]==P[j] ? j+1 : 0;
}
}

int main() {
int T, kase = 0; scanf("%d", &T);
while (T--) {
scanf("%s", s1);
int len1 = strlen(s1);
for(int i = 0; i < len1; ++i)
s2[i] = s2[i+len1] = s1[i];
int len2 = 2 * len1;
s2[len2] = 0;
EKMP(s1, len1, s2, len2, fail, extend);
int cnt1 = 0, cnt2 = 0, cnt3 = 0;
for(int i = 0; i < len1; ++i) {
int cur = extend[i];
if(cur >= len1) ++cnt2;
else {
if(s2[i+cur] < s1[cur])
++cnt1;
else ++cnt3;
}
}
getFail(s1, fail, len1);
int t = len1 - fail[len1];
int tot = len1 % t ? 1 : len1 / t;
printf("Case %d: %d %d %d\n", ++kase, cnt1/tot, cnt2/tot, cnt3/tot);
}
return 0;
}
```