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

import bisect
import math
N = int(input())
A = list(map(int, input().split()))
T = [2 ** i for i in range(int(math.log2(max(A))) + 1, -1, -1)]

A.sort()
already = set()

def is_in(t):
    i = bisect.bisect_left(A, t)
    if i < len(A):
        while t == A[i]:
            if i not in already:
                already.add(i)
                return i
    return -1

res = 0
for n in range(len(A) - 1, -1, -1):
    if n in already:
        continue

    already.add(n)
    a = A[n]
    T2 = [t - a for t in T if a < t <= 2 * a]
    for t in T2:
        i = is_in(t)
        if i != -1:
            res += 1
            break

print(res)



### FIXED CODE ###

import bisect
import math
N = int(input())
A = list(map(int, input().split()))
T = [2 ** i for i in range(31)]
A.sort()
already = set()


def to_dic(A):
    d = {}
    for a in A:
        d[a] = d.setdefault(a, 0) + 1

    return d

def is_in(t, num):
    i = D.setdefault(t, 0)
    if i == 0:
        return 0
    s = min(i, num)
    D[t] -= s
    return s


res = 0
D = to_dic(A)
A2 = list(D.keys())
A2.sort()

for n in range(len(A2) - 1, -1, -1):
    a = A2[n]

    if a in T:
        res += D[a] // 2
        D[a] = 0

        if D[a] % 2 == 0:
            continue

    num = D[a]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        s = is_in(t - a, num)
        res += s
        num -= s
        if num == 0:
            break

        t >>= 1

print(res)
### BUGGY CODE ###

n=int(input())
segSize=n+1
def init_max(init_max_val):
    for i in range(segSize):
        seg_max[i+num_max-1]=init_max_val[i]
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res
ide_ele_max = 0
num_max =2**(segSize-1).bit_length()
seg_max=[ide_ele_max]*2*num_max
mod=998244353

XD=[tuple(map(int,input().split()))for i in range(n)]
XD.sort()
XD.append((XD[-1][0],10**9))

import bisect

init_max(list(range(segSize)))
update_max(n,n)
combs=[1]*(n+2)
t=0
for x,d in XD[-2::-1]:
    idx=n-1-t
    t+=1
    p=bisect.bisect_right(XD,(x+d-1,10**9+1))
    p=query_max(idx,p)
    update_max(idx,p)
    combs[idx]=(combs[p+1]+combs[idx+1])%mod
print(combs[0])

### FIXED CODE ###

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

n=int(readline())
segSize=n+1
def init_max(init_max_val):
    for i in range(segSize):
        seg_max[i+num_max-1]=init_max_val[i]
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res
ide_ele_max = 0
num_max =2**(segSize-1).bit_length()
seg_max=[ide_ele_max]*2*num_max
mod=998244353

m = map(int,read().split())
XD = sorted(zip(m,m))
X=[x for x,d in XD]

from bisect import bisect_right
X=[bisect_right(X,x+d-1)for x,d in XD]

init_max(list(range(segSize)))
update_max(n,n)
combs=[1]*(n+1)
t=0
for x,d in reversed(XD):
    idx=n-1-t
    t+=1
    p=X[idx]
    p=query_max(idx,p)
    update_max(idx,p)
    combs[idx]=(combs[p+1]+combs[idx+1])%mod
print(combs[0])
### BUGGY CODE ###

import numpy as np

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

maze_x = [input() for _ in range(H)]
maze_y = [''.join(x) for x in zip(*maze_x)]

def count_light(maze, W, H):
    cnt = [[0]*W for _ in range(H)]
    for hh in range(H):
        lst = [i for i in maze[hh].split('#') if i != '']
        ww = 0
        k = 0
        while 0 <= ww <= W - 1:
            if maze[hh][ww] == '.':
                for i in range(len(lst[k])):
                    cnt[hh][ww + i] = len(lst[k])
                ww += i
                k += 1
            ww += 1
    return cnt

cnt_x = np.array(count_light(maze_x, W, H))
cnt_y = np.array(count_light(maze_y, H, W))
cnt = (cnt_y.T + cnt_x - 1).tolist()

print(max(0,max([max(cnt[i]) for i in range(H)])))


### FIXED CODE ###

import numpy as np

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

maze01 = np.array([[int(x=='.') for x in input()] for _ in range(H)]) 

u = np.zeros((H, W), dtype=np.int32)
d = np.zeros((H, W), dtype=np.int32)
r = np.zeros((H, W), dtype=np.int32)
l= np.zeros((H, W), dtype=np.int32)


u[0] = maze01[0]
d[H - 1] = maze01[H - 1]
for hh in range(1,H):
    u[hh] = u[hh-1] + maze01[hh]
    u[hh] *= maze01[hh]
    d[H - hh - 1] = d[H - hh] + maze01[H - hh - 1]
    d[H - hh - 1] *= maze01[H - hh - 1]

l[:, 0] = maze01[:, 0]
r[:, W - 1] = maze01[:, W - 1]
for ww in range(1, W):
    l[:, ww] = l[:, ww -1] + maze01[:, ww]
    l[:, ww] *= maze01[:, ww]
    r[:, W - ww -1] = r[:, W - ww] + maze01[:, W - ww - 1]
    r[:, W - ww -1] *= maze01[:, W - ww - 1]

cnt = r + l + u + d - 3

print(max([max(cnt[i]) for i in range(H)]))
### BUGGY CODE ###

n,m  =map(int,input().split())
lm = []
for _ in range(n):
    lm.append(list(map(int,input().split())))
s = 0
mon = 0
lm.sort(key = lambda x:x[0])
while s < m:
    s += 1
    mon += lm[0][0]
    lm[0][1] -= 1
    if lm[0][1] == 0:
        lm = lm[1::]
print(mon)

### FIXED CODE ###

N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for i in range(N)]
 
AB.sort()
Ans = 0
for i in AB:
  if i[1] >= M:
    Ans += i[0] * M
    break
  else:
    Ans += i[0] * i[1]
    M -= i[1]
 
print(Ans)
### BUGGY CODE ###

n = int(input())
b = list(map(str, input().split()))
''.join(b)
ans = []
def dfs(b):
    if len(b) == 1:
        if int(b[0]) == 1:
            return True
    else:
        f = 0
        for j in range(len(b)):
            if int(b[j]) == j + 1:
                f += 1
            else:
                break
        if f == len(b):
            for j in range(1, len(b)):
                ans.append(b[j])
            return True

        for i in range(len(b) - 1, -1, -1):
            if int(b[i]) == i + 1:
                if i == 0:
                    if dfs(b[1:]):
                        ans.append(i + 1)
                        return True
                else:
                    if dfs(b[:i] + b[i+1:]):
                        ans.append(i + 1)
                        return True
        return False
if dfs(b):
    ans.insert(0, 1)
    for i in range(len(ans)):
        print(ans[i])
else:
    print(-1)


### FIXED CODE ###

n = int(input())
b = list(map(int, input().split()))
ans = []
while(len(b) != 1):
    count = 0
    for i in range(len(b) - 1, -1, -1):
        if b[i] == i + 1:
            b.pop(i)
            ans.append(i + 1)
            count = 0
            break
        else:
            count += 1
    if count == len(b):
        print(-1)
        exit()
if b[0] == 1:
    ans.append(1)
    ans = list(reversed(ans))
    for i in range(len(ans)):
        print(ans[i])
else:
    print(-1)
### BUGGY CODE ###

n,K = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(n)]

ans = 10**20

for i in range(n):
    for j in range(i+1,n):
        if K == 2:
            ans = min(ans,abs(xy[i][0]-xy[j][0])*abs(xy[i][1]-xy[j][1]))
        for k in range(j+1,n):
            if K == 2:
                break
            max_x = max(xy[i][0],xy[j][0],xy[k][0])
            min_x = min(xy[i][0],xy[j][0],xy[k][0])
            max_y = max(xy[i][1],xy[j][1],xy[k][1])
            min_y = min(xy[i][1],xy[j][1],xy[k][1])
            if K == 3:
                #max_x = max(xy[i][0],xy[j][0],xy[k][0])
                #min_x = min(xy[i][0],xy[j][0],xy[k][0])
                #max_y = max(xy[i][1],xy[j][1],xy[k][1])
                #min_y = min(xy[i][1],xy[j][1],xy[k][1])
                ans = min(ans,abs(max_x-min_x)*abs(max_y-min_y))
            for l in range(k+1,n):
                if K == 2 or K == 3:
                    break
                cnt = 0
                max_x = max(max(xy[i][0],xy[j][0],xy[k][0]),xy[l][0])
                min_x = min(min(xy[i][0],xy[j][0],xy[k][0]),xy[l][0])
                max_y = max(max(xy[i][1],xy[j][1],xy[k][1]),xy[l][1])
                min_y = min(min(xy[i][1],xy[j][1],xy[k][1]),xy[l][1])
                for m in range(n):
                    if xy[m][0] >= min_x and xy[m][0] <= max_x\
                       and xy[m][1] >= min_y and xy[m][1] <= max_y:
                           cnt += 1
                if cnt >= K:
                    #print(cnt,K)
                    ans = min(ans,(max_x-min_x)*(max_y-min_y))
                
print(ans)

### FIXED CODE ###

n,K = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(n)]

ans = 10**20

for i in range(n):
    for j in range(i+1,n):
        if K == 2:
            ans = min(ans,abs(xy[i][0]-xy[j][0])*abs(xy[i][1]-xy[j][1]))
        for k in range(j+1,n):
            if K == 2:
                break
            max_x_old = max(xy[i][0],xy[j][0],xy[k][0])
            min_x_old = min(xy[i][0],xy[j][0],xy[k][0])
            max_y_old = max(xy[i][1],xy[j][1],xy[k][1])
            min_y_old = min(xy[i][1],xy[j][1],xy[k][1])
            if K == 3:
                #max_x = max(xy[i][0],xy[j][0],xy[k][0])
                #min_x = min(xy[i][0],xy[j][0],xy[k][0])
                #max_y = max(xy[i][1],xy[j][1],xy[k][1])
                #min_y = min(xy[i][1],xy[j][1],xy[k][1])
                ans = min(ans,abs(max_x_old-min_x_old)*abs(max_y_old-min_y_old))
            for l in range(k+1,n):
                if K == 2 or K == 3:
                    break
                cnt = 0
                max_x = max(max_x_old,xy[l][0])
                min_x = min(min_x_old,xy[l][0])
                max_y = max(max_y_old,xy[l][1])
                min_y = min(min_y_old,xy[l][1])
                for m in range(n):
                    if xy[m][0] >= min_x and xy[m][0] <= max_x\
                       and xy[m][1] >= min_y and xy[m][1] <= max_y:
                           cnt += 1
                if cnt >= K:
                    #print(cnt,K)
                    ans = min(ans,(max_x-min_x)*(max_y-min_y))
                
print(ans)
### BUGGY CODE ###

K=int(input())
S=input()
n=K+len(S)
#ans=comb(n,min(K,len(S)))
com=1
p=1
q=(26**K)%(10**9+7)
ans=0
for i in range(K+1):
  ans+=(p*q*com)%(10**9+7)#comb(len(S)+i-1,len(S)-1))%(10**9+7)
  p=(p*25)%(10**9+7)
  q=(q*576923081)%(10**9+7)
  com=(com*(len(S)+i))//(i+1)
print(ans%(10**9+7))

### FIXED CODE ###

K=int(input())
S=input()
n=K+len(S)
MAX=2000000
fac=[0]*MAX
finv=[0]*MAX
inv=[0]*MAX
MOD=10**9+7
#テーブルを作る前処理
def COMinit():
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,MAX):
      fac[i] = fac[i-1] * i % MOD
      inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
      finv[i] = finv[i - 1] * inv[i] % MOD

#二項係数計算
def comb(n,k):
  if (n < k):
    return 0
  if (n < 0 or k < 0):
    return 0
  else:
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

COMinit()
com=1
q=(26**K)%(10**9+7)
ans=0
for i in range(K+1):
  ans+=(q*comb(len(S)+i-1,i))%(10**9+7)#comb(len(S)+i-1,len(S)-1))%(10**9+7)
  q=(q*423076927)%(10**9+7)
  #com=(com*(len(S)+i))//(i+1)
print(ans%(10**9+7))
#print((25*576923081)%(10**9+7))
### BUGGY CODE ###

import numpy as np
import heapq

INF=10**12
# def daik(s,g,d):
#     used=np.array([])
#     heap=[]
#     table=np.array([INF for i in range(N)])
#     table[s]=0
#     heapq.heappush(heap,(table[s],s))
#     used=np.append(used,s)
                
#     while heap and not(g in used):
#         q=heapq.heappop(heap)
#         a=q[1]
#         used=np.append(used,a)
#         for i in range(N):
#             if not(i in used):
#                 cost=d[a,i] if a<=i else d[i,a]
#                 if cost!=INF:
#                     table[i]=min(table[i],table[a]+cost)
#                     heapq.heappush(heap,(table[i],i))
#     return table[g]

def daik(s,g,d):
    used=np.array([])
    heap=[]
    table=np.array([INF for i in range(N)])
    table[s]=0
    heapq.heappush(heap,(table[s],s))
    used=np.append(used,s)
                
    while heap and not(g in used):
        q=heapq.heappop(heap)
        a=q[1]
        used=np.append(used,a)
        for i in range(N):
            if not(i in used):
                cost=d[a,i] 
                if cost!=INF:
                    table[i]=min(table[i],table[a]+cost)
                    heapq.heappush(heap,(table[i],i))
    return table[g]

N,M=map(int,input().split())
LRC=[]
for i in range(M):
    L,R,C=map(int,input().split())
    LRC.append([L-1,R-1,C])
LRC=np.array(LRC)
LRC=LRC[np.argsort(LRC[:,2])][::-1]

d=np.array([[INF for j in range(N)] for i in range(N)])
# for i in range(N):
#     d[i,i]=0
# l=np.array([i+1 for i in range(N)])
# l[-1]=N
# for m in range(M):
#     L,R,C=LRC[m,0],LRC[m,1],LRC[m,2]
#     for i in range(L,R+1):
#         if l[i]<N:
#             d[i,l[i]:R+1]=C
#             l[i]=R+1
for i in range(N-1):
    d[i+1,i]=0
for i in range(M):
    C=LRC[i,2]
    d[LRC[i,0],LRC[i,1]]=C
    d[LRC[i,1],LRC[i,0]]=C
ans=daik(0,N-1,d)
if ans==INF:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import numpy as np
import heapq

INF=10**15
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append((R,C))
    adj[R].append((L,C))
for i in range(N-1):
    adj[i+1].append((i,0))
    
s=0
g=N-1
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,(table[s],s))
                
while heap:
    q=heapq.heappop(heap)
    a=q[1]
    if q[0]>table[a]: continue
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if table[p]>table[a]+co:
            table[p]=table[a]+co
            heapq.heappush(heap,(table[p],p))
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 標準入力を取得
N = int(input())

# 求解処理
F = [0 for n in range(N + 1)]
for n in range(1, N + 1):
    for i in range(1, N + 1):
        if i % n == 0:
            F[i] += 1
            
ans = sum([n * F[n] for n in range(N + 1)])

# 結果出力
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 標準入力を取得
N = int(input())

def g(N: int) -> int:
    return int(N * (N + 1) / 2)

# 求解処理
ans = 0
for n in range(1, N + 1):
    ans += n * g(N // n)
            
# 結果出力
print(ans)
### BUGGY CODE ###

import math
n= int(input())
s = str(input())
num = len(s)
ans = 0
for i in range(1000):
    t = (3-len(str(i))) * "0" + str(i)
    key1,key2 = 0,0
    num= len(s)
    for j in range(num):
        if s[j] == t[2] and key2:
            ans += 1
            break
        if s[j] == t[1] and key1:
            key2 = 1
        if s[j] == t[0]:
            key1 = 1
print(ans)

### FIXED CODE ###

import math
n= int(input())
s = str(input())
num = len(s)
ans = 0
for i in range(1000):
    t = (3-len(str(i))) * "0" + str(i)
    key1,key2 = 0,0
    num= len(s)
    for j in range(num):
        if s[j] == t[2] and key2:
            ans += 1
            break
        if s[j] == t[1] and key1:
            key2 = 1
        if s[j] == t[0]:
            key1 = 1
print(ans)
### BUGGY CODE ###

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

cnt = 0
for d1 in range(10):
    for d2 in range(10):
        for d3 in range(10):
            find1 = False
            find2 = False
            for i, n in enumerate(L):
                if not find1 and L[i] == d1:
                    find1 = True
                    continue
                if find1 and not find2 and L[i] == d2:
                    find2 = True
                    continue
                if find1 and find2 and L[i] == d3:
                    cnt += 1
                    break
print(cnt)


### FIXED CODE ###

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

cnt = 0
for d1 in range(10):
    for d2 in range(10):
        for d3 in range(10):
            find1 = False
            find2 = False
            for i, n in enumerate(L):
                if not find1 and L[i] == d1:
                    find1 = True
                    continue
                if find1 and not find2 and L[i] == d2:
                    find2 = True
                    continue
                if find1 and find2 and L[i] == d3:
                    cnt += 1
                    break
print(cnt)
### BUGGY CODE ###

import queue
import copy
import math
from collections import deque
import bisect

# 2つの入力を空白で分割し、数値化
n, k = map(int, input().split())

# 空白区切りの数値をリスト化
pn = list(map(int, input().split()))

expects = []

for p in pn:
    e = (((1 + p) * p) // 2) / p
    expects.append(e)

max_e = 0
for i in range(0, n - k + 1):
    tmp = sum(expects[i:i+k])
    max_e = max(max_e, tmp)

print(max_e)




### FIXED CODE ###

import queue
import copy
import math
from collections import deque
import bisect

# 2つの入力を空白で分割し、数値化
n, k = map(int, input().split())

# 空白区切りの数値をリスト化
pn = list(map(int, input().split()))

expects = []
max_e = 0
prev_e = 0

for p, i in zip(pn, range(0, n)):
    e = (((1 + p) * p) // 2) / p
    expects.append(e)
    if i + 1 == k:
        max_e = sum(expects)
        prev_e = max_e
    elif i + 1 > k:
        current_e = prev_e + expects[-1] - expects[i-k]
        max_e = max(max_e, current_e)
        prev_e = current_e
    else:
        continue

print(max_e)
### BUGGY CODE ###

s = input()
q = int(input())
cnt = 0
for _ in range(q):
    t = input()
    if t[0] == '1':
        cnt += 1
    elif t[2] == '1':
        if cnt%2 == 0:
            s = t[4] + s
        else:
            s = s + t[4]
    else:
        if cnt%2 == 0:
            s = s + t[4]
        else:
            s = t[4] + s
if cnt%2 == 1:
    s = s[::-1]
print(s)


### FIXED CODE ###

s = input()
q = int(input())
cnt = 0
front = ''
rear = ''
for _ in range(q):
    t = input()
    if t[0] == '1':
        cnt += 1
    elif t[2] == '1':
        if cnt%2 == 1:
            rear = rear + t[4]
        else:
            front = front + t[4]
    else:
        if cnt%2 == 1:
            front = front + t[4]
        else:
            rear = rear + t[4]
if cnt%2 == 1:
    s = (front[::-1] + s + rear)[::-1]
else:
    s = front[::-1] + s + rear
print(s)
### BUGGY CODE ###

#!/usr/bin/env python3

from itertools import combinations

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

total = sum([x * y for x, y in list(combinations(A, 2))])
result = total % (10**9 + 7)
print(result)


### FIXED CODE ###

#!/usr/bin/env python3


def solve(N, A):
    MOD = 10**9 + 7
    total = sum(A)
    ans = 0

    for i in range(N - 1):
        total -= A[i]
        ans += A[i] * total
        ans %= MOD

    return ans


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

    ans = solve(N, A)

    print(ans)


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

S = list(raw_input())
c = 0
while 'BW' in "".join(S):
    idx = "".join(S).index('BW')
    S[idx] = 'W'
    S[idx + 1] = 'B'
    c += 1

print c


### FIXED CODE ###

S = raw_input()
n = 0
wc = 0
s_pos = 0
for i, c in enumerate(S):
    if c == "W":
        n += 1
        wc += i - s_pos
        s_pos = n

n = 0
bc = 0
s_pos = 0
for i, c in enumerate(reversed(S)):
    if c == "B":
        n += 1
        bc += i - s_pos
        s_pos = n

print max(wc, bc)
### BUGGY CODE ###

h,n = map(int,input().split())
a = []
b = []
for _ in range(n):
  tmp = list(map(int,input().split()))
  a.append(tmp[0])
  b.append(tmp[1])

dp = [[10**9 for _ in range(h+1)] for _ in range(n+1)]

for i in range(n):
  for j in range(h+1):
    if j <= a[i]:
      dp[i+1][j] = min(dp[i][j],b[i])
    else:
      dp[i+1][j] = min(dp[i][j],dp[i+1][j-a[i]]+b[i])

print(dp[n][h])

### FIXED CODE ###

import sys

def dp_all(dp):
  length = len(dp)
  for i in range(length):
    print(dp[i])

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

a = []
b = []

for i in range(N):
  a_dash,b_dash = map(int,input().split())
  a.append(a_dash)
  b.append(b_dash)

#dp[i+1][j] = i番目までの魔法で体力jのモンスターに
#勝つことができる、魔力の最小値
INF = 10**9
dp = [[INF for _ in range(H+1)] for _ in range(N+1)]

for i in range(N+1):
  dp[i][0] = 0

for i in range(N):
  for j in range(H+1):
    if a[i] > j:
      dp[i+1][j] = min(dp[i][j],b[i])
    else:
      dp[i+1][j] = min(dp[i][j],dp[i+1][j-a[i]]+ b[i])

print(dp[N][H])
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q):
    query = input()
    if query == '1':
        s = s[::-1]
    else:
        _, f, c = query.split()
        if f == '1':
            s = c+s
        else:
            s = s+c

print(s)

### FIXED CODE ###

s = input()
q = int(input())

add_s = ['', ''] #pre, post
rev_flag = 0

for i in range(q):
    query = input()
    if query == '1':
        rev_flag = (rev_flag+1)%2
    else:
        _, f, c = query.split()
        if f == '1':
            add_s[rev_flag] += c
        else:
            add_s[(rev_flag+1)%2] += c

if rev_flag == 1:
    s = s[::-1]

print(add_s[rev_flag][::-1]+s+add_s[(rev_flag+1)%2])
### BUGGY CODE ###

import sys


def solve():
    N, K, *H = map(int, sys.stdin.read().split())
    dp = [10**10] * N
    dp[0] = 0
    for i, h in enumerate(H):
        for k in range(1, K+1):
            if i+k > N-1:
                break
            tmp_dp = dp[i] + abs(h - H[i+k])
            if dp[i+k] > tmp_dp:
                dp[i+k] = tmp_dp
    return dp[-1]


if __name__ == "__main__":
    answer = solve()
    print(answer)


### FIXED CODE ###

import sys


def solve():
    N, K, *H = map(int, sys.stdin.read().split())
    dp = [0] * N
    for i in range(1, N):
        s = i-K if i-K > 0 else 0
        dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(s, i))
    return dp[-1]


if __name__ == "__main__":
    answer = solve()
    print(answer)
### BUGGY CODE ###

n=int(input())
l=[int(input()) for _ in range(n)]
c=0
z=[]
i=1
while 1:
    i=l[i-1]
    c+=1
    if i==2:
        break
    if i in z:
        print(-1)
        exit()
    z.append(i)
print(c)


### FIXED CODE ###

n=int(input())
l=[int(input()) for _ in range(n)]
c=0
i=1
while 1:
    if i==2:
        print(c)
        break
    if c>=n:
        print(-1)
        break
    c+=1
    i=l[i-1]
### BUGGY CODE ###

a,b,c,d = input().split()
a,b,c,d = int(a),int(b),int(c),int(d)
ad = []
for num in range(a,b+1):
    if num%c!=0 and num%d!=0:
        ad.append(num)
print(len(ad))

### FIXED CODE ###

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

def lcm(a,b):
    return int(a*b//gcd(a,b))

def div(x,c,d):
    return x - x//c - x//d + x//lcm(c,d)


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

a = div(a-1,c,d)
b = div(b,c,d)
num = b-a

print(num)
### BUGGY CODE ###

mod = 998244353
n = int(input())
a = list(map(int, input().split()))
m = max(a)
cnt = [0]*(m+1)
for ai in a:
    cnt[ai]+=1
ans = 0
res = [0]*(m+1)
for i in range(1, m+1)[::-1]:
    sm = 0
    sq = 0
    for j in range(i, m+1, i):
        sm+=j*cnt[j] 
        sq+=cnt[j]*j*j
        res[i]-=res[j]
    res[i]+=sm*sm-sq
    res[i]%=mod
    ans+=res[i]*pow(i, mod-2, mod)
    ans%=mod
print(ans*(pow(2, mod-2, mod))%mod)






### FIXED CODE ###

mod = 998244353
n = int(input())
a = list(map(int, input().split()))
m = max(a)
cnt = [0]*(m+1)
for ai in a:
    cnt[ai]+=1
ans = 0
res = [0]*(m+1)
for i in range(1, m+1)[::-1]:
    sm = 0
    sq = 0
    for j in range(i, m+1, i):
        sm+=j*cnt[j] 
        sq+=cnt[j]*j*j
        res[i]-=res[j]
    res[i]+=sm*sm-sq
    ans+=res[i]//i
    ans%=mod
print(ans*(pow(2, mod-2, mod))%mod)