Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import deque


class LinkedGraph:
    def __init__(self, n):
        self.n = n
        self.ll = [[] for _ in range(self.n)]

    def link(self, u, v, direction=False):
        self.ll[u].append(v)
        if not direction:
            self.ll[v].append(u)

    def check(self, start, goal):
        states = [1] * self.n
        queue = deque([start])

        while queue:
            u = queue.popleft()
            states[u] = 0

            for v in self.ll[u]:
                if v == goal:
                    print('yes')
                    return
                if states[v]:
                    queue.append(v)
        else:
            print('no')
            return


if __name__ == '__main__':
    n, m = map(int, input().split())
    g = LinkedGraph(n)

    for _ in range(m):
        u, v = map(int, input().split())
        g.link(u, v)

    q = int(input())
    for _ in range(q):
        u, v = map(int, input().split())
        g.check(u, v)



### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)


class LinkedList:
    def __init__(self, n):
        self.n = n
        self.ll = [[] for _ in range(self.n)]

    def link(self, u, v, direction=False):
        self.ll[u].append(v)
        if not direction:
            self.ll[v].append(u)

    def dfs(self):
        self.cc = [None] * self.n

        color = 1
        for u in range(self.n):
            if not self.cc[u]:
                self.dfs_visit(u, color)
                color += 1

    def dfs_visit(self, u, color):
        self.cc[u] = color
        for v in self.ll[u]:
            if not self.cc[v]:
                self.dfs_visit(v, color)

    def check(self, u, v):
        if self.cc[u] == self.cc[v]:
            print('yes')
        else:
            print('no')


if __name__ == '__main__':
    n, m = map(int, input().split())
    ll = LinkedList(n)

    for _ in range(m):
        u, v = map(int, input().split())
        ll.link(u, v)
    ll.dfs()

    q = int(input())
    for _ in range(q):
        u, v = map(int, input().split())
        ll.check(u, v)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
import os

memo = {}

def is_prime(n):
    if n in memo:
        return memo[n]

    if n==2 or n==3:
        return True
    if n%2==0 or n<2:
        return False
    for i in range(3,int(n**0.5)+1,2):
        if n%i==0:
            memo[n] = False
            return False
    memo[n] = True
    return True

for s in sys.stdin:
    n = int(s)
    if n == 0:
        break

    if n % 2 == 1:
        if is_prime(n - 2):
            print(1)
        else:
            print(0)
    else:
        counter = 0
        for i in range(1, n, 2):
            prime0 = i
            prime1 = n - i
            if prime0 <= prime1 and is_prime(prime0) and is_prime(prime1):
                counter += 1
        print(counter)

### FIXED CODE ###

import sys

N = 50001
lst = [True] * N
lst[0] = False
lst[1] = False
for i in range(2, int(N ** 0.5) + 1):
    if lst[i]:
        for j in range(i * i, N, i):
            lst[j] = False

primes = [i for i in range(1, N) if lst[i]]

for s in sys.stdin:
    n = int(s)
    if n == 0:
        break
    elif n % 2 == 1:
        if lst[n - 2]:
            print(1)
        else:
            print(0)
    elif n == 4:
        print(1)
    else:
        counter = 0
        for prime0 in primes:
            prime1 = n - prime0
            if prime0 <= prime1 and lst[prime1]:
                #print(prime0, prime1)
                counter += 1
        print(counter)
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
S = input()

strList = defaultdict(list)

for leng in range(N):
    for left in range(N - leng + 1):
        sub = S[left: left + leng]
        strList[sub].append(left)

ans = 0
for sub, leftList in strList.items():
    leng = len(sub)
    leftList.sort()
    if leftList[0] + leng <= leftList[-1]:
        ans = max(ans, leng)

print(ans)


### FIXED CODE ###

from collections import deque

N = int(input())
S = input()

def isOk(leng):
    hashList = set()
    que = deque([])
    for left in range(N - leng + 1):
        hs = hash(S[left: left + leng])
        if hs in hashList:
            return True
        que.append(hs)
        if len(que) >= leng:
            hashList.add(que.popleft())
    return False

ok = 0
ng = N

while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

N=int(input())
S=input()
c=0
for i in range(N):
    for j in range(i):
        for k in range(j):
            if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i] and j-i!=k-j:
                c+=1
print(c)

### FIXED CODE ###

import itertools
N=int(input())
S=input()
ans=S.count("R")*S.count("G")*S.count("B")
c=list(itertools.permutations(["R","B","G"],3))
for j in range(1,N):
    for i in range(N-j*2):
        if (S[i],S[i+j],S[i+j*2]) in c:
            ans-=1
print(ans)
### BUGGY CODE ###

import numpy as np
NM = list(map(int,input().split()))
N = NM[0]
M = NM[1]
A = list(map(int,input().split()))
listBC =[]
while True:
    try:
        listBC.append(list(map(int,input().split())))
    except:
        break;
B = []
C = []
for i in range(0,len(listBC)):
    B.append(listBC[i][0])
    C.append(listBC[i][1])
B = np.array(B)
C = np.array(C)
BC = np.vstack([B,C])
# BCnum = np.argsort(BC[0,:])[::-1]
# BCs = BC[:,BCnum]
Cjun = []
for i in range(len(B)):
    for j in range(BC[0,i]):
        Cjun.append(BC[1,i])
Cjun.sort(reverse=True)
A.sort()
keyi = min(len(A),len(Cjun))
for i in range(min(len(A),len(Cjun))):
    if A[i]>=Cjun[i]:
        keyi = i
        break
output = sum(Cjun[0:keyi])+sum(A[keyi:])
print(output)

### FIXED CODE ###

import numpy as np
NM = list(map(int,input().split()))
N = NM[0]
M = NM[1]
A = list(map(int,input().split()))
listBC =[]
while True:
    try:
        listBC.append(list(map(int,input().split())))
    except:
        break;
BC = np.array(listBC)
BCnum = np.argsort(BC[:,1])[::-1]
BC = BC[BCnum,:]

A.sort()
j=0
for i in range(len(A)):
    times = BC[j,0]
    if BC[j,0]==0:
        j+=1
        if j == BC.shape[0]:
            break
        times = BC[j,0]
    if A[i]<BC[j,1]:
        A[i]=BC[j,1]
        BC[j,0] += -1
output = sum(A)
print(output)
### BUGGY CODE ###

import sys 
input = sys.stdin.readline
 
 
n = int(input())
 
a= list(map(int,input().split())) 
 
from operator import mul
from functools import reduce
 
ans = 1
for i in a:
    ans *= i 
 
if ans > 10**18:
    print('-1')
else:
    print(ans) 


### FIXED CODE ###

# import sys 
# input = sys.stdin.readline
 
 
n = int(input())
 
a= list(map(int,input().split())) 
 
def main(a):
    if 0 in a:
        print(0)
        return
     
    ans = 1
    for i in a:
        ans *= i 
        
        if ans > 1000000000000000000:
            print(-1)
            return
    
    print(ans)
    
main(a)
### BUGGY CODE ###

import sys

(H,W)=map(int,(input().split()))

INF=1000
mymap=list()

for i in range(H):
    mymap.append(input().rstrip())

#print(mymap)

costmap=[[INF for i in range(W)] for j in range(H)]
#print(costmap)

def make_costmap(i,j,prev_state,c):
    #print(i,j,prev_state,c)
    state=mymap[i][j]
    if (prev_state == "." and state=="#"):
        c+=1
    if costmap[i][j]>c:
        costmap[i][j]=c
    if (i<H-1):
        make_costmap(i+1,j,state,c)
    if (j<W-1):        
        make_costmap(i,j+1,state,c)
    return

make_costmap(0,0,".",0)

#for i in range(H):
#    print(mymap[i])
#for i in range(H):
#    print(costmap[i])

print(costmap[H-1][W-1])



### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)

(H,W)=map(int,(input().split()))

INF=1000
mymap=list()

for i in range(H):
    mymap.append(input().rstrip())

#print(mymap)

costmap=[[INF for i in range(W)] for j in range(H)]
#print(costmap)

def make_costmap(i,j,prev_state,c):
    #print(i,j,prev_state,c)
    state=mymap[i][j]
    if (prev_state == "." and state=="#"):
        c+=1
    if costmap[i][j] == INF or costmap[i][j]>c:
        costmap[i][j]=c
    else:
        return
        
    if (i<H-1):
        make_costmap(i+1,j,state,c)
    if (j<W-1):        
        make_costmap(i,j+1,state,c)
    return

make_costmap(0,0,".",0)

#for i in range(H):
#    print(mymap[i])
#for i in range(H):
#    print(costmap[i])

print(costmap[H-1][W-1])
### BUGGY CODE ###

import sys


def main():
    input = sys.stdin.readline

    h, w, k = map(int, input().split())
    s = [input() for _ in range(h)]

    cs = [[0] * (w + 1) for _ in range(h + 1)]
    for i in range(h):
        for j in range(w):
            cs[i +
               1][j +
                  1] = cs[i][j + 1] + cs[i + 1][j] - cs[i][j] + int(s[i][j])

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1 == 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        cand0 = cand
        j0 = 0
        cut = []
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    cut.append(j - 1)
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.readline

    h, w, k = map(int, input().split())
    s = [input() for _ in range(h)]

    cs = [[0] * (w + 1) for _ in range(h + 1)]
    for i in range(h):
        for j in range(w):
            cs[i +
               1][j +
                  1] = cs[i][j + 1] + cs[i + 1][j] - cs[i][j] + int(s[i][j])

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        if cand >= ans:
            continue
        j0 = 0
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1
            if cand >= ans:
                break

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

_, K = map(int, input().split())
S = input() + '2'

current_length = 1
sections = []  # (start_i, end_i)
current_section = (S[0], 1)

max_length = 0

k = 0


def display_section(sections, current_section):
    a = sections[:]
    b = current_section[:]
    a += b
    s = ''
    for section in a:
        s += section[0] * section[1]
    return s


for i in range(1, len(S)):
    t = display_section(sections, [current_section, (S[i], 1)])
    # print(t)
    if S[i - 1] == S[i]:
        current_section = (S[i], current_section[1] + 1)
        current_length += 1
    else:
        if current_section[0] == '0':
            k += 1
            while k > K:
                if sections[0][0] == '0':
                    k -= 1
                current_length -= sections[0][1]
                sections.pop(0)
        sections.append(current_section)

        if current_length > max_length:
            max_length = current_length

        current_section = (S[i], 1)
        current_length += 1

print(max_length)


### FIXED CODE ###

_, K = map(int, input().split())
S = input() + '2'

current_length = 1
sections = []  # (start_i, end_i)
current_section = (S[0], 1)

max_length = 0

k = 0


# def display_section(sections, current_section):
#     a = sections[:]
#     b = current_section[:]
#     a += b
#     s = ''
#     for section in a:
#         s += section[0] * section[1]
#     return s


for i in range(1, len(S)):
    # t = display_section(sections, [current_section, (S[i], 1)])
    # print(t)
    if S[i - 1] == S[i]:
        current_section = (S[i], current_section[1] + 1)
        current_length += 1
    else:
        if current_section[0] == '0':
            if len(sections) > 0 and sections[-1][0] == '1':
                pop = sections.pop(-1)
                sections.append((0, pop[1] + current_section[1]))
            else:
                sections.append(current_section)
            k += 1
            if k > K:
                current_length -= sections[0][1]
                sections.pop(0)
        else:
            sections.append(current_section)

        if current_length > max_length:
            max_length = current_length

        current_section = (S[i], 1)
        current_length += 1

print(max_length)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

k,s = map(int,input().split())

cnt = 0

for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i + j + l == s:
                cnt += 1

print(cnt)


### FIXED CODE ###

# -*- coding: utf-8 -*-

k,s = map(int,input().split())

ans = 0

for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if 0 <= z <= k:
            ans += 1

print(ans)
### BUGGY CODE ###

from itertools import permutations
import sys
input = sys.stdin.readline

if __name__ == "__main__":
    N, M, RR = map(int, input().split())
    R = list(map(int, input().split()))
    INF = float("inf")
    T = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = tuple(map(int, input().split()))
        T[a-1][b-1] = c
        T[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if T[i][j] > T[i][k]+T[k][j]:
                    T[i][j] = T[i][k]+T[k][j]
    print(min(sum(T[rs[i]-1][rs[i+1]-1] for i in range(RR-1)) for rs in permutations(R)))

### FIXED CODE ###

from itertools import permutations
import sys
input = sys.stdin.readline

def main():
    N, M, RR = map(int, input().split())
    R = list(map(int, input().split()))
    INF = float("inf")
    T = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = tuple(map(int, input().split()))
        T[a-1][b-1] = c
        T[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if T[i][j] > T[i][k]+T[k][j]:
                    T[i][j] = T[i][k]+T[k][j]
    ans = INF
    for rs in permutations(R):
        cost = 0
        for i in range(RR-1):
            cost += T[rs[i]-1][rs[i+1]-1]
        ans = min(ans, cost)
    print(ans)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
c=[n for i in range(n)]
for j in range(k):
    d=[0 for i in range(n+1)]
    for i in range(n):
        d[max(i-a[i],0)]+=1
        d[min(i+a[i]+1,n)]-=1
    e=[d[i] for i in range(n)]
    for i in range(n-1):#ちょっと特殊な累積和 普通のものの[1:-1]
        e[i+1]=e[i]+d[i+1]
    #print(d,e,sep='\n')
    #print(e)
    a=e
    if e==c:
        break
print(*a)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
c=[n for i in range(n)]
for j in range(k):
    d=[0 for i in range(n+1)]
    for i in range(n):
        d[max(i-a[i],0)]+=1
        d[min(i+a[i]+1,n)]-=1
    e=[d[0]]
    for i in range(n-1):#ちょっと特殊な累積和 普通のものの[1:-1]
        e.append(e[i]+d[i+1])
    #print(d,e,sep='\n')
    #print(e)
    a=e
    if e==c:
        break
print(*a)
### BUGGY CODE ###

#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

H, W = LI()
A = []
for i in range(H):
    a = list(str(input()))
    A.append(a)
# 複数のスタート地点が存在してもqueに突っ込むことで同様の効果が得られる．
visited = [[-1 for i in range(W)] for j in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            d.append((i,j))
            visited[i][j] = 0

moves = [[0,1],[1,0],[-1,0],[0,-1]]
cnt = 0
while len(d) > 0:
    X, Y = d.popleft()
    cnt = visited[X][Y]
    for x, y in moves:
        n_X = X + x
        n_Y = Y + y
        if 0 <= n_X < H and 0 <= n_Y< W:
            if visited[n_X][n_Y] == -1:
                visited[n_X][n_Y] = cnt + 1
                d.append((n_X, n_Y))
print(cnt)


### FIXED CODE ###

#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

H, W = LI()
A = [[] for i in range(H)]
for i in range(H):
    a = list(str(input()))
    A[i] = a
# 複数のスタート地点が存在してもqueに突っ込むことで同様の効果が得られる．
visited = [[-1 for i in range(W)] for j in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            d.append((i,j))
            visited[i][j] = 0

moves = [[0,1],[1,0],[-1,0],[0,-1]]
cnt = 0
while len(d) > 0:
    X, Y = d.popleft()
    cnt = visited[X][Y]
    for x, y in moves:
        n_X = X + x
        n_Y = Y + y
        if 0 <= n_X < H and 0 <= n_Y< W:
            if visited[n_X][n_Y] == -1:
                visited[n_X][n_Y] = cnt + 1
                d.append((n_X, n_Y))
print(cnt)
### BUGGY CODE ###

A, B, N = list(map(int, input().split()))
def function(a, b, x):
  return (a*x)//b - a*(x//b)
print(max([function(A, B, i) for i in range(max([1, N-N%B-1]), N+1)]))

### FIXED CODE ###

A, B, N = list(map(int, input().split()))
def function(a, b, x):
  return (a*x)//b - a*(x//b)
print(max([function(A, B, N), function(A, B, max([1, N-N%B-1]))]))
### BUGGY CODE ###

n,x,y=map(int,input().split())
li=[0]*n
for i in range(1,n+1):
  for j in range(1,n+1):
    d=min(abs(i-j),abs(i-x)+abs(j-y)+1,1+abs(i-y)+abs(j-x))
    li[d]+=1
for k in range(1,n):
  print(li[k]//2)

### FIXED CODE ###

n,x,y=map(int,input().split())
li=[0]*n
for i in range(1,n+1):
  for j in range(1,n+1):
    d=min(abs(i-j),abs(i-x)+abs(j-y)+1,1+abs(i-y)+abs(j-x))
    li[d]+=1
for k in range(1,n):
  print(li[k]//2)
### BUGGY CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
from heapq import heapify,heappush,heappop
s=s0()
n=len(s)

ans=[0]*n
for i in range(n):
    c=[0]*n
    c[i]=1
    j=i
    g=0
    while True:
        g+=1
        if s[j]=="R":
            j+=1
        else:
            j-=1
        if c[j]==1:
            break
        else:
            c[j]=1
    if g%2==1 and s[j]=="R":
        ans[j+1]+=1
    elif g%2==1 and s[j]=="L":
        ans[j-1]+=1
    else:
        ans[j]+=1
print(*ans)

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
s=s0()
n=len(s)

L=[]
R=[]
for i in range(n):
    if s[i]=="L":
        L.append(i)
    else:
        R.append(i)

ans=[0]*n
for i in range(n):
    if s[i]=="R":
        j=L[bisect_right(L,i)]
        if (j-i)%2==1:
            ans[j-1]+=1
        else:
            ans[j]+=1
    else:
        j=R[bisect_right(R,i)-1]
        if (i-j)%2==1:
            ans[j+1]+=1
        else:
            ans[j]+=1
print(*ans)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
left = 0
ans = 1
l = 1
pre = A[0]
right = 1
while len(A) > 1:
    if right >= len(A):
        A.pop(left)
        l = 1
        ans += 1
        right = left+1
        pre = A[left]
    elif pre < A[right]:
        l += 1
        pre = A.pop(right)
    else:
        right += 1
print(ans)


### FIXED CODE ###

import bisect
def LIS():
    L[0] = A[0]
    length = 1
    for i in range(1, N):
        if L[length-1] < A[i]:
            L[length] = A[i]
            length += 1
        else:
            j = bisect.bisect_left(L, A[i])
            L[min(length-1, j)] = A[i]
    return length

def LISDesc():
    L[0] = A[-1]
    length = 1
    for i in range(N-2, -1, -1):
        if L[length-1] <= A[i]:
            L[length] = A[i]
            length += 1
        else:
            j = bisect.bisect_right(L, A[i])
            L[min(length-1, j)] = A[i]
    return length

INFTY = 10**13
N = int(input())
A = [int(input()) for i in range(N)]
L = [INFTY for i in range(N)]
ans = LISDesc()
print(ans)
### BUGGY CODE ###

def MAIN():
    T = input()
    P = input()
    t = -1
    while True:
        t = T.find(P, t + 1)
        if t == -1:
            break
        print(t)
MAIN()



### FIXED CODE ###

def kmpTable(w):
    lw = len(w)
    nx = [-1] * (lw + 1)
    j = -1
    for i in range(lw):
        while j >= 0 and w[i] != w[j]:
            j = nx[j]
        j += 1
        nx[i + 1] = j
    return tuple(nx)
def kmpSearch(s, w):
    ls = len(s)
    start = 0
    w_idx = 0
    ret = []
    nx = kmpTable(w)
    while start + w_idx < ls:
        if s[start + w_idx] == w[w_idx]:
            w_idx += 1
            if w_idx == len(w):
                ret.append(start)
                start = start + w_idx - nx[w_idx]
                w_idx = nx[w_idx]
        else:
            if w_idx == 0:
                start += 1
            else:
                start = start + w_idx - nx[w_idx]
                w_idx = nx[w_idx]
    return ret
T = input()
P = input()
ans = kmpSearch(T, P)

if ans:
    print(*ans, sep="\n")
#    print("\n".join(map(str, ans)))