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

def opt(N,W):
    dp=[0]*(W+1)
    for _ in range(N):
        w,v=map(int,input().split())
        for i in range(W,w-1,-1):
            dp[i]=max(dp[i],dp[i-w]+v)
    print(dp[W])

N,W=map(int,input().split())
opt(N,W)

### FIXED CODE ###

def opt(N,W):
    dp=[0]*(W+1)
    for _ in range(N):
        w,v=map(int,input().split())
        for i in range(W,w-1,-1):
            tmp=dp[i-w]+v
            if tmp>dp[i]:
                dp[i]=tmp
    print(dp[W])

N,W=map(int,input().split())
opt(N,W)
### BUGGY CODE ###

from collections import*
n,*a=map(int,open(0).read().split())
b=Counter(a)
for i in range(n):
    c=(b-Counter([a[i]]))
    print(sum([v*(v-1)//2 for k,v in c.items()if v>=2]))

### FIXED CODE ###

from collections import*
n,*a=map(int,open(0).read().split())

b=Counter(a)

ans=sum(v*(v-1)//2 for k,v in b.items())

for i in range(n):
    x=b[a[i]]
    print(ans-x*(x-1)//2+(x-1)*(x-2)//2)
### BUGGY CODE ###

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

ans = 0
for i in range(n):
    cnt = 0
    for j in range(n):
        if i == j:
            continue
        if A[i]%A[j] == 0:
            cnt += 1
            break
    if cnt == 0:
        ans += 1

print(ans)

### FIXED CODE ###

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

A.sort()
dp = [True for _ in range(A[-1]+1)]

for i in range(n-1):#同じものがいたらその番号をfalseにする
    if A[i] == A[i+1]:
        dp[A[i]] = False

res = 0
for a in A:
    if dp[a]:
        res += 1
    for b in range(a,len(dp),a):#aの倍数を削除する
        dp[b] = False
print(res)
### BUGGY CODE ###

S = str(input())
S_len = len(S)

DP = list = [[0] * 13 for i in range(S_len)]

for i in reversed(range(S_len)):

    if i == len(S) - 1:
        if S[i] != "?":
            DP[i][int(S[i]) % 13] = 1
        else:
            for j in range(10):
                DP[i][j] = 1

    else:

        if S[i] != "?":
            for j in range(13):
                if DP[i + 1][j] != 0:
                    DP[i][(j + int(S[i]) * (10 ** (S_len - 1 - i))) % 13] = (DP[i][(j + int(S[i]) * (
                                10 ** (S_len - 1 - i))) % 13] + DP[i + 1][j]) % 1000000007
        else:
            for j in range(13):
                for k in range(10):
                    if DP[i + 1][j] != 0:
                        DP[i][(j + k * (10 ** (S_len - 1 - i))) % 13] = (DP[i][
                                                                              (j + k * (10 ** (S_len - 1 - i))) % 13] +
                                                                          DP[i + 1][j]) % 1000000007

print(DP[0][5])


### FIXED CODE ###

s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(1,l+1):
  if s[i-1]=='?':
    for j in range(10):
      for k in range(13):
        dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
  else:
    for k in range(13):
      dp[i][(k*10+int(s[i-1]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)
### BUGGY CODE ###

from bisect import*
n,k,*a=map(int,open(0).read().split())
if 0 in a:
    k-=1
    a.remove(0)
#print(a)
ans=[]
for i in range(-k,1):
    b=a[bisect(a,0)+i:bisect(a,0)+i+k]
    if len(b)==0:
        continue
    if len(b)==k:
        #print(b)
        ans.append(abs(b[0])+abs(b[-1]-b[0]))
        ans.append(abs(b[-1])+abs(b[-1]-b[0]))
print(min(ans or [0]))

### FIXED CODE ###

from bisect import*
n,k,*a=map(int,open(0).read().split())
if 0 in a:
    k-=1
    a.remove(0)
#print(a)
ans=[]

x=bisect(a,0)
for i in range(-k,1):
    p=x+i
    q=x+i+k-1

    if 0<=p<n and 0<=q<n:
        #print(p,q)
        c=a[p]
        d=a[q]
        ans.append(abs(c)+abs(d-c))
        ans.append(abs(d)+abs(d-c))
#print(ans)
print(min(ans or [0]))
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
for i in range(Q):
    l,r=map(int,input().split())
    print(int((r-l+1-len(S[l-1:r].replace("AC","")))/2))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
list1=[list(map(int,input().split())) for _ in range(Q)]
list2=[0]*(N+1)
count=0
for i in range(N):
    if i>0:
        list2[i+1]=list2[i]
    if i==N-1:
        continue
    elif S[i:i+2]=="AC":
        list2[i+1]+=1
for tmp in list1:
    print(list2[tmp[1]-1]-list2[tmp[0]-1])
### BUGGY CODE ###

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

ans = [i for i in range(A, B+1) if i <= A+K-1 or i >= B-K+1]

for j in ans:
    print(j)


### FIXED CODE ###

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

k = K-1
if A+k >= B-k:
    for i in range(A, B+1):
        print(i)
else:
    for j in range(A, A+k+1):
        print(j)
    for k in range(B-k, B+1):
        print(k)
### BUGGY CODE ###

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

j_Aj = [0]

for j, aj in enumerate(a):
    j_Aj.append(j + 1 - aj)
i_Ai = [0] * (max(j_Aj)+1)
ans = 0
for j, j_aj in enumerate(j_Aj):
    if j == 0:
        continue
    if j_aj >= 2:
        ans += i_Ai[j_aj]
    if j + a[j - 1]<=max(j_Aj):
        i_Ai[j + a[j - 1]] += 1
print(ans)

### FIXED CODE ###

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

j_Aj = [0]

for j, aj in enumerate(a):
    j_Aj.append(j + 1 - aj)
maxj=max(j_Aj)
i_Ai = [0] * (maxj+1)
ans = 0
for j, j_aj in enumerate(j_Aj):
    if j == 0:
        continue
    if j_aj >= 2:
        ans += i_Ai[j_aj]
    if j + a[j - 1]<=maxj:
        i_Ai[j + a[j - 1]] += 1
print(ans)
### BUGGY CODE ###

#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    numbers=[]
    n = int(input())
    [numbers.append(int(input().rstrip())) for _ in range(n)]
    s_numbers=sorted(numbers)

    for i in numbers:
        if i == max(numbers):
            print(s_numbers[-2])
        else:
            print(s_numbers[-1])
    

if __name__=="__main__":
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline
import heapq

def main():
    numbers=[]
    n = int(input())
    [numbers.append(int(input().rstrip())) for _ in range(n)]

    max_n=0
    second_n=0

    for i in numbers:
        if i > max_n:
            max_n=i
        elif i > second_n:
            second_n=i
    
    for i in numbers:
        if i==max_n:
            print(second_n)
        else:
            print(max_n)
    

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

import sys
input = sys.stdin.readline 
sys.setrecursionlimit(10 ** 6)

N,M = map(int,input().split())
path = [[] for i in range(N)]
inf = 10 ** 6 * 2

ans = [[None,inf] for i in range(N - 1)]

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

def dfs(cur,par,con):
  if con == N + 1:
    return
  for chi in path[cur]:
    if chi == par:
      continue
    if con < ans[chi - 1][1]:
      ans[chi - 1][0] = cur
      ans[chi - 1][1] = con + 1
      dfs(chi,cur,con + 1)

dfs(0,-1,0)

if all([i[0] != None for i in ans]):
  print("Yes")
  for i in range(N - 1):
    print(ans[i][0] + 1)
else:
  print("No")

### FIXED CODE ###

from collections import deque

import sys
input = sys.stdin.readline 

N,M = map(int,input().split())
path = [[] for i in range(N)]
ans = [None for i in range(N)]
visited = [0 for i in range(N)]

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

def bfs(path, root,visited):
  visited[root] = 1
  queue = deque([root])
  while queue:
    cur = queue.popleft()
    for chi in path[cur]:
      if visited[chi] == 1:
        continue
      else:
        ans[chi] = cur + 1
        visited[chi] = 1
        queue.append(chi)

  if all([i == 1 for i in visited]):
    return "Yes"
  else:
    return "No"
  
flag = bfs(path,0,visited)

print(flag)

if flag == "Yes":
  for i in range(1,N):
    print(ans[i])
### BUGGY CODE ###

import math
import bisect
def logcomp(n,m):
    if m in [0,n]:
        r = 1
    else:
        a = (sum(map(math.log,[i for i in range(max(n-m+1,m+1),n+1)])))
        b = (sum(map(math.log,[i for i in range(1,min(n-m+1,m+1))])))
        r = a-b
    return r



n = int(input())
num_list = sorted([ int(v) for v in input().split() ])


for i in range(1,n):
    x = num_list[i]
    y = bisect.bisect_left(num_list,x/2)
    if y == i:
        z = logcomp(x,num_list[y-1])
        w = num_list[y-1]
    else:
        if abs(num_list[y]-(x/2)) <= abs(num_list[y+1]-(x/2)):
            z = logcomp(x,num_list[y])
            w = num_list[y]
        else:
            z = logcomp(x,num_list[y+1])
            w = num_list[y+1]
    if i == 1:
        ans = (x,w)
        max_z = z
    else:
        if max_z < z:
            max_z = z
            ans = (x,w)
print(*ans)


### FIXED CODE ###

import bisect

n = int(input())
num_list = sorted([ int(v) for v in input().split() ])

x = num_list[-1]
x_half = x / 2
y = bisect.bisect_left(num_list,x_half)
if y != 0:
    if y == n-1:
        y -= 1
    else:
        if abs(num_list[y] - x_half) >= abs(num_list[y-1] - x_half):
            y -= 1
print(x,num_list[y])
### BUGGY CODE ###

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

ans = 0
sub = []
for i, a in enumerate(A, 1):
    sub.append(a - i)
    ans += abs(a - i)

#print(sub)

#b = min(sub)
for b in range(min(sub), max(sub) + 1):
    cand = 0
    for s in sub:
        cand += abs(s - b)
    ans = min(ans, cand)
print(ans)


### FIXED CODE ###

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

for i, a in enumerate(A):
    A[i] = a - i

A = sorted(A)
b = A[len(A)//2]

ans = 0
for a in A:
    ans += abs(a - b)

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

#ABC-127-C
N, M = map(int, input().split())
LR  = []
for _ in range(M):
    Li, Ri = map(int, input().split())
    LR.append((Li, Ri))

possible_card_list = [i for i in range(LR[0][0], LR[0][1]+1)]

for Li, Ri in LR:
    for possible_card in possible_card_list[:]:
        if Li <= possible_card and possible_card <= Ri:
            #OK
            pass
        else:
            possible_card_list.remove(possible_card)
            
print(len(possible_card_list))
        

### FIXED CODE ###

#ABC-127-C
N, M = map(int, input().split())
L_list  = []
R_list = []
for _ in range(M):
    Li, Ri = map(int, input().split())
    L_list.append(Li)
    R_list.append(Ri)

max_L = max(L_list)
min_R = min(R_list)

if max_L > min_R:
    print(0)
else:
    print(min_R-max_L+1)
### BUGGY CODE ###

import numpy as np
words = lambda t : list(map(t, input().split()))



h,w = words(int)
wq = [0] * w

grid = []
for i in range(h):
    grid.append(list(input()))

ans = 0
for i in range(h):
    j = 0
    while j < w:
        #print(i,j, grid[i][j])
        if grid[i][j] == '#':
            wq[j] = 0
            j+=1
            continue
        k = 0
        while j+k < w:
            if grid[i][j+k] == '.':
                k += 1
            else:
                break
        #print(i,j,k)
        if k + h <= ans:
            j = j + k
            continue
        for x in range(j,j+k):

            vplus = 0
            if not wq[x] == 0:
                vplus = wq[x]
            else:
                for vi in range(i-1,-1,-1):
                    if grid[vi][x] == '#':
                        break
                    else:
                        vplus += 1
                for vi in range(i+1,h):
                    if grid[vi][x] == '#':
                        break
                    else:
                        vplus += 1
            ans = max(ans, vplus+k)
            wq[x] = vplus
        j = j+k
print(ans)


### FIXED CODE ###

#import numpy as np
words = lambda t : list(map(t, input().split()))



h,w = words(int)
wq = [0] * w

grid = []
for i in range(h):
    grid.append(list(input()))

ans = 0
for i in range(h):
    j = 0
    while j < w:
        #print(i,j, grid[i][j])
        if grid[i][j] == '#':
            wq[j] = 0
            j+=1
            continue
        k = 0
        while j+k < w:
            if grid[i][j+k] == '.':
                k += 1
            else:
                break
        #print(i,j,k)
        if k + h > ans:
            for x in range(j,j+k):
                vplus = 0
                if not wq[x] == 0:
                    vplus = wq[x]
                else:
                    for vi in range(i-1,-1,-1):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                    for vi in range(i+1,h):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                ans = max(ans, vplus+k)
                wq[x] = vplus
        j += k
print(ans)
### BUGGY CODE ###

N,a,b=map(int,input().split())
m = 10**9+7
def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
            ans %= m
        x *= x
        n >>= 1
    return ans

M = pow(2, N)%m

m = 10**9+7
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
  

res = 1
for i in range(N-a+1,N+1):
    res = res*i%m
for i in range(1,a+1):
    res = res*mod_inv(i,m)%m

rs = 1
for i in range(N-b+1,N+1):
    rs = rs*i%m
for i in range(1,b+1):
    rs = rs*mod_inv(i,m)%m

print(M-1-res-rs)


### FIXED CODE ###

N,a,b=map(int,input().split())
m = 10**9+7

M = pow(2, N, m)

def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    else:
        a = b = 1
        for i in range(r):
            a = a * (n - i) % m
            b = b * (r - i) % m
        return (a * pow(b,m-2,m)) % m
 
ans = M - 1 - nCr(N,a) - nCr(N,b)
print(ans%m)
### BUGGY CODE ###

def check(s):
    n=1
    for i in range(1,int(s**0.5)+1):
        if s%i==0:
            n=i
    return n
s=int(input())
a=check(s)
b=s//a
print(0,0,a,0,0,b)

### FIXED CODE ###

import math 
s=int(input())
if s<=10**9:
    print(0,0,1,0,0,s)
else:
    b=int(math.ceil(s/10**9))
    a=10**9*b-s
    print(0,0,10**9,1,a,b)
### BUGGY CODE ###

# coding: utf-8
from collections import deque
def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    D = [[float("inf") for _ in range(N)] for _ in range(N)]
    D[X][Y] = 1
    D[Y][X] = 1
    queue = deque([[X, Y]])
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[X][Y] = True 
    while queue:
        x,y = queue.popleft()
        for i, j in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+i, y+j
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            if visited[nx][ny]:
                continue
            else:
                visited[nx][ny] = True
                D[nx][ny] = min(abs(ny-nx), D[x][y]+1)
                queue.append([nx, ny])
    ans = [0 for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(i+1, N):
            v = D[i][j]
            ans[v-1] += 1
    print(*ans[:-1], sep="\n")
main()

### FIXED CODE ###

# coding: utf-8
from collections import deque
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
D = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        D[i][j] = abs(j-i)
        D[j][i] = abs(j-i)
D[X][Y] = 1
D[Y][X] = 1
# print(*D, sep="\n")
queue = deque([[X, Y]])
visited = [[False for _ in range(N)] for _ in range(N)]
visited[X][Y] = True 
while queue:
    x,y = queue.popleft()
    for i, j in zip([1, 0, -1, 0], [0, 1, 0, -1]):
        nx, ny = x+i, y+j
        if nx < 0 or nx >= N or ny < 0 or ny >= N:
            continue
        if visited[nx][ny]:
            continue
        else:
            visited[nx][ny] = True
            D[nx][ny] = min(D[nx][ny], D[x][y]+1)
            queue.append([nx, ny])
# print(*D, sep="\n")
ans = [0 for _ in range(N)]
cnt = 0
for i in range(N):
    for j in range(i+1, N):
        # cnt += 1
        v = D[i][j]
        # print(i,j, v)
        ans[v-1] += 1
print(*ans[:-1], sep="\n")
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
from functools import lru_cache
sys.setrecursionlimit(10**9)
mod = 998244353

def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    @lru_cache(maxsize=None)
    def g(n, S):
        if S < 0: return 0
        if S == 0: return pow(2, n + 1, mod) - 1
        if n == 0 and S == A[0]: return 1
        if n == 0: return 0
        val = (g(n - 1, S) * 2 + g(n - 1, S - A[n])) % mod
        if A[n] == S: val += 1
        #print("g({},{})={}".format(n, S, val))
        return val % mod
    
    print(g(N - 1, S))

    

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
from functools import lru_cache
sys.setrecursionlimit(10**9)
mod = 998244353

def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    """
    再帰の計算式自体は合っていた！
    メモ化再帰とdpで計算量は変わらないはずだが、取りあえずdpで書き直してみる。
    """

    dp = [[0] * (S + 1) for _ in range(N)] # dp[n][s] = (N=n, S=sに対する問題の解)
    dp[0][0] = 1
    for n in range(1, N): dp[n][0] = (dp[n - 1][0] * 2 + 1) % mod
    for s in range(1, S + 1): dp[0][s] = 1 if s == A[0] else 0
    for n in range(1, N):
        for s in range(1, S + 1):
            dp[n][s] = (dp[n - 1][s] * 2 + dp[n - 1][s - A[n]]) if s >= A[n] else dp[n - 1][s] * 2
            if A[n] == s: dp[n][s] += 1
            dp[n][s] %= mod
    print(dp[N - 1][S])

    

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

n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
    print(max(a[:i] + a[i + 1:]))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m = sorted(a, reverse = True)
a_max = m[0]
b = m[1]
for i in range(n):
    if a[i] == a_max:
        print(b)
    else:
        print(a_max)
### BUGGY CODE ###

n,k=map(int,input().split())
c=list(map(int,input().split()))
dp=[0]
if n>1:
    dp.append(abs(c[1]-c[0]))
    for i in range(2,n):
        m=10**9+1
        for j in range(1,min(k+1,n)):
            m=min(m,dp[max(0,i-j)]+abs(c[i]-c[max(0,i-j)]))
        dp.append(m)
print(dp[-1])


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * n
    a[0] = 0
    for i in range(1, n):
        a[i] = min([a[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i)])
    print(a[-1])
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
B=sorted(list(map(int,input().split())),reverse=True)
C=sorted(list(map(int,input().split())),reverse=True)
a=1
b=1
c=1
A.append(-10**11)
B.append(-10**11)
C.append(-10**11)
A.insert(0,-10**11)
B.insert(0,-10**11)
C.insert(0,-10**11)
print(A[a]+B[b]+C[c])

memo=[[[False]*(z+2) for _ in range(y+2)] for _ in range(x+2)]
memo[a][b][c]=True

for _ in range(k-1):
    keepv=0
    for a2 in range(1,x+2):
        for b2 in range(1,y+2):
            for c2 in range(1,z+2):
                if not memo[a2][b2][c2]:
                    if A[a2]+B[b2]+C[c2]>keepv:
                        keepv=A[a2]+B[b2]+C[c2]
                        keepa=a2
                        keepb=b2
                        keepc=c2
    a=keepa
    b=keepb
    c=keepc
    print(A[a]+B[b]+C[c])
    #print(a,b,c)
    #print(memo[2][1][1])
    memo[a][b][c]=True

### FIXED CODE ###

x,y,z,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
AB=[]
for a in A:
    for b in B:
        AB.append(a+b)
AB=sorted(AB,reverse=True)[:k]
ABC=[]
for ab in AB:
    for c in C:
        ABC.append(ab+c)
ABC.sort(reverse=True)
for abc in ABC[:k]:
    print(abc)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

DIV = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))

# ある数の取り得る状態は以下
# (1)部分集合Pに含まれない
# (2)部分集合Pに含まれ、和に使われている
# (3)部分集合Pに含まれ、和に使われていない

# dp[k] = 総和がkになっている場合の数
dp = [0] * (S + 1)
dp[0] = 1

for i in range(N):
  nextline = [0] * (S + 1)
  for k in range(S, -1, -1):
    # (1)部分集合Pに含まれない
    # (3)部分集合Pに含まれ、和に使われていない
    nextline[k] += dp[k] * 2
    nextline[k] %= DIV

    # (2)部分集合Pに含まれ、和に使われている
    if k + A[i] <= S:
      nextline[k + A[i]] += dp[k]
      nextline[k + A[i]] %= DIV
    
  dp = nextline

print(dp[-1])


### FIXED CODE ###

# 解説AC
# Tの部分集合をUとすると
# A[i]番目の項目について、
# (1)Tに選ばれない
# (2)Uに選ばれない
# (3)Uに選ばれる
# の3通りの遷移がある
# (1)(2)の場合も含めて数え上げていく（その場合、和は変わらない）

import sys
readline = sys.stdin.readline

N,S = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 998244353

dp = [0] * (S + 1)
dp[0] = 1
for i in range(N):
  newline = [0] * (S + 1)
  for j in range(len(dp)):
    # 選択肢(1)(2)の場合
    newline[j] += dp[j] * 2
    newline[j] %= DIV
    # 選択肢(3)の場合
    if j + A[i] <= S:
      newline[j + A[i]] += dp[j]
      newline[j + A[i]] %= DIV
  dp = newline

print(dp[S])
### BUGGY CODE ###

count=0
mainasu=0
num=int(input())
An=[int(i) for i in input().split()]

for i in An[0:num]:
    mainasu+=1
    for w in An[mainasu:]:
        if w==i:
            count+=1
        
    if count>=1:
        break
    
if 0==count:
    print("YES")
    
else :
    print("NO")

### FIXED CODE ###

def duplication(lis):
    return len(lis) == len(set(lis)) 

num=int(input())
An=[int(i) for i in input().split()]


if duplication(An) == True:
    print("YES")
    
else :
    print("NO")
### BUGGY CODE ###

import numpy as np
N = int(input())
b = np.sqrt(N)//1.0
while True:
    if N%b != 0:
        b -= 1
    else:
        break
print(int(b+N/b-2))

### FIXED CODE ###


N = int(input())
b = N**0.5//1.0
while True:
    if N%b != 0:
        b -= 1
    else:
        break
print(int(b+N/b-2))
### BUGGY CODE ###

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

def kitai(x):
  p = 1/x
  ex = 0
  for i in range(1, x+1):
    px = p*i
    ex += px
  return ex

mem = {}
isum = 0
keys = (0, 0)
for i in range(n):
  if i+k > n:
    break
  temp = p[i:i+k]
  if sum(temp) > isum:
    isum = sum(temp)
    keys = (i, i+k)

ans = 0
for i in p[keys[0]:keys[1]]:
  if i in mem:
    ans += mem[i]
  else:
    m = kitai(i)
    ans += m
    mem[i] = m
print(ans)

### FIXED CODE ###

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

def kitai(x):
  return (1+int(x))/2

p = list(map(kitai, input().split()))

pre = psum = sum(p[0:k])

for i in range(1, n):
  if i+k > n:
    break
  pre = pre - p[i-1] + p[i+k-1]
  psum = max(psum, pre)

print(psum)
### BUGGY CODE ###

N, Q = map(int, input().split())
So = input()
import re
S = So.replace('AC', '11')
S = re.sub('[A-Z]', '0', S)
Si = list(map(int, S))

for q in range(Q):
    s, e = map(int,input().split())
    si = Si[s-1:e]
    so = So[s-1:e]
    if So[s-1] == 'C':
        si.pop(0)
    if So[e-1] == 'A':
        si.pop()
    #print(si)
    print(sum(si)//2)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

n=int(input())
x=list(map(int,input().split()))
for i in range(n):
    x1=x[:i]
    x2=x[i+1:]
    x1.extend(x2)
    x1.sort()
    print(x1[n//2-1])


### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
y=sorted(x)
for i in range(n):
    if x[i]<=y[n//2-1]:
        print(y[n//2])
    else:
        print(y[n//2-1])
### BUGGY CODE ###

from math import floor
a,b,n = map(int,input().split())
ans = 0
dd = 0
for i in range(n+1):
    y = (floor(a*i/b) - a*floor(i/b))
    if y >= ans:
        dd = 1
        ans = y
    else:
        print(ans)
        exit()
print(ans)

### FIXED CODE ###

from math import floor
a,b,n = map(int,input().split())
ans = 0
if n <= b:
    for i in range(max(0,n-9),n+1):
        ans = max(ans,floor(a*i/b) - a*floor(i/b))
else:
    for i in range(max(0,b-10),min(n,b+10)):
        ans = max(ans,floor(a*i/b) - a*floor(i/b))
print(ans)