The Sum of Good Numbers solution codeforces

The Sum of Good Numbers solution codeforces

Let’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. 𝑥=𝑎𝑖+𝑎𝑖+1x=ai+ai+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 𝑎=[12,5,6,133]a=[12,5,6,133], then 𝑠=1256133s=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.

Input

The first line contains the string 𝑠s (2|𝑠|51052≤|s|≤5⋅105).

The second line contains an integer 𝑥x (2𝑥<102000002≤x<10200000).

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.

Output

In the first line, print two integers 𝑙1l1, 𝑟1r1, meaning that the first term of the sum (𝑎𝑖ai) is in the string 𝑠s from position 𝑙1l1 to position 𝑟1r1.

In the second line, print two integers 𝑙2l2, 𝑟2r2, meaning that the second term of the sum (𝑎𝑖+1ai+1) is in the string 𝑠s from position 𝑙2l2 to position 𝑟2r2.

Examples
input

Copy
1256133
17
output

Copy
1 2
3 3
input

Copy
9544715561
525
output

Copy
2 3
4 6
input

Copy
239923
5
output

Copy
1 1
2 2
input

Copy
1218633757639
976272
output

Copy
2 7
8 13
Note

In the first example 𝑠[1;2]=12s[1;2]=12 and 𝑠[3;3]=5s[3;3]=5, 12+5=1712+5=17.

In the second example 𝑠[2;3]=54s[2;3]=54 and 𝑠[4;6]=471s[4;6]=471, 54+471=52554+471=525.

In the third example 𝑠[1;1]=2s[1;1]=2 and 𝑠[2;2]=3s[2;2]=3, 2+3=52+3=5.

In the fourth example 𝑠[2;7]=218633s[2;7]=218633 and 𝑠[8;13]=757639s[8;13]=757639, 218633+757639=976272218633+757639=976272.

Leave a Comment