Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

memory = {}


def solve(N: int, C: "List[int]"):
    # print(dfs(tuple(C), N, 0))

    dp = [0]*N
    last = [-1]*N
    for i, s in enumerate(C):
        if i == 0:
            dp[i] = 1
        else:
            dp[i] = dp[i-1]
            if last[s] != -1 and last[s] < i-1:
                dp[i] = (dp[i] + dp[last[s]]) % MOD
        last[s] = i
    # print(dp, souwa, pre)
    print(dp[-1])
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, C)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

memory = {}


def solve(N: int, C: "List[int]"):
    # print(dfs(tuple(C), N, 0))

    dp = [0]*N
    last = [-1]*(2*(10**5)+1)
    for i, s in enumerate(C):
        if i == 0:
            dp[i] = 1
        else:
            dp[i] = dp[i-1]
            if last[s] != -1 and last[s] < i-1:
                dp[i] = (dp[i] + dp[last[s]]) % MOD
        last[s] = i
    # print(dp, souwa, pre)
    print(dp[-1])
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, C)


if __name__ == '__main__':
    main()
n,k=map(int,input().split())
if n<k:
  if:k<2*n:
      print(k-n)
  else:
    print(n)
elif n==k:
  print(0)
else:
  m=n//k
  r=n-m*k
  print(min(r,abs(r-k)))

### FIXED CODE ###

n,k=map(int,input().split())
if n<k:
  if k<2*n:
      print(k-n)
  else:
    print(n)
elif n==k:
  print(0)
else:
  m=n//k
  r=n-m*k
  print(min(r,abs(r-k)))
list = [0] * 4
a = int(input())
list[0] = a/3600
a_p = a%3600
list[1] = a_p/60
list[2] = a_p%60
print ":".int(list)

### FIXED CODE ###

int = int(input())

h = int // 3600
h_mod = int % 3600

m = h_mod // 60
s = h_mod % 60

print(h, ":", m, ":", s, sep='')
W = input()

count = 0
while True:
    line = input()
    if line == 'END_OF_TEXT'
        break
    for s in line.lower()split():
        if s == W:        
            count += 1


print(count)

### FIXED CODE ###

W = input()
 
count = 0
while True:
    line = input()
    if line == 'END_OF_TEXT':
        break
 
    for word in line.split():
        if word.lower() == W.lower():
            count += 1
print(count)
k,n = map(int,input().split())
a = list(map(int,input().split()))
b = []

for i in range(1,n+1):
  b.append(a[i] - a[i-1])
b.append(k - a[n] + a[0])
b = sorted(b)

print(sum(b[:n-1])


### FIXED CODE ###

k,n = map(int,input().split())
a = list(map(int,input().split()))
b = []

for i in range(1,n):
  b.append(a[i] - a[i - 1])
b.append(k - a[n-1] + a[0])

b = sorted(b)
print(sum(b[:n-1]))
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N, M, K = input_int()
A = many_int()
B = many_int()


A_index=0
B_index=0
books = 0

while True:
    temp = books
    if N <= A_index and M <= B_index:
        break
    
    elif N <= A_index  and K>=B[B_index]:
        books += 1
        K -= B[B_index]
        B_index += 1
        
    elif M <= B_index  and K>=A[A_index]:
        books += 1
        K -= A[A_index]
        A_index += 1
        
    elif A[A_index] > B[B_index] and K>=B[B_index]:
        books += 1
        K -= B[B_index]
        B_index += 1
        
    elif A[A_index] < B[B_index] and K>=A[A_index]:
        books += 1
        K -= A[A_index]
        A_index += 1
    if temp==books:
        break
print(books)

### FIXED CODE ###

def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N, M, K = input_int()
A = many_int()
B = many_int()


import itertools as it
import bisect

def bins(A, B, K):
    A_it = list(it.accumulate(A))
    B_it = list(it.accumulate(B))

    A_index = bisect.bisect_right(A_it, K)
    B_index = bisect.bisect_right(B_it, K)

    A_it = [0]+A_it[:A_index]
    B_it = B_it[:B_index]

    maxs = 0
    count=0
    for i in A_it[::-1]:
        if K-i < 0:
            continue
        now = K-i
        B_index = bisect.bisect_right(B_it, now)

        maxs = max(maxs, B_index + max(A_index - count,0))
        count+=1

    return maxs

print(bins(A,B,K))
#!/usr/bin/env python3
from collections import Counter

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = set()
    for i,l in Counter(A).items():
        if l == 1:
            B.add(i)
    A = sorted(B)
    N = len(A)
    # L = [1] * (N+1)
    # for i in range(N):
    #     L[i+1] = (L[i]*A[i])//gcd(L[i],A[i])
    ans = 0
    # print(A)
    # print(L)
    A.sort()
    for i in range(N):
        flag = True
        for j in range(i):
            if A[i] % A[j] == 0:
                flag = False
                break
        if flag:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    x = list(map(int, input().split()))
    print(x.index(0)+1)

if __name__ == "__main__":
    main()
N,M,P = map(int, input().split())

es = []

for i in range(M):
    a,b,c = map(int, input().split())
    es.append((a-1, b-1, c))

INF = float("inf")

d = [INF for _ in range(N)] 
d[0] = 0
"""
頂点Nに向かうまでに関係ない閉路に注意する

無限にコインを拾える場合、
・ある閉路を一周したときの得点と支払いの収支がプラス
・その閉路からゴールまで行ける
である。これがない場合、全てのノードを経由してゴールまで行く（N-1回移動）までにコインの枚数が最大になる
なので、一回ベルマンフォード法をやった後もう一回行って一回目と２回目でゴールまでのコイン枚数に変化があればゴ、
ールに行くまでの道に無限にコインをとれる閉路があるといえる

"""

def solve(start):
    for i in range(N):
        for a,b,c, in es:
            if d[a] != INF and d[a] + (-c) + P < d[b]:
                d[b] = d[a] + (-c) + P
                

                if i == N-1 and b == N-1:
                    return -1


    return max(-d[-1][0])


first=solve(0)
if first == -1:
    print(-1)
else:
    second=solve(0)
    if first == second:
        print(max(first, 0))
    else:
        print(-1)

### FIXED CODE ###

N,M,P = map(int, input().split())

es = []

for i in range(M):
    a,b,c = map(int, input().split())
    es.append((a-1, b-1, c))

INF = float("inf")

d = [INF for _ in range(N)] 
d[0] = 0
"""
頂点Nに向かうまでに関係ない閉路に注意する

無限にコインを拾える場合、
・ある閉路を一周したときの得点と支払いの収支がプラス
・その閉路からゴールまで行ける
である。これがない場合、全てのノードを経由してゴールまで行く（N-1回移動）までにコインの枚数が最大になる
なので、一回ベルマンフォード法をやった後もう一回行って一回目と２回目でゴールまでのコイン枚数に変化があればゴ、
ールに行くまでの道に無限にコインをとれる閉路があるといえる

"""

def solve(start, f):
    for i in range(N):
        for a,b,c, in es:
            if d[a] != INF and d[a] + (-c) + P < d[b]:
                # ２週目と区別する。２週目で更新される部分は-INFとか適当に置いておくと、ゴールまでの影響がわかる
                if f == 0:
                    d[b] = d[a] + (-c) + P
                else:
                    d[b] = -INF


    return d[-1]


first=solve(0,0)
second=solve(0, 1)
if first != second:
    print(-1)
else:
    print(max(-first, 0))
s=input()
l=input()
len_s=len(s)
len_l=len(l)
a=len_s-len_l
ans=1001
for i in range(len_s-a):
    cnt=0
    for j in range(len_s):
        if l[j]==s[i+j]:
            cnt+=1
    ans=min(ans,len_l-cnt)

print(ans)

### FIXED CODE ###

s=input()
l=input()
len_s=len(s)
len_l=len(l)
a=len_s-len_l
ans=1001
for i in range(len_s-len_l+1):
    cnt=0
    for j in range(len_l):
        if l[j]!=s[i+j]:
            cnt+=1
    ans=min(ans,cnt)

print(ans)
import sys
S = sys.stdin.readline().rstrip()
L = ['Sunny', 'Cloudy', 'Rainy']
if S ==L[0]:
    print(L[1])
elif S ==L[1]:
    print(L[2])
elif S ==L[2]:
    printf(L[0])

### FIXED CODE ###

#import sys
S = input()
#L = ["Sunny", "Cloudy", "Rainy"]

if S == "Sunny":
    print("Cloudy")
elif S =="Cloudy":
    print("Rainy")
elif S == "Rainy":
    print("Sunny")
N, M = map(int, input().split()) 
A = [int(input()) for _ in range(M)]

s = sum(A)
ans = -1
if N >= s: ans = N - s
print(ans)

### FIXED CODE ###

N, M = map(int, input().split()) 
A = list(map(int, input().split()))
 
# N-sum(A)が残り日数である
s = sum(A)
ans = -1
if N >= s: ans = N - s
print(ans)
import math

A, B = map(int, input().split())


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


print(lcm(A, B))


### FIXED CODE ###

from fractions import gcd

A, B = map(int, input().split())


def lcm(x, y):
    return (x * y) // gcd(x, y)


print(lcm(A, B))
from collections import deque

H, W = map(int, input().split())
S = [input() for _ in range(H)]
for i in range(H):
    j = S[i].find(".")
    if j >= 0:
        break
def bfs(s, t):
    dist = [[None] * W for _ in range(H)]
    que = deque([(s, t)])
    dist[s][t] = 0
    while que:
        u, v = que.popleft()
        d = dist[u][v]
        G = []
        if u > 0 and S[u-1][v] == ".":
            G.append((u-1, v))
        if u < H - 1 and S[u+1][v] == ".":
            G.append((u+1, v))
        if v > 0 and S[u][v-1] == ".":
            G.append((u, v-1))
        if v < W - 1 and S[u][v+1] == ".":
            G.append((u, v+1))
        for w, x in G:
            if dist[w][x] is not None:
                continue
            dist[w][x] = d + 1
            que.append((w, x))
    return max(max((d, (i, j)) for j, d in enumerate(di) if d is not None) for i, di in enumerate(dist))
_, (u, v) = bfs(i, j)
d, _ = bfs(u, v)
print(d)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
S = [input() for _ in range(H)]
def bfs(s, t):
    dist = [[None] * W for _ in range(H)]
    que = deque([(s, t)])
    dist[s][t] = 0
    while que:
        u, v = que.popleft()
        d = dist[u][v]
        G = []
        if u > 0 and S[u-1][v] == ".":
            G.append((u-1, v))
        if u < H - 1 and S[u+1][v] == ".":
            G.append((u+1, v))
        if v > 0 and S[u][v-1] == ".":
            G.append((u, v-1))
        if v < W - 1 and S[u][v+1] == ".":
            G.append((u, v+1))
        for w, x in G:
            if dist[w][x] is None:
                dist[w][x] = d + 1
                que.append((w, x))
    return max(d if d is not None else 0 for di in dist for d in di)

print(max(bfs(i, j) for i in range(H) for j in range(W) if S[i][j] == "."))
tmp = input().split(" ")
if tmp[2]-tmp[1] <= 0:
  print("delicious")
elif tmp[2]-tmp[1]>tmp[0] :
  print("dangerous")
else :
  print("safe")

### FIXED CODE ###

tmp = input().split(" ")
x=int(tmp[0])
a=int(tmp[1])
b=int(tmp[2])

if b-a <= 0:
  print("delicious")
elif b-a>x :
  print("dangerous")
else :
  print("safe")
x=input()
otoshi=x.split(" ")
N=int(otoshi[0])
Y=int(otoshi[1])
ten_t=Y//10000
 
if ten_t>N:
    ansa=-1 
    ansb=-1 
    ansc=-1
elif ten_t==N:
    if Y==100000*N:
        ansa=N
        ansb=0
        ansc=0
    else:
        ansa=-1 
        ansb=-1 
        ansc=-1
elif 0<=ten_t<N:
    for i in range(0,ten_t+1):
        ra=Y-10000*(ten_t-i)
        fiv_t=ra//5000
        
        if fiv_t+ten_t-i>N:
            ansa=-1 
            ansb=-1 
            ansc=-1
            break
        elif 0<=fiv_t+ten_t-i<=N:
            if ra==5000*(N-ten_t+i):
                ansa=ten_t-i
                ansb=N-ten_t+i
                ansc=0
                break
            else:
                for j in range(0,fiv_t+1):
                    rb=ra-5000*(fiv_t-j)
                    if rb==1000*(N-ten_t+i-fiv_t+j):
                        ansa=ten_t-i
                        ansb=fiv_t-j
                        ansc=N-ten_t+i-fiv_t+j
                        break
    
else:
    ansa=-1 
    ansb=-1 
    ansc=-1
print(ansa,ansb,ansc)                   

### FIXED CODE ###

N,Y=input().split()
n=int(N)
y=int(Y)//1000
p=y-n
s=y//10
t=y//5
i=-1
j=-1
k=-1
fl=False
for X in range(0,s+1):
    for Y in range(0,t+1):
        q=p-(9*X+4*Y)
        if q==0 and X+Y<=n:
            Z=n-X-Y
            i=X
            j=Y
            k=Z
            break
        if fl:
            break
    if fl:
        break
print(i,j,k)
n = int(input())
a,b,c=0,0,0
for i in range(n):
    t,x,y = map(int, input().split())
    sa = t-a
    if sa<abs(x-b)+abs(y-c):
        print("No")
        exit()
    else:
        tw = sa-abs(x-b)-abs(y-c)
        if tw%2!=0:
            print("No")
            exit()
    a,b,c=x,y,z
print("Yes")


### FIXED CODE ###

n = int(input())
a,b,c=0,0,0
for i in range(n):
    t,x,y = map(int, input().split())
    sa = t-a
    if sa<abs(x-b)+abs(y-c):
        print("No")
        exit()
    else:
        tw = sa-abs(x-b)-abs(y-c)
        if tw%2!=0:
            print("No")
            exit()
    a,b,c=t,x,y
print("Yes")
ls = [abs(A-(T-x*6/1000)) for x in list_H]
ls.index(min(ls)+1)

### FIXED CODE ###

N = int(input())
T,A = map(int, input().split())
list_H = list(map(int, input().split()))

ls = [abs(A-(T-x*6/1000)) for x in list_H]
print(ls.index(min(ls))+1)
import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to only numbers
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

N = ri()
A = np.array(rl())
answer = 0
c = np.bincount(A)

for i in range(1, len(c)):
    result = c[i-1] + c[i] + c[i+1]
    if result > answer:
        answer = result

print(answer)
# 32

### FIXED CODE ###

import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to only numbers
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

N = ri()
A = np.array(rl())
c = np.bincount(A)
answer = c[0]

for i in range(1, len(c)-1):
    result = c[i-1] + c[i] + c[i+1]
    if result > answer:
        answer = result

print(answer)
# 32
import itertools

n = int(input())
s_li = []
for i in range(n):
    s = input()
    s_i = {}
    for j in range(10):
        s_i[s[j]] = 0
    for j in range(10):
        s_i[s[j]] += 1    
    s_li.append(s_i)

ans = 0

for i in range(n):
    for j in range(n):
        if i >= j :
            continue
        if s_li[i] == s_li[j]:
            ans += 1
print(ans)

### FIXED CODE ###

a,b = map(int,input().split())

print(max(a + b, a - b, a * b))
a, b, k = map(int, input().split())

def ooo(x):
    lix =[]
    for i in range(1, x+1):
        if x % i == 0:
            li.append(i)
    return lix

lia = ooo(a)
lib = ooo(b)
li = lia + lib

li2 =[]
for n in range(len(li)):
    if not li[n] in li2: 
        if li.count(li[n]) == 2:
            li2.append(li[n])

li2.sort(reverse=True)
print(li2[k-1])

### FIXED CODE ###

a, b, k = map(int, input().split())

def ooo(x):
    lix =[]
    for i in range(1, x+1):
        if x % i == 0:
            lix.append(i)
    return lix

lia = ooo(a)
lib = ooo(b)
li = lia + lib

li2 =[]
for n in range(len(li)):
    if not li[n] in li2: 
        if li.count(li[n]) == 2:
            li2.append(li[n])

li2.sort(reverse=True)
print(li2[k-1])
import numpy as np

#initialization
nmatch = [2,5,5,4,5,6,3,7,6]
f = input()
f = f.split()
N = int(f[0])
M = int(f[1])
dp = [-1]*(N+1) # contains the number of digits it can make
dp[0] = 0
ff = input()
ff = ff.split()
Atemp = [] #contains the number that can be used and the number of matches needed to make the match
for number in ff:
    temp = [int(number),nmatch[int(number)-1]]
    Atemp.append(temp)
Atemp = np.array(Atemp)
index0 = np.argsort(Atemp[:,0])
index1 = np.argsort(Atemp[:,1])
A = Atemp[index1] #sorted by the number of matches: ascending
B = Atemp[index0]
B = B[::-1] #sorted by the number: descending

for i in range(1,N+1):
    #dp(i)を求める
    for k in range(M):
        j = A[k,1]
        i_old = i - j #available matches
        if (i-j) < 0:
            break
        if (i-j) == 0 and dp[i] == -1:
            dp[i] = 1
        if dp[i_old] != -1 and dp[i_old]+1 > dp[i]:
            dp[i] = dp[i_old] + 1
ndigits = dp[N]
j = N
final_number = ''
for l in range(ndigits,0,-1):
    #桁を求めていく
    index = 0
    while True:
        temp_j = j - B[index,1]
        if dp[temp_j] + 1 == dp[j]:
            final_number  += str(B[index,0])
            j = temp_j
            break
        else:
            index += 1
        if index > M:
            print('smth is wrong')
            break
print(int(final_number))


### FIXED CODE ###

import numpy as np

#initialization
nmatch = np.array([0,2,5,5,4,5,6,3,7,6])
N,M = map(int,input().split())
dp = [-1]*(N+1) # contains the number of digits it can make
dp[0] = 0
ff = np.array(list(map(int,input().split()))).reshape(-1,1)
fg = nmatch[ff].reshape(-1,1)
Atemp = np.concatenate([ff,fg],axis=1)
index0 = np.argsort(Atemp[:,0])
index1 = np.argsort(Atemp[:,1])
A = Atemp[index1] #sorted by the number of matches: ascending
B = Atemp[index0]
B = B[::-1] #sorted by the number: descending
for i in range(1,N+1):
    for k in range(M):
        j = A[k,1]
        i_old = i - j #available matches
        if (i-j) < 0:
            break
        if (i-j) == 0 and dp[i] == -1:
            dp[i] = 1
        if dp[i_old] != -1 and dp[i_old]+1 > dp[i]:
            dp[i] = dp[i_old] + 1
#print(dp)
ndigits = dp[N]
j = N
final_number = ''
for l in range(ndigits,0,-1):
    index = 0
    while True:
        temp_j = j - B[index,1]
        if temp_j < 0:
            index += 1
            continue
        if dp[temp_j] + 1 == dp[j]:
            final_number += str(B[index,0])
            j = temp_j
            break
        else:
            index += 1
        if index > M:
            break
print(int(final_number))
global n
n = int(input())
a_array = [int(x) for x in input().split()]
q = int(input())
m_array = [int(x) for x in input().split()]

def solve(a, m):
    if m == 0:
        return True
    if a >= n:
        return False
    res = solve(a + 1, m) or solve(a + 1, m - a_array[a])
    return res

for m in m_array:
    if solve(0, m):
        print("yes")
    else:
        print("no")



### FIXED CODE ###

from itertools import combinations

n = int(input())
a_array = [int(x) for x in input().split()]
q = int(input())
m_array = [int(x) for x in input().split()]

array = []
for j in range(n + 1):
    x = combinations(a_array, j)
    for y in x:
        array.append(sum(y))

for m in m_array:
    print("yes" if m in array else "no")
N = int(input())
alist = list(map(int, input().split()))
min_x, max_x = min(alist), max(alist)
max_num = 0
for x in range(min_x, max_x + 1):
    num = len([xx for xx in alist if x -1 <= xx <== x + 1])
    max_num = max(max_num, num)
print(max_num)

### FIXED CODE ###

from collections import defaultdict as dd
N = input()
a_raw = list(map(int, input().split()))
num_count = dd(int)
for item in a_raw:
    num_count[item] += 1
    num_count[item-1] += 1
    num_count[item+1] += 1
print(max(num_count.values()))
N = int(input())
for i in range(N):
    l,r = map(int, input().split())
    ans += r - l + 1
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(N):
    l,r = map(int, input().split())
    ans += r - l + 1
print(ans)
n = len(L)
c = 0
result = []
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            
            if abs(L[i]-L[j])<L[k]<L[i]+L[j] and  L[i]!=L[j] and L[j]!=L[k]:
                #print(L[i], L[j], L[k])
                c += 1
print(c)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))

n = len(L)
c = 0
result = []
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if L[i]!=L[j] and L[j]!=L[k] and L[i]!=L[k]:
                if L[i]+L[j]>L[k] and L[j]+L[k]>L[i] and L[i]+L[k]>L[j]:
                    #print(L[i], L[j], L[k])
                    c += 1
print(c)
def main():
    c11, c12, c13 = map(int, input().split())
    c21, c22, c23 = map(int, input().split())
    c31, c32, c33 = map(int, input().split())

    r1max = max([c11, c12, c13])
    r2max = max([c21, c22, c23])
    r3max = max([c31, c32, c33])
    c1max = max([c11, c21, c31])
    c2max = max([c12, c22, c32])
    c3max = max([c13, c23, c33])
    for a1, a2, a3 in [[a1, a2, a3] for a1 in range(0, r1max + 1) for a2 in range(0, r2max + 1) for a3 in range(0, r3max + 1)]:
        m = max([a1, a2, a3])
        for b1 in range(0, c1max - m + 1):
            if a1 + b1 == c11 and a2 + b1 == c21 and a3 + b1 == c31:
                for b2 in range(0, c2max - m + 1):
                    if a1 + b2 == c12 and a2 + b2 == c22 and a3 + b2 == c32:
                        for b3 in range(0, c3max - m + 1):
                            if a1 + b3 == c13 and a2 + b3 == c23 and a3 + b3 == c33:
                                print('Yes')
                                return

    print('No')
    return


if __name__ == '__main__':
    main()
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    c11, c12, c13 = map(int, input().split())
    c21, c22, c23 = map(int, input().split())
    c31, c32, c33 = map(int, input().split())

    r1max = max([c11, c12, c13])
    r2max = max([c21, c22, c23])
    r3max = max([c31, c32, c33])
    c1max = max([c11, c21, c31])
    c2max = max([c12, c22, c32])
    c3max = max([c13, c23, c33])
    for a1 in range(0, r1max + 1):
        for a2 in range(0, r2max + 1):
            for a3 in range(0, r3max + 1):
                m = max([a1, a2, a3])
                for b1 in range(0, c1max - m + 1):
                    C11 = a1 + b1
                    C21 = a2 + b1
                    C31 = a3 + b1
                    if C11 == c11 and C21 == c21 and C31 == c31:
                        for b2 in range(0, c2max - m + 1):
                            C12 = a1 + b2
                            C22 = a2 + b2
                            C32 = a3 + b2
                            if C12 == c12 and C22 == c22 and C32 == c32:
                                for b3 in range(0, c3max - m + 1):
                                    C13 = a1 + b3
                                    C23 = a2 + b3
                                    C33 = a3 + b3
                                    if C13 == c13 and C23 == c23 and C33 == c33:
                                        print('Yes')
                                        return

    print('No')
    return


if __name__ == '__main__':
    main()
s=input()
dic={}
key_letters=[]
flag=0
for letter in s:
    if letter not in dic.keys():
        dic[letter]=1
    else:
        dic[letter]+=1
for key,value in dic.items():
    if value>=len(s)//2:
        key_letters.append(key)
        flag=1

if flag==0:
    print('-1 -1')
else:
    for i in range(len(s)):
        if s[i] in key_letters and s[i]==s[i+1]:
            print(str(i+1)+' '+str(len(s)))
            break
            

            


        


### FIXED CODE ###

s=input()
flag=0
if len(s)==2:
    if s[0]==s[1]:
        print('1 2')
    else:
        print('-1 -1')
else:
    for i in range(len(s)-2):
        if s[i]==s[i+2] and s[i]!=s[i+1]:
            print(str(i+1)+' '+str(i+3))
            flag=1
            break
        elif s[i]==s[i+1] and s[i]!=s[i+2]:
            print(str(i+1)+' '+str(i+3))
            flag=1
            break
        elif s[i+1]==s[i+2] and s[i+1]!=s[i]:
            print(str(i+1)+' '+str(i+3))
            flag=1
            break
    if flag==0:
        print('-1 -1')