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

# -*- coding: utf-8 -*-
# E
# 文字列比較をローリングハッシュを用いると高速
# 用いなくてもpypy使わなくえれば通る

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
s = input()[:-1]
# s = list(map(ord, list(input()[:-1])))
# print(s)

lb = 0
ub = n//2 + 1


def check(len):
    # これはTLE
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


def check3(m):
    # これはOK(pypyではなくpython3）
    dic = defaultdict(str)
    # dic = {}
    for i in range(n-m+1):
        s_ = s[i:i+m]
        if s_ in dic.keys():
            if dic[s_]+m<=i:
                return True
        else:
            dic[s_] = i
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod

def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod

    dic = {res: 0}
    # defaultdictが早い
    # dic = defaultdict(int)
    # dic[res] = 0

    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check3(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# E
# 文字列比較をローリングハッシュを用いると高速

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
s = input()[:-1]
# s = list(map(ord, list(input()[:-1])))
# print(s)

lb = 0
ub = n//2 + 1


def check(len):
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod


def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod

    dic = {res: 0}
    # defaultdictが早い
    # dic = defaultdict(int)
    # dic[res] = 0

    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


def check3(m):
    dic = {}
    for i in range(n-m+1):
        s_ = s[i:i+m]
        if s_ in dic.keys():
            if dic[s_]+m<=i:
                return True
        else:
            dic[s_] = i
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check3(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [1]*2 + [0 for _ in range(n-1)]
MOD = 10**9+7
for i in range(1,m):
  if a[i]==a[i-1]+1:
    print(0)
    sys.exit() 
    
for i in range(n-1):
  if i+1 in a:
    dp[i+1] = 0
  dp[i+2] = dp[i]+dp[i+1]
  dp[i+2] %= MOD

print(dp[-1])  


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
hole = [0]*(n+1)
for i in range(m):
  hole[int(input())] = 1

dp = [0]*(n+1)
dp[0] = 1
MOD = 10**9+7
   
for i in range(1,n+1):
  if hole[i]==1:
    dp[i] = 0
  else:
    dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= MOD

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

md=1000003
q=int(input())
for _ in range(q):
    x,d,n=map(int,input().split())
    used=set()
    seki=[]
    tmp=1
    s=x
    for i in range(n):
        tmp=tmp*s%md
        seki+=[tmp]
        s+=d
        if s>md:
            s-=md
        if s==x:
            break
    k,a=divmod(n,i+1)
    ans=pow(tmp,k,md)
    if a:
        ans=ans*seki[a-1]%md

    print(ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

md=10**6+3
n_max = md-1
fac = [1]
for i in range(1, n_max + 1): fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1) % md

def main():
    for _ in range(II()):
        x,d,n=MI()
        if x==0:ans=0
        elif d==0:ans=pow(x,n,md)
        else:
            invd=pow(d,md-2,md)
            x=x*invd%md
            if x+n-1>=md:ans=0
            else:
                ans=fac[x+n-1]*ifac[x-1]*pow(d,n,md)%md
        print(ans)

main()
### BUGGY CODE ###

import math
import sys
sys.setrecursionlimit(2000000)
# import itertools
# import statistics
# import numpy as np
# x = int(input())
a, b, n = list(map(int, input().split()))
# a, b = list(map(int, input().split()))
# sy, sx = map(int, input().split())
# gy, gx = map(int, input().split())

ans = a*n//b - a*(n//b)
count = 0
for i in range(n, int(pow(n, 0.5))-1, -1):
    if ans < a*i//b - a*(i//b):
        ans = a*i//b - a*(i//b)
    elif a*i//b - a*(i//b) == 0:
        count += 1
    if count > 1:
        print(ans)
        exit()

print(ans)


### FIXED CODE ###

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

x = min(b-1, n)
ans = a*x//b - a*(x//b)

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

n, q = [int(_) for _ in input().split()]
w = {}
add = {}
seen = {}
ans_d = {}
for i in range(1, n + 1):
    w[i] = []
    seen[i] = 0
    add[i] = 0
    ans_d[i] = 0
for i in range(n - 1):
    a, b = [int(_) for _ in input().split()]
    w[a].append(b)
    w[b].append(a)
for i in range(q):
    p, x = [int(_) for _ in input().split()]
    add[p] += x

que = [1]
ans_d[1] = add[1]
seen[1] = 1
while len(que) != 0:
    v = que.pop()
    for node in w[v]:
        if seen[node] == 0:
            ans_d[node] = ans_d[v] + add[node]
            que.append(node)
            seen[node] = 1

ans_l = []
for i in range(1, n + 1):
    ans_l.append(str(ans_d[i]))
print(' '.join(ans_l))

### FIXED CODE ###

n, q = [int(_) for _ in input().split()]
w = {}
add = {}
seen = {}
ans_d = {}
for i in range(1, n + 1):
    w[i] = []
    seen[i] = 0
    add[i] = 0
    ans_d[i] = 0
for i in range(n - 1):
    a, b = [int(_) for _ in input().split()]
    w[a].append(b)
    w[b].append(a)
for i in range(q):
    p, x = [int(_) for _ in input().split()]
    add[p] += x

que = [1]
ans_d[1] = add[1]
seen[1] = 1
while len(que) != 0:
    v = que.pop()
    for node in w[v]:
        if seen[node] == 0:
            ans_d[node] = ans_d[v] + add[node]
            que.append(node)
            seen[node] = 1

ans_l = []
for i in range(1, n + 1):
    ans_l.append(str(ans_d[i]))
print(' '.join(ans_l))
### BUGGY CODE ###

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

x = [0, a[0]]
s = [0, a[0]]
for i in range(1, n):
    x.append(x[-1] ^ a[i])
    s.append(s[-1] + a[i])

cnt = 0
for i in range(1, n + 1):
    for j in range(i, n + 1):
        xor = x[j] ^ x[i-1]
        sm = s[j] - s[i-1]
        if xor == sm:
            cnt += 1

print(cnt)


### FIXED CODE ###

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

r = 0
s = 0

ans = 0
for l in range(n):
    while r < n and not (s & a[r]):
        s ^= a[r]
        r += 1
    ans += r - l
    s ^= a[l]

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

n=int(input())
a=list(map(int,input().split()))
ans=1
for i in range(n):
    ans=ans*a[i]
if ans>10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
for i in range(n):
    if a[i]==0:
        ans=0
        break
for i in range(n):
    ans=ans*a[i]
    if ans>10**18:
        print(-1)
        break
else:
    print(ans)
### BUGGY CODE ###

def cul(i,x):
    if tmp[i][x]==-1:
        tmp[i][x]=( cul(i+1,x)*(N-1-i) + cul(i+1,x%a[i]) )%MOD
    return tmp[i][x]

MOD=10**9+7
N,x=map(int,input().split())

a=list(map(int,input().split()))
a.sort(reverse=True)
tmp= [[-1 for j in range(x+1)] for i in range(N)] + [[j for j in range(x+1)]]
for i in range(N-1,-1,-1):
    for j in range(x+1):
        tmp[i][j]=( tmp[i+1][j]*(N-1-i) + tmp[i+1][j%a[i]] )  % MOD

print(tmp[0][x])

### FIXED CODE ###

import math

def cul(i,x):
    if tmp[i][x]==-1:
        tmp[i][x]=( cul(i+1,x)*(N-1-i) + cul(i+1,x%a[i]) )%MOD
    return tmp[i][x]

MOD=10**9+7
N,x=map(int,input().split())

a=list(map(int,input().split()))
a.sort(reverse=True)
tmp= [[-1 for j in range(x+1)] for i in range(N)] + [[j for j in range(x+1)]]

print(cul(0,x))
### BUGGY CODE ###

num = int(input())

value = input().split(" ")

ans = 1
for i in range(num):
    ans *= int(value[i])
    if ans > 10 ** 18:
        ans = -1
    
print(ans)

### FIXED CODE ###

num = int(input())

value = list(map(int, input().split()))

if 0 in value:
    print(0)
    exit()

ans = 1
for i in value:
    ans *= i
    if ans > 10 ** 18:
        print(-1)
        exit()
    
print(ans)
### BUGGY CODE ###

s = input()
mod = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for __ in range(len(s) + 1)]
dp[0][0] = 1
for i, si in enumerate(s):
    if si == '?':
        for n in range(10):
            for j in range(13):
                dp[i+1][(n + j * 10) % 13] += dp[i][j]
    else:
        for j in range(13):
                dp[i+1][(int(si) + j * 10) % 13] += dp[i][j]
    for k in range(13):
      dp[i+1][k] = dp[i+1][k] % mod
print(dp[len(s)][5])


### FIXED CODE ###

s = input()
mod = 10 ** 9 + 7
memo = [0] * (len(s) + 1)
memo[0] = 1
dp = [[0 for _ in range(13)] for __ in range(len(s) + 1)]
dp[0][0] = 1
for i, si in enumerate(s[::-1]):
    memo[i+1] = memo[i] * 10 % 13
    if si == '?':
        for n in range(10):
            a = n * memo[i]
            for j in range(13):
                dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
    else:
        a = int(si) * memo[i]
        for j in range(13):
            dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
print(dp[len(s)][5])
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
  T = input().split()
  if T[0] == "1":
    S = S[::-1]
  else:
    if T[1] == "1":
      S = T[-1] + S
    elif T[1] == "2":
      S = S + T[-1]
print(S)
    

### FIXED CODE ###

flag = True
sen = ""
ushi = ""
S = input()
Q = int(input())
for i in range(Q):
  T = input().split()
  if T[0] == "1" :
    flag = not flag
  else:
    if flag:
      if T[1] == "1":
        sen = T[2] + sen
      else:
        ushi = ushi + T[2]
    else:
      if T[1] == "1":
        ushi = ushi + T[2]
      else:
        sen = T[2] + sen
ans = sen + S + ushi
if flag == False:
  print(ans[::-1])
else:
  print(ans)
### BUGGY CODE ###

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

generate_seq = []


def is_ok(b):
    len_b = len(b)
    if len_b == 1 and b[0] == 1:
        generate_seq.append(1)
        return True

    processing = []
    for idx in range(len_b):
        if b[idx] != idx + 1:
            processing.append(False)
        else:
            b_tmp = b[:]
            del b_tmp[idx]
            processing.append(is_ok(b_tmp))
    if any(processing):
        generate_seq.append(processing.index(True) + 1)
        return True
    return False


result = is_ok(b_list)
if result:
    print('\n'.join(list(map(str, generate_seq))))
else:
    print(-1)


### FIXED CODE ###

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

generate_seq = []


def is_ok(b):
    len_b = len(b)
    if len_b == 1 and b[0] == 1:
        generate_seq.append(1)
        return True

    for idx, val in enumerate(b):
        if idx + 1 < val:
            return False

    processing = []
    for idx in range(len_b):
        if b[idx] != idx + 1:
            processing.append(False)
        else:
            b_tmp = b[:]
            del b_tmp[idx]
            tmp = is_ok(b_tmp)
            if tmp:
                generate_seq.append(idx + 1)
                return True
    return False


result = is_ok(b_list)
if result:
    print('\n'.join(list(map(str, generate_seq))))
else:
    print(-1)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
sum_=1
for i in range(N):
    while sum_ < 10**18:
        sum_ *= a[i]
        if sum_ > 10**18:
            sum_ =-1
        break
print(sum_)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
sum_=1
if 0 in a:
    print (0)
else:
    for i in range(N):
        sum_ *= a[i]
        if sum_> 10**18:
            sum_ =-1
            break
    print(sum_)
### BUGGY CODE ###

import collections
n, k = map(int,input().split())
a = list(map(int, input().split()))
c = collections.Counter(a)
ans = 0
if len(set(a)) <= k:
    print(ans)
    exit()
for i in range(0,k):
    ans += c.most_common()[i][1]
print(n-ans)

### FIXED CODE ###

import collections
n, k = map(int,input().split())
a = list(map(int, input().split()))
c = collections.Counter(a)
ans = 0
cnt = 0
if len(set(a)) <= k:
    print(ans)
    exit()
for  tuple in c.most_common():
    ans += tuple[1]
    cnt += 1
    if cnt == k:
      print(n-ans)
      exit()
### BUGGY CODE ###

import sys
from collections import deque, Counter, defaultdict
from itertools import permutations
import heapq


def resolve():
    N = int(sys.stdin.readline().strip())
    pq = []
    for _ in range(N):
        X, L = map(int, sys.stdin.readline().strip().split())
        heapq.heappush(pq, (X + L, X - L))
    ans = 0
    while pq:
        ans += 1
        right, _ = heapq.heappop(pq)
        if pq:
            _, next_left = min(pq)
            while next_left < right:
                heapq.heappop(pq)
                if not pq:
                    break
                _, next_left = min(pq)

    print(ans)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

import sys
from collections import deque, Counter, defaultdict
from itertools import permutations
import heapq


def resolve():
    N = int(sys.stdin.readline().strip())
    pq = []
    for _ in range(N):
        X, L = map(int, sys.stdin.readline().strip().split())
        heapq.heappush(pq, (X + L, X - L))
    ans = 0
    while pq:
        ans += 1
        right, _ = heapq.heappop(pq)
        if pq:
            _, next_left = pq[0]
            while next_left < right:
                heapq.heappop(pq)
                if not pq:
                    break
                _, next_left = pq[0]

    print(ans)


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

import sys

(n) = map(int, sys.stdin.readline().strip().split())
list_input = list(map(int, input().split()))

# 1の数をカウント
counts_one = list_input.count(1)
if counts_one == 1:
    print(counts_one)
    sys.exit()
elif counts_one > 1:
    print(0)
    sys.exit()

# 全て同じ数字かチェック
counts_same = list_input.count(list_input[0])
if counts_same == n:
    print(0)
    sys.exit()

counts_two = list_input.count(2)

anti_ans = 0
list_a = list_input.copy()
for i in list_input:
    for iloop in range(len(list_a)-1):
        if i == 2 and counts_two == 1:
            break
        if i == 2 and counts_two >= 2:
            anti_ans += 1
            break
        if i != 2 and counts_two >= 2 and i % 2 == 0:
            anti_ans += 1
            break
        if i % list_a[iloop+1] == 0:
            anti_ans += 1
            break
    # a = list_a.pop(0)
    # list_a.append(a)
    list_a.append(list_a.pop(0))
print(len(list_input) - anti_ans)


### FIXED CODE ###

import sys

n = int(input())
list_input = list(map(int, sys.stdin.readline().split()))

list_input.sort()

# 倍数判断用のリストを作成
list_div = [0]*(max(list_input))

for i in list_input:
    # print(i)
    a = list_div[i-1]
    # list_div[i-1::i] = [1]*(len(list_div[i-1::i]))
    list_div[i-1::i] = map(lambda x: x+1, list_div[i-1::i])
    if a == 1:
        pass
    else:
        # list_div[i-1] = 0
        pass

ans = 0
for i in list_input:
    if list_div[i-1] == 1:
        ans += 1

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

import copy
import numpy as np

H, W = map(int, input().split())
state = np.array([list(input()) for _ in range(H)])


def light(row, col, state):
    lighted_count = 0
    col1 = copy.copy(col)
    next = '.'
    while next == '.':
        lighted_count += 1
        col1 += 1
        if col1 >= W:
            break
        next = state[row, col1]
    
    col2 = copy.copy(col)
    next = '.'
    while next == '.':
        lighted_count += 1
        col2 -= 1
        if col2 < 0:
            break
        next = state[row, col2]

    row1 = copy.copy(row)
    next = '.'
    while next == '.':
        lighted_count += 1
        row1 += 1
        if row1 >= H:
            break
        next = state[row1, col]

    row2 = copy.copy(row)
    next = '.'
    while next == '.':
        lighted_count += 1
        row2 -= 1
        if row2 < 0:
            break
        next = state[row2, col]

    lighted_count -= 3
    return lighted_count



def blank_fun(state):
    blank_list = []
    for i, item in np.ndenumerate(state):
        if item == '.':
            blank_list.append(i)
    return blank_list


blank_list = blank_fun(state)
blank_count = 0
for blank in blank_list:
    row = blank[0]
    col = blank[1]
    blank_count_now = light(row, col, state)

    if blank_count_now > blank_count:
        blank_count = blank_count_now


print(blank_count)






### FIXED CODE ###

import copy
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
S = [[1 if a == '.' else 0 for a in list(input())]  for _ in range(H)]

def main():
    R = copy.deepcopy(S)
    for h in range(H):
        s = 0
        for w in range(W):
            if R[h][w] == 1:
                s += 1
                R[h][w] = s
            else:
                s = 0
        l = 0
        for w in range(W-1, -1, -1):
            if R[h][w] > 0:
                l = max(l, R[h][w])
                R[h][w] = l
            else:
                l = 0

    L = copy.deepcopy(S)
    for w in range(W):
        s = 0
        for h in range(H):
            if L[h][w] == 1:
                s += 1
                L[h][w] = s
            else:
                s = 0
        l = 0
        for h in range(H-1, -1, -1):
            if L[h][w] > 0:
                l = max(l, L[h][w])
                L[h][w] = l
            else:
                l = 0
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, L[h][w]+R[h][w]-1)
    print(ans)

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

n,m = list(map(lambda x: int(x), input().split()))

jobs = []
for i in range(n):
    jobs.append(list(map(lambda x: int(x), input().split())))

# 貪欲解法
# 最終日から決める
jobs.sort()
selected = []
ans = 0
for i in range(m+1):
    # 振込までi+1日以内の仕事のうち最大の仕事を選び働く
    max_reward = 0
    max_job = -1
    for j in range(n):
        if jobs[j][0] < i+1:
            if max_reward <= jobs[j][1]:
                max_reward = max([max_reward, jobs[j][1]])
                max_job = j
        else:
            break
    ans += max_reward
    if max_job != -1:
        jobs[max_job][1] = 0

print (ans)

### FIXED CODE ###

import heapq

n,m = list(map(lambda x: int(x), input().split()))

jobs = {}
for i in range(n):
    a,b = list(map(lambda x: int(x), input().split()))
    if a in jobs.keys():
        jobs[a].append(b)
    else:
        jobs[a] = [b]

# 貪欲解法
# 最終日から決める
ans = 0
day = m

possible_job = []
# heapqでjobを管理すれば現時点で最大の給与を得ることのできる仕事を容易に取り出せる
for i in range(m+1):
    if i in jobs.keys():
        for x in jobs[i]:
            heapq.heappush(possible_job, -1 * x)
    if len(possible_job)>0:
        day_work = heapq.heappop(possible_job)
        ans += -1 * day_work
    
print (ans)
### BUGGY CODE ###

from fractions import gcd
N,A,B,K=map(int,input().split())
mod=998244353

Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

inverseFactorial=[1]*(N+1)
inverseFactorial[N]=power(Factorial[N],mod-2)
for i in range(0,N)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def f(i,j):
  if i>j:
    i,j=j,i
  res=0
  if j<=N:
    for k in range(max(0,i+j-N),i+1):
      res+=Factorial[N]*inverseFactorial[i-k]*inverseFactorial[j-k]*inverseFactorial[k]*inverseFactorial[N-i-j+k]
  return res%mod
      
ans=0
g=gcd(A,B)
if K%g==0:
  A,B,K=A//g,B//g,K//g
else:
  print(0)
  exit()
for i in range(K//A+1):
  if (K-A*i)%B==0:
    x0=i
    y0=(K-A*i)//B
    break
m=0
while y0-A*m>=0:
  ans+=f(x0+B*m,y0-A*m)
  ans%=mod
  m+=1
    
print(ans%mod)

  

### FIXED CODE ###

N,A,B,K=map(int,input().split())
mod=998244353

Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

inverseFactorial=[1]*(N+1)
inverseFactorial[N]=power(Factorial[N],mod-2)
for i in range(0,N)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y:
    return 0
  return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod
      
ans=0  
for i in range(K//A+1):
  if (K-A*i)%B==0:
    j=(K-A*i)//B
    ans+=comb(N,i)*comb(N,j)
    ans%=mod
  

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

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

l = a.copy()

a.sort()
ans = 0
i = 0
while True:
    cnt = 0
    while a[i + cnt] == a[i]:
        cnt += 1
        if i + cnt == n:
            break
    ans += cnt*(cnt - 1)//2
    i += cnt
    if i == n:
        break

for i in range(n):
    num = l[i]
    del l[i]
    ac = l.count(num)
    print(ans + (ac*(ac - 1) - ac*(ac + 1))//2)
    l.insert(0, num)

### FIXED CODE ###

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

d = Counter(a)
key = d.keys()
ans = 0
for i in key:
    ans += (d[i]*(d[i]  - 1))//2

for i in a:
    print(ans - d[i] + 1)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
s=[1]
for i in range(n):
  s.append(s[-1]*a[i])
for i in range(k+1,n+1):
  if s[i]/s[i-k]>s[i-1]/s[i-1-k]:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(k,n):
  if a[i]/a[i-k]>1:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]

l = []
for i in range(K):
    for j in range(LR[i][1] - LR[i][0] + 1):
        l.append(LR[i][0] + j)

dp = [0] * N
dp[0] = 1
for i in range(N):
    for j in range(len(l)):
        if i + l[j] < N:
            dp[i + l[j]] += dp[i]

print(dp[N - 1] % 998244353)


### FIXED CODE ###

N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]


mod = 998244353
dp = [0] * (N + 1)
dpsum = [0] * (N + 1)
dp[1] = 1
dpsum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - LR[j][1], 1)
        ri = i - LR[j][0]
        if ri < 0:
            continue
        dp[i] += dpsum[ri] - dpsum[li - 1]
        dp[i] %= mod
    dpsum[i] = dpsum[i - 1] + dp[i]

print(dp[N])
### BUGGY CODE ###

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

for i in range(M):
  b, c = map(int, input().split())
  A.extend([c]*b)
A.sort(reverse=True)
ans = sum(A[:N])
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
table = []
for i in range(N):
  table.append((A[i],1))
for i in range(M):
  b,c = map(int, input().split())
  table.append((c,b))
table.sort()
count = 0
ans = 0
while True:
  c, b = table.pop()
  if b <= N - count:
    ans += c*b
    count += b
  else:
    ans += (N-count)*c
    break
print(ans)