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

s = input()
 
m = 1000000007
dp = [0] * 4
dp[0] = 1
 
for c in s:
    if c=='A':
        dp[1] += dp[0]
    elif c=='B':
        dp[2] += dp[1]
    elif c=='C':
        dp[3] += dp[2]
    elif c=='?':
        dp = [dp[0]*3, dp[0]+dp[1]*3, dp[1]+dp[2]*3, dp[2]+dp[3]*3]
print(dp[3]%m)
                

### FIXED CODE ###

S = input()
def ABC(S):
    N = len(S)
    dp = [[0 for j in range(4)] for i in range(N+1)]
    model = 'ABC'
    p = 10**9 + 7
    for i in range(N, -1, -1):
        for j in range(3,-1,-1):
            if i == N and j == 3:
                dp[i][j] = 1
            elif i == N and j < 3:
                dp[i][j] = 0
            elif i < N and j == 3:
                if S[i] == '?':
                    dp[i][j] = 3 * dp[i+1][j] % p
                else:
                    dp[i][j] = dp[i+1][j] % p
            else:
                if S[i] == '?':
                    m1 = 3
                else:
                    m1 = 1
                if S[i] == '?' or S[i] == model[j]:
                    m2 = 1
                else:
                    m2 = 0
                dp[i][j] = (m1 * dp[i+1][j])%p + m2 * (dp[i+1][j+1])%p
    return dp[0][0] % p
print(ABC(S))
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
mod = 10 ** 9 + 7
ans = 0
for i in range(N - 1):
  for j in range(i+1, N):
    a = A[i] % mod
    b = A[j] % mod
    ans += (a * b) % mod
    ans = ans % mod

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
mod = 10 ** 9 + 7
ans = 0
#TLE
'''
for i in range(N - 1):
  for j in range(i+1, N):
    a = A[i] % mod
    b = A[j] % mod
    ans += (a * b) % mod
    ans = ans % mod
'''
tot = 0
for i in range(N):
  A[i] %= mod
  tot += A[i]
  tot %= mod
for i in range(N-1):
  tot -= A[i]
  ans += (A[i] * tot) % mod
  ans %= mod
print(ans)
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))


heapq.heapify(A)

for i in range(M):
  B, C = map(int, input().split())
  for i in range(B):
    heapq.heappush(A, C)

print(sum(heapq.nlargest(N, A)))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]
BC = sorted(BC, key= lambda x:x[1], reverse=True)


BC2 = []
for i in range(M):
  BC2.extend([BC[i][1]] * BC[i][0])
  if len(BC2) > N : break
A.extend(BC2)
A.sort(reverse=True)

print(sum(A[:N]))
### BUGGY CODE ###

n = int(input())

A = [int(input()) for i in range(n)]

for i in range(n):
    a = A[0]
    A = A[1:]
    print(max(A))
    A.append(a)


### FIXED CODE ###

n = int(input())

A = [int(input()) for i in range(n)]

S = sorted(A)

m1 = max(A)
m2 = S[-2]

for a in A:
    if a != m1:
        print(m1)
    else:
        print(m2)
### BUGGY CODE ###

import copy

N = int(input())
list = [int(i) for i in input().split()]

count = 0

for j in range(N):
    #print(j)
    #print(list)
    #print("j="+str(j))
    list2 = copy.copy(list)
    #print(list2)
    #print(j)
    del list2[j+1:]
    #print(list2)
    #list2 = sorted(list2)
    #print(list[j])
    if(min(list2) >= list[j]):
        count +=1

print(count)


### FIXED CODE ###

N = int(input())
list = [int(i) for i in input().split()]

ans = 0
min = list[0]

for j in range(N):
    if (min  >= list[j]):
        ans += 1
        min = list[j]
    else:
        continue

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

L = input()
INF = 10**9+7

count = L.count('1')
ans = 2**count
for i in range(len(L)-1,-1,-1):
  if L[i]=='1':
    count -= 1
    m = 3**(len(L)-i-1)*(2**count)
    ans += m
    ans %= INF
print(ans)


### FIXED CODE ###

L = input()
MOD = 10**9+7

pow_3=[1]
for _ in range(2*10**5):
  pow_3.append((pow_3[-1]*3)%MOD)
  
pow_2=[1]
for _ in range(2*10**5):
  pow_2.append((pow_2[-1]*2)%MOD)
  
count = L.count('1')
ans = pow_2[count]

for i in range(len(L)-1,-1,-1):
  if L[i]=='1':
    count -= 1
    m = pow_3[len(L)-i-1]*pow_2[count]
    ans += m
    ans %= MOD
print(ans)
### BUGGY CODE ###

input_number = int(input())
int_list = list(map(int, input().split()))

ans = int_list[0]
for i in int_list[1:]:
    ans = ans * i

if ans > (10 ** 18):
    ans = -1
print(ans)


### FIXED CODE ###

input_number = int(input())
int_list = list(map(int, input().split()))

check = 10 ** 18
ans = int_list[0]
for i in int_list[1:]:
    ans = ans * i

    if ans > check:
        ans = -1
        break

for i in int_list:
    if i == 0:
        ans = 0
        break

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

n = int(input())
s = input()
c = n
for i in range(n+1):
  cnew = s[0:i].count('#')+s[i:n].count('.')
  if cnew < c:
    c = cnew
print(c)

### FIXED CODE ###

n = int(input())
s = input()
m = s.count('.')
ans = m
for i in range(n):
  if s[i] == '#':
    m = m + 1
  else:
    m = m - 1
  ans=min(m,ans)
print(ans)
### BUGGY CODE ###

cubes = input()

removed_cubes_count = 0

while True:
    count01 = cubes.count('01')
    count10 = cubes.count('10')

    if count01 == 0 and count10 == 0:
        break

    removed_cubes_count += count01 + count10

    cubes = cubes.translate({
        '01': '',
        '10': ''
    })



print(removed_cubes_count)


### FIXED CODE ###

cube = input()

zero_count = 0
one_count = 0

for i in range(len(cube)):
    if cube[i] == '0':
        zero_count += 1
    else:
        one_count += 1

if zero_count < one_count:
    print(zero_count * 2)
else:
    print(one_count * 2)
### BUGGY CODE ###

n = int(input())
tmp = 0
max = 0
for i in range(n):
    max = max + i
print(max)


### FIXED CODE ###

n = int(input())
m = (n-1)*n//2
print(m)
### BUGGY CODE ###

import numpy as np
import math

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)
ans = np.zeros(2019, dtype=int)

for i in range(length):
    if i == 0:
        a[i] = int(s[i])
        d[i] = a[i]
        ans[d[i]] += 1
    else:
        a[i] = int(s[i]) * pow(10, i) % 2019
        d[i] = (d[i-1] + a[i]) % 2019
        ans[d[i]] += 1

print(int(sum([ans[i] * (ans[i]-1) for i in range(ans.shape[0])]) / 2) + ans[0])

### FIXED CODE ###

import numpy as np

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)
ans = np.zeros(2019, dtype=int)
x = 10

a[0] = int(s[0])
d[0] = a[0]
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * x % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1
    x = x * 10 % 2019

ans_c = ans[np.nonzero(ans)]

print(int(sum([ans_c[i] * (ans_c[i]-1) for i in range(ans_c.shape[0])]) / 2) + ans[0])
### BUGGY CODE ###

n,m = map(int, input().split())
ab = []
num = 0
for i in range(m):
    a,b = map(int, input().split())
    if a == 1:
        num += 1
    ab.append((a,b))
ab.sort()
x = 'IMPOSSIBLE'
for h in range(num):
    if (ab[h][1],n) in ab:
        x = 'POSSIBLE'
        break
print(x)

### FIXED CODE ###

n,m = map(int, input().split())
b1 = []
b2 = []
for i in range(m):
    a,b = map(int, input().split())
    if a == 1:
        b1.append(b)
    if b == n:
        b2.append(a)
if len(b1) + len(b2) == len(list(set(b1+b2))):
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

l = [1]
bot = 1
for i in range(n):
    bot = a[bot - 1]
    if bot == 2:
        print(i + 1)
        break
    if bot in l:
        print(-1)
        break
    else:
        l.append(bot)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

l = [1]
bot = 1
flag = True
for i in range(n):
    bot = a[bot - 1]
    if bot == 2:
        print(i + 1)
        flag = False
        break

if flag:
    print(-1)
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 9 + 7
def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

N = int(input())

adj = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1    
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

ans = 0
def dfs(v, p):
    global ans
    subs = []
    res = 1
    for u in adj[v]:
        if u == p:
            continue
        val = dfs(u, v)
        res += val
        subs.append(val)
    # add sub-tree on the parent side
    if p != -1:
        subs.append(N - res)
    now = (2 ** (N - 1)) - 1 # N - 1 means that it chooses freelye other than v
    now %= MOD
    for sub in subs:
        now -= ((2 ** sub) - 1)
        now %= MOD
    ans += now
    ans %= MOD
    return res

dfs(0, -1)
print(ans * my_pow(2 ** N, MOD - 2, MOD) % MOD)

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 9 + 7
def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

N = int(input())

adj = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1    
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

pows = [1] * N
for i in range(1, N):
    pows[i] = (pows[i - 1] * 2) % MOD

ans = 0
def dfs(v, p):
    global ans
    subs = []
    res = 1
    for u in adj[v]:
        if u == p:
            continue
        val = dfs(u, v)
        res += val
        subs.append(val)
    # add sub-tree on the parent side
    if p != -1:
        subs.append(N - res)
    now = pows[N - 1] - 1 # N - 1 means that it chooses freelye other than v
    for sub in subs:
        now -= pows[sub] - 1
    ans += now
    ans %= MOD
    return res

dfs(0, -1)
print(ans * my_pow(2 ** N, MOD - 2, MOD) % MOD)
### BUGGY CODE ###

import numpy as np
S = input()[::-1]
mod = 1000000007

n = len(S)
a = S[0]
x = np.zeros(26, int)
l = [[13 - i * j % 13 for j in range(0, 10)] for i in [1, 10, 9, 12, 3, 4]] * (n // 6 + 1)
if a == "?":
    x[0:10] += 1
else:
    x[int(a)] += 1
for s, l_ in zip(S[1:], l[1:]):
    x[13:] = x[:13]
    if s == "?":
        x[:13] = np.sum(x[v:v+13] for v in l_)
    else:
        v = l_[int(s)]
        x[:13] = x[v:v+13]
    x %= mod
print(x[5])

### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


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

N=int(input())
A=[int(i) for i in input().split()]
s=0
t=0
for i in range(N):
    s+=abs(A[i]-1-i)
    t+=abs(A[i]-i)
if s>t:
    d=0
    while True:
        d-=1
        r=0
        u=0
        for i in range(N):
            r+=abs(A[i]-d-1-i)
            u+=abs(A[i]-d-i)
        if r>u:
            continue
        else:
            print(r)
            break
elif s==t:
    print(s)
else:
    e=0
    while True:
        e+=1
        x=0
        y=0
        for i in range(N):
            x+=abs(A[i]-e-1-i)
            y+=abs(A[i]-e-i)
        if x<y:
            continue
        else:
            print(y)
            break

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
u=[]
for i in range(N):
    u.append(A[i]-i)
a=sorted(u)
if len(a)%2==0:
    p=a[len(a)//2]
else:
    p=a[len(a)//2]
ans=0
for j in range(N):
    ans+=abs(a[j]-p)
print(ans)
### BUGGY CODE ###

N = int(input())

inf = float('inf')

import heapq
def dijkstra(adj, n, st=1):
    dj = [inf] * (n + 1)
    paths = dict((x, [x]) for x in range(n + 1))
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                paths[tn] = paths[fn] + [tn]
                heapq.heappush(q, (dj[tn], tn))
    return dj, paths

adj = dict((x, []) for x in range(N + 1))
for _ in range(N - 1):
    a, b = map(int, input().split())
    adj[a].append((b, 1))
    adj[b].append((a, 1))

costs, paths = dijkstra(adj, N, 1)
main_street = paths[N]
import math
mid = math.ceil(len(main_street) / 2) - 1
mid_v0 = main_street[mid]
mid_v1 = main_street[mid + 1]
adj[mid_v0] = filter(lambda x: x[0] != mid_v1, adj[mid_v0])
adj[mid_v1] = filter(lambda x: x[0] != mid_v0, adj[mid_v1])

fennec = N - dijkstra(adj, N, 1)[0].count(inf) + 1
snuke = N - fennec

print("Fennec" if fennec > snuke else "Snuke")

### FIXED CODE ###

N = int(input())

inf = float('inf')

import heapq
def dijkstra(adj, n, st=1):
    dj = [inf] * (n + 1)
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                heapq.heappush(q, (dj[tn], tn))
    return dj

adj = dict((x, []) for x in range(N + 1))
for _ in range(N - 1):
    a, b = map(int, input().split())
    adj[a].append((b, 1))
    adj[b].append((a, 1))

c_f = dijkstra(adj, N, 1)
c_s = dijkstra(adj, N, N)

score = 0
for i in range(1, N + 1):
    if c_f[i] > c_s[i]:
        score -= 1
    else:
        score += 1

print("Fennec" if score > 0 else "Snuke")
### BUGGY CODE ###

N = 10**8
for i in range(N):
    b = 0

a = int(input())
print(a + a**2 + a**3)


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    a = in_n()
    print(a + a**2 + a**3)


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

def isOdd(num):
	if num % 2 == 0:
		return False
	else:
		return True

A, B, C = map(int, raw_input().split())
ans = 0
while not isOdd(A) and not isOdd(B) and not isOdd(C):
	ans += 1
	new1, new2, new3 = B/2 + C/2, A/2 + C/2, A/2 + B/2
	if set([A, B, C]) == set([new1, new2, new3]):
		print -1
	else:
		A, B, C = new1, new2, new3
print ans


### FIXED CODE ###

A, B, C = map(int, raw_input().split())
[A, B, C] = sorted([A, B, C])
ans = 0
while A%2==0 and B%2==0 and C%2==0:
	ans += 1
	new1, new2, new3 = B/2 + C/2, A/2 + C/2, A/2 + B/2
	if new1 == new3:
		ans = -1
		break
	else:
		A, B, C = new1, new2, new3
print ans
### BUGGY CODE ###

import bisect
N = int(input())
X = list(map(int, input().split()))

A = []
for i in range(N):
    bisect.insort(A, X[i])

leftB = A[N//2 - 1]
rightB = A[N//2]

for i in range(N):
    if X[i] <= leftB:
        print(rightB)
    else:
        print(leftB)


### FIXED CODE ###

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

leftB = A[N//2 - 1]
rightB = A[N//2]

for i in range(N):
    if X[i] <= leftB:
        print(rightB)
    else:
        print(leftB)
### BUGGY CODE ###

import queue,sys
sys.setrecursionlimit(10**7)
INF = 10**10
N = int(input())
x = [0 for _ in range(N)]
y = [0 for _ in range(N)]
for i in range(N):
    x[i], y[i] = map(int,input().split())
x_ix = [i for i in range(N)]
y_ix = [i for i in range(N)]
sort_x_ix = sorted(x_ix, key=lambda i:x[i])
sort_x = [x[i] for i in sort_x_ix]
sort_y_ix = sorted(y_ix, key=lambda i:y[i])
sort_y = [y[i] for i in sort_y_ix]

g = [i for i in range(N+1)]
def root(x):
    if g[x] == x : return x
    g[x] = root(g[x])
    return g[x]
q = []
for i in range(N-1):
    q.append((sort_x[i+1]-sort_x[i],sort_x_ix[i],sort_x_ix[i+1]))
    q.append((sort_y[i+1]-sort_y[i],sort_y_ix[i],sort_y_ix[i+1]))
q.sort()
ans = 0
cnt = N
for d,s,t in q:
    if cnt <= 1: break
    if root(s) != root(t):
        ans += d
        cnt -= 1
        g[root(t)] = g[s]

print(ans)

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    xy = [LI() for _ in range(N)]

    x = [(xy[i][0],i) for i in range(N)]
    y = [(xy[i][1],i) for i in range(N)]

    x.sort()
    y.sort()

    edge = []
    p,i = x[0]
    for q,j in x[1:]:
        edge.append((q-p,i,j))
        p,i = q,j

    p,i = y[0]
    for q,j in y[1:]:
        edge.append((q-p,i,j))
        p,i = q,j

    edge.sort()

    g = [i for i in range(N + 1)]
    g_num = [1 for i in range(N + 1)]

    def find(x):
        if g[x] == x: return x
        g[x] = find(g[x])
        return g[x]

    def union(x, y):
        if find(x) == find(y): return
        if g_num[g[x]] < g_num[g[y]]: x, y = y, x
        g_num[g[x]] += g_num[g[y]]
        g_num[g[y]] = 0
        g[g[y]] = g[x]

    ans = 0
    for v,i,j in edge:
        if find(i) != find(j):
            ans += v
            union(i,j)

    print(ans)



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

#abc110 C
N, X = map(int, input().split())
x = list(map(int, input().split()))
distance = [ abs(x[i]-X) for i in range(N)]


for d in range(min(distance),0,-1):
    flag = 1
    for i in range(N):
        if distance[i] % d != 0:
            flag = 0
    if flag == 1:
        print(d)
        break

### FIXED CODE ###

#abc110 C 最大公約数
N, X = map(int, input().split())
x= list(map(int, input().split()))
distance = [ abs(x[i]-X) for i in range(N)]

def gcd( x , y ):
    while y != 0:
        x,y = y, x%y
    return x

def GCD(lis):
    g = lis[0]
    for i in range(1,len(lis)):
        g = gcd( g , lis[i] )
    return g

maxD = GCD(distance)
print(maxD)
### BUGGY CODE ###

N=input()

A=list(map(int,raw_input().split()))
B=list(map(int,raw_input().split()))
C=list(map(int,raw_input().split()))
A.sort()
B.sort()
C.sort()
#print A
#print B
#print C

sum=0

for i in range(N):
	j_start=0
	for j in range(N):
		if B[j]<=A[i]:
			continue
		for k in range(j_start,N):
			#print "# loop C"
			#print A[i],B[j],C[k],N-k
			if C[k]>B[j]:
				#print A[i],B[j],C[k],N-k
				sum+=(N-k)
				j_start=k
				break

print sum
			



### FIXED CODE ###

import bisect
N=input()

A=list(map(int,raw_input().split()))
B=list(map(int,raw_input().split()))
C=list(map(int,raw_input().split()))
A.sort()
B.sort()
C.sort()

sum=0
for val_b in B:
	sum+=bisect.bisect_left(A, val_b)*( N-bisect.bisect_right(C, val_b) )
			
print sum
### BUGGY CODE ###

N = int(input())
S = list(input())
numS = [0 for i in range(N)]
for i in range(N):
    if S[i] == 'E':
        numS[i] = 0
    else:
        numS[i] = 1
# print(numS)
minS = N
for i in range(N):
    numT = [0 for j in range(i)] + [numS[i]] + [1 for j in range(i+1,N)]
    # print(numT)
    minS = min(minS,sum([abs(numT[i]-numS[i]) for i in range(N)]))

print(minS)

### FIXED CODE ###

N = int(input())
S = list(input())
numS = [0 for i in range(N)]
sumS = [0 for i in range(N)]
for i in range(N):
    if S[i] == 'E':
        numS[i] = 0
    else:
        numS[i] = 1

for i in range(N):
    sumS[i] = sumS[i-1] + numS[i]
# print(sumS)
minS = (N-1) - (sumS[N-1]-sumS[0])
for i in range(1,N):
    minS = min(minS,sumS[i-1]+(N-i-1)-(sumS[N-1]-sumS[i]))
print(minS)
### BUGGY CODE ###

from collections import deque
 
def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    d = [[10**9] * w for _ in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               d[i][j] = 0
           else:
               d[i][j] = 10 ** 9
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 10**9:
                d[nx][ny] = d[x][y] + 1
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)
    
    return
    
main()
 

### FIXED CODE ###

from subprocess import call
call (('pypy3', '-c', """
from collections import deque
 
def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    d = [[10**9] * w for _ in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               d[i][j] = 0
           else:
               d[i][j] = 10 ** 9
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 10**9:
                d[nx][ny] = d[x][y] + 1
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)
    
    return
    
main()
 
"""))
### BUGGY CODE ###

import heapq
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

na = 0
nb = 0
t = 0
b = 0
hq = []
heapq.heappush(hq,(t, na, nb))

while hq:
  t, na, nb = heapq.heappop(hq)
  if (na < N) and (t + A[na] <= K):
    heapq.heappush(hq,(t + A[na], na + 1, nb))
    b = max(b,na + nb + 1)
  if (nb < M) and (t + B[nb] <= K):
    heapq.heappush(hq,(t + B[nb], na, nb + 1))
    b = max(b,na + nb + 1)
#
print(b)




### FIXED CODE ###

import heapq
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

TA = [0]
TB = [0]
na = 0
nb = 0

for i in range(N):
  n = TA[-1]+A[i]
  if n > K:
    break
  TA.append(n)
  na = i + 1
#
for i in range(M):
  n = TB[-1]+B[i]
  if n > K:
    break
  TB.append(n)
  nb = i + 1
#
a = 0
ans = 0

for b in range(nb,-1,-1):
  while TB[b]+TA[a] <= K:
    ans = max(ans,a+b)
    a += 1
    if a > na:
      a -= 1
      break
#
print(ans)
### BUGGY CODE ###

n, x, y = list(map(int, input().split()))
x -= 1
y -= 1

cnt = [0] * n
for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        dist = min(j - i, abs(j - y) + 1 + abs(i - x), abs(j - x) + 1 + abs(i - y))
        cnt[dist] += 1
for i in range(1, n):
    print(cnt[i])


### FIXED CODE ###

n, x, y = list(map(int, input().split()))
x -= 1
y -= 1

cnt = [0] * n

dist = []
for i in range(n):
    dist.append([-1] * n)
for i in range(n):
    dist[i][x] = abs(i-x)
    dist[i][y] = abs(i-y)
    dist[x][i] = abs(i-x)
    dist[y][i] = abs(i-y)

for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        dis = min(j - i, dist[j][y] + 1 + dist[i][x], dist[j][x] + 1 + dist[i][y])
        cnt[dis] += 1
for i in range(1, n):
    print(cnt[i])