Harryxun/stf_run huggingface dataset:
import numpy as np
import math 
N, K=map(int,input().split())
A2 = np.zeros(N)
A = list(map(int,input().split()))
#A = list(map(lambda x: x -1 , A))
current_town = 0



i=0
while i<K:
    current_town = A[current_town]
    if  A2[current_town] != 0:
        cycle = i - A2[current_town] 
        i = K - (K-i) % cycle
    else:
        A2[current_town] = i

print(current_town+1)


### FIXED CODE ###

import numpy as np
n, k=map(int,input().split())

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

 
s = list()
ord = np.full(n+1, -1)
c=1
l=0

v=1
while ord[v]==-1:
    ord[v]=len(s)
    s.append(v)
    v=a[v-1]
c=len(s)-ord[v]
l=ord[v]

if k<l:
    print(s[k])  
else:
    k-=l
    k%=c
    print(s[l+k])
n=int(input())
a=int(input())
b=int(input())
print("Hello World" if n==1 else a+b)

### FIXED CODE ###

n=int(input())
if n==1:print("Hello World")
else:print(int(input())+int(input()))
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
# import math
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(int(pow(10, 2)))
sys.stdin = open("input.txt", "r")
sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]





# @lru_cache(None)

# def seive():
#     prime=[1 for i in range(10**6+1)]
#     prime[0]=0
#     prime[1]=0
#     for i in range(10**6+1):
#         if(prime[i]):
#             for j in range(2*i,10**6+1,i):
#                 prime[j]=0


n=int(input())
a=list(map(int,input().split()))
ans=1
temp=0
for i in range(1,n):
  if a[i-1]<a[i] and temp==0:
    temp=1
  elif a[i-1]>a[i] and temp==0:
    temp=2
  elif a[i-1]>a[i] and temp==1:
    temp=0
    ans=ans+1
  elif a[i-1]<a[i] and temp==2:
    temp=0
    ans=ans+1
print(ans)

### FIXED CODE ###

import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
# import math
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(int(pow(10, 2)))
#sys.stdin = open("input.txt", "r")
#sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]





# @lru_cache(None)

# def seive():
#     prime=[1 for i in range(10**6+1)]
#     prime[0]=0
#     prime[1]=0
#     for i in range(10**6+1):
#         if(prime[i]):
#             for j in range(2*i,10**6+1,i):
#                 prime[j]=0


n=int(input())
a=list(map(int,input().split()))
ans=1
temp=0
for i in range(1,n):
  if a[i-1]<a[i] and temp==0:
    temp=1
  elif a[i-1]>a[i] and temp==0:
    temp=2
  elif a[i-1]>a[i] and temp==1:
    temp=0
    ans=ans+1
  elif a[i-1]<a[i] and temp==2:
    temp=0
    ans=ans+1
print(ans)
def main():
    a, b = map(int, input().split())
    x = 13
    while x <= int(a/0.08):
        x+=1
        if int(x*0.08) == a:
            if int(x*0.1) == b:
                return x
    return -1



if __name__ == "__main__":
    print(main()

### FIXED CODE ###

import math
def main():
    a, b = map(int, input().split())
    ra = [math.ceil(i/0.08) for i in range(1, 102)]
    rb = [math.ceil(i/0.1) for i in range(1, 102)]
    x = ra[a-1] 
    while x < ra[a] :
        if int(x*0.1) == b:
            return x
        x+=1
    return -1



if __name__ == "__main__":
    print(main())
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

al=sorted(a)
bl=sorted(b)
cl=sorted(c)
print(al)
print(bl)
print(cl)
j=0
k=0
ans=0
saved_j=0
saved_k=0
for i in range(n):
    j=saved_j
    while al[i]>=bl[j]:
        j+=1
        saved_j=j
    #print("j",j)
    while j!=n:
        k=saved_k
        while bl[j]>=cl[k]:
            if k==n-1:
                break
            k+=1
        if j==saved_j:
            saved_k=k
        #print("k",k)
        ans+=n-k
        j+=1
        #print("暫定",ans)
print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
al=sorted(a)
bl=sorted(b)
cl=sorted(c)
 
abl=[0]*n
bcl=[0]*n
i=n-1
for j in range(n-1,-1,-1):
    if i==-1:
        abl[j]=0
        continue
    while al[i]>=bl[j]:
        i-=1
        if i==-1:
            break
    if i==-1:
        abl[j]=0
    else:
        abl[j]=i+1
j=0
bcl=[0]*n
k=0
for j in range(n):
    if k==n:
        bcl[j]=0
        continue
    while cl[k]<=bl[j]:
        k+=1
        if k==n:
            break
    if k==n:
        bcl[j]=0
    else:
        bcl[j]=(n-k)
ans=0
for s in range(n):
    ans+=abl[s]*bcl[s]
print(ans)
n = int(input())
d = list(map(int,input().split()))
p = 0
q = 0
m = 0
d.sort()
if (len(d))%2 == 0:
  m = ((d[(len(d)//2)-1])+(d[len(d)//2]))/2
else:
  m = d[(len(d)//2)]
for i in range(len(d)):
  if d[i]>=m:
    if d[i] == d[i+1]:
      break
    else:
      p = d[i]
      q = d[i-1]
      break
print(p-q)

### FIXED CODE ###

n = int(input())
d = sorted(list(map(int,input().split())))
print(d[n//2]-d[n//2-1])
#!/usr/bin/env python

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
INF = float("inf")
MOD = 10**9+7

def popcount(n):
    ret = 0
    for i in range(18):
        if n>>i & 1:
            ret += 1
    return ret

def main():
    N = int(input())
    X = input().decode().rstrip()

    # X に含まれる "1" の数
    x_cnt = X.count("1")

    # i 桁目が 0 : x_cnt += 1
    # i 桁目が 1 : x_cnt -= 1
    # より, X mod x_cnt +1, X mod x_cnt-1 を事前計算しておく
    n_plus,n_minus = 0,0
    for i in range(N):
        if X[i]=="1":
            n_plus += 2**(N-1-i)
            n_plus %= x_cnt + 1
            n_minus += 2**(N-1-i)
            n_minus %= x_cnt - 1
    
    for i in range(N):
        ans = 1
        if X[i]=="1":
            a = (n_minus - pow(2,(N-1-i), x_cnt-1)) % (x_cnt-1)
        else:
            a = (n_plus + pow(2,(N-1-i), x_cnt+1)) % (x_cnt+1)
        while a > 0:
            pop_cnt = popcount(a)
            a %= pop_cnt
            ans += 1
        print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
INF = float("inf")

def popcount(n):
    ret = 0
    for i in range(18):
        if n>>i & 1:
            ret += 1
    return ret

def main():
    N = int(input())
    X = input().decode().rstrip()

    # X に含まれる "1" の数
    x_cnt = X.count("1")

    # i 桁目が 0 : x_cnt += 1
    # i 桁目が 1 : x_cnt -= 1
    # より, X mod x_cnt +1, X mod x_cnt-1 を事前計算しておく
    x_mod_pl,x_mod_mi = 0,0
    d_pl,d_mi = 1,1
    mod_pl,mod_mi = x_cnt+1,max(1,x_cnt-1)
    for i in range(N-1,-1,-1):
        if X[i]=="1":
            x_mod_pl = (x_mod_pl + d_pl) % mod_pl
            x_mod_mi = (x_mod_mi + d_mi) % mod_mi
        d_pl = (d_pl*2) % mod_pl
        d_mi = (d_mi*2) % mod_mi
    
    for i in range(N):
        ans = 1
        if X[i] == "1":
            # 1 -> 0 に変換した結果, １が全く存在しない場合
            if x_cnt == 1:
                print(0)
                continue
            a = (x_mod_mi - pow(2,(N-1-i), mod_mi)) % mod_mi
        else:
            a = (x_mod_pl + pow(2,(N-1-i), mod_pl)) % mod_pl

        while a > 0:
            pop_cnt = popcount(a)
            a %= pop_cnt
            ans += 1

        print(ans)

if __name__ == "__main__":
    main()
class Node:
    def __init__(self, key, parent=None):
        self.key = key
        self.parent = parent
        self.children = []
        self.counter = 0

    def add_child(self, node):
        self.children.append(node)

    def add_counter(self, counter):
        self.counter += counter
        for child in self.children:
            child.add_counter(counter)


N, Q = map(int, input().split())
nodes = [Node(i) for i in range(1, N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    nodes[a-1].add_child(nodes[b-1])
for _ in range(Q):
    p, x = map(int, input().split())
    nodes[p-1].add_counter(x)
print(*[node.counter for node in nodes])

### FIXED CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
n, q = map(int, input().split())

tree_index = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  tree_index[a].append(b) # a<bとは限らないため、双方向にする
  tree_index[b].append(a)
ans = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
def dfs(cur, par):
    for chl in tree_index[cur]:
      if chl == par: #parentとchildが等しい時はスキップ
        continue
      ans[chl] += ans[cur] 
      dfs(chl, cur)
dfs(0, -1)
print(*ans)
import math
from fractions import gcd


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


s = int(math.sqrt(g))

f = {}
for i in range(2, s+1):
    while g % i == 0:
        f[i] = f.get(i, 0) + 1
        g = g/i
if g != 1:
    f[g] = f.get(g, 0) + 1

print(len(f)+1)

### FIXED CODE ###

n = int(input())
p = 0
for i in range(n+1):
    if i % 2 == 1:
        p += 1
print('{:.10}'.format(p/n))
import math
#x=int(input())
a,b=map(int,input().split())
c=math.gcd(a,b)
print((a*b)//c)

### FIXED CODE ###

def gcd(a,b):
    if a==0:
        return b
    else:
        return gcd(b%a,a)
#x=int(input())
a,b=map(int,input().split())
c=gcd(a,b)
print((a*b)//c)
import sys
input = sys.stdin.readline

"""
・とりあえず部分点解法：各クエリに対してO(N)
・いくつかを残していくつかを自由に埋める
・残すもの：被覆区間がoverlapしないように残す
・つまり、区間で覆えている点が処理できて、区間で覆えていない点が他所から持ってこないといけない。
"""

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
XY = [tuple(int(x) for x in input().split()) for _ in range(M)]

def subscore_solution():
    from collections import Counter
    for x,y in XY:
        A[x-1] = y
        covered = [False] * (N+N+10)
        for key,cnt in Counter(A).items():
            for i in range(cnt):
                covered[max(0,key-i)] = True
        print(sum(not bl for bl in covered[1:N+1]))

if N <= 200 and M <= 200:
    subscore_solution()
    exit()

raise Exception



### FIXED CODE ###

import sys
input = sys.stdin.readline

"""
・とりあえず部分点解法：各クエリに対してO(N)
・いくつかを残していくつかを自由に埋める
・残すもの：被覆区間がoverlapしないように残す
・つまり、区間で覆えている点が処理できて、区間で覆えていない点が他所から持ってこないといけない。
"""

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
XY = [tuple(int(x) for x in input().split()) for _ in range(M)]

def subscore_solution():
    from collections import Counter
    for x,y in XY:
        A[x-1] = y
        covered = [False] * (N+N+10)
        for key,cnt in Counter(A).items():
            for i in range(cnt):
                covered[max(0,key-i)] = True
        print(sum(not bl for bl in covered[1:N+1]))

counter = [0] * (N+1)
covered = [0] * (N+N+10)
for a in A:
    counter[a] += 1
    covered[a-counter[a]+1] += 1
magic = sum(x==0 for x in covered[1:N+1])

for i,y in XY:
    x = A[i-1]
    A[i-1] = y
    rem = x - counter[x] + 1
    counter[x] -= 1
    counter[y] += 1
    add = y - counter[y] + 1
    covered[rem] -= 1
    if 1<=rem<=N and covered[rem] == 0:
        magic += 1
    if 1<=add<=N and covered[add] == 0:
        magic -= 1
    covered[add] += 1
    print(magic)
N = int(input())
As = sorted(list(map(int, input().split())))

sieve = [True] * 1000000

count = 1
prev = As[0]
for j in range(1000000 // prev + 1):
    sieve[prev * j - 1] = False


for i in range(N):
    if As[i] == prev:
        continue
    else:
        prev = As[i]
        if sieve[prev] is True:
            count += 1
        for j in range(1000000 // prev + 1):
            sieve[prev * j - 1] = False

print(count)

### FIXED CODE ###

N = int(input())
As = sorted(list(map(int, input().split())))

sieve = [True] * 1000001

prev = 0

for i in range(N):
    if As[i] == prev:
        sieve[As[i]] = False
        continue
    else:
        prev = As[i]
        try:
            for j in range(2, 1000000 // prev + 1):
                sieve[prev * j] = False
        except:
            continue

count = 0
As = list(set(As))
for i in range(len(As)):
    if sieve[As[i]] is True:
        count += 1
        
print(count)
while(True):
    i,j=input().split()
    
    if a != 0 and b != 0:
        if int(i) <= int(j):
            print('{} {}'.format(i,j))
        else:
            print('{} {}'.format(j,i))
    else:
        break


### FIXED CODE ###

while(True):
    i,j= map(int, input().split())
    if i != 0 or j != 0:
        if i <= j:
            print(i,j)
        else:
            print(j,i)
    else:
        break
A , B, T =map,int,(input().split())
print((T // A)*B)

### FIXED CODE ###

A , B, T =map(int,input().split())
print((T // A)*B)
b = int(input())
 
if b == "A":
  print("T")
elif b == "T":
  print("A")
elif b == "G":
  print("C")
else:
  print("G")

### FIXED CODE ###

b = input()
 
if b == "A":
  print("T")
elif b == "T":
  print("A")
elif b == "G":
  print("C")
else:
  print("G")
S = list(input())
L = list('keyence')
while L[0] == S[0]:
    L = L[1:]
    S = S[1:]
while len(L)*len(S) != 0 and L[-1] == S[-1]:
    L = L[:-1]
    S = S[:-1]
if L == []:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

S = list(input())
L = list('keyence')
while len(L)*len(S) > 0 and L[0] == S[0]:
    del L[0]
    del S[0]
while len(L)*len(S) > 0 and L[-1] == S[-1]:
    del L[-1]
    del S[-1]
if L == []:
    print('YES')
else:
    print('NO')
S=str(input())
ans=0
N=len(S)
for i in range(N):
    j=i+4
    while j<=N:
        if int(S[i:j])%2019==0:
            ans+=1
            i=j+1
            j=j+4
        else:
            j=j+1
print(ans)

### FIXED CODE ###

S,W=map(int,input().split())
if W>=S:
    print("unsafe")
else:
    print("safe")
print(int(input()+0.5)//2)

### FIXED CODE ###

a=int(input()) 
print(((a+1)//2)/a)
k=int(input())
s=str(input())
if len(s) <= k:
  print(s)
else:
  print(s[0:k] + "...")

### FIXED CODE ###

S = str(input())[-1]
tmp = ['0', '1', '6', '8']
if S == '3':
    print('bon')
elif S in tmp:
    print('pon')
else:
    print('hon')
S=input()
if s="aaa" or s="bbb":
  print("No")
else:print("Yes")

### FIXED CODE ###

S=input()
if S=="AAA" or S=="BBB":
  print("No")
else:print("Yes")
import math

A = int(input())
B = int(input())
if a >= 2 and B>= 1
    x = (B-1) / (A-1)

    print(math.ceil(x))

### FIXED CODE ###

import math
A, B = list(map(int, input().split()))
print(math.ceil((B-1)/(A-1)))
# -*- coding: utf-8 -*-


N = input()
N -= 1
A = list(map(int, input().split()))

xor_sum = 0
for i in range(N-1):
  for j in range(i+1, N):
    xor_sum += (A[i]^A[j])

dst = xor_sum % (10**9+7)
print(dst)
    
    


### FIXED CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = np.array(A)

mod = 10 ** 9 + 7
s = 0

for i in range(60):# Aは2の6乗より小さい
    c = np.count_nonzero(A & 1) # 最下位のbitで0じゃないものの個数
    s += 2 ** i * c * (N - c) # https://qiita.com/ZhangChaoran/items/0d59eb5c95cd9414801d
    A >>= 1 #　1bitずつ右にずらす。これを繰り返し続ける
print(s % mod)
n,m = int(input())
a = []
b = [1 for i in range(m)]
for i in range(n):
  a.append(list(int(input()).split()))
for s in range(m):
  for i in range(n):
    if (s+1) in a[i] == False:
      b[s] = 0
cnt = 0
for d in range(len(b)):
  if b[d] = 1:
    cnt+= 1
print(cnt)

### FIXED CODE ###

n,m=map(int,input().split())
food=[0 for i in range(m)]
for i in range(n):
  per=list(map(int,input().split()))
  for j in range(1,per[0]+1):
    food[per[j]-1]+=1
ans=0
for i in range(m):
  if food[i] == n:
    ans+=1
print(ans)
a = list(map(innt, input().split()))
print(len(set(a)))

### FIXED CODE ###

a = list(map(int, input().split()))
print(len(set(a)))
k, n = map(int, input().split())
 
An = list(map(int, input().split()))
 
mn = 0
Amax = max(An)
Amin = min(An)
for i in range(len(An)):
    cal = 0
    A = An[i:]  + An[:i]
    for i in range(len(A)-1):
        if A[i] == Amax and A[i+1] == Amin:
            cal += A[i+1] + k - A[i]
        elif A[i] == Amin and A[i+1] == Amax:
            cal += A[i] + k - A[i+1]
        elif A[i+1] >= A[i]:
            cal += A[i+1] - A[i]
        else:
            cal += A[i] - A[i+1]
        
        if mn > 0 and cal > mn:
            break
    
    if mn ==0 or mn > cal:
        mn = cal
        
rAn = An[:]
rAn.reverse()
for i in range(len(rAn)):
    cal = 0
    A = rAn[i:]  + rAn[:i]
    for i in range(len(A)-1):
        if A[i] == Amax and A[i+1] == Amin:
            cal += A[i+1] + k - A[i]
        elif A[i] == Amin and A[i+1] == Amax:
            cal += A[i] + k - A[i+1]
        elif A[i+1] >= A[i]:
            cal += A[i+1] - A[i]
        else:
            cal += A[i] - A[i+1]
            
        if mn > 0 and cal > mn:
            break
 
    if mn ==0 or mn > cal:
        mn = cal
print(mn)
k, n = map(int, input().split())

An = list(map(int, input().split()))

mn = 0
Amax = max(An)
Amin = min(An)
for i in range(len(An)):
    cal = 0
    A = An[i:]  + An[:i]
    for i in range(len(A)-1):
        if A[i] == Amax and A[i+1] == Amin:
            cal += A[i+1] + k - A[i]
        elif A[i] == Amin and A[i+1] == Amax:
            cal += A[i] + k - A[i+1]
        elif A[i+1] >= A[i]:
            cal += A[i+1] - A[i]
        else:
            cal += A[i] - A[i+1]
        
        if mn > 0 and cal > mn:
            break
    
    if mn ==0 or mn > cal:
        mn = cal
        
rAn = An[:]
rAn.reverse()
for i in range(len(rAn)):
    cal = 0
    A = rAn[i:]  + rAn[:i]
    for i in range(len(A)-1):
        if A[i] == Amax and A[i+1] == Amin:
            cal += A[i+1] + k - A[i]
        elif A[i] == Amin and A[i+1] == Amax:
            cal += A[i] + k - A[i+1]
        elif A[i+1] >= A[i]:
            cal += A[i+1] - A[i]
        else:
            cal += A[i] - A[i+1]
            
        if mn > 0 and cal > mn:
            break

    if mn ==0 or mn > cal:
        mn = cal
print(mn)


### FIXED CODE ###

k, n = map(int, input().split())
 
An = list(map(int, input().split()))
 
node = [An[i+1] - An[i]  for i in range(len(An) - 1)]
 
node = node[:] + [k - An[n-1] + An[0]]
 
print(k - max(node))
import fractions
n=int(input())
t=[]
for i in range(n):
  t.append(int(input()))
a=t[0]
for i in range(n-1):
  a=fractions.gcd(a,a[i+1])
print(a)
  

### FIXED CODE ###

import fractions
n=int(input())
t=[]
for i in range(n):
  t.append(int(input()))
a=t[0]
for i in range(n-1):
  a=(a*t[i+1])//(fractions.gcd(a,t[i+1]))
print(a)
N, K, Q = (int(i) for i in input().split())
A = [int(input()) for i in range(Q)]

import numpy as np
T = K - Q
S = np.ones(N)*T

for i in range(Q):
  S[A[i]] += 1

for i in range(N):
  if S[i] <= 0:
    print('No')
  else:
    print('Yes')

### FIXED CODE ###

N, K, Q = (int(i) for i in input().split())
A = [int(input()) for i in range(Q)]

import numpy as np
S = np.ones(N)*(K - Q)

for i in range(Q):
  x = A[i]
  S[x-1] += 1

for i in range(N):
  if S[i] <= 0:
    print('No')
  else:
    print('Yes')
n = int(input())
p = list(map(int, input().split()))

count = 0
for i in range(1,n-1):
    nums = p[(i-1):(i+1)]
    nums.sort()
    if p[i] == nums[1]
        count += 1
print(count)


### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))

c = 0
for i in range(n-2):
    a = p[i:i+3]
    b = sorted(a)
    if a[1] == b[1]:
        c += 1
print(c)
#!/usr/bin/env python3

def main():
    n, k, c = map(int, input().split())
    s = input()

    left = getleft(s, n, c)
    right = list(reversed(getleft(s[::-1], n, c)))

    for i in range(n):
        if i == 0:
            canrest = (right[i + 1][0] >= k)
        elif i == n - 1:
            canrest = (left[i - 1][0] >= k)
        else:
            if left[i - 1][0] + right[i + 1][0] >= k + 1:
                canrest = True
            elif (left[i - 1][0] + right[i + 1][0] >= k) and (left[i - 1][1] + right[i + 1][1] >= c - 1):
                canrest = True
            else:
                canrest = False
        if not canrest:
            print(i + 1)

def getleft(s, n, c):
    left = [None for i in range(n)]
    x = 0
    d = 10 ** 9
    for i in range(n):
        if s[i] == "o":
            if d >= c:
                x += 1
                d = 0
            else:
                d += 1
        else:
            d += 1
        left[i] = (x, d)
    return left

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    n, k, c = map(int, input().split())
    s = input()

    left = getleft(s, n, c)
    right = list(reversed(getleft(s[::-1], n, c)))

    if n == 1:
        print(1)
        return

    for i in range(n):
        if i == 0:
            canrest = (right[i + 1][0] >= k)
        elif i == n - 1:
            canrest = (left[i - 1][0] >= k)
        else:
            if left[i - 1][0] + right[i + 1][0] >= k + 1:
                canrest = True
            elif (left[i - 1][0] + right[i + 1][0] >= k) and (left[i - 1][1] + right[i + 1][1] >= c - 1):
                canrest = True
            else:
                canrest = False
        if not canrest:
            print(i + 1)

def getleft(s, n, c):
    left = [None for i in range(n)]
    x = 0
    d = 10 ** 9
    for i in range(n):
        if s[i] == "o":
            if d >= c:
                x += 1
                d = 0
            else:
                d += 1
        else:
            d += 1
        left[i] = (x, d)
    return left

if __name__ == "__main__":
    main()
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7

ndp = [1] * (M+1)
for n in range(N):
    #ndp = [1]
    for m in range(M):
        if S[n] == T[m]:
            #ndp.append(ndp[-1] + dp[m+1])
            ndp[m+1] = ndp[m] + dp[m+1]
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = ndp[m] + dpleft[m]
            #ndp.append(ndp[m] + dpleft[m])
    dp = ndp[:]
    print(dpleft)
print(dp[-1] % MOD)

### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7
ndp = [1] * (M+1)
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            ndp[m+1] = ndp[m] + dp[m+1]
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = ndp[m] + dpleft[m]
    dp = ndp[:]
print(dp[-1] % MOD)
S_a = input()
S_b = input()
S_c = input()
a = []
b = []
c = []
for i in range(len(S_a)):
    a.append(S_a[i])
for j in range(len(S_b)):
    b.append(S_b[i])
for k in range(len(S_c)):
    c.append(S_c[i])
l = a
winner = 'A'
wlile len(l) > 0:
    x = l.pop(0)
    if x == 'a':
        l = a
        winner = 'A'
    elif x == 'b':
        l = b
        winner = 'B'
    else:
        l = c
        winner = 'C'
print(winner)

### FIXED CODE ###

S_a = input()
S_b = input()
S_c = input()
a = []
b = []
c = []
for i in range(len(S_a)):
    a.append(S_a[i])
for j in range(len(S_b)):
    b.append(S_b[j])
for k in range(len(S_c)):
    c.append(S_c[k])
l = a
winner = 'A'
while len(l) > 0:
    x = l.pop(0)
    if x == 'a':
        l = a
        winner = 'A'
    elif x == 'b':
        l = b
        winner = 'B'
    else:
        l = c
        winner = 'C'
print(winner)