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

#心折れた

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return x

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
		return

n = int(input())
x = []
y = []
for i in range(n):
	a, b = map(int, input().split())
	x.append([i, a])
	y.append([i, b])

vx = sorted(x, key=lambda x: x[1])
vy = sorted(y, key=lambda x: x[1])

edges = []

for i in range(n - 1):
	edges.append([vx[i][0], vx[i + 1][0], vx[i + 1][1] - vx[i][1]])
	edges.append([vy[i][0], vy[i + 1][0], vy[i + 1][1] - vy[i][1]])

edges = sorted(edges, key=lambda x: x[2], reverse=True)
#print(edges)

uf = UnionFind(n)

ans = 0

while edges != []:
	e = edges.pop()
	if uf.find(e[0]) != uf.find(e[1]):
		uf.union(e[0], e[1])
		ans += e[2]

print(ans)

### FIXED CODE ###

import heapq
import sys
sys.setrecursionlimit(10 ** 7)

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.count = 0

#	def find(self, x):
#		while self.table[x] >= 0:
#			x = self.table[x]
#		return x

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1

			self.count += 1
			return True
		return False

n = int(input())
x = []
y = []
for i in range(n):
	a, b = map(int, input().split())
	x.append([i, a])
	y.append([i, b])

vx = sorted(x, key=lambda x: x[1])
vy = sorted(y, key=lambda x: x[1])

edges = []
uf = UnionFind(n)

for i in range(n - 1):
	if vx[i][1] == vx[i + 1][1]:
		uf.union(vx[i][0], vx[i + 1][0])
	else:
		heapq.heappush(edges, (vx[i + 1][1] - vx[i][1], vx[i][0], vx[i + 1][0]))

	if vy[i][1] == vy[i + 1][1]:
		uf.union(vy[i][0], vy[i + 1][0])
	else:
		heapq.heappush(edges, (vy[i + 1][1] - vy[i][1], vy[i][0], vy[i + 1][0]))


#edges = sorted(edges, key=lambda x: x[2], reverse=True)
#print(edges)

ans = 0

while edges != []:
	e = heapq.heappop(edges)
	if uf.union(e[1], e[2]):
		ans += e[0]
	if uf.count == n - 1:
		break

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

import bisect
N,K = map(int,input().split())
h_list = []
result = []
for i in range(N):
    bisect.insort(h_list,int(input()))
for i in range(N-K+1):
    result.append(h_list[i+K-1]-h_list[i])
print(min(result))

### FIXED CODE ###

N,K = map(int,input().split())
h_list = [int(input()) for i in range(N)]
h_list.sort()
result = []
print(min([h_list[i+K-1]-h_list[i] for i in range(N-K+1)]))
### BUGGY CODE ###

# coding: utf-8
n=int(input())
A=list(map(int,input().split()))
B=[]
for i in range(n):
    B.append(str(A[i]))
    B=B[::-1]
print(' '.join(B))

### FIXED CODE ###

# coding: utf-8
n=int(input())
A=list(map(int,input().split()))
B=[0]*n
l=n//2
if n%2==0:
    for i in range(n):
        if i%2==0:
            B[l+i]=str(A[i])
            l=l+i
        else:
            B[l-i]=str(A[i])
            l=l-i
else:
    for i in range(n):
        if i%2==0:
            B[l-i]=str(A[i])
            l=l-i
        else:
            B[l+i]=str(A[i])
            l=l+i
print(' '.join(B))
### BUGGY CODE ###

from sys import stdin

N = int(stdin.readline())
A = list(map(int,stdin.readline().split()))
Q = int(stdin.readline())
D = dict()
S = set(A)
sum=0

for y in A:
    sum+=y

for t in S:
    D[t]=A.count(t)

for u in range(0,Q):
    U= list(map(int,stdin.readline().split()))
    SS=S.copy()
    SS.add(U[0])
    if len(SS)==len(S):

        SS.add(U[1])
        if len(SS)==len(S):
            sum+=(D[U[0]])*(U[1]-U[0])

            D[U[1]]+=D[U[0]]
            D[U[0]]=0
        else:
            sum += (D[U[0]]) * (U[1] - U[0])
            D[U[1]]=D[U[0]]
            D[U[0]]=0
        S=SS

    print(sum)

### FIXED CODE ###

from sys import stdin

N = int(stdin.readline())
A = list(map(int,stdin.readline().split()))
A.sort()
Q = int(stdin.readline())
D = dict()
S = set(A)
sum=0
count=0

for y in range(0,N):
    sum+=A[y]
    if y>0 and A[y]!=A[y-1]:
        D[A[y-1]]=count
        count=1
    elif y==0:
        count=1
    else:
        count+=1
    if y==N-1:
        D[A[y]]=count

for u in range(0,Q):
    U= list(map(int,stdin.readline().split()))
    if U[0] in D:
        sum+=(D[U[0]])*(U[1]-U[0])
        if U[1] in D:
            D[U[1]]+=D[U[0]]
        else:
            D[U[1]]=D[U[0]]
        D[U[0]]=0


    print(sum)
### BUGGY CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
f=[int(i) for i in input().split()]

a.sort()
f.sort(reverse=True)

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        sup = int(x/F)
        if sup < A:
            syugyo += A-sup
    if syugyo <= k:
        return True
    return False


left = 0
right = a[-1]*f[0]+1
while left < right-1:
    mid = (left+right)//2
    if score(mid):
        right = mid
    else:
        left = mid
print(left+1 if left != 0 else 0)

### FIXED CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
f=[int(i) for i in input().split()]

# aとfの組み合わせはソートして逆向きが最適
# 帰納法で示す

# チームの成績x→単に成績x,メンバーiの成績→xi

# 0<=x<=a[-1]*f[0]な整数xがあったら
# 成績x以下にすることはできるか？という命題を考える

# gi=int(x/fi)は食べ物iで成績xiを出せる最大値
# 　aiがgiを超えてしまうと成績xi以下は修行しないと出せない
# 　ai<=giならその人の成績はxi以下になる
# なのでmax(ai-gi,0)は成績xi以下であるために必要な修行の回数

# よってsum=Σmax(ai-gi,0)は成績x以下を達成するのに、必要なチーム全体の総修行回数
# したってsum<=Kなら成績x以下にすることができる

# 各整数について命題はFalseかTrueを返す
# その順番は1から順にF...FT...Tとなる
# この一番左のTの整数xが求めたい最小値：チームの成績xの最小値

a.sort()
f.sort(reverse=True)

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        syugyo += max(A-int(x/F),0)
    if syugyo <= k:
        return True
    else:
        return False


left = 0
right = a[-1]*f[0]+1
while left < right-1:
    mid = (left+right)//2
    if score(mid):
        right = mid
    else:
        left = mid
print(left+1 if left != 0 else 0)
    
# 計算量は 1+2logN + N*log(2)N <= N*logN < 3.6 * 10^6 
# ぎりぎりセーフ？
### BUGGY CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
# dp[i][j][k] i番目まで見て和がjとなる総数
# k=0がL,Rが決まっていない、k=1がLだけ決定、k=2がLとRが決定
dp = [[[0] * 3 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(S+1):
        zero = dp[i][j][0]; one = dp[i][j][1]; two = dp[i][j][2]
        dp[i+1][j][0] += zero
        dp[i+1][j][1] += zero + one
        dp[i+1][j][2] += zero + one + two
        if a + j <= S:
            dp[i+1][j+a][1] = zero + one
            dp[i+1][j+a][2] = zero + one
            dp[i+1][j+a][1] %= MOD

answer = dp[N][S][2] % MOD
print(answer)
# 11


### FIXED CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
dp = [0] * (S+1)
answer = 0
for a in A:
    dp[0] += 1 # Lの数は１個ずつ加わる
    prev = dp.copy()
    for i in range(S-a+1):
        dp[i+a] += prev[i]
    answer += dp[-1] # その位置Rとした時

print(answer % MOD)
# 26
### BUGGY CODE ###

# match matching
import bisect
compare=[10**i for i in range(5*10**3+1)]
N, M = map(int, input().split())
ok = list(map(int, input().split()))
ok.sort()
a = [i for i in range(1, 10)]
b = [2, 5, 5, 4, 5, 6, 3, 7, 6]

data = {a[i]: b[i] for i in range(9)}

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


def find(X):
    return bisect.bisect_right(compare,X)


def main():
    for i in range(M):
        for cnt in range(N+1):
            for j in range(M):
                num = ok[j]
                cost = data[num]
                if cnt > cost:
                    K=dp[i+1][cnt-cost]
                    if K > 0:
                        dp[i+1][cnt] = max(K + num*10 ** find(K), dp[i+1][cnt])
                    else:
                        dp[i+1][cnt]=max(K, dp[i+1][cnt])
                elif cnt == cost:
                    dp[i+1][cnt]=max(num, dp[i+1][cnt])
                else:
                    dp[i+1][cnt]=max(dp[i][cnt], dp[i+1][cnt])
    ans=dp[M][N]
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

matches = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

n, m = map(int, input().split())
alist = list(map(int, input().split()))
alist.sort(reverse=True)

dp = [-1 for _ in range(n + 1)]
dp[0] = 0
for a in alist:
    match = matches[a]
    for i in range(n - match + 1):
        if dp[i] == -1: continue
        dp[i + match] = max(dp[i + match], dp[i] * 10 + a)

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

X,K,D = map(int,input().split())
dp = [[0]*2 for i in range(K+1)]
dp[0][0] = X
dp[0][1] = X

for i in range(1,K+1):
    dp[i][0] = min(abs(dp[i-1][0] - D),abs(dp[i-1][1] - D))
    dp[i][1] = min(abs(dp[i-1][0] + D),abs(dp[i-1][1] + D))
    
print(min(dp[-1]))

### FIXED CODE ###

X,K,D = map(int,input().split())
X =abs(X)
if X == 0:
    if K % 2 == 0:
        ans = 0
    else:
        ans = D
else:
    cnt = X//D
    if cnt >= K:
        ans = X - (D*K)
    else:
        K -= cnt
        if K % 2 == 0:
            ans = X - (D*cnt)
        else:
            ans = D -(X - (D*cnt))
    
print(ans)
### BUGGY CODE ###

from functools import lru_cache

N, K = map(int, input().split())
P = list(map(int, input().split()))


@lru_cache(maxsize=None)
def calc_exp(n: int):
    return (n + 1) / 2


len_sum = -1
max_len = None
for i in range(N):
    if len(P[i:i + K]) == K:
        l = sum(P[i:i + K])
        if l > len_sum:
            max_len = P[i:i + K]
            len_sum = sum(max_len)

print(sum(map(calc_exp, max_len)))


### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
P = list(map(lambda x: (x + 1) / 2, P))

s = sum(P[:K])
ans = [s]
for prev_a, next_a in zip(P, P[K:]):
    s -= prev_a
    s += next_a
    ans.append(s)
print(max(ans))
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n = ni()
s = input()
dp = [[0] * 5005 for _ in range(5005)]
for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if s[i] != s[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(n):
    for j in range(n):
        if i >= j: continue
        now = min(dp[i][j], j-i)
        ans = max(ans, now)
print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n = ni()
s = input()
dp = [[0] * 5005 for _ in range(5005)]
for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if s[i] != s[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(n):
    for j in range(n):
        if i >= j: continue
        now = min(dp[i][j], j-i)
        ans = max(ans, now)
print(ans)
### BUGGY CODE ###

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

score = [[0 for x in range(K+1)] for y in range(K+1)]
base_hope = 0

for i in range(N):
    x, y, c = input().split()
    x2, y2 = int(x) // K, int(y) // K
    x_coord, y_coord = int(x) % K + 1, int(y) % K + 1
    if ((x2 + y2) % 2 == 0 and c == "W") or ((x2 + y2) % 2 == 1 and c == "B"):
        score[y_coord][x_coord] += 1
        base_hope += 1
    else:
        score[y_coord][x_coord] -= 1

xy = [(x, y) for x in range(K) for y in range(K)]
for x, y in xy:
    score[y+1][x+1] += score[y+1][x] + score[y][x+1] - score[y][x]

max_hope = 0
for x, y in xy:
    hope = base_hope - score[K][x] - score[y][K] + 2 * score[y][x]
    true_hope = max(hope, N - hope)
    if true_hope > max_hope:
        max_hope = true_hope

print(max_hope)

### FIXED CODE ###

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

score = [[0] * (K+1) for y in range(K+1)]
base_hope = 0

for i in range(N):
    x, y, c = input().split()
    x2, y2 = int(x) // K, int(y) // K
    x_coord, y_coord = int(x) % K + 1, int(y) % K + 1
    if ((x2 + y2) % 2 == 0 and c == "W") or ((x2 + y2) % 2 == 1 and c == "B"):
        score[y_coord][x_coord] += 1
        base_hope += 1
    else:
        score[y_coord][x_coord] -= 1

xy = [(x, y) for x in range(K) for y in range(K)]
for x, y in xy:
    score[y+1][x+1] += score[y+1][x] + score[y][x+1] - score[y][x]

max_hope = 0
for x, y in xy:
    hope = base_hope - score[K][x] - score[y][K] + 2 * score[y][x]
    true_hope = hope if hope > N - hope else N - hope
    if true_hope > max_hope:
        max_hope = true_hope

print(max_hope)
### BUGGY CODE ###

N,K,Q=map(int,input().split())
a = [int(input()) for i in range(Q)]
for i in range(N):
  if a.count(i+1)>=Q-K+1:
    print("Yes")
  else:
    print("No")


### FIXED CODE ###

N,K,Q=map(int,input().split())
a = [int(input()) for i in range(Q)]
point=[0 for i in range(N)]
for i in range(Q):
  point[a[i]-1]=point[a[i]-1]+1
for j in range(N):
  if point[j]>=Q-K+1:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

n=int(input())
llist=list(map(int,input().split()))
llist.sort()

counter=0
for i in range(2,n):

	for j in range(1,i):
		now=i+1
		while now <= n:
			if llist[j-1] + llist[i-1] > llist[now-1]:
				counter += 1
				now += 1
			else:
				now += n
			

print(counter)





### FIXED CODE ###

n=int(input())
llist=list(map(int,input().split()))
llist.sort()

counter=0
for i in range(2,n):
	now=i+1
	tmpcounter=0
	for j in range(1,i):
		while now <= n:
			if llist[j-1] + llist[i-1] > llist[now-1]:
				tmpcounter += 1
				now += 1
			else:
				break
		counter += tmpcounter

print(counter)
### BUGGY CODE ###

r=10000000
sqrt=int(r**0.5)
p=[1]*r
p[0]=0
p[3::2]=[0 for i in xrange(3,r,2)]
for i in xrange(2,sqrt,2):
	if p[i]:
		p[2*i+1::i+1]=[0 for x in range(2*i+1,r,i+1)]

while 1:
	n=input()
	if n==0:break
	for i in xrange(n-1,11,-1):
		if p[i] and p[i-2] and p[i-4] and p[i-6]:
			print i+1
			break

### FIXED CODE ###

ref = [[[10,8],[4,4]],[[10,2],[4,2]]]
r =10000001
p = [1]*r
p[0]= p[1] = 0
for i in range(int(r**0.5)):
	if p[i]:
		p[2*i::i] = [0]*len(p[2*i::i])
		
while 1:
	try:
		n = input()
		if n == 0: break
		n -= 1-n%2
		while any(not p[n-i] for i in [0,2,6,8]):
			n -= ref[p[n-2]][p[n-6]][p[n-8]]
		print n
	except:
		pass
### BUGGY CODE ###

def main():
    n =int( input())
    sn=[]

    for i in range(n):
        inWord = str(input())
        addFlag = True
        for s in sn:
            if s["word"] == inWord and len(sn) !=0:
                s["count"]+=1
                addFlag = False
                break
        if addFlag ==True:
            sn.append( {"word":inWord,"count":1})
    
    a= sorted(sn, reverse=True,key=lambda x:x['count'])

    most = int(a[0]["count"])
    mostWords=[]
    for elm in a:
        if elm["count"] == most:
            mostWords.append(elm["word"])
    mostWords.sort()

    for elm in mostWords:
        print(elm)
    return
main()



### FIXED CODE ###

def main():
    n =int( input())

    cnt=dict()
    
    for _ in range(n):
        s=input()
        if s in cnt:
            cnt[s]+=1
        else :
            cnt[s]=1
    #print(cnt)
    
    num = 0
    res =[]
    for key,value in cnt.items():
        #print(key,":::",value)
        if value > num:
            num=value
            res=[]
            res.append(key)

        elif value==num:
            res.append(key)

    #print("res::",res)

    
    #a = [k for k, v in cnt.items() if v == max(cnt.values())]


    #print("結果発表：：：：",len(res))
    res.sort()
    for elm in res:
        print(elm)


main()
### BUGGY CODE ###

n,k,*t=map(int,open(0).read().split())
c,e=k,[0]*-~n
for v in t:
 e[v]+=1
 if(v>1)-e[v]:c*=k-e[v]
print(c%(10**9+7))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def dfs(v,c):
  for i,w in enumerate(e[v]):
    e[w].discard(v)
    c=c*dfs(w,k-i+~(v>0))%(10**9+7)
  return c
n,k,*t=map(int,open(0).read().split())
e=eval('set(),'*n)
for a,b in zip(t[::2],t[1::2]):
  e[a-1].add(b-1)
  e[b-1].add(a-1)
print(dfs(0,k))
### BUGGY CODE ###

import copy
n = int(input())
a = [int(input()) for i in range(n)]
pre_max = max(a)

for i in range(n):
  copy_a = copy.copy(a)
  tmp = copy_a.pop(i)
  if pre_max != tmp:
    print(pre_max)
  else:
    this_max = max(copy_a)
    print(this_max)
    pre_max = this_max
  
  

### FIXED CODE ###

import copy
n = int(input())
a = [int(input()) for i in range(n)]
sorted_a = sorted(a, reverse=True)
n1 = sorted_a[0]
n2 = sorted_a[1]
if(n1 == n2):
  for i in range(n):
    print(n1)
else:
  for i in range(n):
    if a[i] == n1:
      print(n2)
    else:
      print(n1)
### BUGGY CODE ###

from collections import deque, Counter
n, x, y = map(int, input().split())
edge = [[] for i in range(n)]

for i in range(n-1):
    edge[i].append(i+1)
    edge[i+1].append(i)
edge[x-1].append(y-1)
edge[y-1].append(x-1)

def bfs(i):
    dq = deque([i])
    dist = [-1]*n
    dist[i] = 0
    while dq:
        now = dq.popleft()
        d = dist[now]
        for e in edge[now]:
            if dist[e]==-1:
                dist[e] = d + 1
                dq.append(e)
    return dist

c = Counter()
for i in range(n):
    c = c + Counter(bfs(i))

for i in range(1, n):
    print(c[i]//2)


### FIXED CODE ###

from collections import deque, Counter
n, x, y = map(int, input().split())
edge = [[] for i in range(n)]

for i in range(n-1):
    edge[i].append(i+1)
    edge[i+1].append(i)
edge[x-1].append(y-1)
edge[y-1].append(x-1)

def bfs(i):
    dq = deque([i])
    dist = [-1]*n
    dist[i] = 0
    while dq:
        now = dq.popleft()
        d = dist[now]
        for e in edge[now]:
            if dist[e]==-1:
                dist[e] = d + 1
                dq.append(e)
    return dist

c = Counter()
for i in range(n):
    c = c + Counter(bfs(i))

for i in range(1, n):
    print(c[i]//2)
### BUGGY CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))




    n = 10 ** 6
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    prime_list = [i for i in range(n + 1) if is_prime[i]]




    lcm_dic = {}
    Alist = []

    for a in A:
        a_dic = {}
        for num in prime_list:
            if num > a ** 0.5 + 1:
                if a in a_dic:
                    a_dic[a] += 1
                    break
                else:
                    a_dic[a] = 1
                    break
            while a % num == 0:
                if num in a_dic:
                    a //= num
                    a_dic[num] += 1
                else:
                    a //= num
                    a_dic[num] = 1
        Alist.append(a_dic)
        for k, v in a_dic.items():
            if k not in lcm_dic:
                lcm_dic[k] = v
            else:
                lcm_dic[k] = max(lcm_dic[k], v)

    ans = 0
    for ad in Alist:
        tmpnum = 1
        for k, v in lcm_dic.items():
            if k in ad:
                tmpnum *= pow(k, (v - ad[k]), mod)
            else:
                tmpnum *= pow(k, v, mod)
        ans += tmpnum
        ans %= mod
    print(ans)




if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    lcmnum = 1
    def gcd(a, b):
        if (a == 0):
            return b
        return gcd(b%a, a)

    def lcm(x, y):
        return (x * y) // gcd(x, y)
    for a in A:
        lcmnum = lcm(lcmnum, a)

    ans = 0
    for a in A:
        a = lcmnum // a
        ans += a
    ans %= mod

    print(ans)




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


[a,b] = list(map(int,input().split()))

tou = []
dam=0
for i in range(1,1000):
    dam +=i
    tou.append(dam)
# print(tou[-1])

for ans in range(1,5000000):
    west, east = a+ans, b+ans
    for j in range(998):
        if west==tou[j] and east==tou[j+1]:
            # print("west,wast,j,ans", west,east,j,ans)
            out=ans
            break
print(out)

### FIXED CODE ###


[a,b] = list(map(int,input().split()))

tou = []
dam=0
for i in range(1,1000):
    dam +=i
    tou.append(dam)
# print(tou)

X = b-a
print(tou[X-1] - b)
### BUGGY CODE ###

#!/usr/bin/env python3

(R, C, K), *D = [[*map(int,o.split())] for o in open(0)]
D = {(r - 1, c - 1) : v for r, c, v in D}

dp = [[[-1] * 4 for _ in [None] * C] for _ in [None] * R]

dp[0][0][0] = 0
for r in range(R):
    for c in range(C):
        v = D.get((r, c), None)
        for i in range(4):
            if dp[r][c][i] > -1:
                if r < R - 1:
                    dp[r + 1][c][0] = max(dp[r + 1][c][0], dp[r][c][i])
                if c < C - 1:
                    dp[r][c + 1][i] = max(dp[r][c + 1][i], dp[r][c][i])
                if i < 3 and v:
                    if r < R - 1:
                        dp[r + 1][c][0] = max(dp[r + 1][c][0], dp[r][c][i] + v)
                    if c < C - 1:
                        dp[r][c + 1][i + 1] = max(dp[r][c + 1][i + 1], dp[r][c][i] + v)

v = D.get((R - 1, C - 1), 0)
for i in range(3):
    dp[R - 1][C - 1][i] += v
print(max(dp[R - 1][C - 1]))

### FIXED CODE ###

import sys

def solve():
    input = sys.stdin.readline
    R, C, K = map(int, input().split())
    item = [[0 for _ in range(C)] for r in range(R)]
    for _ in range(K):
        r, c, k = map(int, input().split())
        item[r-1][c-1] = k
    
    DP = [[[-1 for _ in range(C)] for r in range(R)] for i in range(4)]
    DP[0][0][0] = 0
    for r in range(R):
        for c in range(C):
            for i in range(4):
                if DP[i][r][c] > -1:
                    if r + 1 < R: 
                        DP[0][r+1][c] = max(DP[0][r+1][c], DP[i][r][c])
                    if c + 1 < C: 
                        DP[i][r][c+1] = max(DP[i][r][c+1], DP[i][r][c])
                    if i < 3 and item[r][c] > 0:
                        if r + 1 < R: DP[0][r+1][c] = max(DP[0][r+1][c], DP[i][r][c] + item[r][c])
                        if c + 1 < C: DP[i+1][r][c+1] = max(DP[i+1][r][c+1], DP[i][r][c] + item[r][c])

    ans = DP[3][R-1][C-1]
    for i in range(3): ans = max(ans, DP[i][R-1][C-1] + item[R-1][C-1])
    print(ans)
    return 0

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

n,a,b,k = map(int,input().split())
mod = 998244353

fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,n+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

def nPr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[n-r]%mod

ans = 0
for i in range(n+1):
    d = k-a*i
    if d < 0:
        break
    if d%b:
        continue
    x = d//b
    v = nCr(n,i,mod)
    for j in range(x+1):
        if i+j > n:
            break
        ans += v*nCr(i,x-j,mod)%mod*nCr(n-i,j,mod)%mod
        ans %= mod
print(ans)

### FIXED CODE ###

n,a,b,k = map(int,input().split())
mod = 998244353

fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,n+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

def nPr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[n-r]%mod


ans = 0
for i in range(n+1):
    if i*a > k:
        break
    d = k-i*a
    if d%b or d//b > n:
        continue
    ans += nCr(n,i,mod)*nCr(n,d//b,mod)%mod
    ans %= mod
print(ans)