#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
struct pair{
int word;
int indexInS;
};
int cmp(const void* a, const void* b) {
return (((struct pair*)a)->indexInS - ((struct pair*)b)->indexInS);
}
// find substring such that the return index % n == 0
char* findSubstringAtN(char* s, char* word, int n) {
int i;
while (1) {
i = 0;
for (i = 0; i < n; ++i)
if (s[i] != word[i]) break;
if (i == n) return s;
// not found
s+=i;
while (*s != '\0' && i < n) {
++s;
++i;
}
if (i != n) return NULL;
}
}
int* findSubstring(char* s, char** words, int wordsSize, int* returnSize) {
int wordLen
= strlen(words
[0]); *returnSize = 0;
int i, j, k, continue_flag;
char* ptr;
struct pair index[wordsSize], temp;
for (i = 0; i < wordLen && s+i != '\0'; ++i) {
//if (start[i] == 0) continue;
char* s1 = s + i;
int skip = 0;
for (j = 0; j < wordsSize ; ++j) {
ptr = findSubstringAtN(s1+skip, words[j], wordLen);
printf("%d %d %p ", i
, j
, ptr
); if (ptr) {
index[j].word = j;
index[j].indexInS = ptr - s1;
if (index[j].indexInS == skip) skip += wordLen;
}
else break;
}
if (ptr == NULL) continue;
while (1) {
continue_flag = 0;
qsort(index
, wordsSize
, sizeof(struct pair
), cmp
); for (j = 0; j < wordsSize - 1; ++j) {
for (k = 0; k < wordsSize; ++k)
printf("%d ", index
[k
].
indexInS); // words = ["aa","aa", ...]
if (index[j].indexInS == index[j + 1].indexInS) {
ptr = findSubstringAtN(s1+index[j].indexInS+wordLen, words[index[j].word], wordLen);
if (ptr) {
index[j+1].indexInS = ptr - s1;
temp = index[j + 1];
for (k = j+2; k<wordsSize; ++k) {
if (index[k].indexInS < temp.indexInS)
index[k-1] = index[k];
else break;
}
index[k-1] = temp;
//qsort(index, wordsSize, sizeof(struct pair), cmp);
--j;
continue;
}
else break;
}
if (index[j].indexInS + wordLen != index[j + 1].indexInS) {
ptr = findSubstringAtN(s1+index[0].indexInS+wordLen, words[index[0].word], wordLen);
if (ptr) {
index[0].indexInS = ptr - s1;
temp = index[0];
for (k = 1; k<wordsSize; ++k) {
if (index[k].indexInS < temp.indexInS)
index[k-1] = index[k];
else break;
}
index[k-1] = temp;
if (j == 0) --j;
else j -= 2;
continue;
}
break;
}
}
if (ptr == NULL) break;
//if (continue_flag == 1) continue;
ans[*returnSize] = index[0].indexInS + i;
(*returnSize)++;
// find next concatenated string
ptr = findSubstringAtN(s1+index[wordsSize-1].indexInS+wordLen, words[index[0].word], wordLen);
if (ptr) index[0].indexInS = ptr - s1;
else break; // no more concatenated string
}
}
return ans;
}
int main(void) {
// your code goes here
//char s[] = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
char s[] = "b";
char* words[5000];
//for (int i = 0; i < 5000; ++i)
// words[i] = "a";
words[0] = "bbb";
words[1] = "bbb";
words[2] = "a";
words[3] = "c";
words[4] = "a";
words[5] = "a";
words[6] = "a";
words[7] = "b";
words[8] = "c";
int returnSize;
int*a = findSubstring(s, words, 2, &returnSize);
for (int i = 0; i < returnSize; ++i)
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgoKLyoqCiAqIE5vdGU6IFRoZSByZXR1cm5lZCBhcnJheSBtdXN0IGJlIG1hbGxvY2VkLCBhc3N1bWUgY2FsbGVyIGNhbGxzIGZyZWUoKS4KICovCnN0cnVjdCBwYWlyewogICAgaW50IHdvcmQ7CiAgICBpbnQgaW5kZXhJblM7Cn07CgppbnQgY21wKGNvbnN0IHZvaWQqIGEsIGNvbnN0IHZvaWQqIGIpIHsKICAgIHJldHVybiAoKChzdHJ1Y3QgcGFpciopYSktPmluZGV4SW5TIC0gKChzdHJ1Y3QgcGFpciopYiktPmluZGV4SW5TKTsKfQovLyBmaW5kIHN1YnN0cmluZyBzdWNoIHRoYXQgdGhlIHJldHVybiBpbmRleCAlIG4gPT0gMApjaGFyKiBmaW5kU3Vic3RyaW5nQXROKGNoYXIqIHMsIGNoYXIqIHdvcmQsIGludCBuKSB7CiAgICBpbnQgaTsKICAgIHdoaWxlICgxKSB7CiAgICAgICAgaSA9IDA7CiAgICAgICAgZm9yIChpID0gMDsgaSA8IG47ICsraSkKICAgICAgICAgICAgaWYgKHNbaV0gIT0gd29yZFtpXSkgYnJlYWs7CiAgICAgICAgaWYgKGkgPT0gbikgcmV0dXJuIHM7CiAgICAgICAgLy8gbm90IGZvdW5kCiAgICAgICAgcys9aTsKICAgICAgICB3aGlsZSAoKnMgIT0gJ1wwJyAmJiBpIDwgbikgewogICAgICAgICAgICArK3M7CiAgICAgICAgICAgICsraTsKICAgICAgICB9CiAgICAgICAgaWYgKGkgIT0gbikgcmV0dXJuIE5VTEw7CiAgICB9Cn0KCmludCogZmluZFN1YnN0cmluZyhjaGFyKiBzLCBjaGFyKiogd29yZHMsIGludCB3b3Jkc1NpemUsIGludCogcmV0dXJuU2l6ZSkgewogICAgaW50IHdvcmRMZW4gPSBzdHJsZW4od29yZHNbMF0pOwogICAgaW50KiBhbnMgPSAoaW50KiltYWxsb2Moc2l6ZW9mKGludCkgKiBzdHJsZW4ocykpOwogICAgKnJldHVyblNpemUgPSAwOwoKICAgIGludCBpLCBqLCBrLCBjb250aW51ZV9mbGFnOwogICAgY2hhciogcHRyOwoKICAgIHN0cnVjdCBwYWlyIGluZGV4W3dvcmRzU2l6ZV0sIHRlbXA7CiAgICBmb3IgKGkgPSAwOyBpIDwgd29yZExlbiAmJiBzK2kgIT0gJ1wwJzsgKytpKSB7CiAgICAgICAgLy9pZiAoc3RhcnRbaV0gPT0gMCkgY29udGludWU7CiAgICAgICAgY2hhciogczEgPSBzICsgaTsKICAgICAgICBpbnQgc2tpcCA9IDA7CgogICAgICAgIGZvciAoaiA9IDA7IGogPCB3b3Jkc1NpemUgOyArK2opIHsKICAgICAgICAgICAgcHRyID0gZmluZFN1YnN0cmluZ0F0TihzMStza2lwLCB3b3Jkc1tqXSwgd29yZExlbik7CiAgICAgICAgICAgIHByaW50ZigiJWQgJWQgJXAgIiwgaSwgaiwgcHRyKTsKICAgICAgICAgICAgaWYgKHB0cikgewogICAgICAgICAgICAgICAgaW5kZXhbal0ud29yZCA9IGo7CiAgICAgICAgICAgICAgICBpbmRleFtqXS5pbmRleEluUyA9IHB0ciAtIHMxOwogICAgICAgICAgICAgICAgaWYgKGluZGV4W2pdLmluZGV4SW5TID09IHNraXApIHNraXAgKz0gd29yZExlbjsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIGJyZWFrOwogICAgICAgIH0KICAgICAgICBpZiAocHRyID09IE5VTEwpIGNvbnRpbnVlOwogICAgICAgIHdoaWxlICgxKSB7CiAgICAgICAgICAgIGNvbnRpbnVlX2ZsYWcgPSAwOwogICAgICAgICAgICBxc29ydChpbmRleCwgd29yZHNTaXplLCBzaXplb2Yoc3RydWN0IHBhaXIpLCBjbXApOwogICAgICAgICAgICBmb3IgKGogPSAwOyBqIDwgd29yZHNTaXplIC0gMTsgKytqKSB7CiAgICAgICAgICAgIAlmb3IgKGsgPSAwOyBrIDwgd29yZHNTaXplOyArK2spCiAgICAgICAgICAgIAkJcHJpbnRmKCIlZCAiLCBpbmRleFtrXS5pbmRleEluUyk7CiAgICAgICAgICAgIAlwcmludGYoIlxuIik7CiAgICAgICAgICAgICAgICAvLyB3b3JkcyA9IFsiYWEiLCJhYSIsIC4uLl0KICAgICAgICAgICAgICAgIGlmIChpbmRleFtqXS5pbmRleEluUyA9PSBpbmRleFtqICsgMV0uaW5kZXhJblMpIHsKICAgICAgICAgICAgICAgIAlwcmludGYoIjE6JWRcbiIsIGopOwogICAgICAgICAgICAgICAgICAgIHB0ciA9IGZpbmRTdWJzdHJpbmdBdE4oczEraW5kZXhbal0uaW5kZXhJblMrd29yZExlbiwgd29yZHNbaW5kZXhbal0ud29yZF0sIHdvcmRMZW4pOwogICAgICAgICAgICAgICAgICAgIGlmIChwdHIpIHsKICAgICAgICAgICAgICAgICAgICAgICAgaW5kZXhbaisxXS5pbmRleEluUyA9IHB0ciAtIHMxOwogICAgICAgICAgICAgICAgICAgICAgICB0ZW1wID0gaW5kZXhbaiArIDFdOwogICAgICAgICAgICAgICAgICAgICAgICBmb3IgKGsgPSBqKzI7IGs8d29yZHNTaXplOyArK2spIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIChpbmRleFtrXS5pbmRleEluUyA8IHRlbXAuaW5kZXhJblMpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaW5kZXhbay0xXSA9IGluZGV4W2tdOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgZWxzZSBicmVhazsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBpbmRleFtrLTFdID0gdGVtcDsKICAgICAgICAgICAgICAgICAgICAgICAgLy9xc29ydChpbmRleCwgd29yZHNTaXplLCBzaXplb2Yoc3RydWN0IHBhaXIpLCBjbXApOwogICAgICAgICAgICAgICAgICAgICAgICAtLWo7CiAgICAgICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBlbHNlIGJyZWFrOwogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIGlmIChpbmRleFtqXS5pbmRleEluUyArIHdvcmRMZW4gIT0gaW5kZXhbaiArIDFdLmluZGV4SW5TKSB7CiAgICAgICAgICAgICAgICAJcHJpbnRmKCIyOiVkXG4iLCBqKTsKICAgICAgICAgICAgICAgICAgICBwdHIgPSBmaW5kU3Vic3RyaW5nQXROKHMxK2luZGV4WzBdLmluZGV4SW5TK3dvcmRMZW4sIHdvcmRzW2luZGV4WzBdLndvcmRdLCB3b3JkTGVuKTsKICAgICAgICAgICAgICAgICAgICBpZiAocHRyKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIGluZGV4WzBdLmluZGV4SW5TID0gcHRyIC0gczE7CiAgICAgICAgICAgICAgICAgICAgICAgIHRlbXAgPSBpbmRleFswXTsKICAgICAgICAgICAgICAgICAgICAgICAgZm9yIChrID0gMTsgazx3b3Jkc1NpemU7ICsraykgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGluZGV4W2tdLmluZGV4SW5TIDwgdGVtcC5pbmRleEluUykKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpbmRleFtrLTFdID0gaW5kZXhba107CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBlbHNlIGJyZWFrOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGluZGV4W2stMV0gPSB0ZW1wOwogICAgICAgICAgICAgICAgICAgICAgICBpZiAoaiA9PSAwKSAtLWo7CiAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UgaiAtPSAyOwogICAgICAgICAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYgKHB0ciA9PSBOVUxMKSBicmVhazsKICAgICAgICAgICAgLy9pZiAoY29udGludWVfZmxhZyA9PSAxKSBjb250aW51ZTsKICAgICAgICAgICAgcHJpbnRmKCJvdXRcbiIpOwogICAgICAgICAgICBhbnNbKnJldHVyblNpemVdID0gaW5kZXhbMF0uaW5kZXhJblMgKyBpOwogICAgICAgICAgICAoKnJldHVyblNpemUpKys7CiAgICAgICAgICAgIC8vIGZpbmQgbmV4dCBjb25jYXRlbmF0ZWQgc3RyaW5nCiAgICAgICAgICAgIHB0ciA9IGZpbmRTdWJzdHJpbmdBdE4oczEraW5kZXhbd29yZHNTaXplLTFdLmluZGV4SW5TK3dvcmRMZW4sIHdvcmRzW2luZGV4WzBdLndvcmRdLCB3b3JkTGVuKTsKICAgICAgICAgICAgaWYgKHB0cikgaW5kZXhbMF0uaW5kZXhJblMgPSBwdHIgLSBzMTsKICAgICAgICAgICAgZWxzZSBicmVhazsgLy8gbm8gbW9yZSBjb25jYXRlbmF0ZWQgc3RyaW5nCiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIGFuczsKfQoKCmludCBtYWluKHZvaWQpIHsKCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCS8vY2hhciBzW10gPSAiYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWEiOwoJY2hhciBzW10gPSAiYiI7CgljaGFyKiB3b3Jkc1s1MDAwXTsKCS8vZm9yIChpbnQgaSA9IDA7IGkgPCA1MDAwOyArK2kpCgkvLwl3b3Jkc1tpXSA9ICJhIjsKCXdvcmRzWzBdID0gImJiYiI7Cgl3b3Jkc1sxXSA9ICJiYmIiOwoJd29yZHNbMl0gPSAiYSI7Cgl3b3Jkc1szXSA9ICJjIjsKCXdvcmRzWzRdID0gImEiOwoJd29yZHNbNV0gPSAiYSI7Cgl3b3Jkc1s2XSA9ICJhIjsKCXdvcmRzWzddID0gImIiOwoJd29yZHNbOF0gPSAiYyI7CgoJaW50IHJldHVyblNpemU7CglpbnQqYSA9IGZpbmRTdWJzdHJpbmcocywgd29yZHMsIDIsICZyZXR1cm5TaXplKTsKCXByaW50Zigib3V0cHV0OiIpOwoJZm9yIChpbnQgaSA9IDA7IGkgPCByZXR1cm5TaXplOyArK2kpCgkJcHJpbnRmKCIlZCAiLCBhW2ldKTsKCXJldHVybiAwOwp9Cg==