Find a substring whose numeric value is divisible by 3, then report its ends.
Problem
You are given a string consisting of decimal digits. Your task is to find a contiguous substring that can be interpreted as a number divisible by 3.
Among all such substrings, output one valid pair of indices for its left and right ends. If there are multiple answers, any one of them is acceptable.
If no such substring exists, report that it is impossible.
Notes
- A substring must be contiguous.
- The substring should contain at least one digit.
- Leading zeros are allowed if they appear in the chosen substring.
Input Format
- A single line containing a digit string
s.
Output Format
- If a valid substring exists, output two integers
landr— the 1-based indices of one substring whose numeric value is divisible by3. - Otherwise, output
-1.
Constraints
1 <= |s| <= $10^{5}$scontains only characters0-9
Hints
- A number is divisible by 3 if the sum of its digits is divisible by 3.
- Use prefix sums of digit values modulo 3 to compare substrings efficiently.
Input Format
A single string s of digits.
Output Format
Print either:
- two 1-based indices
l rfor a substring divisible by3, or -1if no such substring exists.
Constraints
1 <= |s| <= $10^{5}$scontains only digits0-9
Example 1
Input
303
Output
1 1
Explanation
The substring s[1..1] = "3" is divisible by 3.
Example 2
Input
1234
Output
1 2
Explanation
The substring "12" has sum 3, so it is divisible by 3.
Show 1 more example
Example 3
Input
1
Output
-1
Explanation
There is no non-empty substring divisible by 3.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.