**QUESTION**

Puchi and Ghissi are playing a game with strings. As Ghissi is a champion at strings, Puchi decides to challenge her. \nHe gives Ghissi a string S and an integer K . The objective for Ghissi is to find a substring of S such that: \n- The substring occurs at the start of the string S. \n- The substring occurs at the end of the string S. \n- The substring also occurs somewhere in the middle of the string S but should not be a prefix of S and it should end on or before position K (1-Based Index). In other words, this substring should not start from the beginning of the string and must end on or before the position K.\n\nHelp Ghissi win the game by finding the largest possible substring.\n\nINPUT\nFirst line contains an integer T. T test cases follow. \nEach test case contains a string S of lowercase alphabets ( [a-z] ) and an integer K separated by a space. \n\nOUTPUT\nPrint the largest possible substring that satisfies the given criteria.\nIf such a substring does not exist, print \”Puchi is a cheat!\” without the quotes.\n\nCONSTRAINTS\n1<=T<=10\n1<=|S|<=10^6\n1<=K<=|S|\nS contains only lowercase alphabets [a-z].

**ANSWER**

```
#include <stdio.h>
#include <string.h>
int main() {
int t;
scanf("%d", &t);
while(t--) {
char s[1000001];
int k;
scanf("%s%d", s, &k);
int len = strlen(s);
int arr[1000001], j = 0, i = 1, m, temp, l, p, count;
arr[0] = 0;
while(i < len) {
if(s[j] == s[i]) {
arr[i++] = j + 1;
j++;
} else if(s[j] != s[i] && j >= 1) {
j = 0;
} else if(s[j] != s[i] && j == 0) {
arr[i++] = 0;
}
}
int max = arr[0];
for (m = 1; m < k; m++) {
if (max < arr[m]) {
max = arr[m];
}
}
count = arr[len - 1];
while (count > max) {
count = arr[count - 1];
}
if (count) {
for (p = 0; p < count; p++) {
printf("%c",s[p]);
}
printf("\n");
} else {
printf("Puchi is a cheat!\n");
}
}
return 0;
}
```