Harryxun/stf_run huggingface dataset:
from collections import deque

def bfs():
    d = [[inf]*(w+1) for _ in range(h+1)]
    que = deque()
    que.append((0,0))
    d[0][0] = 0

    while que:
        cx,cy = que.popleft()
        if cx == w and cy == h:
            break
        for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
            nx, ny = cx+dx, cy+dy
            if 0 <= nx <= w and 0 <= ny <= h and s[nx][ny] != "#" and d[nx][ny] == inf:
                que.append((nx,ny))
                d[nx][ny] = d[cx][cy] + 1
    return d[w][h]

h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
inf = float("inf")
h,w = h-1,w-1
cnt = bfs()
dot = 0
for i in s:
    dot += i.count(".")
if 0 < cnt < inf:
  print(dot-cnt-1)
else:
  print(-1)

### FIXED CODE ###

from collections import deque

def bfs():
    d = [[inf]*(w+1) for _ in range(h+1)]
    que = deque()
    que.append((0,0))
    d[0][0] = 0

    while que:
        cx,cy = que.popleft()
        if cx == w and cy == h:
            break
        for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
            nx, ny = cx+dx, cy+dy
            if 0 <= nx <= h and 0 <= ny <= w and s[nx][ny] != "#" and d[nx][ny] == inf:
                que.append((nx,ny))
                d[nx][ny] = d[cx][cy] + 1
    return d[h][w]

h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
inf = float("inf")
h,w = h-1,w-1
cnt = bfs()
dot = 0
for i in s:
    dot += i.count(".")
if 0 < cnt < inf:
  print(dot-cnt-1)
else:
  print(-1)
N = int(input())
S = input()

counta = 0
i = 0

while i < N - 2:
    j = i + 1
    while j < N - 1:
        if S[j] != S[i]:
            k = j + 1
            rest = [l for l in ['R', 'G', 'B'] if l != S[i] and l != S[j]]
            while k < N:
                if S[k] == rest[0] and  k - j != j - i:
                    counta += 1
                k += 1
        j += 1
    i += 1

print(counta)

### FIXED CODE ###

import math
import itertools
from functools import reduce

def gcd(numbers):
    return reduce(math.gcd, numbers)

K = int(input())

ans = 0
for lst in itertools.combinations_with_replacement([i + 1 for i in range(K)], 3):
    ans += int(6 / math.factorial(4 - len(set(lst)))) * gcd(list(lst))

print(ans)
[x, y] = [x forx in map(int, input().split(' '))]
flg = -1
if y % 2 == 1:
  flg = 1
else:
  for i in range(0, x):
    if i * 2 + (x - i) * 4 == y:
      flg = 0
      break
if flg == 1 or flg == -1:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

[x, y] = [x for x in map(int, input().split(' '))]
flg = -1
if y % 2 == 1:
  flg = 1
else:
  for i in range(0, x):
    if i * 2 + (x - i) * 4 == y or (x - i) * 2 + i * 4 == y:
      flg = 0
      break
print('Yes' if flg == 0 else 'No')
C = input()
C_asc ord(C)
ret = chr(C_asc + 1)
print(ret)


### FIXED CODE ###


C = input()
C_asc = ord(C)
ret = chr(C_asc + 1)
print(ret)
o = str(input())
e = str(input())
ans = []
for i in range(len(o)):
    ans.append(o[i])
    ans.append(e[i])
print("".join(ans))

### FIXED CODE ###

O = str(input())
E = str(input())
ans = []
for i in range(len(E)):
    ans.append(O[i])
    ans.append(E[i])
if(len(O) != len(E)):
    ans.append(O[-1])
print("".join(ans))
import sys
input = sys.stdin.readline

s = input()
n = len(s)

ans = [0 for _ in range(n)]
cnt = 0
for i in range(n):
    if s[i] == 'R':
        cnt += 1
    else:
        ans[i] += cnt // 2
        ans[i-1] += (cnt + 1) // 2
        cnt = 0
s_inv = ''.join(reversed(s))
for i in range(n):
    if s_inv[i] == 'L':
        cnt += 1
    else:
        ans[n-i-1] += cnt // 2
        ans[n-i] += (cnt + 1) // 2
        cnt = 0
print(' '.join(map(str, ans)))


### FIXED CODE ###

s = input()
n = len(s)

ans = [0 for _ in range(n)]
cnt = 0
for i in range(n):
    if s[i] == 'R':
        cnt += 1
    else:
        ans[i] += cnt // 2
        ans[i-1] += (cnt + 1) // 2
        cnt = 0
cnt = 0
s_inv = ''.join(reversed(s))
for i in range(n):
    if s_inv[i] == 'L':
        cnt += 1
    else:
        ans[n-i-1] += cnt // 2
        ans[n-i] += (cnt + 1) // 2
        cnt = 0
print(' '.join(map(str, ans)))
#%%
def c(s):
    n = len(s)

    if n < 2:
        print(0)

    else:
        ans, i = 0, 0
        rem = []

        while i < n:
            print(rem,s[0:i],s[i:])

            if not rem:

                if i+1 < n:
                    if s[i] == s[i+1]:
                        rem.append(s[i])
                        i += 1

                    else:
                        i += 2
                        ans += 2

                else:
                    i += 1

            else:
                if rem[-1] != s[i]:
                    rem.pop()
                    i += 1
                    ans += 2
                
                else:
                    if i + 1 < n:
                        if s[i] == s[i+1]:
                            rem.append(s[i])
                            i += 1

                        else:
                            i += 2
                            ans += 2

                    else:
                        i += 1
    print(ans)

#%%
s = input()

c(s)

### FIXED CODE ###

#%%
s = input()
n = len(s)

if n < 2:
    print(0)

else:
    ans, i = 0, 0
    rem = []

    while i < n:

        if not rem:

            if i+1 < n:
                if s[i] == s[i+1]:
                    rem.append(s[i])
                    i += 1

                else:
                    i += 2
                    ans += 2

            else:
                i += 1

        else:
            if rem[-1] != s[i]:
                rem.pop()
                i += 1
                ans += 2
            
            else:
                if i + 1 < n:
                    if s[i] == s[i+1]:
                        rem.append(s[i])
                        i += 1

                    else:
                        i += 2
                        ans += 2

                else:
                    i += 1
    print(ans)
t=input()
s=[0]*len(t)
for i in range(len(t)):
  
  if t[i]=='?':
    if i==0:
      if t[i+1]=='D':s[i]='P'
      else:s[i]='D'
      
    if i==len(t)-1:
      if t[i-1]=='D':s[i]='P'
      else:s[i]='D'
    
    if t[i-1]=='P':s[i]='D'
    elif t[i+1]=='P':s[i]='D'
    else:s[i]='P'
  else:s[i]=t[i]
print(''.join(s))

### FIXED CODE ###

t=input()
s=[0]*len(t)

for i in range(len(t)):
  
    if t[i]=='?':
        if i==0:
            if len(t)>=2:
                if t[i+1]=='D':
                    s[i]='P'
                else:
                    s[i]='D'
            else:s[i]='D'
      
      
        elif i==len(t)-1:
            s[i]='D'
        
    
        else:
            if s[i-1]=='P':s[i]='D'
            elif t[i+1]=='P':s[i]='D'
            else:s[i]='P'

    elif t[i]=='D' or t[i]=='P':s[i]=t[i]
    else:continue
#print(s)
print(''.join(s))
from statistics import mode
import numpy as np
N=input()
p=list(map(int,input().split()))
p=np.array(p)
q=p-np.arange(len(p-1))
q = list(q)
r = len(list(set(q)))
if sum(list(q))==2*mode(q):
    print('YES')
else:
    print('NO')
    



### FIXED CODE ###

N=int(input())
p=list(map(int,input().split()))
q=sorted(p)
count=0
for i in range(N):
    if p[i]!=q[i]:
        count+=1
if count<=2:
    print('YES')
else:
    print('NO')
h,w,k = map(int, input().split())

for _ in range(h):
    c=list(input())

ans = 0

for i in range(h):
    for j in range(w):
    cnt = 0
        for m in range(h):
            for l in range(w):
                if (i>>m)&1==0 and (j>>l)&1==0 and c[m][l]== "#":
                    cnt+=1
        if cnt == k: ans+=1
print(ans)


### FIXED CODE ###

h,w,k = map(int, input().split())
grid = [input() for _ in range(h)]

ans = 0

for i in range(2**h):
    for j in range(2**w):
        count = 0
        for m in range(h):
            for l in range(w):
                if (i>>m)&1==0 and (j>>l)&1==0 and grid[m][l] == "#":
                    count+=1
        if count == k: ans+=1
print(ans)
rom sys import stdin

N, K = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()
cnt = 1
run = []
for i in range(1, len(S)):
    if S[i - 1] == S[i]:
        cnt += 1
    else:
        run.append(cnt)
        cnt = 1
    if i == len(S) - 1:
        run.append(cnt)
X = [sum(run[j: j + 2 * K + 1]) for j in range(max(len(run) - 2 * K, 1))]
if len(X) == 0:
    print(1)
else:
    print(max(X))


### FIXED CODE ###

from sys import stdin

N, K = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()
cnt = 1
run = []
if len(S) == 1:
    run.append(1)
else:
    for i in range(1, len(S)):
        if S[i - 1] == S[i]:
            cnt += 1
        else:
            run.append(cnt)
            cnt = 1
        if i == len(S) - 1:
            run.append(cnt)
if S[0] == '0':
    run = [0] + run
if S[N - 1] == '0':
    run = run + [0]
if len(run) < 2 * K + 1:
    print(sum(run))
    exit()
ans = sum(run[0: 2 * K + 1])
sb = ans
for j in range(2, len(run) - 2 * K):
    if j % 2 == 1:
        continue
    else:
        sb = sb - run[j - 1] - run[j - 2] + run[j + 2 * K] + run[j + 2 * K - 1]
        if sb > ans:
            ans = sb
print(ans)
N, M = map(int, input().split())
connect_list = [set() for _ in range(N)]    #繋がっているリスト
for _ in range(M):
    A, B = map(int, input().split())
    connect_list[A-1].add(B)
    connect_list[B-1].add(A)

root_list = [0]*N
root_list[0] = "Yes"

for i in list(connect_list[0]):
    root_list[i-1] = 1
now_set = connect_list[0]

def do_ranking(now_set):
    global connect_list, root_list
    if len(now_set) == 0:
        return 0
    # next_set = set()
    for j in list(now_set):
        for m in list(connect_list[j-1]):
            if root_list[m-1] == 0:
                root_list[m-1] = j
                # next_set.add(i)
                now_set.add(m)
        now_set.remove(j)
    do_ranking(now_set)


do_ranking(now_set)   #道しるべ作成

for k in root_list:
    print(k)


### FIXED CODE ###

N, M = map(int, input().split())
connect_list = [set() for _ in range(N)]    #繋がっているリスト
for _ in range(M):
    A, B = map(int, input().split())
    connect_list[A-1].add(B)
    connect_list[B-1].add(A)

root_list = [0]*N
root_list[0] = "Yes"

for i in list(connect_list[0]):
    root_list[i-1] = 1
now_set = connect_list[0]
while len(now_set) != 0:
    for j in list(now_set):
        for i in list(connect_list[j-1]):
            if root_list[i-1] == 0:
                root_list[i-1] = j
                now_set.add(i)
        now_set.remove(j)

for i in root_list:
    print(i)
import sys
import math
import itertools
import numpy

rl = sys.stdin.readline

r = map(int, rl().split())
n1 = int(rl().strip())
n2 = int(rl().strip())
li = itertools.combinations(n1, r)
print(abs(li.index(n1) - li.index(n2)))

### FIXED CODE ###

import sys
import math
import itertools
import numpy

rl = sys.stdin.readline

r = int(rl())
n1 = tuple(map(int, rl().split()))
n2 = tuple(map(int, rl().split()))
li = list(itertools.permutations(range(1, r+1)))
print(abs(li.index(n1) - li.index(n2)))
N = int(input())
line = list(map(int,input().split()))
a = 0
p = []
for i in N:
    p.append(N)
    if  min(p) >= N:
       a += 1

print(a)

### FIXED CODE ###

N = int(input())
line = list(map(int,input().split()))
a = 1
m = line[0]
for i in range(N-1):
    if m >= line[i]:
        m = line[i]

    if m >= line[i+1]:
       a += 1

print(a)
import math
A, B , C , D = map(int, input().split())

bc = B // C 
bd = B // D
bcd = B // (C*D//math.gcd(C, D))
ans = B- (bc + bd - bcd)
ac = (A-1) // C
ad = (A-1) // D
acd = (A-1) //(C*D//math.gcd(C, D))
ans2=  A-1 - (ac + ad - acd)
ans = ans - ans2
print(ans)

### FIXED CODE ###

import fractions
A, B , C , D = map(int, input().split())

bc = B // C 
bd = B // D
bcd = B // (C*D//fractions.gcd(C, D))
ans = B- (bc + bd - bcd)
ac = (A-1) // C
ad = (A-1) // D
acd = (A-1) //(C*D//fractions.gcd(C, D))
ans2=  A-1 - (ac + ad - acd)
ans = ans - ans2
print(ans)
numbers = map(int, raw_input().split())
a = numbers[0]
b = numbers[1]
i = 1
while True:
    if a != i:
        i += 1
        continue
    else:
        if b < i:
            print(i - 1)
            break
        else:
            print(i)
            break

### FIXED CODE ###

numbers = input().split()
a = int(numbers[0])
b = int(numbers[1])
i = 1
while True:
    if a != i:
        i += 1
        continue
    else:
        if b < i:
            print(i - 1)
            break
        else:
            print(i)
            break
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
s = ['0' * (W+2)]
for _ in range(H):
    s.append('0' + input().rstrip() + '0')
s.append('0' * (W+2))

ans = []
if s[1][1] == '#': a = 1
else: a = 0
temp = [[1, 1, a]]

while temp:
    p = temp.pop()
    for y, x in [[p[0]+1, p[1]], [p[0], p[1]+1]]:
        if s[y][x] == '0':continue
        if s[y][x] == '#' and s[p[0]][p[1]] == '.':
            d = p[2] + 1
        if y == H and x == W:
            ans.append(d)
        else:
            temp.append([y, x, d])
            
print(min(ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
s = [input().rstrip() for _ in range(H)]

dp = [[1000]*W for _ in range(H)]

if s[0][0] == '#': dp[0][0] = 1
else: dp[0][0] = 0

for j in range(W):
    for i in range(H):
        if i <= H - 2:

            if s[i][j] == '.' and s[i+1][j] == '#':
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
            else: dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if j <= W - 2:

            if s[i][j] == '.' and s[i][j+1] == '#':
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
            else: dp[i][j+1] = min(dp[i][j+1], dp[i][j])


print(dp[H-1][W-1])
A B =int(input().split())
print(A*B)

### FIXED CODE ###

A, B=map(int, input().split())
print(A*B)
x(1),y(1),x(2),y(2)=map(int,input().split())
for i in range(3,5):
  x(i)=x(i-1)+y(i-2)-y(i-1)
  y(i)=y(i-1)+x(i-1)-x(i-2)
print(x(3) y(3) x(4) y(4))


### FIXED CODE ###

x1,y1,x2,y2=map(int,input().split())
x3=x2+y1-y2
y3=y2+x2-x1
x4=x3+y2-y3
y4=y3+x3-x2
print(x3,y3,x4,y4)
s =input()
if s=='AAA' or s=='BBB:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

s =input()
if s=='AAA' or s=='BBB':
  print('No')
else:
  print('Yes')
N = int(input())
w = []
for i in range(N):
    w.append(input())
    if i ==0:
        continue
    if w[i][0] !=  w[i-1][-1]:
        print('No')
        return

if N == len(set(w)):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

def main():
    N = int(input())
    w = []
    for i in range(N):
        w.append(input())
        if i == 0:
            continue
        if w[i][0] != w[i-1][-1]:
            print('No')
            return

    if N == len(set(w)):
        print('Yes')
    else:
        print('No')

main()
import numpy as np
from scipy.sparse import csr_matrix, csgraph
n, m, s, t = map(int, input().split())
src = [list(map(int, input().split())) for _ in range(m)]
u, v, a, b = zip(*src)
pa = csgraph.dijkstra(csr_matrix((a, (u, v)), (n + 1, n + 1), dtype=np.int32),
                      False, s)
pb = csgraph.dijkstra(csr_matrix((b, (u, v)), (n + 1, n + 1), dtype=np.int32),
                      False, t)

dist = [int(pa[-1] + pb[-1])]
for i in range(n - 1, 0, -1):
    dist.append(min(dist[-1], int(pa[i] + pb[i])))

snuk = 10 ** 15
print(*(snuk - d for d in reversed(dist)), sep='\n')

### FIXED CODE ###

from heapq import heappop, heappush
n, m, s, t = map(int, input().split())
edge_a = [set() for _ in range(n + 1)]
edge_b = [set() for _ in range(n + 1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    edge_a[u].add((v, a))
    edge_a[v].add((u, a))
    edge_b[u].add((v, b))
    edge_b[v].add((u, b))

def dijkstra(edge, s):
    sp = [10 ** 19] * (n + 1)
    sp[s] = 0
    q = [(0, s)]
    while q:
        dist, s = heappop(q)
        for t, w in edge[s]:
            if dist + w < sp[t]:
                sp[t] = dist + w
                heappush(q, (sp[t], t))
    return sp

sp_a = dijkstra(edge_a, s)
sp_b = dijkstra(edge_b, t)
dist = [int(sp_a[-1] + sp_b[-1])]
for i in range(n - 1, 0, -1):
    dist.append(min(dist[-1], int(sp_a[i] + sp_b[i])))

snuk = 10 ** 15
print(*(snuk - d for d in reversed(dist)), sep='\n')
#include"bits/stdc++.h"

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<< #str << " " str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 1000000007;// 10^9+7

int N;
vector<ll> A, B;
vector<pair<ll, ll>> diff;

//���C���֐�
int main()
{
	cin >> N;
	A.resize(N);
	B.resize(N);
	diff.resize(N);
	REP(i, N)cin >> A[i] >> B[i];
	REP(i, N)diff[i] = make_pair(A[i] + B[i], i);
	sort(diff.begin(), diff.end());
	reverse(diff.begin(), diff.end());

	ll tak = 0, ao = 0;
	REP(i, N)
	{
		auto p = diff[i];
		if(i % 2 == 0)tak += A[p.second];
		else ao += B[p.second];
	}
	cout << tak - ao << endl;
	//cerr << tak << " " << ao << endl;

	cin >> N;
	return 0;
}


### FIXED CODE ###

print(-sum([v[k%2]*(k%2*2-1)for k,v in enumerate(sorted([[int(j) for j in input().split()] for i in range(int(input()))],key=lambda x:-x[0]-x[1]))]))
k,y=map(int,input().split())
for i in range(x-y+1,x+y):
    print(i,end=" ")

### FIXED CODE ###

k,y=map(int,input().split())
for i in range(y-k+1,k+y):
    print(i,end=" ")
import math
n,k = map(int,input().split())
ai = [int(i) for i in input().split()]

g = math.gcd(ai[0],ai[1])

for i in range(1,n-1):
    #print(i)
    g = math.gcd(g,ai[i+1])

if k % g == 0 and max(ai) >= k:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

import fractions
n,k = map(int,input().split())
ai = [int(i) for i in input().split()]

if n == 1:
    if k == ai[0]:
        print('POSSIBLE')
        exit()
    else:
        print('IMPOSSIBLE')
        exit()

g = fractions.gcd(ai[0],ai[1])

for i in range(1,n-1):
    #print(i)
    g = fractions.gcd(g,ai[i+1])

if k % g == 0 and max(ai) >= k:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
import sys
def input():
	return sys.stdin.readline().strip()

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

graph = [[] for _ in range(N)]

for _ in range(M):
	s, t = list(map(int, input().split()))
	graph[s - 1].append(t - 1)

base_dist = [-1]*N
base_dist[-1] = 0


for i in range(N - 2, -1, -1):
	total = 0
	for node in graph[i]:
		total += base_dist[node]
	base_dist[i] = total/len(graph[i]) + 1


ans = base_dist[0]
for stop in range(0, N - 1):
	dist = copy.deepcopy(base_dist)
	total = 0
	if len(graph[stop]) == 1:
		continue
	max_d = 0
	for node in graph[stop]:
		max_d = max(max_d, dist[node])
		total += dist[node]
	total -= max_d
	total /= (len(graph[stop]) - 1)
	total += 1
	dist[stop] = total

	for i in range(stop - 1, -1, -1):
		total = 0
		for node in graph[i]:
			total += dist[node]
		dist[i] = total / len(graph[i]) + 1

	ans = min(ans, dist[0])
	#print(stop,dist)

print(ans)

### FIXED CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions
from operator import itemgetter


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

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

graph = [[] for _ in range(N)]

for _ in range(M):
	s, t = list(map(int, input().split()))
	graph[s - 1].append(t - 1)

base_dist = [-1]*N
base_dist[-1] = 0


for i in range(N - 2, -1, -1):
	total = 0
	for node in graph[i]:
		total += base_dist[node]
	base_dist[i] = total/len(graph[i]) + 1


ans = base_dist[0]
for stop in range(0, N - 1):
	dist = copy.deepcopy(base_dist)
	total = 0
	if len(graph[stop]) == 1:
		continue
	max_d = 0
	for node in graph[stop]:
		max_d = max(max_d, dist[node])
		total += dist[node]
	total -= max_d
	total /= (len(graph[stop]) - 1)
	total += 1
	dist[stop] = total

	for i in range(stop - 1, -1, -1):
		total = 0
		for node in graph[i]:
			total += dist[node]
		dist[i] = total / len(graph[i]) + 1

	ans = min(ans, dist[0])
	#print(stop,dist)

print(ans)
seconds = int(input())

hour = seconds // 3600
minute = seconds % 3600 // 60
second = seconds % 3600  % 60

print(hour + ':' + minute + ':' + second)

### FIXED CODE ###

seconds = int(input())

hour = str(seconds // 3600)
minute = str(seconds % 3600 // 60)
second = str(seconds % 3600  % 60)

print(hour + ':' + minute + ':' + second)
a , b = map(int(),input().split())

X = 0
Y = 0

list = [X,Y]

for i in b:
  X = X + 'a'
  
for v in a:
  Y = Y + 'b'
  
if 'X' < 'Y':
  print(X)
else:
  print(Y)

### FIXED CODE ###

a , b =input().split()
 
if a <= b:
    print(a*int(b))
else:
	print(b*int(a))
def main():
    MOD = 998244353

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

    dp = [0] * (S + 1)

    ans = 0
    for x in A:
        ans += dp[S]
        if S - x >= 0:
            ans += dp[S - x]
        if S == x:
            ans += 1
        for s in range(S, x, -1):
            dp[s] = (dp[s] + dp[s - x]) % MOD
        dp[x] = (dp[x] + dp[0] + 1) % MOD
        dp[0] += 1
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

#             dp[i + 1][s][0] = (dp[i + 1][s][0] + dp[i][s][0]) % MOD
#             dp[i + 1][s][1] = (dp[i + 1][s][1]
#                                + dp[i][s][1] + (dp[i][s - x][1] if s - x >= 0 else 0)
#                                + dp[i][s][0] + (dp[i][s - x][0] if s - x >= 0 else 0)) % MOD
#             dp[i + 1][s][2] = (dp[i + 1][s][2]
#                                + dp[i][s][2] +
#                                dp[i][s][1] + (dp[i][s - x][1] if s - x >= 0 else 0)
#                                + dp[i][s][0] + (dp[i][s - x][0] if s - x >= 0 else 0)) % MOD

#     for i, x in enumerate(A):
#         dp[i + 1][0][0] = dp[i][0][0]
#         for s in range(S, -1, -1):
#             dp[i + 1][s][1] = (dp[i][s][1] + dp[i][s][0]) % MOD
#             dp[i + 1][s][2] = (dp[i][s][2] + dp[i][s][1] + dp[i][s][0]) % MOD
#
#             if s - x >= 0:
#                 v = dp[i][s - x][1] + dp[i][s - x][0]
#                 dp[i + 1][s][1] = (dp[i + 1][s][1] + v) % MOD
#                 dp[i + 1][s][2] = (dp[i + 1][s][2] + v) % MOD

#         dp[i + 1][0][0] = dp[i][0][0]
#         dp[i + 1][0][1] = (dp[i][0][1] + dp[i][0][0]) % MOD
#         dp[i + 1][0][2] = (dp[i][0][2] + dp[i][0][1] + dp[i][0][0]) % MOD
#         for s in range(S, 0, -1):
#             dp[i + 1][s][1] = dp[i][s][1] % MOD
#             dp[i + 1][s][2] = (dp[i][s][2] + dp[i][s][1]) % MOD
#             if s - x >= 0:
#                 v = dp[i][s - x][1] + dp[i][s - x][0]
#                 dp[i + 1][s][1] = (dp[i + 1][s][1] + v) % MOD
#                 dp[i + 1][s][2] = (dp[i + 1][s][2] + v) % MOD

#     for x in A:
#         for s in range(S, 0, -1):
#             dp[s][1] += dp[s][0]
#             if s - x >= 0:
#                 v = dp[s - x][0] + (1 if s - x == 0 else 0)
#                 dp[s][0] += v
#                 dp[s][1] += v
#             dp[s][0] %= MOD
#             dp[s][1] %= MOD
#         dp[0][0] += 1
#         dp[0][1] += (dp[0][0] + 1)


### FIXED CODE ###

# https://atcoder.jp/contests/abc159/submissions/11139734

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [0] * (S + 1)

    ret = 0
    for i, x in enumerate(a):
        dp[0] += 1
        if x > S: continue
        ret = (ret + dp[S - x] * (N - i)) % MOD
        for k in range(S - 1, x - 1, -1):
            dp[k] = (dp[k] + dp[k - x]) % MOD

    print(ret)


if __name__ == '__main__':
    main()
a = int(input())
b = list(map(int, input().split()))
c = sorted(b)
d = c[(a//2)]-c[(a//2)-1]
print(d)

### FIXED CODE ###

S = input()
A = set (S)
B = len (A)
if B == 2:
    print ('Yes')
else:
    print ('No')