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

import bisect

s = list(input())
t = list(input())

# 辞書を作る
dictionary = {}

tt = t[:]
ss = s * 2

while len(tt):
    _t = tt.pop(0)
    if _t not in ss:
        print(-1)
        exit(0)
    indexes = [i for i, x in enumerate(ss) if x == _t]
    if _t not in dictionary:
        dictionary[_t] = indexes
    else:
        dictionary[_t].extend(indexes)

result = 0
before = 0
sLen = len(s)
while len(t) > 0:
    _t = t.pop(0)
    next = dictionary[_t][bisect.bisect_left(dictionary[_t], before)] + 1
    result += next - before
    before = next
    if next >= sLen:
        before -= sLen

print(result)




### FIXED CODE ###

import bisect

s = list(input())
t = list(input())

# 辞書を作る
dictionary = {}

tt = t[:]
ss = dict(zip(list(range(len(s * 2))), s * 2))

for i in range(len(ss)):
    c = ss[i]
    if c not in dictionary:
        dictionary[c] = []
    dictionary[c].append(i)

result = 0
current_idx = 0
sLen = len(s)

for c in t:
    if c not in dictionary:
        print(-1)
        exit(0)
    indexes = dictionary[c]
    next = dictionary[c][bisect.bisect_left(indexes, current_idx)] + 1
    result += next - current_idx
    current_idx = next
    if next >= sLen:
        current_idx -= sLen

print(result)
### BUGGY CODE ###

from bisect import*
r=range
n,*t=map(int,open(0).read().split())
m=2**17
x=t[:n]
d=[[bisect(x,y+t[n])-1for y in x]]+[[0]*n for _ in r(m)]
for i in r(m):
  for j in r(n):
    d[i+1][j]=d[i][d[i][j]]
for a in zip(t[n+2::2],t[n+3::2]):
  a,b=sorted(i-1for i in a)
  c=1
  for i in r(m,-1,-1):
    if d[i][a]<b:
      a=d[i][a]
      c+=2**i
  print(c)

### FIXED CODE ###

from math import*
from bisect import*
n,*t=map(int,open(0).read().split())
m=int(log2(n))+1
x=t[:n]
l=t[n]
d=[[bisect(x,y+l)-1for y in x]]+[[0]*n for _ in range(m)]
for i in range(m):
    for j in range(n):
        d[i+1][j]=d[i][d[i][j]]
for a,b in zip(t[n+2::2],t[n+3::2]):
    a-=1
    b-=1
    if b<a:a,b=b,a
    c=1
    for i in range(m,-1,-1):
        if d[i][a]<b:
            a=d[i][a]
            c+=2**i
    print(c)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

b = sorted(a, reverse=True)
for x in a:
   if x == max(a):
      print(b[1])
   else:
      print(b[0])


### FIXED CODE ###

n = int(input())
A = [int(input()) for x in range(n)]

right = [0]
left = [0]

for a in A:
   left.append(max(a, left[-1]))

for a in reversed(A):
   right.append(max(a, right[-1]))

for i in range(n):
   print(max(left[i], right[n-i-1]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
	
def main():
	N, M, Q = map(int, input().split(" "))
	
	LR = []
	for _ in range(M):
		l, r = map(int, input().split(" "))
		LR.append((l, r))
		
	LRs = []
	for i in LR:
		l, r = i
		l -= 1
		tmp = [0 for i in range(N)]
		for i in range(l, r):
			tmp[i] = 1
		for i in range(r, N):
			tmp[i] = 2
		LRs.append(tmp)
		
	ans = []
	for _ in range(Q):
		p, q = map(int, input().split(" "))
		p -= 1
		q -= 1
		tmp = 0
		for val in LRs:
			if val[p] < 1 and val[q] > 1:
				tmp += 1
			elif (p == 0 or val[p-1] == 0) and (q == N-1 or val[q+1] == 2):
				tmp += 1	
		ans.append(tmp)
			
	for i in ans:
		print(i)
	#print(LRs)
	
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np

def main():
	N, M, Q = map(int, input().split(" "))
	N_list = [[0 for _ in range(N)] for _ in range(N)]
	
	for _ in range(M):
		l, r = map(int, input().split(" "))
		l -= 1
		r -= 1
		N_list[l][r] += 1
		
	#print(N_list)
	
	for i in range(N):
		for j in range(N):
			if i == 0 and j == 0:
				continue
			if i == 0:
				N_list[i][j] = N_list[i][j] + N_list[i][j-1]
				continue
			if j == 0:
				N_list[i][j] = N_list[i][j] + N_list[i-1][j]
				continue
			N_list[i][j] = N_list[i][j] + N_list[i-1][j] + N_list[i][j-1] - N_list[i-1][j-1]
			
	#print(N_list)
		
	for _ in range(Q):
		p, q = map(int, input().split(" "))
		p -= 1
		q -= 1
		
		a = 0
		b = 0
		c = 0
		if p != 0:
			a = N_list[q][p-1]
			b = N_list[p-1][q]
			c = N_list[p-1][p-1]
		ans = N_list[q][q] - a - b + c
		print(ans)
		
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

n = int(input())
h = list(map(int,input().split()))
count = 0
done = False
while done == False:
    start = 0
    for i in range(n):
        if i > 0 and h[i-1] >= 0 and h[i] <= 0:
            count += 1
        elif i == n-1 and h[i] > 0:
            count += 1
        h[i] -= 1
    if max(h) == 0:
        done = True
print(count)


### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
count = 0
done = False
while done == False:
    for i in range(n):
        if h[i] >= 0:
            h[i] -= 1
        
        if i > 0 and h[i] < 0 and h[i-1] >= 0:
            count += 1

        if i == n-1 and h[i] >= 0:
            count += 1
    if max(h) <= 0:
        done = True
print(count)
### BUGGY CODE ###

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

for _ in range(K):
    S = [0] * (N + 1)
    for i, a in enumerate(A):
        l = min(N-1, max(0, i-a))
        r = min(N-1, i+a)
        S[l] += 1
        S[r+1] -= 1
    t = 0
    for i in range(N):
        t += S[i]
        A[i] = t
    if sum(A) == N**2:
        break
print(*A)

### FIXED CODE ###

from itertools import accumulate
N, K = map(int, input().split())
A = [int(i) for i in input().split()]

for _ in range(K):
    S = [0] * (N + 1)
    for i, a in enumerate(A):
        l = min(N-1, max(0, i-a))
        r = min(N-1, i+a)
        S[l] += 1
        S[r+1] -= 1
    A = list(accumulate(S))[:-1]
    if all([a == N for a in A]):
        break
print(*A)
### BUGGY CODE ###

import sys
mod=10**9+7
input=sys.stdin.buffer.readline
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[ [0 for _ in range(m)] for _ in range(n)]
for i in range(0,n):
    for j in range(0,m):
        ret=0
        if i-1>=0:
            ret+=dp[i-1][j]
        if j-1>=0:
            ret+=dp[i][j-1]
        if i-1>=0 and j-1>=0:
            ret-=dp[i-1][j-1]
        if s[i]==t[j]:
            ret+=1
            if i-1>=0 and j-1>=0:
                ret+=dp[i-1][j-1]
        if ret>=mod:
            ret%=mod
        if ret<0:
            ret+=mod
        dp[i][j]=ret
print((dp[n-1][m-1]+1))



### FIXED CODE ###

import sys
mod=10**9+7
input=sys.stdin.buffer.readline
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[ [0 for _ in range(m)] for _ in range(n)]
for i in range(0,n):
    for j in range(0,m):
        ret=0
        if i-1>=0:
            ret+=dp[i-1][j]
        if j-1>=0:
            ret+=dp[i][j-1]
        if i-1>=0 and j-1>=0:
            ret-=dp[i-1][j-1]
        if s[i]==t[j]:
            ret+=1
            if i-1>=0 and j-1>=0:
                ret+=dp[i-1][j-1]
        if ret>=mod:
            ret%=mod
        if ret<0:
            ret+=mod
        dp[i][j]=ret
print((dp[n-1][m-1]+1))
### BUGGY CODE ###

import copy

data = input().split()
N = int(data[0])
K = int(data[1])

TL = input()
TL = list(TL)
TLlist = []
now = TL[0]
nowlist = now

for lop in range(1,len(TL)):
    if not (now == TL[lop]):
        TLlist.append(nowlist)
        nowlist = TL[lop]
        now = TL[lop]
    else:
        nowlist += now
TLlist.append(nowlist)

maxS = 0
cnt = 0
fg = 0
tfg = 0
fg2 = False
loplist = copy.deepcopy(TLlist)

for lop3 in range(len(loplist)):
    for lop2 in range(len(loplist)):
        if loplist[lop2][:1] == "0":
            if fg <= tfg:
                loplist[lop2] = loplist[lop2].replace('0', '1')
                cnt += 1
                if cnt == K:
                    fg2 = True
                    break
            else:
                tfg += 1
    loplist = "".join(loplist).split("0")
    for lop2 in loplist:
        if maxS < len(lop2):
            maxS = len(lop2)

    loplist = copy.deepcopy(TLlist)
    fg += 1
    cnt = 0
    tfg = 0
    if fg2 == False:
        break
    else:
        fg2 = False

print(maxS)


### FIXED CODE ###

data = input().split()
N = int(data[0])
K = int(data[1])
 
TL = list(input())
TLlist = []
TLLlist = []
now = TL[0]
nowlist = now
anslist = []
 
for lop in range(1,len(TL)):
    if not (now == TL[lop]):
        TLlist.append(nowlist)
        TLLlist.append(len(nowlist))
        nowlist = TL[lop]
        now = TL[lop]
    else:
        nowlist += now
TLlist.append(nowlist)
TLLlist.append(len(nowlist))
 
 
if TLlist[0][:1] == "0" :
    anslist.append( sum(TLLlist[:2*K]) )
    anslist.append( sum(TLLlist[1:2*K + 2]) )
    for lop in range(3,len(TLlist),2):
        if 2*K +  lop > len(TLlist):
            break
        anslist.append( anslist[len(anslist)-1] - sum(TLLlist[lop-2:lop]) + sum(TLLlist[lop + 2*K - 1 : lop + 2*K + 1])  )
elif TLlist[0][:1] == "1" :
    anslist.append( sum(TLLlist[:2*K + 1 ]) )
    for lop in range(2,len(TLlist),2):
        if 2*K +  lop > len(TLlist):
            break
        anslist.append( anslist[len(anslist)-1] - sum(TLLlist[lop-2:lop]) + sum(TLLlist[lop + 2*K - 1 : lop + 2*K + 1])  )
 
print(max(anslist))
### BUGGY CODE ###

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

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

bef=-1
x =0
count = 0

while True:
	if count>0:
		N=bef
	x=abs(N-K)
	count+=1
	if bef!=-1 and bef<=x:
		break
	bef=x


print(bef)




### FIXED CODE ###

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

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

t=N//K


ans = min(N - K * t, -(N - K * (t + 1)))
print(ans)
### BUGGY CODE ###

import math
from functools import reduce
from itertools import product

def gcd(*num):
    return reduce(math.gcd, num)

N = int(input())

I = range(1, N+1)
J = range(1, N+1)
K = range(1, N+1)

count = 0

for i, j, k in product(I, J, K):
    count = count + gcd(i, j, k)

print(count)

### FIXED CODE ###

n = int(input())

from math import gcd

y = 0
for i in range(1, n + 1):
    for j in range(1, n + 1):
        x = gcd(i, j)
        for k in range(1, n + 1):
            y += gcd(x, k)

print(y)
### BUGGY CODE ###

N = int(input())
S = list(input())
R = []
G = []
B = []
for i in range(N):
    if S[i] == "R":
        R.append(i)
    elif S[i] == "G":
        G.append(i)
    elif S[i] == "B":
        B.append(i)
    #if i / 2 in R or i / 2 in G or i / 2 in B
count = len(R)*len(G)*len(B)


for a in R:
    for b in G:
        if 2 * a - b in B:
            count -= 1
        if 2 * b - a in B:
            count -= 1
        if (a + b)/2 in B:
            count -= 1
print(count)

### FIXED CODE ###

N = int(input())
S = list(input())
R = []
G = []
B = []
Reval = {}
Geval = {}
Beval = {}
for i in range(N):
    if S[i] == "R":
        R.append(i)
        Reval[2*i] = 2*i
    elif S[i] == "G":
        G.append(i)
        Geval[2*i] = 2*i
    elif S[i] == "B":
        B.append(i)
        Beval[2*i] = 2*i
count = len(R)*len(G)*len(B)

for a in R:
    for b in G:
        if (a + b) in Beval:
            count -= 1
for a in G:
    for b in B:
        if (a + b) in Reval:
            count -= 1
for a in B:
    for b in R:
        if (a + b) in Geval:
            count -= 1
print(count)
### BUGGY CODE ###

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
B = [0]*N
days = 0
games_amount = 0
while True:
    C = [0]*N
    for i in range(N):
        if C[i] == 0 and B[i] != N-1:
            b = A[i][B[i]]
            if C[b] == 1:
                continue
            if A[b][B[b]] == i:
                B[i] += 1
                B[b] += 1
                C[i], C[b] = 1, 1
    if sum(C) == 0:
        break
    days += 1
print(days if sum(B) == N*(N-1) else -1)

### FIXED CODE ###

import time

start = time.time()

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
B = [0]*N
days = 0
games_amount = 0

for i in range(N*(N-1)//2):
    games = 0
    played = set()
    for j in range(N):
        if len(A[j]) == 0 or j in played or A[j][0] in played:
            continue
        if A[A[j][0]][0] == j:
            t1 = A[j].pop(0)
            played.add(t1)
            played.add(A[t1].pop(0))
            games += 1
            games_amount += 1
    if games == 0:
        print(-1)
        exit(0)
    else:
        days += 1
    if games_amount == N*(N-1)//2:
        break
    if time.time() - start > 1.9:
        print(N*(N-1)//2)
        exit(0)
print(days)
### BUGGY CODE ###

#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
import sys

INF = 1145141919


def solve(S: int):
    ans = 0
    s = [0]+list(map(int, str(S)))
    for i in range(1, len(s)):
        s[i] = s[i-1]*10+s[i]
    for i in range(len(s)-4):
        for j in range(i + 4, len(s)):
            if (s[j] - s[i]*10**(j-i)) % 2019 == 0:
                ans += 1

    return ans


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    print(solve(S))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
import sys
import itertools
import collections

INF = 1145141919


def solve(S: int):
    l = list(reversed(str(S)))
    a = [int(l[c]) * pow(10, c, 2019) for c in range(len(l))]

    def list_cumsum(l):
        return list(itertools.accumulate(l))
    s = [n % 2019 for n in list_cumsum([0]+a)]

    return sum([int(v * (v-1) / 2) for v in collections.Counter(s).values()])


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    print(solve(S))


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

k = int(input())
n = 0

for i in range(1, 10**6+100):
    n = n * 10 + 7
    if n % k == 0:
        print(i)
        exit()

print(-1)


### FIXED CODE ###

k = int(input())
n = 0

for i in range(1, 10**6+100):
    n = n * 10 + 7
    n %= k
    if n == 0:
        print(i)
        exit()

print(-1)
### BUGGY CODE ###

n,m,k=map(int,input().split())
l=list(map(int,input().split()))
ll=list(map(int,input().split()))

l_ans=[]
for i in range(m+1):
  l_ans.append([0]*(n+1))
ct=0

for i in range(m+1):
  we=i+n
  for j in range(n+1):
    if i==0 and j==0:
      l_ans[i][j]=0
    elif i==0:
      l_ans[i][j]=l_ans[i][j-1]+l[j-1]
    elif j==0:
      l_ans[i][j]=l_ans[i-1][j]+ll[i-1]
    else:
      l_ans[i][j]=l_ans[i][j-1]+l[j-1]
    
    if l_ans[i][0]>k:
      we=0
      break
    if l_ans[i][j]>k:
      we=i+j-1
      break
    elif l_ans[i][j]==k:
      we=i+j
      break
  
  #print(ct,we)

  if we>ct:
    ct=we
#print(l_ans)
print(ct)

### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
  a.append(a[i] + A[i])
for i in range(M):
  b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
  if a[i] > K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
count = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if k-j == j-i:
                continue
            if (s[i] != s[j]) and (s[j] != s[k]) and (s[k] != s[i]):
                count += 1
print(count)


### FIXED CODE ###

n = int(input())
s = input()

count = 0
r = []
g = []
b = []

for i in range(n):
    if s[i] == 'R':
        r.append(i)
    if s[i] == 'G':
        g.append(i)
    if s[i] == 'B':
        b.append(i)

count += len(r)*len(g)*len(b)

for i in range(n-2):
    for j in range(i+1,n):
        if j+(j-i) >= n:
            continue
        k = j + (j-i)
        if (s[i] != s[j]) and (s[j] != s[k]) and (s[k] != s[i]):
            count -= 1

print(count)
### BUGGY CODE ###

#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
n = int(input())
L = list( map(int, input().split()) )	# 1 2 3 4 5 ...

L.sort()

ans=0

#p(L)

def bsl(c,L):
	
	rMax = len(L)-1
	
	l=0
	r=rMax
	
	while True:
		m=(l+r)//2
		#p("  [bsl]c,l,r,m ",c,l,L[l],r,L[r],m,L[m] )

		if L[m]==c:
			while True:
				if m==rMax: return m
				if L[m]==L[m+1]:
					m+1
				else:
					return m
		
		if (r-l)==1:
			if L[r]<=c:
				return r
			else:
				return l
		
		if c<L[m]: r=m
		if L[m]<c: l=m


for i in range(n-2):
	a=L[i]
	
	for j in range(i+1, n-1):
		b=L[j]
		#if b>(a*2): break
		
		#p("a,b,a+b-1 ",a,b,a+b-1)
		k = bsl(a+b-1, L)
		
		if j<k: ans += (k-j)
		#p("j,k,(k-j),ans ",j,k,(k-j),ans)

print(ans)





### FIXED CODE ###

#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
from bisect import bisect_left  as bl
from bisect import bisect_right as br
from bisect import insort_left  as il    # insort_leftはO(N)
from bisect import insort_right as ir
#-------------------------------------------------------------------
n = int(input())
L = list( map(int, input().split()) )	# 1 2 3 4 5 ...

L.sort()

ans=0

for i in range(n-2):
	a=L[i]
	
	for j in range(i+1, n-1):
		b=L[j]
		
		k = bl(L,a+b)
		
		ans+=k-j-1

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


N, A, B = list(map(int, input().split()))
i = 0
b = 0
r = 0
while i < N:
    if (i+A <= N):
        b += A
        i += A
    elif(i+A > N):
        b += N-i
        break
    if (i+B <= N):
        r += B
        i += B
    elif(i+B > N):
        r += N-i
        break        
print(b)


### FIXED CODE ###


N, A, B = list(map(int, input().split()))
i = 0
b = 0
r = 0

c = N//(A+B)
#print(c)
d = N%(A+B)
#print(d)
if d <= A:
    b = c*A + d
else:
    b = (c+1)*A
print(b)
### BUGGY CODE ###

A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
xyc = list(list(map(int, input().split())) for _ in range(M))
l1 = []
lx = []
ly = []
for i in range(M):
    l1.append(list(c for x, y, c in xyc))
min_a = min(a)
min_b = min(b)
max_l1 = max(list(map(int, max(l1))))
for k in range(M):
    lx.append(list(x for x, y, c in xyc))
    ly.append(list(y for x, y, c in xyc))
    j = lx[0][k]
    p = ly[0][k]
    ans = min((min_a + min_b), ((a[j - 1] + b[p - 1]) - max_l1))
print(ans)

### FIXED CODE ###

A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = min(a) + min(b)
for k in range(M):
    x, y, c = map(int, input().split())
    ans = min(ans, ((a[x - 1] + b[y - 1]) - c))
print(ans)
### BUGGY CODE ###

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

sei=[0]*(n-k+1)
for i in range(n-k+1):
  for j in range(i,i+k):
    sei[i]+=a[j]

for i in range(n-k):
  if sei[i]<sei[i+1]:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

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

for i in range(n-k):

  if  a[i]<a[i+k]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

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

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
l = [0] * N
ans = 0
count = 0
check = [False] * N
tmpl = []

while(count <= N - 1):
    check = [False] * N
    for i in range(N):
        if l[i] < N - 1:
            to = A[i][l[i]] - 1
            if (not check[to]) and (not check[i]):
                if A[to][l[to]] - 1 == i:
                    l[i] += 1
                    l[to] += 1
                    check[to] = True
                    check[i] = True
                if l[i] == N - 1:
                    count += 1
                if l[to] == N - 1:
                    count += 1
    ans += 1
    if tmpl == l:
        print(-1)
        exit()
    tmpl = l[:]
    # print(l, ans)

print(ans)


### FIXED CODE ###

import sys
import time
def input():
    return sys.stdin.readline()
 
def main():
    a = time.time()
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    l = [0] * N
    ans = 0
    count = 0
    check = [False] * N
    tmpl = []
    next = False
 
    while(count < N):
        check = [False] * N
        for i in range(N):
            if l[i] < N - 1:
                to = A[i][l[i]] - 1
                if (not check[to]) and (not check[i]):
                    if A[to][l[to]] - 1 == i:
                        l[i] += 1
                        l[to] += 1
                        check[to] = True
                        check[i] = True
                        next = True
                    if l[i] == N - 1:
                        count += 1
                    if l[to] == N - 1:
                        count += 1
        ans += 1
        if not next:
            print(-1)
            exit()
        next = False

        b = time.time()
        if b - a >= 1.7:
            print(N*(N - 1)//2)
            exit()
        # print(l, ans)
 
    print(ans)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, M = map(int, input().split())
L, R = [], []
for i in range(M):
    l, r = map(int, input().split())
    L.append(l), R.append(r)

s = []
for i in range(M):
    s.append([i for i in range(L[i], R[i]+1)])

a = s[0]
for i in s:
    a = set(a) & set(i)

ans = 0
for i in range(N+1):
    if i in a:
        ans += 1

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
L, R = [], []

for i in range(M):
    l, r = map(int, input().split())
    L.append(l), R.append(r)

if max(L) <= min(R):
    print(min(R) - max(L) + 1)
else:
    print(0)
### BUGGY CODE ###

s=list(input())
count=0
i=0
while True:
  flag=1
  for i in range(len(s)):
    if i+1<len(s):
      if s[i]=="B" and s[i+1]=="W":
        s[i]="W"
        s[i+1]="B"
        count+=1
        i+=1
        flag=0
  if flag==1:
    break

print(count)

### FIXED CODE ###

s=list(input())
count=0
# print('lens',len(s))
indexes = [i for i, x in enumerate(s) if x == "B"]
ideal=sorted([len(s)-i-1 for i in range(len(indexes))])
# print(indexes)
# print(ideal)
for i in range(len(indexes)):
  count+=ideal[i]-indexes[i]

print(count)
### BUGGY CODE ###

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

mod=998244353

comb=1
pw=(M*pow(M-1,N-1,mod))%mod
ans=pw*comb

invmodk=[0,1]
invmodm=pow(M-1,mod-2,mod)
for k in range(2,K+1):
    invmodk.append(invmodk[mod%k]*(mod-mod//k)%mod)

for k in range(1,K+1):
    pw=(pw*invmodm)%mod
    comb*=(N-k)*invmodk[k]
    ans=(ans+pw*comb)%mod

print(ans)

### FIXED CODE ###

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

mod=998244353

com=1
ans=0

for i in range(K+1):
    ans+=M*com*pow(M-1,N-1-i,mod)
    ans%=mod
    com*=(N-1-i)*pow(i+1,mod-2,mod)
    com%=mod

print(ans)