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

import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
def main():
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while(e[0] > d):
			if cont == True:
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			else:
				mini = min(kouho)
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
		
def sub():
	V = [list(map(int,inputs().split())) for p in [0]*N]
	M = [int(inputs()) for p in [0]*Q]
	V.sort(key = lambda x:(x[2],x[0],x[1]))
	for v in V:
		v[0] -= v[2]
		v[1] -= v[2] + 1
	for m in M:
		for n in range(N):
			if V[n][0] <=m and m <= V[n][1]:
				print(V[n][2])
				break
		else:
			print(-1)


if N>150000:
	sub()
else:
	main()

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###


from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq


import sys
def input():
	return sys.stdin.readline().strip()


X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

kouho = []
all_set = []
heapq.heappush(kouho, [-(A[0] + B[0] + C[0]), 0, 0, 0])
all_set.append([-(A[0] + B[0] + C[0]), 0, 0, 0])
for i in range(K):
	comb = heapq.heappop(kouho)
	print(-comb[0])
	if comb[1] < X - 1 and not [-(A[comb[1] + 1] + B[comb[2]] + C[comb[3]]), comb[1] + 1, comb[2], comb[3]] in all_set:
		heapq.heappush(kouho,  [-(A[comb[1] + 1] + B[comb[2]] + C[comb[3]]), comb[1] + 1, comb[2], comb[3]])
		all_set.append([-(A[comb[1] + 1] + B[comb[2]] + C[comb[3]]), comb[1] + 1, comb[2], comb[3]])
	if comb[2] < Y - 1 and not [-(A[comb[1]] + B[comb[2] + 1] + C[comb[3]]), comb[1], comb[2] + 1, comb[3]] in all_set:
		heapq.heappush(kouho,  [-(A[comb[1]] + B[comb[2] + 1] + C[comb[3]]), comb[1], comb[2] + 1, comb[3]])
		all_set.append([-(A[comb[1]] + B[comb[2] + 1] + C[comb[3]]), comb[1], comb[2] + 1, comb[3]])
	if comb[3] < Z - 1 and not [-(A[comb[1]] + B[comb[2]] + C[comb[3] + 1]), comb[1], comb[2], comb[3] + 1] in all_set:
		heapq.heappush(kouho,  [-(A[comb[1]] + B[comb[2]] + C[comb[3] + 1]), comb[1], comb[2], comb[3] + 1])
		all_set.append([-(A[comb[1]] + B[comb[2]] + C[comb[3] + 1]), comb[1], comb[2], comb[3] + 1])




### FIXED CODE ###



from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq


import sys
def input():
	return sys.stdin.readline().strip()


X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

kouho = []
all_set = set()
heapq.heappush(kouho, [-(A[0] + B[0] + C[0]), 0, 0, 0])
all_set.add(0)
for i in range(K):
	comb = heapq.heappop(kouho)
	print(-comb[0])
	if comb[1] < X - 1 and not (comb[1] + 1)*Y*Z + comb[2]*Z + comb[3] in all_set:
		heapq.heappush(kouho,  [-(A[comb[1] + 1] + B[comb[2]] + C[comb[3]]), comb[1] + 1, comb[2], comb[3]])
		all_set.add((comb[1] + 1)*Y*Z + comb[2]*Z + comb[3])
	if comb[2] < Y - 1 and not comb[1]*Y*Z + (comb[2] + 1)*Z + comb[3] in all_set:
		heapq.heappush(kouho,  [-(A[comb[1]] + B[comb[2] + 1] + C[comb[3]]), comb[1], comb[2] + 1, comb[3]])
		all_set.add(comb[1]*Y*Z + (comb[2] + 1)*Z + comb[3])
	if comb[3] < Z - 1 and not comb[1]*Y*Z + comb[2]*Z + comb[3] + 1 in all_set:
		heapq.heappush(kouho,  [-(A[comb[1]] + B[comb[2]] + C[comb[3] + 1]), comb[1], comb[2], comb[3] + 1])
		all_set.add(comb[1]*Y*Z + comb[2]*Z + comb[3] + 1)
### BUGGY CODE ###

n = int(input())
A = []
for _ in range(n) :
    A.append(list(map(int, input().split())))

wf = [[A[i][j] for j in range(n)] for i in range(n)]
ans = sum([sum(_A) for _A in A])
for k in range(n) :
    for i in range(n) :
        for j in range(n) :
            if i == k :
                break
            elif j == k :
                continue
            
            d = wf[i][k] + wf[k][j]
            if d == wf[i][j] :
                ans -= d
            elif d < wf[i][j] :
                print(-1)
                exit()

print(ans//2)

### FIXED CODE ###

def main() :
    n = int(input())
    A = [list(map(int, input().split())) for _ in range(n)]

    ans = 0
    for i in range(n) :
        for j in range(i+1, n) :
            cost = A[i][j]
            for k in range(n) :
                if i == k or j == k:
                    continue

                d = A[i][k] + A[k][j]
                if d == A[i][j] :
                    cost = 0
                elif d < A[i][j] :
                    print(-1)
                    exit()
            ans += cost
    print(ans)

main()
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
ans = 0
for i in range(2, N):
    for j in range(N-i):
        if A[j+i] + A[j] == i:
            ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
L = [0] * 2 * N
R = [0] * 2 * N
for i in range(N):
    l = i + A[i]
    if l < N: L[l] += 1
    r = i - A[i]
    if r > 0: R[r] += 1
ans = 0 
for i in range(N):
    ans += L[i] * R[i]
print(ans)
### BUGGY CODE ###

s = input()
n = len(s)

temp = [0]*2019
num = 0
for i in range(n):
    num += int(s[n-i-1])*10**(i)
    temp[num % 2019] += 1

ans = temp[0]
for t in temp:
    if t > 1:
        ans += t*(t-1)/2

print(int(ans))

### FIXED CODE ###

S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)
### BUGGY CODE ###

def G(N,R):
	X=1
	for I in range(R):X=X*(N-I)*F(I+1)%M
	return X
F=lambda X:pow(X,M-2,M);M=10**9+7;H,W,A,B=map(int,input().split());Z=G(H+W-2,H-1)
for I in range(B):C=(C*(H-A+I-1)*F(I)*(W-I)*F(A+W-I-1)if I else G(H-A+I-1,H-A-1)*G(A+W-I-2,A-1))%M;Z-=C
print(Z%M)

### FIXED CODE ###

F=lambda X:pow(X,M-2,M);M=10**9+7;H,W,A,B=map(int,input().split());Z=C=1
for I in range(min(W-1-B,H-1)):Z=C=C*(W+H-B-2-I)*F(I+1)%M
for I in range(1,H-A):C=C*(B-1+I)*F(I)*(H-I)*F(W+H-B-1-I)%M;Z=(Z+C)%M
print(Z)
### BUGGY CODE ###

import numpy as np
import math
n,m = map(int,input().split())
a = list(map(int,input().split()))
SUM =0 
for i in range(m):#チケットの数
	a[np.argmax(a)] /= 2

for i in range(len(a)):
	a[i] = math.floor(a[i])
	SUM += a[i]
print(SUM)


### FIXED CODE ###

import heapq
n,m = map(int,input().split())
a = [int(i) * (-1) for i in input().split()]

heapq.heapify(a)

for _ in range(m):
	a_min = heapq.heappop(a)
	heapq.heappush(a,(-(-a_min//2)))

print(-sum(a))
### BUGGY CODE ###

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

for i in range(n):
    b = A[i] - (i + 1)
    B.append(b)
    
ans = 10 ** 9
    
for b in B:
    Sum = 0
    for i in range(n):
        Sum += abs(A[i] - (b + (i + 1))) 
    ans = min(ans, Sum)
    
print(ans)

### FIXED CODE ###

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

for i in range(n):
    b = A[i] - (i + 1)
    B.append(b)

B.sort()
medianB = B[n // 2]

Sum = 0
for i in range(n):
    Sum += abs(A[i] - (medianB + (i + 1))) 
    
print(Sum)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
p=[]
cnt=[]
zero=0
for i in range(n):
	if a[i]==0:
		zero+=1
	elif a[i] not in p:
		p.append(a[i])
		cnt.append(1)
	else:
		for j in range(len(p)):
			if a[i]==p[j]:
				cnt[j]+=1
if n%3!=0 and zero!=n:
	print("No")
	exit()
if len(p)>=4:
	print("No")
	exit()
if len(p)==3:
	if cnt[0]==cnt[1]==cnt[2]==n/3:
		if p[0]^p[1]^p[2]==0:
			print("Yes")
			exit()
	else:
		print("No")
		exit()
elif len(p)==1:
	if cnt[0]==n/3*2:
		print("Yes")
		exit()
elif len(p)==0:
	if sum(a)==0:
		print("Yes")
		exit()
print("No")

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
p=[]
cnt=[]
zero=0
for i in range(n):
	if len(p)>=4:
		print("No")
		exit()
	if a[i]==0:
		zero+=1
	elif a[i] not in p:
		p.append(a[i])
		cnt.append(1)
	else:
		for j in range(len(p)):
			if a[i]==p[j]:
				cnt[j]+=1
if n%3!=0 and zero!=n:
	print("No")
	exit()
if len(p)>=4:
	print("No")
	exit()
if len(p)==3:
	if cnt[0]==cnt[1]==cnt[2]==n/3:
		if p[0]^p[1]^p[2]==0:
			print("Yes")
			exit()
	else:
		print("No")
		exit()
elif len(p)==1:
	if cnt[0]==n/3*2:
		print("Yes")
		exit()
elif len(p)==0:
	if sum(a)==0:
		print("Yes")
		exit()
print("No")
### BUGGY CODE ###

import bisect,collections,copy,itertools,math,string
def I(): return int(input())
def S(): return input()
def LI(): return list(map(int,input().split()))
def LS(): return list(input().split())
##################################################
N = I()
A = LI()
_123 = [0]*N
_123count = [0]*N
for x in A:
    _123[x-1] += 1
_123copy = copy.copy(_123)
_123copy.sort(reverse=True)
for i,x in enumerate(_123copy):
    if x==0:
        break
    if x==1:
        _123count[i] = 0
    else:
        _123count[i] = math.factorial(x)//((math.factorial(x-2))*(math.factorial(2)))
_sum = sum(_123count)
for x in A:
    temp = _123[x-1]-1
    if temp<=0:
        print(_sum)
    elif temp==1:
        print(_sum-1)
    else:
        tempminus = math.factorial(temp+1)//((math.factorial(temp-1))*(math.factorial(2)))
        tempplus = math.factorial(temp)//((math.factorial(temp-2))*(math.factorial(2)))
        print(_sum-tempminus+tempplus)

### FIXED CODE ###

import bisect,collections,copy,itertools,math,string
def I(): return int(input())
def S(): return input()
def LI(): return list(map(int,input().split()))
def LS(): return list(input().split())
##################################################
N = I()
A = LI()
_123 = [0]*N
_123count = [0]*N
for x in A:
    _123[x-1] += 1
_123copy = copy.copy(_123)
_123copy.sort(reverse=True)
_count = {}
for i,x in enumerate(_123copy):
    if x==0:
        break
    if x==1:
        _123count[i] = 0
    elif i!=0 and _123copy[i]==_123copy[i-1]:
        _123count[i] = _123count[i-1]
    else:
        _123count[i] = math.factorial(x)//((math.factorial(x-2))*(math.factorial(2)))
        _count[x] = _123count[i]
_sum = sum(_123count)
for x in A:
    temp = _123[x-1]-1
    if temp<=0:
        print(_sum)
    elif temp==1:
        print(_sum-1)
    else:
        if (temp+1) in _count:
            tempminus = _count[temp+1]
        else:
            tempminus = math.factorial(temp+1)//((math.factorial(temp-1))*(math.factorial(2)))
            _count[temp+1] = tempminus
        if (temp) in _count:
            tempplus = _count[temp]
        else:
            tempplus = math.factorial(temp)//((math.factorial(temp-2))*(math.factorial(2)))
            _count[temp] = tempplus
        print(_sum-tempminus+tempplus)
### BUGGY CODE ###

N = int(input())
S = [input() for _ in range(N)]

'''
d = {}
for s in S:
  if s not in d:
    d[s] = 0
  d[s] += 1
  
ans = 0
for k, v in d.items():
  for i in range(v):
    for j in range(i+1,v):
      ans += 1
'''
def helper(s):
  d = {}
  for c in s:
    if c not in d:
      d[c] = 0
    d[c] += 1
  return d

ans = 0
for i in range(len(S)):
  s1 = helper(S[i])
  for j in range(i+1,len(S)):
    s2 = helper(S[j])
    if s1 == s2:
      ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = [''.join(sorted(input())) for _ in range(N)]

def helper(s):
  d = {}
  for c in s:
    if c not in d:
      d[c] = 0
    d[c] += 1
  
  return d

def pairs(n):
    return int(n * (n - 1) / 2)

d = {}
for s in S:
  if s not in d:
    d[s] = 0
  d[s] += 1

ans = sum([pairs(v) for v in d.values() if v > 1])
  
print(ans)
### BUGGY CODE ###

def main():
    n, K = map(int, input().split())
    a = list(map(int, input().split()))
    cnt = a.count(n)
    for k in range(min(K, 100)):
        an = [0] * n
        for i in range(n):
            if an[i] < n:
                an[i] += 1
            for j in range(1, a[i]+1):
                if i - j >= 0 and an[i-j] < n:
                    an[i-j] += 1
                    if an[i-j] == n:
                        cnt += 1
                if i + j < n and an[i+j] < n:
                    an[i+j] += 1
                    if an[i+j] == n:
                        cnt += 1
        else:
            a = an
            if cnt == n:
                break
    print(*a)
main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    for _ in range(k):
        imos = [0] * (n + 1)
        for i in range(n):
            imos[max(0, i - a[i])] += 1
            imos[min(n, i + a[i] + 1)] -= 1
        for i in range(1, n):
            imos[i] += imos[i-1]
        imos.pop()
        a = imos
        if min(a) == n:
            break 
    print(*a)
main()
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
count = 0
for i in range(0,N):
    for j in range(0,i+1):
        if P[i] > P[j]:
            break
        if j == i:
            count += 1
print(count)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
count = 0
min = P[0]
for i in range(0,N):
    if P[i] <= min:
        min = P[i]
        count += 1
print(count)
### BUGGY CODE ###

def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = gcd(x, a[i])
    return x

n = int(input())
ans = 0
for a in range(1, n+1):
    for b in range(1, n+1):
        for c in range(1, n+1):
            ans += lcm([a, b, c])
print(ans)

### FIXED CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

n = int(input())
ans = 0
for a in range(1, n+1):
    for b in range(1, n+1):
        for c in range(1, n+1):
            ans += gcd_list([a, b, c])
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    D = list(map(int, input().split()))
    if D[0] != 0:
        print(0)
        exit()
    Dnum = [0 for _ in range(N)]
    for i in D:
        Dnum[i] += 1
    if Dnum[0] != 1:
        print(0)
        exit()
    ans = 1
    num = 0
    for i in range(N-1):
        if num == N:
            break
        else:
            ans *= Dnum[i] ** Dnum[i+1]
    print(ans%998244353)


if __name__ == '__main__': main()

### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline

def main():
    _ = int(input())
    D = list(map(int, input().split()))
    Dnum = Counter(D)
    if D[0] != 0 or Dnum[0] != 1:
        print(0)
        exit()
    ans = 1
    for i in range(1, max(D)+1):
        ans *= Dnum[i] ** Dnum[i+1]
        if ans == 0:
            break
    print(ans%998244353)


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

#D
#入力
S=input()
Q=int(input())
#Query=[]
#for i in range(Q):
#    Query.append(list(input().split()))
    
    
#処理
t=0
b=""
a=""
for j in range(Q):
    i=list(input().split())
    if i[0]=="1":
        t+=1
        c=b
        b=a[::-1]
        a=c[::-1]
    elif i[0]=="2":
        if i[1]=="1":
            b=i[2]+b
        elif i[1]=="2":
            a=a+i[2]
if t%2==0:
    print(b+S+a)
    
else:
    print(b+S[::-1]+a)

### FIXED CODE ###

#D
#入力
S=input()
Q=int(input())
#Query=[]
#for i in range(Q):
#    Query.append(list(input().split()))
    
    
#処理
t=0
b=""
a=""
for j in range(Q):
    i=list(input().split())
    if i[0]=="1":
        t+=1
    elif i[0]=="2":
        if t%2==0:
            if i[1]=="1":
                b=i[2]+b
            elif i[1]=="2":
                a=a+i[2]
        elif t%2==1:
            if i[1]=="1":
                a=a+i[2]
            elif i[1]=="2":
                b=i[2]+b
if t%2==0:
    print(b+S+a)
    
else:
    print(a[::-1]+S[::-1]+b[::-1])
### BUGGY CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

N,M,K = list(map(int,input().split()))
fr = [[] for i in range(N+1)]
bl = [[] for i in range(N+1)] 
      
for _ in range(M):
    a,b = map(int,input().split())
    fr[a].append(b)
    fr[b].append(a)
for _ in range(K):
    c,d = map(int,input().split())
    bl[c].append(d)
    bl[d].append(c)

fl = [-1 for i in range(N+1)]
fl[0] = 0
fl[1] = 1
nxt = 1
dic = {}
while nxt != 0:
    q = collections.deque([nxt])
    
    fl[nxt]=nxt
    cnt = 0
    while q:
        now = q.popleft()
        for f in fr[now]:
            if fl[f] == -1:
                fl[f] = nxt
                cnt +=1
                q.append(f)
    dic[nxt] = cnt
    try:
        nxt = fl.index(-1)
    except:
        nxt = 0

mbf = collections.deque()
for i in range(1,N+1):
    ff = 0
    for j in bl[i]:
        if fl[j] == fl[i]:
            ff -= 1
    
    ff += dic[fl[i]]-len(fr[i])
    mbf.append(ff)
print(*mbf)


### FIXED CODE ###

import sys,collections
input = sys.stdin.readline

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)]

          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    s = set(range(1,N+1))
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            s.discard(now)
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        #try:
            #nxt = fl.index(-1)
        #except:
            #nxt = 0
        if len(s) == 0:
            nxt = 0
        else:
            nxt = s.pop()


    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        mbf.append(ff)
    print(*mbf)

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

N,M,K=map(int, input().split())
'''
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

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

    return result
'''

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


ans=0

for i in range(K+1):
  temp=(M*(M-1)**(N-1-i)*cmb(N-1,i))%998244353
  ans+=temp

print(ans%998244353)

### FIXED CODE ###

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

MOD=998244353

ans=0
temp2=1
#temp4=(M-1)**(N-1)%MOD

def getInvs(n, MOD):
  invs = [1] * (n+1)
  for x in range(2, n+1):
    invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
  return invs

invs = getInvs(max(N+3,M-1), MOD)

Vec=[0]*N
#inv=1
#for i in range(MOD-2):
#  inv*=M-1
#  inv%=MOD

'''
for i in range(K+1):
  if i == 0:
    temp1=M
    temp1*=(M-1)**(N-1)%MOD
    temp1%=MOD
    ans+=temp1*temp2%MOD
    #print(cmb)
  else:
    temp1*=invs[M-1]%MOD
    temp2*=(N-i)*invs[i]
    temp2%=MOD
    ans+=temp1*temp2%MOD
    cmb=cmb*(N-i-1)*i*invs[i]%MOD
    #print(cmb)
'''
for i in range(N):
  if i == 0:
    temp1=M
    Vec[N-i-1]=temp1
  else:
    temp1*=(M-1)*(N-i)
    temp1*=invs[i]
    temp1%=MOD
    Vec[N-i-1]=temp1


ans=sum(Vec[:K+1])

print(ans%MOD)
### BUGGY CODE ###

import math


def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

for k in range(N):
    ans = 0
    a = A[k]
    for i, n in d.items():
        if a == i:
            ans += comb(n-1, 2)
        else:
            ans += comb(n, 2)
    print(ans)


### FIXED CODE ###

import math


def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

b = 0
for n in d.values():
    b += comb(n, 2)

for k in range(N):
    a = A[k]
    print(b - d[a] + 1)
### BUGGY CODE ###

def we_love_abc(S: str)->int:
    ABC = 'ABC'

    dp = [0, 0, 0, 0]
    dp[3] = 1

    for c in reversed(S):
        for j in range(3):
            m1 = 3 if c == '?' else 1
            m2 = 1 if c == '?' or c == ABC[j] else 0
            dp[j] = m1 * dp[j] + m2 * dp[j+1]
        dp[3] = (3 if c == '?' else 1) * dp[3]

    return dp[0] % 1000000007


if __name__ == "__main__":
    S = input()
    ans = we_love_abc(S)
    print(ans)


### FIXED CODE ###

def we_love_abc(S: str)->int:
    ABC = 'ABC'
    MOD = 1000000007

    dp = [0, 0, 0, 0]
    dp[3] = 1

    for c in reversed(S):
        for j in range(3):
            m1 = 3 if c == '?' else 1
            m2 = 1 if c == '?' or c == ABC[j] else 0
            dp[j] = (m1 * dp[j] + m2 * dp[j+1]) % MOD
        dp[3] = (3 if c == '?' else 1) * dp[3]
        dp[3] %= MOD

    return dp[0] % MOD


if __name__ == "__main__":
    S = input()
    ans = we_love_abc(S)
    print(ans)
### BUGGY CODE ###

N= int(input())
A = list(map(int,input().split()))
dict_L = {}
for i in range(-max(A),N+max(A)+1):
    dict_L[i] = 0
for i in range(N):
    dict_L[i+1+A[i]] += 1
cnt = 0
for j in range(N):
    R = j+1-A[j]
    cnt += dict_L[R]
print(cnt)

### FIXED CODE ###

N= int(input())
A = list(map(int,input().split()))
dict_L = {}
for i in range(N):
    if(i+1+A[i] in dict_L.keys()):
        dict_L[i+1+A[i]] += 1
    else:
        dict_L[i+1+A[i]] = 1
cnt = 0
for j in range(N):
    R = j+1-A[j]
    if(R in dict_L.keys()):
        cnt += dict_L[R]
print(cnt)
### BUGGY CODE ###

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

for i in range(n):
    if i % 2 == 0:
        b.append(a[i])
    else:
        b = [a[i]] + b

if n % 2 == 1:
    b.reverse()

print(' '.join(map(str, b)))

### FIXED CODE ###

n = int(input())
a = input().split()

print(' '.join(a[-1::-2] + a[(n % 2)::2]))