G. The Sum of Good Numberstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet's call a positive integer good if there is no digit 0 in its decimal representation.For an array of a good numbers a, one found out that the sum of some two neighboring elements is equal to x (i.e. x = a_i + a_{i + 1} for some i). x had turned out to be a good number as well.Then the elements of the array a were written out one after another without separators into one string s. For example, if a = [12, 5, 6, 133], then s = 1256133.You are given a string s and a number x. Your task is to determine the positions in the string that correspond to the adjacent elements of the array that have sum x. If there are several possible answers, you can print any of them.InputThe first line contains the string s (2 \le |s| \le 5 \cdot 10^5).The second line contains an integer x (2 \le x < 10^{200000}).An additional constraint on the input: the answer always exists, i.e you can always select two adjacent substrings of the string s so that if you convert these substrings to integers, their sum is equal to x.OutputIn the first line, print two integers l_1, r_1, meaning that the first term of the sum (a_i) is in the string s from position l_1 to position r_1.In the second line, print two integers l_2, r_2, meaning that the second term of the sum (a_{i + 1}) is in the string s from position l_2 to position r_2.ExamplesInput
1256133
17
Output
1 2
3 3
Input
9544715561
525
Output
2 3
4 6
Input
239923
5
Output
1 1
2 2
Input
1218633757639
976272
Output
2 7
8 13
NoteIn the first example s[1;2] = 12 and s[3;3] = 5, 12+5=17.In the second example s[2;3] = 54 and s[4;6] = 471, 54+471=525.In the third example s[1;1] = 2 and s[2;2] = 3, 2+3=5.In the fourth example s[2;7] = 218633 and s[8;13] = 757639, 218633+757639=976272.
1256133
17

1 2 3 3 
['hashing', 'math', 'string suffix structures', 'strings', '*3200']