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

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

mod = int(1e9+7)
def powermod(p,n,mod):
  #if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod


memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)
_LR = [0]*(n+3)
_LCR = [0] * (n+3) # _LCR[k] = (L+C+R)C(k)
_k = [0] * (n+3)
_LR[0] = _LCR[0] = _k[0] = 1

LR = [0]*(n+2) #LR[k] = (L+R)C(k)
LR[0] = 1
#LDR = [0]*(n+2)
#LDDR = [0]*(n+2)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
#LDCR = [0] * (n+2) #最後に*2を忘れないこと
#LDCDR = [0] * (n+2)

for k in range(1,n+2):
  _LR[k] = (_LR[k-1] * (L+R+1-k)) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = (_k[k-1] * powermod(k, mod-2, mod)) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod
#  LDR[k] = LR[k-1]
#  LDDR[k] = LDR[k-1]
  
  LCR[k] = (_LCR[k] * _k[k])%mod - LR[k]
#  LDCR[k] = LCR[k-1]
#  LDCDR[k] = LDCR[k-1]
  #print(LR, LCR)
  print((LR[k] + LR[k-1] + LR[k-2] + LCR[k] + 2*LCR[k-1] + LCR[k-2])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

### FIXED CODE ###

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

mod = int(1e9+7)
def powermod(p,n,mod):
    #if n==0: return 1
    if n==1:
        return p%mod
    if n%2:
        return powermod(p,n//2,mod)**2 * p %mod
    else:
        return powermod(p,n//2,mod)**2 %mod


memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)
_LR = [0]*(n+3)
_LCR = [0] * (n+3) # _LCR[k] = (L+C+R)C(k)
_k = [0] * (n+3)
_LR[0] = _LCR[0] = _k[0] = 1

LR = [0]*(n+2) #LR[k] = (L+R)C(k)
LR[0] = 1
#LDR = [0]*(n+2)
#LDDR = [0]*(n+2)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
#LDCR = [0] * (n+2) #最後に*2を忘れないこと
#LDCDR = [0] * (n+2)

for k in range(1,n+2):
  _LR[k] = (_LR[k-1] * (L+R+1-k)) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = (_k[k-1] * powermod(k, mod-2, mod)) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod
#  LDR[k] = LR[k-1]
#  LDDR[k] = LDR[k-1]
  
  LCR[k] = (_LCR[k] * _k[k])%mod - LR[k]
#  LDCR[k] = LCR[k-1]
#  LDCDR[k] = LDCR[k-1]
  #print(LR, LCR)
  print((LR[k] + LR[k-1] + LR[k-2] + LCR[k] + 2*LCR[k-1] + LCR[k-2])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)
### BUGGY CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce

n = int(input())
a = list(map(int, input().split()))
a.sort()
b = set(a)
ans = 0
for i in b:
    if a.count(i) > i:
        ans += a.count(i) - i
    elif a.count(i) < i:
        ans += a.count(i)
print(ans)


### FIXED CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce

n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a).most_common()
# print(cnt)
ans = 0
for i in cnt:
    if i[0] < i[1]:
        ans += i[1] - i[0]
    elif i[0] == i[1]:
        continue
    else:
        ans += i[1]
print(ans)
### BUGGY CODE ###

import sys

N = int(input())


def query(i):
    print(i)
    s = input()
    if s == 'Vacant':
        print(i)
        sys.exit()
    return s


S = [''] * N
S[0] = query(0)
S[N - 1] = query(N - 1)
l = 0
r = N - 1
while r - l > 0:
    m = (l + r) // 2
    if r - l == 2 and S[l] != S[r]:
        break
    S[m] = query(m)
    if (m - l) % 2 == 0 and S[l] != S[m]:
        r = m - 1
    else:
        l = m + 1
print(m)


### FIXED CODE ###

import sys

N = int(input())

S = [''] * N


def query(i):
    print(i)
    s = input()
    if s == 'Vacant':
        print(i)
        sys.exit()
    S[i] = s
    return s


query(0)
query(N - 1)
l = 0
r = N - 1
while r - l >= 2:
    m = (l + r) // 2
    if r - l == 2 and S[l] != S[r]:
        break
    query(m)
    if (m - l) % 2 == 0 and S[l] != S[m] or (m - l) % 2 == 1 and S[l] == S[m]:
        r = m
    else:
        l = m

for i in range(l, r + 1):
    if S[i] == '':
        print(i)
        break
### BUGGY CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

n,m = ip()
graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = ip()
    graph[a].append(b)
    graph[b].append(a)

start = 1
nodes = list(graph.keys())
q = set()
d,parent,vis = {},{},{}
for i in nodes:
    d[i] = float('inf')
    parent[i] = -1
    q.add(i)
d[start] = 0

while len(q):
    mn = float('inf')
    for v in nodes:
        if d[v] < mn and v in q:
            mn = d[v]
            u = v
    q.remove(u)
    for v in graph[u]:
        if d[u]+1 < d[v] and v in q:
            d[v] = d[u] + 1
            parent[v] = u

if float('inf') in list(d.values()):
    print("No")
    exit()
print("Yes")
for i in range(2,n+1):
    print(parent[i])







### FIXED CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

n,m = ip()
graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = ip()
    graph[a].append(b)
    graph[b].append(a)

parent = {i:-1 for i in range(1,n+1)}
parent[1] = 0
q = [1]
while len(q):
    u = q.pop(0)
    for v in graph[u]:
        if parent[v] == -1:
            q.append(v)
            parent[v] = u

if -1 in list(parent.values()):
    print("No")
    exit()
print("Yes")
for i in range(2,n+1):
    print(parent[i])
### BUGGY CODE ###

N = int(input())
src = list(map(int,input().split()))
ans = 0
for i,a in enumerate(src):
     l = r = 0
     for j in range(i-1,-1,-1):
         if src[j] < a: break
         l += 1
     for j in range(i+1,N):
         if src[j] < a: break
         r += 1
     ans += (l+1)*(r+1)*a
print(ans)

### FIXED CODE ###

import heapq

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

pos = [-1] * N
for i,a in enumerate(A):
    pos[a-1] = i

q = []
heapq.heapify(q)
right = [N] * N
for i,a in enumerate(A):
    while q and -q[0] > a:
        v = -heapq.heappop(q)
        right[v-1] = i
    heapq.heappush(q,-a)

q = []
heapq.heapify(q)
left = [0] * N
for i,a in reversed(list(enumerate(A))):
    while q and -q[0] > a:
        v = -heapq.heappop(q)
        left[v-1] = i+1
    heapq.heappush(q,-a)

ans = 0
for i,(p,l,r) in enumerate(zip(pos,left,right)):
    ans += (p-l+1) * (r-p) * (i+1)
print(ans)
### BUGGY CODE ###

def main():
    import sys
    readline = sys.stdin.readline
    sys.setrecursionlimit(10 ** 7)

    n = int(input())
    *a, = map(int, readline().split())

    def calc(l=0, r=n - 1):
        """[l,r]"""
        if l == r:
            return a[l]

        ret = max(
            a[l] - calc(l + 1, r),
            a[r] - calc(l, r - 1)
        )
        return ret

    ret = calc()

    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

n = int(input())
a = tuple(int(x) for x in input().split())

memo = tuple([None] * n for _ in range(n))
for i, aa in enumerate(a):
    memo[i][i] = aa

for l in range(n - 1, -1, -1):
    for r in range(l, n):
        if memo[l][r] is None:
            memo[l][r] = max(a[r] - memo[l][r - 1], a[l] - memo[l + 1][r])

print(memo[0][n - 1])
### BUGGY CODE ###

S = input()
n = len(S)
count = 0
T = [0] * (n + 1)
mod_dict = {0:0}
count  = 0
for i in reversed(range(n)):
    #print(i)
    T[i] = T[i+1] + int(S[i]) * (10 ** (n - i - 1))
    # print("Num : " + str(T[i]))
    mod = T[i] % 2019
    # print("Mod : " + str(mod))
    if(mod in mod_dict.keys()):
        # mod_dict[mod] = mod_dict[mod] + 1
        count = count + 1
    else:
        mod_dict[mod] = 0
print(count)
#print(sum(mod_dict.values()))

### FIXED CODE ###

reverse_S = input()[::-1]
n = len(reverse_S)
count = 0
mod = 0
mods = [0] * 2019
mods[0] = 1
x = 1
for s in reverse_S:
    mod = (mod + (int(s) * x)) % 2019
    mods[mod] = mods[mod] + 1
    x = x * 10
    x = x % 2019

for v in mods:
    count = count + v*(v-1)//2

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

a,b,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = [tuple(map(int,input().split())) for i in range(m)]
p = []
x = 0
p.append(min(a)+min(b))
for ka,ai in enumerate(a):
    for kb,bi in enumerate(b):
        for t in c:
            if t[0]==ka+1 and t[1]==kb+1:
                x = t[2]
                p.append(ai+bi-x)
print(min(p))

### FIXED CODE ###

a,b,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = [tuple(map(int,input().split())) for i in range(m)]
p = min(a)+min(b)
for t in c:
    p = min(p,a[t[0]-1]+b[t[1]-1]-t[2])
print(p)
### BUGGY CODE ###

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

for i in range(a[0]+1):
    ans = [i*2]
    diff = i

    for rep2 in range(1, n-1):
        dam = a[rep2] - diff
        ans += [dam*2]
        diff = dam
        if diff < 0:
            break

    if a[-1] - ans[-1]//2 == a[0]-i:
        print(*([(a[0]-i)*2] + ans))
        exit()

### FIXED CODE ###

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

ans = [0] * (n + 1)
ans[0], ans[1] = a[0] * 2, 0
temp = 0
for num, con in enumerate(a[1:]):
    temp += con
    ans[num+2] = temp * 2
    temp *= -1

diff = (ans[-2] + ans[0]) // 2 - a[-1]

sign = -1
for i in range(n):
    ans[i] += sign * diff
    sign *= -1

print(*ans[:-1])
### BUGGY CODE ###

a=1000000007

m,n=[int(i) for i in input().split(" ")]
print((m**n)%a)

### FIXED CODE ###

from functools import lru_cache
mod=1000000007

m,n=[int(i) for i in input().split(" ")]

@lru_cache()
def power(m,n,mod):
    if n==0:
        return 1
    elif n==1:
        return m
    elif n%2==0:
        return ((power(m,n//2,mod)%mod) * (power(m,n//2,mod)%mod))%mod
    else:
        return (power(m,n-1,mod)*m)%mod

print(power(m,n,mod))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    V=100005
    n=int(input())
    E=[[] for _ in range(V*2)]
    for _ in range(n):
        x,y=map(int,input().split())
        y+=V
        E[x].append(y)
        E[y].append(x)

    visited=[0]*(2*V)
    def dfs(v):
        if(visited[v]): return
        visited[v]=1
        cnt[v//V]+=1
        for nv in E[v]: dfs(nv)

    ans=[0]
    for v in range(2*V):
        if(visited[v]): continue
        cnt=[0]*2 # 連結成分のx,yの個数
        dfs(v)
        ans[0]+=cnt[0]*cnt[1]
    print(ans[0]-n)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    V=100005
    n=int(input())
    E=[[] for _ in range(V*2)]
    for _ in range(n):
        x,y=map(int,input().split())
        y+=V
        E[x].append(y)
        E[y].append(x)

    visited=[0]*(2*V)
    def dfs(v):
        if(visited[v]): return
        visited[v]=1
        cnt[v//V]+=1
        for nv in E[v]: dfs(nv)

    ans=[0]
    for v in range(2*V):
        if(visited[v]): continue
        cnt=[0]*2 # 連結成分のx,yの個数
        dfs(v)
        ans[0]+=cnt[0]*cnt[1]
    print(ans[0]-n)
resolve()
### BUGGY CODE ###

S = input()
Q = int(input())

for _ in range(Q):
    q = input().split(" ")
    if q[0] == "1":
        S = ''.join(list(reversed(S)))
    else:
        if q[1] == "1":
            S = q[2] + S
        else:
            S += q[2]

print(S)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

is_reversed = False

S = deque(S)

for _ in range(Q):
    q = input().split(" ")
    if q[0] == "1":
        is_reversed = not is_reversed
    else:
        if q[1] == "1":
            if is_reversed:
                S.append(q[2])
            else:
                S.appendleft(q[2])
        else:
            if is_reversed:
                S.appendleft(q[2])
            else:
                S.append(q[2])

S = list(S)
if is_reversed:
    S = ''.join(list(reversed(S)))
else:
    S = ''.join((S))

print(S)
### BUGGY CODE ###

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

import heapq
import collections

a_all = []
for i in range(n):
    a_all.append(ab[i][0])

key_all = list(set(a_all))
key_all.sort()

d = dict()
for k in key_all:
    d[k] = []

for i in range(n):
    a = ab[i][0]
    b = ab[i][1]
    d[a].append(b)



ans = 0
l = []
import bisect

for i in range(1, m+1):
    if i in key_all:
        for v in d[i]:
            bisect.insort(l, v)

    # print(l)

    if l != []:
        ans += l[-1]
        l.pop()
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

import heapq
import collections

a_all = []
for i in range(n):
    a_all.append(ab[i][0])

key_all = list(set(a_all))
key_all.sort()

d = dict()
for k in key_all:
    d[k] = []

for i in range(n):
    a = ab[i][0]
    b = ab[i][1]
    d[a].append(b)

ans = 0
l = []
for i in range(1, m+1):
    if key_all != []:
        if i == key_all[0]:
            for v in d[i]:
                heapq.heappush(l, -1 * v)

            heapq.heappop(key_all)

    if l != []:
        ans += heapq.heappop(l) * -1

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

import math
n = int(input())
a = list(map(int,input().split()))
g = a[0]
mod = 10**9 + 7
for i in range(1,n):
    g = (g*a[i])//math.gcd(g,a[i])
ans = 0
for i in range(n):
    ans += g//a[i]
    ans %= mod
print(ans)

### FIXED CODE ###

import math
n = int(input())
a = list(map(int,input().split()))
g = 1
mod = 10**9 + 7
ans = 0
for i in range(n):
    u = (g*a[i])//math.gcd(g,a[i])
    ans *= u//g
    ans %= mod
    ans += u//a[i]
    ans %= mod
    g = u
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(N-1):
    while A[i] > A[i+1]:
        A[i + 1] = A[i + 1] + 1
        count += 1
print(count)

### FIXED CODE ###

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

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

tmp = [0]*N

for i in range(N):
    genzaichi = 0
    count = 0
    tmp = A[:i] + A[i+1:]
    for j in tmp:
        count += abs(genzaichi- j)
        genzaichi = j
    count += abs(genzaichi)
    print(count)

### FIXED CODE ###

N = int(input())
A = [0]+list(map(int, input().split()))+[0]

A_sum = sum([abs(a1-a2) for a1, a2 in zip(A, A[1:])])

for i in range(1,N+1):
    print(A_sum + abs(A[i-1]-A[i+1]) - (abs(A[i-1]-A[i]) + abs(A[i]-A[i+1])))
### BUGGY CODE ###

N = int(input())

for n in range(1, N+1):
  count = 0
  for i in range (1, 101):
    if i*i > n:
      break
    for j in range(1, 101):
      if i*i+j*j > n:
        break
      for k in range(1, 101):
        if i*i+j*j+k*k >n:
          break
        if i*i+j*j+k*k+i*j+j*k+k*i == n:
          count += 1

  print(count)




### FIXED CODE ###

N = int(input())
ans = [0] * (N + 1)
for i in range (1, 101):
  for j in range(1, 101):
    for k in range(1, 101):
      n = i*i+j*j+k*k+i*j+j*k+k*i
      if n <= N:
        ans[n] += 1

print(*ans[1:], sep='\n')
### BUGGY CODE ###

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

cnt = 0
for i in range(N):
    if all([True if P[j] >= P[i] else False for j in range(i+1)]):
        cnt += 1
print(cnt)


### FIXED CODE ###

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

cnt = 0
min_value = N + 1
for i in range(N):
    if P[i] <= min_value:
        cnt += 1
        min_value = P[i]
print(cnt)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
  instructions = list(map(str, input().split()))
  if instructions[0] == '1':
    S = S[::-1]
  else:
    if instructions[1] == '1':
      S = instructions[2] + S
    else:
      S = S + instructions[2]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
t = ''
for i in range(Q):
  instructions = list(map(str, input().split()))
  if instructions[0] == '1':
    S, t = t, S
  else:
    if instructions[1] == '1':
      t += instructions[2]
    else:
      S += instructions[2]
print(t[::-1] + S)
### BUGGY CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print(' '.join(map(str,a)))
main()

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>=n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print(' '.join(map(str,a)))
main()
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    H = [int(input()) for i in range(N)]
    H.sort()
    mi = 10**9
    for i in range(N - K + 1):
        h_ = H[i:i+K]
        if max(h_) - min(h_) < mi:
            mi = max(h_) - min(h_)
    print(mi)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    H = [int(input()) for i in range(N)]
    H.sort()
    mi = 10**9
    for i in range(N - K + 1):
        diff = H[i+K-1] - H[i]
        if diff < mi:
            mi = diff
    print(mi)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
dy=[0,0,1,-1]
dx=[1,-1,0,0]
m=[[-1]*W for i in range(H)]

from collections import deque
q=deque()
for y in range(H):
  for x in range(W):
    if A[y][x]=='#':
      q.append((y,x))
      m[y][x]=0      
      
def bfs(q,m):
  d=0
  while q:
    y,x=q.popleft()
    d=m[y][x]
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W and m[ny][nx]==-1 and A[ny][nx]!='#':
        q.append((ny,nx))
        m[ny][nx]=m[y][x]+1            
bfs(q,m)
ans=0
for i in range(H):
  for j in range(W):
    ans=max(ans,m[i][j])    
print(ans) 

### FIXED CODE ###

from subprocess import call
call(('pypy3','-c',"""
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
dy=[0,0,1,-1]
dx=[1,-1,0,0]
m=[[-1]*W for i in range(H)]

from collections import deque
q=deque()
for y in range(H):
  for x in range(W):
    if A[y][x]=='#':
      q.append((y,x))
      m[y][x]=0      
      
def bfs(q,m):
  d=0
  while q:
    y,x=q.popleft()
    d=m[y][x]
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W and m[ny][nx]==-1 and A[ny][nx]!='#':
        q.append((ny,nx))
        m[ny][nx]=m[y][x]+1            
bfs(q,m)
ans=0
for i in range(H):
  for j in range(W):
    ans=max(ans,m[i][j])    
print(ans)     
"""))
### BUGGY CODE ###

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

def main():
    S = input()
    T = input()

    if S == T:
        print("Yes")
        exit()

    # ある文字cがsとtで場所が半端に一致していたらNO
    ans = S
    len_s = len(S)
    for i in range(len_s):
        if ans[i] != T[i]:
            c1 = ans[i]
            c2 = T[i]
            ans = ans.replace(c1, "?")
            ans = ans.replace(c2, c1)
            ans = ans.replace("?", c2)

    if ans == T:
        print("Yes")
    else:
        print("No")


def main2():
    S = input()
    T = input()

    if S == T:
        print("Yes")
        exit()

    # ある文字cがsとtで場所が半端に一致していたらNO
    len_s = len(S)
    for i in range(len_s):
        if not S[i] in T:
            continue
        flag1 = False
        flag2 = False
        for j in range(len_s):
            if flag1 and flag2:
                print("No")
                exit()
            if S[i] == T[j]:
                if i == j:
                    flag1 = True
                    continue
                flag2 = True
                continue
    print("Yes")



if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def calc(S, T):
    # 差を計算する
    ans = 0
    for i in range(len(S)):
        if S[i] != T[i]:
            ans += 1
    return ans


def solve():
    s = input()
    S = [moji for moji in s]
    T = input()

    # 文字の置き換えをして、差が減ってなかったら無理？
    
    diff = calc(S, T)
    if diff == 0:
        print("Yes")
        return
    pre_diff = diff

    while True:
        # c1, c2を決める
        for i in range(len(S)):
            if S[i] != T[i]:
                c1 = S[i]
                c2 = T[i]
                break
        
        # 文字を置き換える
        for i in range(len(S)):
            if S[i] == c1:
                S[i] = c2
            elif S[i] == c2:
                S[i] = c1
        
        # 差を計算する
        diff = calc(S, T)
        if diff == 0:
            break
        elif diff < pre_diff:
            pre_diff = diff
            continue
        else:
            print("No")
            return
    print("Yes")





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

N, A, B = map(int, input().split())
round_count = 0

med = N / 2 + 0.5

for i in range(int(1e18)):
    if abs(A - B) % 2 == 0:
        if A > B:
            A = A - 1
            B = B + 1

            if A < 1:
                A = 1
            elif B > N:
                B = N
        else:
            A = A + 1
            B = B - 1

            if A > N:
                A = N
            elif B < 1:
                B = 1
    else:
        Max = max([A, B])
        Min = min([A, B])
        if (Max + Min) / 2 > med:
            A = A + 1
            B = B + 1

            if A > N:
                A = N
            elif B > N:
                B = N
        else:
            A = A - 1
            B = B - 1

            if A < 1:
                A = 1
            elif B < 1:
                B = 1

    round_count = round_count + 1

    if A == B:
        break

print(round_count)

### FIXED CODE ###

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

med = N / 2 + 0.5
Sub = B - A

if (Sub) % 2 == 0:
    round_count = Sub // 2
else:
    round_count = min(A - 1, N - B) + 1 + (Sub - 1) // 2
            
print(round_count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
q = int(input())

p=1000003

for j in range(q):
  x,d,n=(int(i) for i in input().split())

  cnt=0
  data1=1
  for i in range(p-2):
    cnt+=1
    data1*=d
    data1=data1%p
  data2=(x*data1)%p

  data3=1
  for i in range(n):
    data3*=(data2+i)
    data3=data3%p
  
  for i in range(n):
    data3*=d
    data3=data3%p
    
  print(data3)

### FIXED CODE ###

import sys
input = sys.stdin.readline
q = int(input())

p=1000003

flist=[1 for i in range(p)]
for i in range(1,p):
    flist[i]=flist[i-1]*i%p

for i in range(q):
  x,d,n=(int(i) for i in input().split())
  if d==0:
    ans=pow(x,n,p)
  else:
    x=x*pow(d,p-2,p)%p    
    if p<=x+n-1:
      ans=0
    else:
      ans=pow(d,n,p)*flist[x+n-1]*pow(flist[x-1],p-2,p)%p
  print(ans%p)
### BUGGY CODE ###

N, M = map(int, input().split())
from  bisect import bisect_right
inf = float("inf")
A = sorted(list(map(int, input().split())))
BC = sorted([tuple(map(int, input().split())) for _ in range(M)], key=lambda x: -x[1])
ans = 0
cnt = 0
L, R = 0, N
for b, c in BC:
    idx = bisect_right(A[L:R], c)

    if idx == 0:
        ans += sum(A[L:R])
        break
    elif idx < b:
        ans += sum(A[L+idx:R]) + c*idx
        break
    elif idx >= b:
        ans += sum(A[L+idx:R]) + b*c
        tmp = L
        L += b
        R = tmp + idx

    cnt += 1
    if cnt == M:
        ans += sum(A[L:R])

print(ans)



### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
P = [(A[i], 1) for i in range(N)]
for j in range(M):
    B, C = map(int, input().split())
    P.append((C, B))
P.sort(reverse=True)
ans, cnt = 0, N
for v, c in P:
    use = min(c, cnt)
    ans += use*v
    cnt -= use
print(ans)