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

n,k=map(int,input().split())
s=list(input())
for i in range(k):
	cur,d,p=0,1,str(s)
	while cur>=0 and cur<n:
		if s[cur]=='A':
			s[cur]='B'
			d=-d
			cur+=d
		else:
			s[cur]='A'
			cur+=d
	if str(s)==p:
		break
print(''.join(s))

### FIXED CODE ###

n,k=map(int,input().split())
s=list(input())*3
p=['A' if s[i]=='B' else 'B' for i in range(n)]*3
head,tail=0,n
for i in range(2*n):
	if s[head]=='A':
		s[head],p[head]='B','A'
	else:
		s,p=p,s
		head+=1
		s[tail],p[tail]='A','B'		
		tail+=1
	if i==k-1:
		print(''.join(s[head:tail]))
		break
else:
	if n%2==1 and k%2==1:
		if s[head]=='A':
			s[head],p[head]='B','A'
		else:
			s,p=p,s
			head+=1
			s[tail],p[tail]='A','B'		
			tail+=1
	print(''.join(s[head:tail]))
### BUGGY CODE ###

import math
num_limit = int(input())
s_limit = int(num_limit**0.5)
for i in range(1,num_limit+1):
    xyz_list = []
    xyz_count = 0
    s_limit_1 = int(i ** 0.5)
    j = 0
    k = 0
    l = 0
    for j in range(1,s_limit+1):
        if i <= j**2:
            break
        for k in range(1,j+1):
            if i <= j**2 + k**2 + j*k:
                break
            for l in range(1,k+1):
                if i < j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    break
                elif i == j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    if j == k and k == l:
                        xyz_count += 1
                    elif j == k and k > l or j > k and k == l:
                        xyz_count += 3
                    else:
                        xyz_count += 6
    print(xyz_count)

### FIXED CODE ###

num_limit = int(input())
num_list = [0] * num_limit
j_limit = int(num_limit ** 0.5)
for j in range(1,j_limit+1):
    for k in range(1,j + 1):
        for l in range(1,k+1):
            if num_limit >= j**2 + k**2 + l**2 + j*k + k*l + l*j:
                if j > k:
                    if k > l:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 6
                    else:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                elif k > l:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                else:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 1
for i in num_list:
    print(i)
### BUGGY CODE ###

N,D,A = map(int,input().split())
d = {}
E = []
import math
for i in range(N):
    x,h = map(int,input().split())
    n = math.ceil(h/A)
    d[x] = n
    E.append(x)
E.sort()
F = {}
import bisect
for i in range(N):
    x = E[i]
    y = bisect.bisect_right(E,x+2*D)
    F[i] = y
ans = 0
for i in range(N):
    x = E[i]
    if d[x] <= 0:
        continue
    y = F[i]
    z = d[x]
    ans += z
    for j in range(i,y):
        d[E[j]] -= z 
print(ans)

### FIXED CODE ###

N,D,A = map(int,input().split())
attack_number = {}
Enemy = []
import math
for i in range(N):
    x,h = map(int,input().split())
    n = math.ceil(h/A)
    attack_number[x] = n
    Enemy.append(x)
Enemy.sort()
bomb_number = [0 for i in range(N+1)]
F = {}
import bisect
for i in range(N):
    x = Enemy[i]
    y = bisect.bisect_right(Enemy,x+2*D)
    F[i] = y
ans = 0
for i in range(N):
    if i > 0:
        bomb_number[i] += bomb_number[i-1]
    x = attack_number[Enemy[i]] - bomb_number[i]
    if x <= 0:
        continue
    y = F[i]
    bomb_number[i] += x
    bomb_number[y] -= x
    ans += x
print(ans)
### BUGGY 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)

### 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 ###

n = int(input())
s = [sorted(input()) for _ in range(n)]
x = []
values = []
combs = []
def cmb(h, r):
    if h - r < r: r = h - r
    if r == 0: return 1
    if r == 1: return h
    r = int(r)

    humerator = [h - r + k + 1 for k in range(r)]
    dehominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = dehominator[p - 1]
        if pivot > 1:
            offset = (h - r) % p
            for k in range(p-1,r,p):
                k = int(k)
                offset = int(offset)
                humerator[k - offset] /= pivot
                dehominator[k] /= pivot

    result = 1
    for k in range(r):
        if humerator[k] > 1:
            result *= int(humerator[k])

    return result

for i in s:
  x.append("".join(i))
for i in set(x):
  if x.count(i) > 1:
    values.append(x.count(i))
for i in values:
  combs.append(cmb(i,2))
print(sum(combs))

### FIXED CODE ###

import collections
n = int(input())
s = ["".join(sorted(input())) for _ in range(n)]
#values = []
combs = 0
c = collections.Counter(s)
# このfor文を削減するためにcollections.Counter()を使用
# for i in set(s):
#   if s.count(i) > 1:
#     values.append(s.count(i))
for i in c.values():
  combs+=i*(i-1)//2
print(combs)
### BUGGY CODE ###

import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    is_all_seen = [False]*n
    cnt = 0
    seen = [None]*n
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    def dfs(graph,s,r):
        seen[s] = s+1
        if rks[s] is None:
            rks[s] = r
            
        for i in range(len(graph[s])):
            if seen[graph[s][i]-1]:
                continue
            dfs(graph, graph[s][i]-1,r)

    for i in range(m):
        a,b = map(int, input().split())

        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):
        seen = [None]*n
        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    is_all_seen = [False]*n
    cnt = 0
    seen = [None]*n
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    def dfs(graph,s,r):
        seen[s] = s+1
        if rks[s] is None:
            rks[s] = r

        for i in range(len(graph[s])):
            if seen[graph[s][i]-1]:
                continue
            dfs(graph, graph[s][i]-1,r)

    for i in range(m):
        a,b = map(int, input().split())

        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):

        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

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

import sys
sys.setrecursionlimit(100000000)
n,q= map(int,input().split())
nodes = [[]for _ in range(n+1)]
subnode = [[]for _ in range(n+1)]
value = [0 for _ in range(n+1)]
for i in range(n-1):
    a,b = map(int,sys.stdin.readline().split())
    nodes[a].append(b)
    nodes[b].append(a)
query = []
for i in range(q):
    a, b = map(int, sys.stdin.readline().split())
    query.append([a,b])
def dfs(node,p):
    temp = []
    for v in nodes[node]:
        if v !=p:
            temp= temp+ dfs(v,node)
    my = temp+[node]
    # print(node,my)
    subnode[node]=my
    return my
dfs(1,-1)
for a,b in query:
    for v in subnode[a]:
        value[v]+=b
print(*value[1:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)
n,q= map(int,input().split())
nodes = [[]for _ in range(n+1)]
value = [0 for _ in range(n+1)]
for i in range(n-1):
    a,b = map(int,sys.stdin.readline().split())
    nodes[a].append(b)
    nodes[b].append(a)
query = []
for i in range(q):
    a, b = map(int, sys.stdin.readline().split())
    value[a]+=b
def dfs(node,p,score):
    for v in nodes[node]:
        if v !=p:
            value[v]+=score
            dfs(v,node,value[v])

dfs(1,-1,value[1])
for i in range(1,n+1):
    sys.stdout.write('{} '.format(int(value[i])))
### BUGGY CODE ###

#!/usr/bin/env python
x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
B = list(map(int, input().split()))
B.sort(reverse=True)
C = list(map(int, input().split()))
C.sort(reverse=True)
D = []
E = []
for b in B:
    for c in C:
        D.append(b+c)
D.sort(reverse=True)
for a in A:
    for d in D[:k]:
       E.append(a+d)
E.sort(reverse=True)
for e in E[:k]:
    print(e)

### FIXED CODE ###

#!/usr/bin/env python
import numpy as np
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()))
D = []
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
for i in range(min(K,X)):
    for j in range(min((K//(i+1),Y))):
        for k in range(min(((K//(i+1)+1)//(j+1)),Z)):
            D.append(A[i]+B[j]+C[k])
D.sort(reverse=True)
for i in range(K):
    print(int(D[i]))
### BUGGY CODE ###

s = input()
K = int(input())
# substrings = {}
substrings = []
for i in range(1,len(s)+1):
    for j in range(0,len(s)):
        if s[j:j+i] not in substrings:
            # substrings[s[j:j+1]] = True
            substrings.append(s[j:j+i])
print(sorted(substrings)[K-1])

### FIXED CODE ###

s = input()
K = int(input())
# substrings = {}
substrings = []
for i in range(1,6):
    for j in range(0,len(s)):
        if s[j:j+i] not in substrings:
            # substrings[s[j:j+1]] = True
            substrings.append(s[j:j+i])
print(sorted(substrings)[K-1])
### BUGGY CODE ###

n,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(w+1):
        weight,value=a[i]
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        if j+weight<=w:
            dp[i+1][j+weight]=max(dp[i][j+weight],dp[i][j]+value)
print(dp[-1][-1])

### FIXED CODE ###

n,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(w+1):
        weight,value=a[i]
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        if j+weight<=w:
            dp[i+1][j+weight]=max(dp[i][j+weight],dp[i][j]+value)
print(dp[-1][-1])
### BUGGY CODE ###

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

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
	N,W = map(int, input().split())
	dp = [0 for _ in range(W+1)]
	for _ in range(N):
		w,v = map(int, input().split())
		for i in range(W,0,-1):
			if i>=w:
				a = dp[i]
				b = dp[i-w]+v
				if a>b:
					dp[i] = a
				else:
					dp[i] = b
		
	print(dp[-1])

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

x, y, z, k = map(int, input().split())
aaa = sorted(map(int, input().split()), reverse=True)
bbb = sorted(map(int, input().split()), reverse=True)
ccc = sorted(map(int, input().split()), reverse=True)
ma, mb, mc = aaa[0], bbb[0], ccc[0]
cakes = [(ma - a, 0) for a in aaa[1:]]
cakes += [(mb - b, 1) for b in bbb[1:]]
cakes += [(mc - c, 2) for c in ccc[1:]]
cakes.sort()

buf = [[ma], [mb], [mc]]
ans = [ma + mb + mc]

for d, i in cakes:
    if i == 0:
        a = aaa[len(buf[i])]
        if len(ans) == k and ans[-1] > a + mb + mc:
            break
        buf[i].append(a)
        ans.extend(a + b + c for b in buf[1] for c in buf[2])
        ans.sort(reverse=True)
        ans = ans[:k]
    elif i == 1:
        b = bbb[len(buf[i])]
        if len(ans) == k and ans[-1] > ma + b + mc:
            break
        buf[i].append(b)
        ans.extend(a + b + c for a in buf[0] for c in buf[2])
        ans.sort(reverse=True)
        ans = ans[:k]
    else:
        c = ccc[len(buf[i])]
        if len(ans) == k and ans[-1] > ma + mb + c:
            break
        buf[i].append(c)
        ans.extend(a + b + c for a in buf[0] for b in buf[1])
        ans.sort(reverse=True)
        ans = ans[:k]

print('\n'.join(map(str, ans)))


### FIXED CODE ###

x, y, z, k = map(int, input().split())
aaa = sorted(map(int, input().split()), reverse=True)
bbb = sorted(map(int, input().split()), reverse=True)
ccc = sorted(map(int, input().split()), reverse=True)
ma, mb, mc = aaa[0], bbb[0], ccc[0]
cakes = [(ma - a, 0) for a in aaa[1:]]
cakes += [(mb - b, 1) for b in bbb[1:]]
cakes += [(mc - c, 2) for c in ccc[1:]]
cakes.sort()

buf = [[ma], [mb], [mc]]
ans = [ma + mb + mc]

for d, i in cakes:
    if i == 0:
        a = aaa[len(buf[i])]
        if len(ans) == k and ans[-1] >= a + mb + mc:
            break
        buf[i].append(a)
        ans.extend(a + b + c for b in buf[1] for c in buf[2])
        ans.sort(reverse=True)
        ans = ans[:k]
    elif i == 1:
        b = bbb[len(buf[i])]
        if len(ans) == k and ans[-1] >= ma + b + mc:
            break
        buf[i].append(b)
        ans.extend(a + b + c for a in buf[0] for c in buf[2])
        ans.sort(reverse=True)
        ans = ans[:k]
    else:
        c = ccc[len(buf[i])]
        if len(ans) == k and ans[-1] >= ma + mb + c:
            break
        buf[i].append(c)
        ans.extend(a + b + c for a in buf[0] for b in buf[1])
        ans.sort(reverse=True)
        ans = ans[:k]

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

import fractions

n = int(input())
a = list(map(int, input().split()))
b = []
tmp = a[0]
ans = 0

for i in range(1, n):
    tmp = tmp * a[i] // fractions.gcd(tmp, a[i])

for i in a:
    ans += tmp // i
    b.append(tmp // i)

print(ans % (10 ** 9 + 7))


### FIXED CODE ###

import fractions

n = int(input())
a = list(map(int, input().split()))
tmp = a[0]
ans = 0

for i in range(1, n):
    tmp = tmp * a[i] // fractions.gcd(tmp, a[i])

for i in a:
    ans += tmp // i

print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
l = [2*10**5]
cnt=0

for i in range(n):
  for j in range(i):
    l.append(p[j])
  m = min(l)
  if m>= p[i]:
    cnt+=1 
print(cnt)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
m = 2*10**5
cnt=0
if n == 1:
  print(1)
else:
  for i in range(n-1):
    if m > p[i]:
      m = p[i]
    if m > p[i+1]:
      #print(p[i+1])
      cnt+=1
  print(cnt+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(L, i, pos):
    global goal, LL
    rst = False
    if i == LL:
        rst |= (pos == goal)
    else:
        d = L[i]
        if pos + d not in memo[i]:
            r = dfs(L, i + 1, pos + d)
            memo[i][pos + d] = r
        rst |= memo[i][pos + d]
        if pos - d not in memo[i]:
            r = dfs(L, i + 1, pos - d)
            memo[i][pos - d] = r
        rst |= memo[i][pos - d]
    return rst


S = input().split('T')
x, y = map(int, input().split())

X = []
Y = []
for i, s in enumerate(S):
    if i % 2 == 0:
        X.append(len(s))
    else:
        Y.append(len(s))

if sum(X) < abs(x) or sum(Y) < abs(y):
    print('No')
    exit()


goal, LL = x, len(X)
memo = [{} for _ in range(LL)]
memo[0][X[0]] = True
flag_x = dfs(X, 1, X[0])

goal, LL = y, len(Y)
memo = [{} for _ in range(LL)]
flag_y = dfs(Y, 0, 0)

if flag_x and flag_y:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

S = input().split('T')
x, y = map(int, input().split())

X = []
Y = []
for i, s in enumerate(S):
    if i % 2 == 0:
        X.append(len(s))
    else:
        Y.append(len(s))

if sum(X) < abs(x) or sum(Y) < abs(y):
    print('No')
    exit()

pos = set([X[0]])
for i in range(1, len(X)):
    d = X[i]
    npos = set()
    for p in pos:
        npos.add(p + d)
        npos.add(p - d)
    pos = npos
flag_x = x in pos

pos = set([0])
for i in range(len(Y)):
    d = Y[i]
    npos = set()
    for p in pos:
        npos.add(p + d)
        npos.add(p - d)
    pos = npos
flag_y = y in pos

if flag_x and flag_y:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

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

l_w = []
l_v = []
dp = [[0 for i in range(W + 1)] for j in range(N)]
for i in range(N):
  w, v = map(int, input().split())
  l_w.append(w)
  l_v.append(v)

def knapsack(id, rem_w):
  if rem_w == 0 or id == N:
    return 0
  if dp[id][rem_w] != 0:
    return dp[id][rem_w]
  if l_w[id] > rem_w:
    dp[id][rem_w] = knapsack(id + 1, rem_w)
  elif l_w[id] <= rem_w:
    dp[id][rem_w] = max(knapsack(id + 1, rem_w), l_v[id] + knapsack(id + 1, rem_w - l_w[id]))
  return dp[id][rem_w]
print(knapsack(0, W))


### FIXED CODE ###

def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)


n, cap = map(int, input().split())
print(nap(n, cap))
### BUGGY CODE ###

import math
A, B, N = list(map(int, input().split()))
def floor(t):
    if t == 0 or t == int(t):
        return t
    return math.floor(t)

ans = 0

for i in range(1, N+1):
    val = floor(A*i/B) - A*floor(i/B)
    ans = max(ans, val)

print(ans)

### FIXED CODE ###

import math
A, B, N = list(map(int, input().split()))
ans = 0
if B+1 < N:
    C = B+1
else:
    C = N
if B//A == 0:
    D = 1
elif B//A > 1:
  	D = B//A-1
else:
    D = B//A
for i in range(1, C+1, D):
    val = math.floor(A*i/B) - A*math.floor(i/B)
    #print("i", i, "val", val)
    ans = max(ans, val)

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

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

from itertools import accumulate

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))

clock = [0] + list(accumulate(T))
t_sum = sum(T)
v_li = []
for t in range(2 * t_sum):
    t /= 2
    mn = min(t, t_sum - t)
    for i in range(1, len(clock)):
        if t < clock[i-1]:
            v = V[i-1] + clock[i-1] - t
        elif clock[i-1] <= t <= clock[i]:
            v = V[i-1]
        else:
            v = V[i-1] + t - clock[i]
        mn = min(mn, v)
    v_li.append(mn)

v_li.append(0)

ans = 0
for i in range(1, len(v_li)):
    ans += (v_li[i-1] + v_li[i]) * 0.5 * 0.5

print(ans)


### FIXED CODE ###

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

from itertools import accumulate

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))

clock = [0] + list(accumulate(T))
t_sum = sum(T)
mn_f = 0
ans = 0
for t in range(2 * t_sum):
    t /= 2
    mn = min(t, t_sum - t)
    for i in range(1, len(clock)):
        v = V[i-1]
        if t < clock[i-1]:
            v_max = v + clock[i-1] - t
        elif clock[i-1] <= t <= clock[i]:
            v_max = v
        else:
            v_max = v + t - clock[i]
        mn = min(mn, v_max)
    ans += (mn_f + mn) * 0.25
    mn_f = mn

ans += mn_f * 0.25

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

n = int(input())
n_list = []
for i in range(1 , n+1):
    n_list.append(i)
    if i % 3 == 0 or i % 5 == 0:
        n_list.remove(i)
print(sum(n_list))

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1 , n+1):
    if i % 3 != 0 and i % 5 != 0:
        ans += i
print(ans)
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
h = [0] * (N+K)
for i, j in enumerate([int(i) for i in input().split()]):
    h[i]=j

INF = 10**12

dp = [INF]*200000

dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]))

print(dp[N-1])


### FIXED CODE ###

N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

INF = 10**9

dp = [INF]*100010

dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        if i < N-j: dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]))

print(dp[N-1])
### BUGGY CODE ###

import numpy as np

s = np.array(list(input()), np.unicode)
sl = len(s)
t = np.array(list(input()), np.unicode)
tl = len(t)
equal = (s[:, None] == t[None, :])

dp = np.array([np.zeros(tl + 1, np.int32)])
for i in range(sl):
    tmp = dp[-1].copy()
    np.maximum(tmp[1:], tmp[:-1] + equal[i], out=tmp[1:])
    np.maximum.accumulate(tmp, out=tmp)
    dp = np.append(dp, [tmp], axis=0)

answer = ''
while sl > 0 and tl > 0:
    if s[sl - 1] == t[tl - 1]:
        sl -= 1
        tl -= 1
        answer += s[sl]
        continue

    if dp[sl - 1][tl] > dp[sl][tl - 1]:
        sl -= 1
    else:
        tl -= 1

print(answer[::-1])

### FIXED CODE ###

import numpy as np

s = np.array(list(input()), np.unicode)
sl = len(s)
t = np.array(list(input()), np.unicode)
tl = len(t)
equal = (s[:, None] == t[None, :])

dp = [np.zeros(tl + 1, np.int32)]
for i in range(sl):
    tmp = dp[-1].copy()
    np.maximum(tmp[1:], tmp[:-1] + equal[i], out=tmp[1:])
    np.maximum.accumulate(tmp, out=tmp)
    dp.append(tmp)

answer = ''
while sl > 0 and tl > 0:
    if s[sl - 1] == t[tl - 1]:
        sl -= 1
        tl -= 1
        answer += s[sl]
        continue

    if dp[sl - 1][tl] > dp[sl][tl - 1]:
        sl -= 1
    else:
        tl -= 1

print(answer[::-1])
### BUGGY CODE ###

N,K = [int(i) for i in input().split()]
mod = 998244353
LR = []
S = []
dp = [0]*(N+1)
for i in range(K):
  LR.append([int(i) for i in input().split()])
for lr in LR:
  S.extend(range(lr[0],lr[1]+1))
S.sort()

for i in range(1,N):
  if i in S:
    dp[i] = 1
  for j in range(len(S)):
    if i-S[j] < 1:
      break
    #print(i, S[j], i-S[j])
    dp[i] += 1*dp[i-S[j]]
    dp[i] %= mod

print(dp[-2])

### FIXED CODE ###

N,K = [int(i) for i in input().split()]
mod = 998244353
LR = []
S = []
dp = [0]*(N+1)
dps = [0]*(N+1)
dps[1] = 1
dp[1] = 1
for i in range(K):
  LR.append([int(i) for i in input().split()])

for i in range(1,N+1):
  for l,r in LR:
    l,r = i - r,i - l
    #print(l,r)
    if r < 1:
      continue
    l = max(1,l)
    dp[i] += dps[r] - dps[l-1]
    dp[i] %= mod
    #print(dp[i])
    
  dps[i] = dps[i-1] + dp[i]
  #print(dp, dps)
print(dp[-1])