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

import sys
sys.setrecursionlimit(10 ** 9)

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

seen = [[False for _ in range(W)] for _ in range(H)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
numb = 0
numw = 0

def dfs(y,x):
  global numb
  global numw
  seen[y][x] = True
  if S[y][x] == '#':
    numb += 1
  if S[y][x] == '.':
    numw += 1
  for i in range(4):
    if not(0<=y+dy[i]<H) or not(0<=x+dx[i]<W):
      continue
    if seen[y+dy[i]][x+dx[i]]:
      continue
    if S[y][x] == S[y+dy[i]][x+dx[i]]:
      continue
    dfs(y+dy[i],x+dx[i])

ans = 0
for i in range(H):
  for j in range(W):
    numb = 0
    numw = 0
    if S[i][j] == '#':
      dfs(i,j)
      ans += numb * numw
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

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

seen = [[False for _ in range(W)] for _ in range(H)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
numb = 0
numw = 0

def dfs(y,x):
  global numb
  global numw
  seen[y][x] = True
  if S[y][x] == '#':
    numb += 1
  if S[y][x] == '.':
    numw += 1
  for i in range(4):
    if not(0<=y+dy[i]<H) or not(0<=x+dx[i]<W):
      continue
    if seen[y+dy[i]][x+dx[i]]:
      continue
    if S[y][x] == S[y+dy[i]][x+dx[i]]:
      continue
    dfs(y+dy[i],x+dx[i])

ans = 0
for i in range(H):
  for j in range(W):
    numb = 0
    numw = 0
    if S[i][j] == '#' and not seen[i][j]:
      dfs(i,j)
      ans += numb * numw
print(ans)
### BUGGY CODE ###

n=int(input())
l=[input() for _ in range(n)]
sl = set(l)
m = 0

for s in sl:
  if m <= l.count(s):
    m = l.count(s)
    
ans = []
    
for s in sl:
  if m == l.count(s):
    ans.append(s)
    
ans = sorted(ans)

for a in ans:
  print(a)

### FIXED CODE ###

from collections import Counter
n=int(input())
l=[input() for _ in range(n)]

c = Counter(l)
co = c.most_common()[0][1]
ans = []
for s in c.most_common():
  if s[1] < co:
    break
    
  ans.append(s[0])

for a in sorted(ans):
  print(a)
### BUGGY CODE ###

N = int(input())
X = input()

a = int(X, 2)
b = X.count("1")
k = 2 ** (N-1)

d = [0 for _ in range(b+2)]
for i in range(1, b+2):
    v = i % bin(i)[2:].count("1")
    d[i] = d[v] + 1

for i, ch in enumerate(X):
    if ch == "0":
        x = a + k
        y = b + 1
    else:
        x = a - k
        y = b - 1
    k //= 2

    if x == 0:
        print(0)
    else:
        print(d[x % y] + 1)


### FIXED CODE ###

N = int(input())
X = input()

a = int(X, 2)
b = X.count("1")

if b > 1:
    a1 = a % (b-1)
else:
    a1 = 0
a0 = a % (b+1)

for i in range(N):
    if X[i] == "1":
        if b == 1:
            print(0)
            continue
        t = (a1 - pow(2, N-1-i, b-1)) % (b-1)
    else:
        t = (a0 + pow(2, N-1-i, b+1)) % (b+1)
    
    ans = 1
    while t > 0:
        t %= bin(t).count("1")
        ans += 1
    print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for i in range(Q):
    l1 ,r1 = map(int, input().split())
    s = S[l1-1:r1]
    print(int((r1-l1+1-len(s.replace("AC","")))/2))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
L = [0]*(N+1)
for i in range(N):
    if S[i:i+2] == "AC":
        L[i+1] = L[i] +1
    else:
        L[i+1] = L[i]
for i in range(Q):
    l,r = map(int, input().split())
    print(L[r-1]-L[l-1])
### BUGGY CODE ###

n = int(input())
s = str(input())
m = []
for i in range(0,n):
    list_1 = s[0:i]
    list_2 = s[i+1:n]
    list_1_unique = list((list_1))
    list_2_unique = list((list_2))
    k = 0
    for j in list_1_unique:
        if j == 'W':
            k += 1
    for l in list_2_unique:
        if l == 'E':
            k += 1
    m.append(k)
print(min(m))

### FIXED CODE ###

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

a = [(0,0) for _ in range(n + 1)]
b = []
for i in range(n):
    if s[i] == "W":
        a[i+1] = (a[i][0] + 1,a[i][1])
    else:
        a[i+1] = (a[i][0],a[i][1] + 1)
    b.append(a[i+1][1]-a[i+1][0])
    
ans = s[0:b.index(max(b))].count('W') + s[b.index(max(b))+1:].count('E')
print(ans)
### BUGGY CODE ###

import fractions
mod = 10 ** 9 + 7

def lcm(a,b):
    return (a * b) // fractions.gcd(a, b)

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

LCM = 1
for i in a:
    LCM = lcm(LCM,i)

ans = 0
for i in a:
    ans += LCM // i
print(ans % mod)

### FIXED CODE ###

import fractions
mod = 10 ** 9 + 7

def lcm(a,b):
    return (a * b) // fractions.gcd(a, b)

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

LCM = 1
for i in a:
    LCM = lcm(LCM,i)

ans = 0
for i in a:
    ans += LCM // i
print(ans % mod)
### BUGGY CODE ###

from collections import deque

H,W = map(int,input().split())
_input = []
for i in range(H):
    row = list(map(str,input().split()))
    _input.append(list(row[0]))

sy,sx = 0,0
gy,gx = H-1,W-1

queue = deque([(sy,sx)])

dyx=((1,0),(-1,0),(0,1),(0,-1))

counted_map = [[-1]*W for _ in range(H)]
counted_map[sy][sx] = 0

reach = False

while queue:
    y,x = queue.popleft()

    if (y,x) == (gy,gx):
        reach = True
        break

    for dy,dx in dyx:
        ny = y + dy
        nx = x + dx

        if ny < 0 or nx < 0 or ny >= H or nx >= W:
            continue

        # 空きマスかつ未訪問
        if _input[ny][nx] == '.' and counted_map[ny][nx] == -1:
            counted_map[ny][nx] = counted_map[y][x] + 1
            queue.append((ny,nx))

if not reach:
    print(-1)
    exit()

y,x = gy,gx
move_num = counted_map[gy][gx]
while move_num != 0:
    _input[y][x] = 'o'
    for dy,dx in dyx:
        ny = y + dy
        nx = x + dx

        if ny < 0 or nx < 0 or ny >= H or nx >= W:
            continue
        
        if _input[ny][nx] == '.':
            tmp_dist = counted_map[ny][nx]
            if tmp_dist < move_num:
                move_num = tmp_dist
                next_y,next_x = ny,nx
    
    y,x = next_y,next_x

_input[sy][sx] = 'o'

res = 0

for raw in _input:
    for i in raw:
        if i == '.':
            res += 1

print(res)

### FIXED CODE ###

from collections import deque

H,W = map(int,input().split())
_input = []
for i in range(H):
    row = list(map(str,input().split()))
    _input.append(list(row[0]))

sy,sx = 0,0
gy,gx = H-1,W-1

queue = deque([(sy,sx)])

dyx=((1,0),(-1,0),(0,1),(0,-1))

counted_map = [[-1]*W for _ in range(H)]
counted_map[sy][sx] = 0

reach = False

while queue:
    y,x = queue.popleft()

    if (y,x) == (gy,gx):
        reach = True
        break

    for dy,dx in dyx:
        ny = y + dy
        nx = x + dx

        if ny < 0 or nx < 0 or ny >= H or nx >= W:
            continue

        # 空きマスかつ未訪問
        if _input[ny][nx] == '.' and counted_map[ny][nx] == -1:
            counted_map[ny][nx] = counted_map[y][x] + 1
            queue.append((ny,nx))

if not reach:
    print(-1)
    exit()
'''
y,x = gy,gx
move_num = counted_map[gy][gx]
while move_num != 0:
    _input[y][x] = 'o'
    for dy,dx in dyx:
        ny = y + dy
        nx = x + dx

        if ny < 0 or nx < 0 or ny >= H or nx >= W:
            continue
        
        if _input[ny][nx] == '.':
            tmp_dist = counted_map[ny][nx]
            if tmp_dist < move_num:
                move_num = tmp_dist
                next_y,next_x = ny,nx
    
    y,x = next_y,next_x

_input[sy][sx] = 'o'
'''

res = 0

for raw in _input:
    for i in raw:
        if i == '.':
            res += 1

print(res-counted_map[gy][gx]-1)
### BUGGY CODE ###

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

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

A.sort()

# print(A)

max_f = 0
min_f = 0

for idx, a in enumerate(A):
    if idx >= K-1:
        max_f += cmb(idx, K-1)*a
        # print("max", cmb(idx, K-1), a)

    if N-(idx+1) >= K - 1:
        min_f += cmb(N-(idx+1), K-1)*a
        # print("min", cmb(N-(idx+1), K-1), a)

print((max_f - min_f) % (10**9+7))

### FIXED CODE ###

import heapq

n, K = map(int, input().split())
A = list(map(int, input().split()))

from operator import mul
from functools import reduce

MOD = 10 ** 9 + 7

def mpow(a, n):
    if n == 0: return 1
    if n == 1: return a % MOD
    if n % 2 == 1: return (a % MOD * mpow(a, n - 1) % MOD) % MOD
    t = mpow(a, n // 2)
    return (t * t) % MOD

fac = [1] * (n + 1)
inv_fac = [1] * (n + 1)
for i in range(n):
    fac[i + 1] = (fac[i] * (i + 1)) % MOD
inv_fac[n] = mpow(fac[n], MOD - 2)
for i in range(n, 0, -1):
    inv_fac[i - 1] = (inv_fac[i] * i) % MOD

def cmb(n, r):
    if n == 0 and r == 0: return 1
    if n < r or n < 0: return 0
    return (fac[n] * (inv_fac[r] * inv_fac[n - r]) % MOD) % MOD

A.sort()

# cmb_list = {}
# cmb_list[(K - 1, K - 1)] = cmb(K - 1, K - 1)
# for i in range(K, n):
#     cmb_list[(i, K-1)] = cmb_list[(i-1, K-1)] * i // (i - (K - 1))

max_f = 0
min_f = 0

for idx in range(n):
    a = heapq.heappop(A)
    if idx >= K - 1:
        max_f += cmb(idx, K - 1) * a
        # print("max", cmb(idx, K-1), idx, K-1, a)

    if n - (idx + 1) >= K - 1:
        min_f += cmb(n - (idx + 1), K - 1) * a
        # print("min", cmb(N-(idx+1), K-1), N-(idx+1), K-1, a)

print((max_f - min_f) % (10**9+7))
### BUGGY CODE ###

S = 1
for c in input():
    if c == 'S':
        S = S << 1 | 1
    else:
        if S > 1 and S & 1:
            S >>= 1
        else:
            S = S << 1 | 0
print(len(bin(S)) - 3)

### FIXED CODE ###

T, S = 0, 0
for c in input():
    if c == 'S':
        S += 1
    else:
        if S:
            S -= 1
        else:
            T += 1
print(T + S)
### BUGGY CODE ###

def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

INF = float("inf")

N, M, L = map(int, input().split())
E = [[INF] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a - 1][b - 1] = E[b - 1][a - 1] = c


E = WarshallFloyd(E)

for i in range(N):
    for j in range(N):
        if E[i][j] <= L:
            E[i][j] = 1
        else:
            E[i][j] = INF

E = WarshallFloyd(E)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    a = E[s - 1][t - 1] - 1
    print(-1 if a == INF else a)


### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall

N, M, L = map(int, input().split())
E = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a - 1][b - 1] = E[b - 1][a - 1] = c

E = floyd_warshall(E)

for i in range(N):
    for j in range(N):
        E[i][j] = (E[i][j] <= L)

E = floyd_warshall(E)

INF = float("inf")

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    a = E[s - 1][t - 1] - 1
    print(-1 if a == INF else int(a))
### BUGGY CODE ###

N = int(input())
h = [int(x) - 1 for x in input().split()]
a = [int(x) for x in input().split()]

l2N = 0
n = N
while n > 1:
    n = -(-n//2)
    l2N += 1
N = 2**l2N

seg = [0] * (2 * 2**l2N - 1)

def update(H, x):
    H += 2**l2N - 1
    seg[H] = x
    while H > 0:
        H = (H - 1) // 2
        seg[H] = max(seg[H*2+1], seg[H*2+2])

def maxSrch(a, b, k, l, r):
    if r <= a or b <= l:
        return 0
    if a <= l and r <= b:
        return seg[k]
    else:
        vl = maxSrch(a, b, k*2+1, l, (l+r)//2)
        vr = maxSrch(a, b, k*2+2, (l+r)//2, r)
        return max(vl, vr)

for H,A in zip(h,a):
    update(H, maxSrch(0,H,0,0,N) + A)
print(seg[0])

### FIXED CODE ###

N = int(input())
h = [int(x) - 1 for x in input().split()]
a = [int(x) for x in input().split()]

l2N = 0
n = N
while n > 1:
    n = -(-n//2)
    l2N += 1
N = 2**l2N

seg = [0] * (2 * 2**l2N - 1)

def update(H, x):
    H += 2**l2N - 1
    seg[H] = x
    while H > 0:
        H = (H - 1) // 2
        seg[H] = max(seg[H*2+1], seg[H*2+2])

def maxSrch(a, b, k, l, r):
    if r <= a or b <= l:
        return 0
    if a <= l and r <= b:
        return seg[k]
    else:
        vl = maxSrch(a, b, k*2+1, l, (l+r)//2)
        vr = maxSrch(a, b, k*2+2, (l+r)//2, r)
        return max(vl, vr)

for H,A in zip(h,a):
    update(H, maxSrch(0,H,0,0,N) + A)
print(seg[0])
### BUGGY CODE ###

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

A.sort(reverse=True)
ans = []

BC_ans = []

for eb in B:
    for ec in C:
        BC_ans.append(eb+ec)
BC_ans.sort(reverse=True)
BC_ans = BC_ans[:K]
for ea in A[:K]:
    for ebc in BC_ans:
        ans.append(ea+ebc)
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
    
    



### FIXED CODE ###

X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse=True)
ans = []
BC_ans = []
for eb in B:
    for ec in C:
        BC_ans.append(eb+ec)
BC_ans.sort(reverse=True)
BC_ans = BC_ans[:K]
for ea in A[:K]:
    for ebc in BC_ans:
        ans.append(ea+ebc)
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

lenght = int(input())
 
x = list(map(int,input().split()))
 
for i in range(lenght-1):
  x[i+1] = x[i] * x[i+1]
if x[-1] > 1e18:
  x[-1] = -1
print(x[-1])

### FIXED CODE ###

lenght = int(input())
 
x = list(map(int,input().split()))
x.sort(reverse=True)
check = False

if x[-1]==0:
  print(0)
else:
  first_value = 1
  for val in x:
    first_value *= val
    if first_value > 1e18:
      check=True
      break
  if check:
    print(-1)
  else:
  	print(first_value)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 998244353
    
    dp0 = [[0]*(s+1) for _ in range(n+1)]
    dp1 = [[0]*(s+1) for _ in range(n+1)]
    dp2 = [[0]*(s+1) for _ in range(n+1)]
    dp0[0][0] = 1
    
    for i in range(n):
        for j in range(s+1):
            dp0[i+1][j] += dp0[i][j]
            dp1[i+1][j] += dp1[i][j]
            dp2[i+1][j] += dp2[i][j]
            
            
            if a[i]+j <= s:
                dp1[i+1][j+a[i]] += dp0[i][j] * (i+1)
                dp2[i+1][j+a[i]] += dp0[i][j] * (i+1) * (n-i)
                
                dp1[i+1][j+a[i]] += dp1[i][j]
                dp2[i+1][j+a[i]] += dp1[i][j] * (n-i)
                
            dp0[i+1][j] %= mod
            dp1[i+1][j] %= mod
            dp2[i+1][j] %= mod
                
    print(dp2[n][s])
    
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 998244353
    
    dp0 = [[0]*(s+1) for _ in range(n+1)]
    dp1 = [[0]*(s+1) for _ in range(n+1)]
    dp2 = [[0]*(s+1) for _ in range(n+1)]
    dp0[0][0] = 1
    
    for i in range(n):
        for j in range(s+1):
            dp0[i+1][j] += dp0[i][j]
            dp1[i+1][j] += dp1[i][j]
            dp2[i+1][j] += dp2[i][j]
            
            
            if a[i]+j <= s:
                dp1[i+1][j+a[i]] += dp0[i][j] * (i+1)
                dp2[i+1][j+a[i]] += dp0[i][j] * (i+1) * (n-i)
                
                dp1[i+1][j+a[i]] += dp1[i][j]
                dp2[i+1][j+a[i]] += dp1[i][j] * (n-i)
                
            dp0[i+1][j] %= mod
            dp1[i+1][j] %= mod
            dp2[i+1][j] %= mod
                
    print(dp2[n][s])
    
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

s=input()
def roopR(l,n):
  if list[k]==1:
    for p in range(a):
      if list[l]==-1:
        if n%2==0:
          return l
        else:
          return l-1
      else:
        l += 1
        n += 1
  else:
    for q in range(a):
      if list[l]==1:
        if n%2==0:
          return l
        else:
          return l+1
      else:
        l -= 1
        n += 1

a=len(s)
endlist=[]
list=[]
for i in range(a):
  if s[i]=='R':
    list.append(1)
  else:
    list.append(-1)
for j in range(a):
  endlist.append(0)
for k in range(a):
  b=roopR(k,0)
  endlist[b] += 1
print(*endlist)

### FIXED CODE ###

S=input()
dp=[0]*len(S)
a=0
for i in range(len(S)):
  if S[i]=='R':
    a+=1
  else:
    dp[i]+=a//2
    dp[i-1]+=a-a//2
    a=0
for i in range(len(S)-1,-1,-1):
  if S[i]=='L':
    a+=1
  else:
    dp[i]+=a//2
    dp[i+1]+=a-a//2
    a=0
print(*dp)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=""
for i in range(1,n+1):
  for j in range(n):
    if a[j]==i:
      ans+=str(j+1)+' '
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(0,n):
  b[a[i]-1]=i+1
ans=''
for i in range(n):
  ans+=str(b[i])+' '
print(ans)
### BUGGY CODE ###

import sys
import math
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

@lru_cache(maxsize=None)
def solve(x, y, z):
    x2 = math.gcd(x, y)
    return math.gcd(x2, z)

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

    ans = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for k in range(1, N + 1):
                x = [i, j, k]
                x.sort()
                ans += solve(x[0], x[1], x[2])

    print(ans)



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


@lru_cache(maxsize=None)
def solve(x, y):
    return math.gcd(x, y)


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

    ans = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            x = math.gcd(i, j)
            for k in range(1, N + 1):
                ans += math.gcd(x, k)

    print(ans)


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

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
  a_max = max(a)
for j in range(n):
  if a[j] != a_max:
    print(a_max)
  else:
    b = sorted(a)
    print(b[n-2])

### FIXED CODE ###

n = int(input())
a = [0 for n in range(n)]
for i in range(n):
  a[i] = int(input())
a_max = max(a)
b = sorted(a)
a_second = b[n-2]
for j in range(n):
  if a[j] != a_max:
    print(a_max)
  else:
    print(a_second)
### BUGGY CODE ###

S = list(input())

i = 0
answer = 0

def back_check(S, m, answer):
	for i in range(m, 0, -1):
		m_color = S[i-1]
		n_color = S[i]
		if m_color == 'B' and n_color == 'W':
			S[i-1] = 'W'
			S[i] = 'B'
			answer += 1
		else:
			break

	return S, answer

while i < len(S)-1:
	i_color = S[i]
	j_color = S[i+1]
	if i_color == 'B' and j_color == 'W':
		S[i] = 'W'
		S[i+1] = 'B'
		answer += 1
		S, answer = back_check(S, i, answer)

	i += 1

print(answer)

### FIXED CODE ###

S = list(input())

i = 0
answer = 0
b_count = 0

while i < len(S)-1:
	i_color = S[i]
	j_color = S[i+1]
	if i_color == 'B' and j_color == 'B':
		b_count += 1
	elif i_color == 'B' and j_color == 'W':
		S[i] = 'W'
		S[i+1] = 'B'
		answer = answer + b_count + 1
	else:
		b_count = 0

	i += 1

print(answer)
### BUGGY CODE ###

num = (int)(input())
button = []
for i in range(num):
  button.append(list(map(int, input().split(" "))))
count = 0
for i in range(num - 1, -1, -1):
  #print(button)
  while(button[i][0] % button[i][1] != 0):
    for j in range(i, -1, -1):
      button[j][0] += 1
    count += 1
print(count)

### FIXED CODE ###

num = (int)(input())
button = []
for i in range(num):
  button.append(list(map(int, input().split(" "))))
count = 0
for i in range(num - 1, -1, -1):
  button[i][0] += count
  tasu = button[i][1] - (button[i][0] % button[i][1]) if button[i][0] % button[i][1] != 0 else 0
  #print(tasu, count)
  count += tasu
print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split(" ")))
 
ans = 0
den = int(1e9 + 7)
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        ans = (ans + (a[i] * a[j]) % den) % den

print(ans)

### FIXED CODE ###

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

ans = 0
den = int(1e9 + 7)
sum_a = [0 for i in range(len(a))]
sum_a[-1] = a[-1]
for i in range(len(a) - 1, 1, -1):
    sum_a[i - 1] = sum_a[i] + a[i - 1]
for i in range(len(a) - 1):
    ans = (ans + a[i] * sum_a[i + 1]) % den

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

import heapq
import sys

input = sys.stdin.readline


class AtCoder:
    def __lt__(self, other):
        return self[0] < other[0]

    def main(self):
        N, K = map(int, input().split())
        A = list(map(int, input().split()))
        F = list(map(int, input().split()))

        A.sort()
        F.sort(reverse=True)

        hq = []
        heapq.heapify(hq)
        for i in range(N):
            heapq.heappush(hq, (-1 * A[i] * F[i], (F[i], A[i])))

        while K > 0:
            score = heapq.heappop(hq)
            if score[1][1] == 0:
                print(0)
                exit()
            else:
                if score[1][1] - F[0] > 0:
                    K -= score[1][1] - F[0]
                    new_A = F[0]
                else:
                    K -= 1
                    new_A = score[1][1] - 1
                heapq.heappush(hq, (-1 * new_A * score[1][0], (score[1][0], new_A)))

        print(-1 * heapq.heappop(hq)[0])


# Run main
if __name__ == '__main__':
    AtCoder().main()


### FIXED CODE ###

import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, K = map(int, input().split())
        A = list(map(int, input().split()))
        F = list(map(int, input().split()))

        A.sort()
        F.sort(reverse=True)

        l, r = -1, 10 ** 12
        while l + 1 < r:
            mid = (l + r) // 2

            s = 0
            for i in range(N):
                s += max(0, A[i] - mid // F[i])
            if s <= K:
                r = mid
            else:
                l = mid
        print(r)


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

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

count = n

shakutori = [0] 
for i in range(len(a)):
    shakutori.append(shakutori[i] + a[i])

for l in range(0, n):
    left = a[l]
    for r in range(l + 1,n):

        right = shakutori[r+1] - shakutori[l]

        left ^= a[r]


        if right == left:
            count += 1
print(count)







### FIXED CODE ###

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

count = 0

xor_temp = 0
sum_temp = 0

r = 0
for l in range(n):
    while r < n and xor_temp^a[r]  == sum_temp + a[r]:
        xor_temp ^= a[r]
        sum_temp += a[r]
        r += 1

    xor_temp ^= a[l]
    sum_temp -= a[l]
    count += r - l

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

abk = input().split()
abk2 = []
for ee in abk:

    abk2.append(int(ee))
a, b, k = abk2
for ii in range(k):
    if a > 0:
        a -= 1
    else:
        b -= 1
print(a, b)

### FIXED CODE ###

a, b, k = map(int, input().split())
if a >= k:
    a -= k
    print(a, b)
elif a < k:
    if b >= (k-a):
        b = b - (k - a)
        print(0, b)
    elif b < (k-a):
        print(0, 0)
### BUGGY CODE ###

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

P = [int(_) for _ in input().split()]

for i in range(N):
    P[i] = int(P[i] * (1 + P[i]) / 2) / P[i]

ans = 0
for i in range(N - K+1):
    ans = max(sum(P[i:i + K]),ans)
print(ans)



### FIXED CODE ###

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

P = [int(_) for _ in input().split()]

for i in range(N):
    P[i] = int(P[i] * (1 + P[i]) / 2) / P[i]

ans = 0
tmp = 0
for i in range(N):
    tmp += P[i]
    if i < K - 1: continue
    ans = max(tmp, ans)
    tmp -= P[i - K + 1]
print(ans)
### BUGGY CODE ###

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

ans = ""
for i in sort_a:
    attend = str(a.index(i) + 1) + " "
    ans += attend
    

print(ans)

### FIXED CODE ###

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

ans = [""]*n

for i in range(n):
    x = a[i]
    b = ans[a[i] - 1]
    c = str(i+1)
    ans[a[i]-1] = str(i+1)

print(" ".join(ans))
### BUGGY CODE ###

N=int(input())
D=list(map(int,input().split()))
ans=1
if D[0]!=0:
    print(0)
else:
    for i in range(max(D)-1):
        ans*=D.count(i+1)**D.count(i+2)
        if ans==0:
            break
    print(ans%998244353)

### FIXED CODE ###

n = int(input())
d = list(map(int,input().split()))
 
from collections import Counter
q=Counter(d)

# 例外対応
if q[0]!=1 or d[0]!=0:
  print(0)
  exit()

ans = 1
for i in range(1,max(d)+1):
  ans *= q[i-1]**q[i]
  if ans == 0:
    break
print(ans%998244353)