Harryxun/stf_run huggingface dataset:
from collections import deque
s = input()
k = int(input())
a = ord("a")codefestival
100
l = deque(list())
l1 = []
for i in range(len(s)):
    s1 = s[i]
    l.append(((a+26)-ord(s1))%26)
while k!=0:
    if len(l)!=0:
        t = l.popleft()
        if k>=t:
            l1.append("a")
            k -= t
        else:
            l1.append(chr(ord('a')-t+26))
    else:
        l1[-1] = chr(int(ord(l1[-1])+k))
        k = 0
print(''.join(l1))

### FIXED CODE ###

from collections import deque
s = input()
k = int(input())
a = ord("a")
l = deque(list())
l1 = []
for i in range(len(s)):
  s1 = s[i]
  l.append(((a+26)-ord(s1))%26)
#print(l)
while k!=0:
    if len(l)!=0:
        t = l.popleft()
        if k>=t:
            l1.append("a")
            k -= t
        else:
          if t=="a":
            l1.append(t)
          else:
            l1.append(chr((ord('a')-t+26)))
    else:
      k %= 26
      l1[-1] = chr(int(ord(l1[-1])+k))
      k = 0
l2 = []
if len(l)>=1:
  for t in l:
    t %= 26
    if t==0:
      l2.append("a")
    else:
      l2.append(chr((ord('a')-t+26)))
  l1 += l2
print("".join(l1))
s = set()
n = int(input())
for _ in range(n):
  x = int(input())
  if x in s:
    s.remove(x)
  else:
    s.add(x)
    
print(len(x))

### FIXED CODE ###

s = set()
n = int(input())
for _ in range(n):
    x = int(input())
    if x in s:
        s.remove(x)
    else:
        s.add(x)

print(len(s))
s,t=input(),input();l,m=len(s),len(t)
for i in range(l-m+1):
 if all(c in"?"+d for c,d in zip(S[-i-m:],t)):s=s.replace(*"?a");exit(print(s[:-i-m]+t+s[l-i:]))
print("UNRESTORABLE")

### FIXED CODE ###

import re
s, t = input().replace('?', '.'), input()
l, m = len(s), len(t)

if l < m:
    print("UNRESTORABLE")
    exit()

can = []  # candidates
for i in range(l - m + 1):
    if re.match(s[i:i + m], t):
        can.append((s[:i] + t + s[i + m:]).replace('.', 'a'))
print(min(can) if can else "UNRESTORABLE")
# -*- coding: utf-8 -*-
import collections


N = int(input())

i = 0
W = []
while i < N:
    W.append(str(input()))
    i += 1

for i in range(len(W)):
    if W[i][-1] != W[i+1][0]:
        print('No')
        break

c = collections.Counter(W)

if c.values() in range(2, N+1):
    print('No')

else:
    print('Yes')

### FIXED CODE ###

def abc112_b():
    n, limit_time = map(int, input().split())
    ans = 1001

    for _ in range(n):
        cost, time = map(int, input().split())

        if time <= limit_time and ans > cost:
            ans = cost

    return ans if ans != 1001 else "TLE"


def abc109_b():
    length = int(input())
    word_list = []

    for _ in range(length):
        word_list.append(input())

    for i in range(len(word_list) - 1):

        if word_list.count(word_list[i]) >= 2 or word_list[i][-1] != word_list[i+1][0]:
            return "No"

    return "Yes"


if __name__ == '__main__':
    print(abc109_b())
N = int(input())
A = list(map(int, input().split()))
ans = [0] * N
for i in range(N):
  ans[A[i] - 1] += 1
for i in range(N):
  print(ans[i])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [0] * N
for i in range(N-1):
  ans[A[i] - 1] += 1
for i in range(N):
  print(ans[i])
import numpy as np
n = int(input())
a = list(map(int, input().split()))
ans = np.prod(a)
if ans > 10**18:
    print(-1)
else :
    print(ans)


### FIXED CODE ###

n = input()
a = list(map(int, input().split()))
if 0 in a:
  print(0)
  exit()
ans = 1
for x in a:
  ans *= x
  if ans > 10**18:
    print(-1)
    exit()
print(ans)
n, x = map(int, input().split())

done = [[False] * (x+1) for _ in range(n+1)]
memo = [[0] * (x+1) for _ in range(n+1)]
for i in range(0, n+1):
	done[i][0] = True
memo[0][1] = 1
done[0][1] = True

def cnt(n, x):
	if not done[n][x]:
		done [n][x] = True
		if x<2**(n+1)-1:
			memo[n][x] = cnt(n-1, x-1)
		elif 2**(n+1)-1 <= x < 2**(n+2)-3:
			memo[n][x] = cnt(n-1, 2**(n+1)-3) + 1 + cnt(n-1, x-2**(n+1)+1)
		else:
			memo[n][x] = cnt(n-1, 2**(n+1)-3) + 1 + cnt(n-1, x-2**(n+1))
	return memo[n][x]

print(cnt(n, x))

### FIXED CODE ###

def cnt(n, x):
	if x==0:
		return 0
	elif n==0:
		return 1
	elif x<2**(n+1)-1:
		return cnt(n-1, x-1)
	elif x==2**(n+1)-1:
		return 2**n
	elif x<2**(n+2)-3:
		return cnt(n-1, 2**(n+1)-3) + 1 + cnt(n-1, x-2**(n+1)+1)
	else:
		return 2**(n+1)-1

n, x = map(int, input().split())
print(cnt(n, x))
import math
S = int(input())
h = math.floor(S/3600)
m = (S - h)/60
s = S - h - m
print(h + ":" + m + ":" + s)

### FIXED CODE ###

S = int(input())
h = (S//3600)
m = (S - (h*3600))//60
b = S - (h*3600) - (m*60)
print(str(h)+":" +str(m) + ":" + str(b))
a, b, c=input().split()
print(a, b, c)

### FIXED CODE ###

a, b, c=input().split(',')
print(a, b, c)
import numpy as np
import math

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

c = int(B/C) - int((A-1)/C)
d = int(B/D) - int((A-1)/D)

CD = C * D / math.gcd(C, D)
cd = int(B/CD) - int((A-1)/CD)

ans = B - (A-1) - (c + d - cd)

print(ans)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

c = B//C - (A-1)//C
d = B//D - (A-1)//D

CD = C * D // gcd(C, D)
cd = B//CD - (A-1)//CD

ans = B - (A-1) - (c + d - cd)
print(ans)
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
c=''
x=0
for i in a:
  x+=1
  b[i-1]=x
for j in b:
  c+=j
  c+=' '
print(c[:-1])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
c=''
x=0
for i in a:
  x+=1
  b[i-1]=x
for j in b:
  c+=str(j)
  c+=' '
print(c[:-1])
import gcc

def gcd(a,b):
    if a<b:
        c=a;
        a=b;
        b=c;
    c=a%b

    if c==0:
        return b
    else:
        return gcc.gcd(b,c)

def lcm(a,b):
    c=gcd(a,b);
    return a/c*b


n=int(input())
t=[int(input()) for lop in range(n)]
ans=t[0]

for lop in range(1,n):
    ans=lcm(ans,t)
print(int(ans))

### FIXED CODE ###

'''
def gcd(a,b):
    if a<b:
     c=a
     a=b
     b=c

    c=a%b

    if c==0:
     return b
    else:
     return gcd(b,c)
'''

def gcd(a,b):
    return a if b == 0 else gcd(b,a%b)

def lcm(e,f):
    c=gcd(e,f)
    g=e*f
    return g//c



n=int(input())
t=[0]*n

for lop2 in range(n):
    t[lop2]=int(input())

ans=t[0]

for lop in range(1,n):
    ans=lcm(ans,t[lop])
print(int(ans))
import sys
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, q = map(int, input().split())
    G[l - 1].append((r - 1, q))
    G[r - 1].append((l - 1, -q))
X = [None] * N


def dfs(u):
    for w, d in G[u]:
        if X[w] is None:
            X[w] = X[u] + d
            f = dfs(w)
            if not f:
                return False
        elif X[w] - X[u] != d:
            return False

    return True


for i, x in enumerate(X):
    if x is None:
        X[i] = 0
        f = dfs(i)
        if not f:
            print("No")
            sys.exit(0)

print("Yes")

### FIXED CODE ###

import sys
sys.setrecursionlimit(200002)
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, q = map(int, input().split())
    G[l - 1].append((r - 1, q))
    G[r - 1].append((l - 1, -q))
X = [None] * N


def dfs(u):
    global X, G
    for w, d in G[u]:
        if X[w] is None:
            X[w] = X[u] + d
            if not dfs(w):
                return False
        else:
            if X[w] != X[u] + d:
                return False

    return True


flag = True
for i in range(N):
    if X[i] is None:
        X[i] = 0
        flag &= dfs(i)

if flag:
    print("Yes")
else:
    print("No")
import sys
import collections
input = sys.stdin.readline
 
N = int(input())
 
for c in str(N):
	if c == '7':
		print('Yes')
		exit(1)
print('No')

### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline

N = int(input())

flag = False
for c in str(N):
	if c == '7':
		flag = True
if flag:
	print('Yes')
else:
	print('No')
a = int(input())
b = int(input())

if a * b % 2 == 1:
    print("Odd")
elif a * b % 2 == 0:
    print("Even")

### FIXED CODE ###

a , b = map(int , input().split())
if a * b % 2 == 1:
    print("Odd")
elif a * b % 2 == 0:
    print("Even")
def main():
    data = []
    while 1:
        n = input().split()
        a = int(n[0])
        b = int(n[1])
        c = int(n[2])
        div = 0

        for i in range(a,b):
            if c % i == 0:
                div += 1

        print(div)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    data = []
    n = input().split()
    a = int(n[0])
    b = int(n[1])
    c = int(n[2])
    div = 0

    one_div=(a == b) and c % a == 0 or c % b == 0

    if one_div:
        div = 1

    for i in range(a, b):
        div_ans = c % i
        if div_ans == 0:
            div += 1

    print(div)

if __name__ == '__main__':
    main()
a, b, c, d = map(int, input().split())
if (a - c) <= c:
    print("Yes"):
else:
    print("No")

### FIXED CODE ###

a, b, c, d = map(int, input().split())
ans = "No"

if abs(a-c) <= d:
    ans = "Yes"
elif abs(a-b) <= d and abs(b-c) <= d:
    ans = "Yes"

print(ans)
n,k = map(int, input().split())

rem = n % k
a = rem - k
ans = min(abs(a)


### FIXED CODE ###

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

if k == 0:
	ans = n
else:
	rem = n % k
	a = rem - k
	ans = min(abs(a), rem)

print(ans)
N = int(input())
a = []
a = input().split()

count = 0

for i in range(int(N/2) + 1):
  cd = 2 * i - 2
  jd = int(a[cd])
  if jd % 2 == 1:
    count += 1
    

print(count)

### FIXED CODE ###

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

count = 0

for i in range(0,N,2):
  jd = a[i]
  if jd % 2 == 1:
    count += 1

print(count)
import math
from functools import reduce

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm_list(a):
    return reduce(lcm_base, a, 1)

N = int(input())
a = list(map(int, input().split()))
ans = 0
num = lcm_list(a) - 1
print(num)
for i in range(len(a)):
	ans += num % a[i]
print(ans)


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 0
for x in a:
	ans += x - 1
print(ans)
a = input() 
b = input()
return a * b 
return 2 * a + 2 * b

### FIXED CODE ###

a, b = map(int, raw_input().split())
print a * b, 2 * a + 2 * b
a,b=map(int,input().split())
if (a*b)%2==0:
  print('Even')
else print('Odd')


### FIXED CODE ###

a,b=map(int,input().split())
if (a*b)%2==0:
  print('Even')
else:
  print('Odd')
n_str = raw_input()
n = int(n_str)
total = sum(map(int, list(n_str)))
if n % total == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n_str = raw_input()
n = int(n_str)
total = sum(map(int, list(n_str)))
if n % total == 0:
    print('Yes')
else:
    print('No')
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]
n = 1
a.insert(0, -1)
a.append(N + 1)

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

def v(x):
    if x == -1:
        return 1
    else:
        q = x // 2
        r = x % 2
        ans = 0
        for i in range(x // 2 + 1):
            ans += cmb(q + r, r)
            r = r + 2
            q = q - 1
        return ans
for i in range(M + 1):
    if a[i + 1] - a[i] == 1:
        print(0)
        exit()

for i in range(M + 1):
    n = n * v((a[i + 1] - 1) - (a[i] + 1)) % 1000000007

print(n)

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for i in range(M)])
n = [0] * (N + 1)
n[0] = 1
n[1] = 1

#listの中をinで探すのはくっそ遅い
if 1 in a:
    n[1] = 0

for i in range(2, N + 1):
    if i in a:
        continue
    else:
        n[i] = (n[i - 1] + n[i - 2]) % 1000000007

print(n[N])
input()
A = list(map(int,input().split()))
A = A.sort(reverse=True)
Alice = sum(A[1::2])
Bob = sum(A[::2])
print(Alice-Bob)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
l = sorted(a, reverse = True)
count = 0
for i in range(N):
    if i % 2 == 0:
        count += l[i]
    else:
        count -= l[i]
print(count)
import numpy as np
n = int(input())
v = list(map(int, input().split()))
gu = [0] * (10**5)
ki = [0] * (10**5)

for i in range(n):
  if i % 2:
    ki[v[i]] += 1
  else:
    gu[v[i]] += 1
import numpy as np
ki = np.array(ki)
gu = np.array(gu)

a = np.argmax(ki)
b = np.argmax(gu)

if a != b:
  print(n-ki[a]-gu[b])
else:
  if a > b:
    gu = sorted(gu)
    print(n-ki[a] - gu[-2])
  else:
    ki = sorted(ki)
    print(n-ki[-2]-gu[b])
  

### FIXED CODE ###

import numpy as np
n = int(input())
v = list(map(int, input().split()))
gu = [0] * (10**5 + 5)
ki = [0] * (10**5 + 5)

for i in range(n):
  if i % 2:
    ki[v[i]] += 1
  else:
    gu[v[i]] += 1
ki = np.array(ki)
gu = np.array(gu)

a = np.argmax(ki)
b = np.argmax(gu)

if a != b:
  print(n-ki[a]-gu[b])
else:
  gu = sorted(gu)
  ki = sorted(ki)
  print(min(n-ki[-1] - gu[-2], n-ki[-2]-gu[-1]))
h = len(nagasa)

if h // 2 <= k:
    print(n)
    exit()
lef = 0
rig = 2*k+1
now = sum(nagasa[lef:rig])
ans = now
while True:
    if rig == h:
        break
    now = now - nagasa[lef] - nagasa[lef+1] + nagasa[rig] + nagasa[rig+1]
    ans = max(ans,now)
    lef += 2
    rig += 2
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
s = input()
cou = 0
p = 1
nagasa = []
for i in range(n):
    if int(s[i]) == p:
        cou += 1
    elif int(s[i]) != p:
        if p == 1:
            p = 0
        elif p == 0:
            p = 1
        nagasa.append(cou)
        cou = 1
nagasa.append(cou)
if len(nagasa) % 2 == 0:
    nagasa.append(0)
h = len(nagasa)

if h // 2 <= k:
    print(n)
    exit()
lef = 0
rig = 2*k+1
now = sum(nagasa[lef:rig])
ans = now
while True:
    if rig == h:
        break
    now = now - nagasa[lef] - nagasa[lef+1] + nagasa[rig] + nagasa[rig+1]
    ans = max(ans,now)
    lef += 2
    rig += 2
print(ans)
N, A = map(int, input().split())
X = [0] + list(map(int, input().split()))

max_X = max(X)
dp = [[[0 for k in range((N + 1) * max_X)]
       for j in range(N + 1)] for i in range(N + 1)]
for i in range(N + 1):
    dp[i][0][0] = 1

for j in range(1, N + 1):
    for k in range(1, j + 1):
        for s in range((N + 1) * max_X):
            if s < X[j]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif s >= X[j]:
                dp[j][k][s] = dp[j - 1][k - 1][s - X[j]] + dp[j - 1][k][s]
ans = 0
for k in range(1, N + 1):
    ans += dp[N][k][k * A]
print(ans)


### FIXED CODE ###

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

dp = [[[0 for k in range(2600)] for j in range(51) ] for i in range(51)]
for i in range(51):
    dp[i][0][0] = 1
for j in range(1,N+1):
    for k in range(1,j+1):
        for s in range(2600):
            if s < ls1[j]:
                dp[j][k][s] = dp[j-1][k][s]
            elif s >= ls1[j]:
                dp[j][k][s] = dp[j-1][k-1][s-ls1[j]] + dp[j-1][k][s]
ans = 0
for k in range(1,N+1):
    ans += dp[N][k][k*A]
print(ans)
print x ** 3

### FIXED CODE ###

x = input()
print x ** 3
n=int(input())
print(min([sum([(x-item)**2 for x in [int(x) for x in input().split()]]) for item in list(range(-100,101))]))

### FIXED CODE ###

n=int(input())
a=[int(x) for x in input().split()]
print(min([sum([(x-item)**2 for x in a]) for item in list(range(-100,101)
                                                         )
          ]
         )
     )
import math
from fractions import gcd

a,b = map(int,input().split())
gc = gcd(a,b)
gcr = int(math.sqrt(gc))
is_p = [True] * (gcr+1)
is_p[0] = False
for i in range(2, gcr+1):
    if is_p[i]:
        for j in range(2*i, gcr+1, i):
            is_p[j] = False

ps = [i for i, v in enumerate(is_p) if v]
ans = len([1 for p in ps if gc % p == 0])
if gcr not in ps and all(gcr % p != 0 for p in ps and p >= 2):
    ans += 1
print(ans)


### FIXED CODE ###

import math
from fractions import gcd

a,b = map(int,input().split())
g = gcd(a,b)
gr = int(math.ceil(math.sqrt(g)))

facs = [1]
i = 2
while i*i <= g:
    if g == 1:
        break
    if g % i == 0:
        facs.append(i)
        while g % i == 0:
            g //= i
    i += 1
if g != 1:
    facs.append(g)

print(len(facs))
N = int(input())
balls = []
for i in range(N):
    x, y = map(int, input().split(' '))
    balls.append([x,y])

dic = {}
for i in range(N):
    px = balls[i][0]
    py = balls[i][1]
    for j in range(N-(i+1)):
        dx = balls[j][0] - px
        dy = balls[j][1] - py
        px = balls[j][0]
        py = balls[j][1]
        if (0>dx):
            dx *= -1
            dy *= -1
        if (dx,dy) not in dic.keys():
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] += 1

d_max = max(dic.values())
print(N - d_max)



### FIXED CODE ###

N = int(input())
balls = []
for i in range(N):
    x, y = map(int, input().split(' '))
    balls.append((x,y))

if N == 1:
    print("1")
    exit()

dic = {}
for i in range(N):
    for j in range(i+1,N):
        dx = balls[j][0] - balls[i][0]
        dy = balls[j][1] - balls[i][1]
        if (dx,dy) not in dic.keys():
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] += 1
        dx *= -1
        dy *= -1
        if (dx,dy) not in dic.keys():
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] += 1

d_max = max(dic.values())
print(N - d_max)
S = input().strip()

a = 130
for i in range(100000)
    b = a % 13

print(a)


### FIXED CODE ###

S = input().strip()

MOD = 10**9 + 7
dp = [[0 for i in range(13)] for j in range(100005)]
N = len(S)

dp[0][0] = 1
for i in range(N):
    c = -1
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])

    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki * 10 + j) % 13] += dp[i][ki]

    for j in range(13):
        dp[i+1][j] %= MOD

res = int(dp[N][5])

print(res)
import sys

s = input().split("T")
x, y = map(int, input().split())
x -= len(s[0])
s.pop(0)

list_yoko = [len(s[i]) for i in range(1, len(s), 2)]
list_tate = [len(s[i]) for i in range(0, len(s), 2)]

set_yoko = {list_yoko[0], -list_yoko[0]}
set_tate = {list_tate[0], -list_tate[0]}

for i in list_yoko[1:]:
	sy = set()
	for j in set_yoko:
		sy |= {j + i, j - i}
	set_yoko = sy

for i in list_tate[1:]:
	st = set()
	for j in set_tate:
		st |= {j + i, j - i}
	set_tate = st

if (x in sy) and (y in st):
	print("Yes")
else:
	print("No")

### FIXED CODE ###

s = input().split("T")
x, y = map(int, input().split())
x -= len(s[0])
s.pop(0)

list_yoko = [len(s[i]) for i in range(1, len(s), 2)]
list_tate = [len(s[i]) for i in range(0, len(s), 2)]

if list_yoko == []:
	list_yoko = [0]

if list_tate == []:
	list_tate = [0]
	
set_yoko = {list_yoko[0], -list_yoko[0]}
set_tate = {list_tate[0], -list_tate[0]}

for i in list_yoko[1:]:
	sy = set()
	for j in set_yoko:
		sy |= {j + i, j - i}
	set_yoko = sy

for i in list_tate[1:]:
	st = set()
	for j in set_tate:
		st |= {j + i, j - i}
	set_tate = st

if (x in set_yoko) and (y in set_tate):
	print("Yes")
else:
	print("No")
# -*- coding: utf-8 -*-

n = int(input())
s = list(input())
t = list(input())

for i in range(n):
    match = True
    for j in range(n):
        if i + j < n:
            if s[i + j] != t[j]:
                match = False
    if match:
        if i == 0:
            print(n)
        else:
            print(n + i)
        break
else:
    print(len(n * 2))


### FIXED CODE ###

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

n = int(input())
s = list(input())
t = list(input())

for i in range(n):
    match = True
    for j in range(n):
        if i + j < n:
            if s[i + j] != t[j]:
                match = False
    if match:
        if i == 0:
            print(n)
        else:
            print(n + i)
        break
else:
    print(n * 2)
a,b = map(input().split())
print((a-1)*(b-1))

### FIXED CODE ###

a,b = map(int,input().split())
print((a-1)*(b-1))
s = input()

ans = True
if s[0] != "A":
    ans = False
    #print("s[0] is not A")
else:
    cnt_C = 0
    length = len(s)

    n = 1
    for check_char in s[1:-1]:
        
        if check_char.islower() is False:
            if check_char != "C" or n == 1 or n == (length - 1):
                ans = False
                break
            
            cnt_C += 1
        
        n += 1

if cnt_C != 1:
    ans = False

if ans:
    print("AC")
else:
    print("WA")

### FIXED CODE ###

"""
B - AcCepted
文字列 S が与えられます。S のそれぞれの文字は英大文字または英小文字です。 S
が次の条件すべてを満たすか判定してください。

S の先頭の文字は大文字の A である。
Sの先頭から 3 文字目と末尾から 2 文字目の間（両端含む）に大文字の C がちょうど 1
個含まれる。
以上の A, C を除く S のすべての文字は小文字である。
"""

s = input()

cnt_C = 0
ans = True
if s[0] != "A":
    ans = False
    #print("s[0] is not A")
else:
    length = len(s)

    n = 1
    for check_char in s[1:]:
        #print(check_char)
        
        if check_char.islower() is False:
            if check_char != "C" or n == 1 or n == (length - 1):
                ans = False
            
            cnt_C += 1
        
        n += 1

if cnt_C != 1:
    ans = False

if ans:
    print("AC")
else:
    print("WA")
import sys
from collections import deque, defaultdict
import heapq

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = lr()

# Aでxの根を求める
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    # 根をbxに統一
    A[by] = bx

edges = [[] for _ in range(N)]
V = [i for i in range(N)]
for _ in range(M):
    x, y = lr()
    if find(V, x) != find(V, y):
        union(V, x, y)
    edges[x].append(y)
    edges[y].append(x)

for i in range(N):
    V[i] = find(V, i)

dig_0 = [i for i in range(N) if len(edges[i]) == 0]
l0 = len(dig_0)
if N == 1:
    print(0); exit()
elif l0 > N//2:
    print('Impossible'); exit()

# 孤立していない頂点の根
roots = [V[i] for i in range(N) if i not in dig_0]
root_point = defaultdict(list)
for i in range(N):
    if i in dig_0:
        continue
    r = V[i]
    heapq.heappush(root_point[r], A[i])

#各グループの最小値以外で使うコストの数
remain = (l0 + len(set(roots)) - 1) * 2 - (l0 + len(set(roots)))
answer = 0
for i in dig_0:
    answer += A[i]

candidates = deque()
for po in root_point:
    answer += heapq.heappop(root_point[po])
    for i in range(min(remain, len(root_point[po]))):
        candidates.append(heapq.heappop(root_point[po]))

for i in range(remain):
    answer += heapq.heappop(candidates)
print(answer)
# 43

### FIXED CODE ###

import sys
from collections import deque, defaultdict
import heapq

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = lr()

# Aでxの根を求める
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    # 根をbxに統一
    A[by] = bx

edges = [[] for _ in range(N)]
V = [i for i in range(N)]
for _ in range(M):
    x, y = lr()
    if find(V, x) != find(V, y):
        union(V, x, y)
    edges[x].append(y)
    edges[y].append(x)

for i in range(N):
    V[i] = find(V, i)

if M == N - 1:
    print(0); exit()
elif N < 2 * (N-M-1):
    print('Impossible'); exit()

root_point = defaultdict(list)
for i in range(N):
    r = V[i]
    heapq.heappush(root_point[r], A[i])

#各グループの最小値以外で使うコストの数
answer = 0
candidates = []
for p_list in root_point:
    answer += heapq.heappop(root_point[p_list])
    candidates.extend(root_point[p_list])

remain = 2 * (N-M-1) - len(set(V))
candidates.sort()
answer += sum(candidates[:remain])
print(answer)