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

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

mode = 1

def prob_d(s, q):
    ans = s
    for i in range(q):
        ans = ope(ans)
    if mode == -1:
        ans = ans[::-1]
    print(ans)

def reverse():
    global mode
    mode *= -1

def add_head(s, c):
    if mode == -1:
        return s + c
    return c + s

def add_tail(s, c):
    if mode == -1:
        return c + s
    return s + c

def ope(s):
    op = input().split()
    if len(op) == 1 and op[0] == '1':
        reverse()
    elif len(op) == 3 and op[0] == '2':
        if op[1] == "1":
            s = add_head(s, op[2])
        elif op[1] == "2":
            s = add_tail(s, op[2])
        else:
            pass
    else:
        pass
    return s

if __name__ == '__main__':
    s = input()
    q = int(input())
    prob_d(s, q)


### FIXED CODE ###

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

from collections import deque as dq

mode = True

def prob_d(s, q):
    ans = dq(s)
    for i in range(q):
        ans = ope(ans)
    if not mode:
        ans = ''.join(list(ans)[::-1])
    else:
        ans = ''.join(ans)
    print(ans)

def ope(s):
    global mode
    op = input().split()
    if len(op) == 1 and op[0] == '1':
        mode = not mode 
    elif len(op) == 3 and op[0] == '2':
        if op[1] == "1":
            if mode:
                s.appendleft(op[2])
            else:
                s.append(op[2])
        elif op[1] == "2":
            if mode:
                s.append(op[2])
            else:
                s.appendleft(op[2])
        else:
            pass
    else:
        pass
    return s

if __name__ == '__main__':
    s = input()
    q = int(input())
    prob_d(s, q)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]

bc.sort(key = lambda x:x[1], reverse = True)

d = []
d_count = 0
loop = 0

while True:
        for b, c in bc:
                d.extend([c] * b)
                d_count += b
                loop += 1
        if d_count > n:
                break
        elif loop == m:
                break

a.extend(d)
a.sort(reverse = True)

print(sum(a[0:n]))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]

bc.sort(key = lambda x:x[1], reverse = True)

a.sort()

a_count = 0
for b, c in bc:
        if c > a[a_count]:
                for i in range(b):
                        if c > a[a_count]:
                                a[a_count] = c
                                a_count += 1    
                        else:
                                break
                        if a_count == n:
                                        break

        else:
                break
        if a_count == n:
                break        

print(sum(a))
### BUGGY CODE ###

import itertools

N,K = map(int,input().split())
p =  list(map(int,input().split()))
ans = 1000000

for v in itertools.combinations(p, K):
    tmp = sum(v) 
    if ans > tmp:
        ans = tmp

print(ans)

### FIXED CODE ###

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

ans=0
p.sort()
for i in range(K):
    ans += p[i]
print(ans)
### BUGGY CODE ###

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

if n == 1:
    price[0] //= (2 ** m)
else:
    while m >= 1:
        while price[-1] >= price[-2]:
            price[-1] //= 2
            m -= 1
        price.sort()
print(sum(price))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
price = list(map(lambda x: -x, map(int, input().split())))
heapq.heapify(price)

while m >= 1:
    a = (heapq.heappop(price) + 1) // 2
    heapq.heappush(price, a)
    m -= 1
    
print(sum(price) * (-1))
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
l = nl()

l = sorted(l)[::-1]

ans = 0


for a in range(n):
    fl = 0
    for b in range(a+1,n):
        if fl == 1:
            break
        for c in range(b+1,n):
            A = l[a]
            B = l[b]
            C = l[c]

            if A >= B + C:
                if a+1 == b:
                    fl = 1
                break

            if B < A + C and C < A + B:
                ans += 1

print(ans)

### FIXED CODE ###

import bisect

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
l = nl()

l = sorted(l)

ans = 0

for a in range(n):
    fl = 0
    A = l[a]
    for b in range(a+1,n):
        B = l[b]

        idx = bisect.bisect_left(l, A+B)
        ans += max(0,idx-b-1)

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

H,W = map(int,input().split())
A = [input() for _ in range(H)]
ans = [[10000]*(W+2) for _ in range(H+2)]
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            ans[i+1][j+1] = 0

for i in range(H):
    for j in range(W):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j]+1)
for i in range(H):
    for j in range(W-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j+2]+1)
for j in range(W):
    for i in range(H):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i][j+1]+1)
for j in range(W):
    for i in range(H-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+2][j+1]+1)

num = 0
for i in range(H):
    for j in range(W):
        num = max(num,ans[i+1][j+1])

print(num)

### FIXED CODE ###

H,W = map(int,input().split())
A = [input() for _ in range(H)]
ans = [[10000]*(W+2) for _ in range(H+2)]
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            ans[i+1][j+1] = 0

for i in range(H):
    for j in range(W):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j]+1)
for i in range(H):
    for j in range(W-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j+2]+1)
for j in range(W):
    for i in range(H):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i][j+1]+1)
for j in range(W):
    for i in range(H-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+2][j+1]+1)

num = 0
for i in range(H):
    for j in range(W):
        num = max(num,ans[i+1][j+1])

print(num)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, w = map(int, readline().split())
wv = [list(map(int, readline().split())) for i in range(n)]
dp = [0]
check = [0]
size = 1
for ww, vv in wv:
    for i in range(size):
        g = ww + check[i]
        v = vv + dp[i]
        if g > w:
            continue
        else:
            if g in check:
                index = check.index(g)
                if dp[index] < v:
                    dp[index] = v
            else:
                dp.append(v)
                check.append(g)
                size += 1

print(max(dp))


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

n, w = map(int, readline().split())
wv = [list(map(int, readline().split())) for i in range(n)]
dp = np.full(n * 1000 + 1, w + 1, dtype=int)
dp[0] = 0
for x, y in wv:
    dp[y:] = np.minimum(dp[y:], dp[:-y] + x)
print(np.max(np.where(dp <= w)))
### BUGGY CODE ###

n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))
for ki in k:
    D=M=DM=C=0
    for i, c in enumerate(s):
        if c == "D":
            D += 1
        elif c == "M":
            M += 1
            DM += D
        if i >= ki:
            j = i-ki
            if s[j] == "D":
                D -= 1
                DM -= M
            elif s[j] == "M":
                M -= 1
        if c == "C":
            C += DM
    print(C)

### FIXED CODE ###

# コピペ https://atcoder.jp/contests/dwacon5th-prelims/submissions/7670569
# 自分の https://atcoder.jp/contests/dwacon5th-prelims/submissions/7822126
# とほぼ変わらないのに自分のものはTLEするので検証
n=int(input())
s=input()
q=int(input())
for i in list(map(int,input().split())):
    a=0
    v=[0,0,0]
    for j in range(n):
        if s[j]=="D":
            v[0]+=1
        elif s[j]=="M":
            v[1]+=1
            v[2]+=v[0]
        if j>=i:
            if s[j-i]=="D":
                v[0]-=1
                v[2]-=v[1]
            elif s[j-i]=="M":
                v[1]-=1
        if s[j]=="C":
            a+=v[2]
    print(a)
### BUGGY CODE ###

import sys

import bisect

# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd

import itertools

# from operator import attrgetter, itemgetter
import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))
    stemp = input()
    s = "R"
    s += stemp
    s += "L"

    unhappy_edge = 0

    if s[1] == "L":
        unhappy_edge += 1
    if s[-2] == "R":
        unhappy_edge += 1

    unhappy_pair = 0
    prev = s[1]
    for i in range(2, n + 1):
        current = s[i]
        if prev == "R" and current == "L":
            unhappy_pair += 1
        prev = current

    while k > 0:
        if unhappy_pair > 0:
            unhappy_pair -= 1
            k -= 1
        elif unhappy_edge == 2:
            unhappy_edge -= 1
            break

    print(n - unhappy_pair * 2 - unhappy_edge)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

import bisect

# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd

import itertools

# from operator import attrgetter, itemgetter
import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))
    stemp = input()
    s = "R"
    s += stemp
    s += "L"

    unhappy_edge = 0

    if s[1] == "L":
        unhappy_edge += 1
    if s[-2] == "R":
        unhappy_edge += 1

    unhappy_pair = 0
    prev = s[1]
    for i in range(2, n + 1):
        current = s[i]
        if prev == "R" and current == "L":
            unhappy_pair += 1
        prev = current

    temp = min(k, unhappy_pair)
    unhappy_pair -= temp
    k -= temp

    if k > 0:
        unhappy_edge = 1

    print(n - unhappy_pair * 2 - unhappy_edge)


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

A = input()[::-1]
A = "0" + A
# lis_num = [int(s) for s in A]

# print(lis_num)

# S = [0] * len(lis_num)
S = [0] * len(A)

for i in range(len(A) - 1):
    S[i + 1] = S[i] + int(A[i + 1]) * 10 ** i
# print(S)

cnt = [0] * 2019

for i in S:
    cnt[i % 2019] += 1

ans = 0

for i in range(2019):
    ans += cnt[i] * (cnt[i] - 1) // 2

print(ans)


### FIXED CODE ###

def main():
    A = input()[::-1]
    A = "0" + A
    # lis_num = [int(s) for s in A]

    # print(lis_num)

    # S = [0] * len(lis_num)
    S = [0] * len(A)
    cnt = [0] * 2019
    cnt[0] = 1

    for i in range(len(A) - 1):
        S[i + 1] = (S[i] + int(A[i + 1]) * pow(10, i, 2019)) % 2019
        cnt[S[i + 1] % 2019] += 1

    # print(S)

    # for i in S:
    #     cnt[i % 2019] += 1

    ans = 0

    for i in cnt:
        ans += i * (i - 1) // 2

    print(ans)


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

import sys
input = sys.stdin.readline

mod=10**9+7
n,k=map(int,input().split())
N=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  N[a-1]+=[b-1]
  N[b-1]+=[a-1]
Chk=[False]*n
S=[0]
Chk[0]=True
ans=k
while S:
  ss=S.pop()
  for sss in N[ss]:
    if Chk[sss]==True:
      continue
    else:
      ct=1
      for ssss in N[ss]:
        if Chk[ssss]==True:
          ct+=1
      ans=(ans*max(k-ct,0))%mod
      Chk[sss]=True
      S.append(sss)
print(ans%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod=10**9+7
n,k=map(int,input().split())
N=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  N[a-1]+=[b-1]
  N[b-1]+=[a-1]
Chk=[0]*n
S=[0]
Chk[0]=1
ans=k
while S:
  ss=S.pop()
  for sss in N[ss]:
    if Chk[sss]>0:
      continue
    else:
      ans=(ans*max(k-Chk[ss],0))%mod
      Chk[ss]+=1
      Chk[sss]=2
      S.append(sss)
print(ans%mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    tmp = 1
    for i in range(K):
        tmp *= A[i]

    for i in range(K,N):
        n = tmp * A[i] / A[i-K]
        if n > tmp:
            print('Yes')
        else:
            print('No')

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    # tmp = 1
    # for i in range(K):
    #     tmp *= A[i]
    # print(tmp)

    for i in range(K,N):
        # n = tmp * A[i] / A[i-K]
        n = A[i]/A[i-K]
        if n > 1:
            print('Yes')
        else:
            print('No')

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

N, K, Q = input().split(' ')
n, k, q = int(N), int(K), int(Q)
a = []
for i in range(q):
    a.append(int(input()) - 1)
for i in range(n):
    res = 'No'
    if k - q + a.count(i) > 0:
        res = 'Yes'
    print(res)

### FIXED CODE ###

N, K, Q = input().split(' ')
n, k, q = int(N), int(K), int(Q)
t = 'No'
if k - q > 0:
    t = 'Yes'
res = [t] * n

p = [k - q] * n
for i in range(q):
    r = int(input()) - 1
    p[r] += 1
    if p[r] > 0:
        res[r] = 'Yes'
for i in res:
    print(i)
### BUGGY CODE ###

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

q = deque()
inf = 10**6
used = [[inf]*W for _ in range(H)]
if S[0][0] == ".":
    used[0][0] = 0
else:
    used[0][0] = 1
q.append((0, 0))

while q:
    temp = q.popleft()
    r = temp[0]
    c = temp[1]
    if r < H-1:
        if S[r+1][c] == "#" and S[r][c] == ".":
            used[r+1][c] = min(used[r+1][c], used[r][c] + 1)
            q.append((r+1, c))
        else:
            used[r+1][c] = min(used[r+1][c], used[r][c])
            q.append((r+1, c))
    if c < W-1:
        if S[r][c+1] == "#" and S[r][c] == ".":
            used[r][c+1] = min(used[r][c+1], used[r][c] + 1)
            q.append((r, c+1))
        else:
            used[r][c+1] = min(used[r][c+1], used[r][c])
            q.append((r, c+1))
    
print(used[-1][-1])

### FIXED CODE ###

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

inf = 10**6
L = [[inf]*W for _ in range(H)]
if S[0][0] == ".":
    L[0][0] = 0
else:
    L[0][0] = 1

for i in range(H):
    for j in range(W):
        n1 = inf
        n2 = inf
        if i > 0:
            if S[i-1][j] == "." and S[i][j] == "#":
                n1 = L[i-1][j] + 1
            else:
                n1 = L[i-1][j]
        if j > 0:
            if S[i][j-1] == "." and S[i][j] == "#":
                n2 = L[i][j-1] + 1
            else:
                n2 = L[i][j-1]
        L[i][j] = min(L[i][j], n1, n2)

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

import sys
import os
import itertools

n = int(input())

def is_prime(n):
    for p in range(2, n):
        if n % p == 0:
            return 0
    return 1

a = is_prime(n)
if a == 1:
    print(n-1)
    sys.exit()

l = []
# for i in range(2, n):
#     for j in range(2, n):
#         if i*j == n:
#             l.append((i-1)+(j-1))
#         else:
#             continue

# print(min(l))

def make_divisors(n):
    # divisors = []
    divisors = {}
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            # divisors.append(i)
            divisors[i] = n//i
            if i != n // i:
                # divisors.append(n//i)
                divisors[i] = n//i

    # divisors.sort()
    return divisors

ans = make_divisors(n)
print( (max(ans)-1) + ans[max(ans)]-1)

### FIXED CODE ###

import sys
import os
import itertools

n = int(input())

def make_divisors(n):
    divisors = {}
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors[i] = n//i
            if i != n // i:
                divisors[i] = n//i

    return divisors

ans = make_divisors(n)
m = max(ans)
print( (m-1) + ans[m]-1)
### BUGGY CODE ###

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

count = 1
for i in range(1, (m//n)+1):
    temp = m - (i*n)
    if temp % i == 0:
        count = i
        
print(count)

### FIXED CODE ###

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

count = 1
for i in range((m//n), 0, -1):
    if m % i == 0:
        count = i
        break

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

def bitsum(bit,i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i&(-i)
    return s
    
def bitadd(bit,i,x):
    n = len(bit)-1
    while i <= n:
        bit[i] += x
        i += i&(-i)
    return bit

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=lambda x:x[1])
for i in range(N):
    xy[i][1] = i+1
xy.sort()
for i in range(N):
    xy[i][0] = i

# x<xi,y<yi
l1 = [0]*N
# x<xi,y>yi
l2 = [0]*N
# x>xi,y<yi
r1 = [0]*N
# x>xi,y>yi
r2 = [0]*N

bitl = [0]*(N+1)
for i in range(N):
    l1[i] = bitsum(bitl,xy[i][1])
    l2[i] = i-l1[i]
    bitadd(bitl,xy[i][1],1)

bitr = [0]*(N+1)
for i in range(N):
    r1[N-i-1] = bitsum(bitr,xy[N-i-1][1])
    r2[N-i-1] = i-r1[N-i-1]
    bitadd(bitr,xy[N-i-1][1],1)

ans = pow(2,N-1,mod)*N%mod
for i in range(N):
    L1 = pow(2,l1[i],mod)
    L2 = pow(2,l2[i],mod)
    R1 = pow(2,r1[i],mod)
    R2 = pow(2,r2[i],mod)
    ans += L1*L2%mod*R1%mod*R2%mod
    ans -= L1*R1%mod
    ans -= L2*R2%mod
    ans -= L1*L2%mod
    ans -= R1*R2%mod
    ans += L1+L2+R1+R2-1
    ans %= mod

print(ans)

### FIXED CODE ###

from operator import itemgetter

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=itemgetter(1))
for i in range(N):
    xy[i][1] = i+1
xy.sort(key=itemgetter(0))

pow2 = [1]*(N+1)
for i in range(N):
    pow2[i+1] = 2*pow2[i]%mod

ans = pow2[N-1]*N%mod

bit = BIT(N)
for i in range(N):
    l1 = bit.sum(xy[i][1])
    l2 = i-l1
    r1 = xy[i][1]-l1-1
    r2 = N-xy[i][1]-l2
    bit.add(xy[i][1],1)
    ans += (pow2[l2]-1)*(pow2[r1]-1)*pow2[r2]*pow2[l1]
    ans += (pow2[r2]-1)*(pow2[l1]-1)*(pow2[l2]+pow2[r1]-1)
    ans %= mod

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

N = int(input())
S = list(input())
numbers = []
for i in range(N):
    S_left = S[:i]
    S_right = S[i+1:]
    number = S_left.count("W")+S_right.count("E")
    numbers.append(number)
print(min(numbers))

### FIXED CODE ###

N = int(input())
S = list(input())
origin = S[1:]
summary = [origin.count("E")]
for i in range(N-1):
    s = summary[-1]
    if S[i] == "W":
        if S[i+1] == "E":
            delta = 0
        else:
            delta = 1
    else:
        if S[i+1] == "E":
            delta = -1
        else:
            delta = 0
    summary.append(delta+s)
print(min(summary))
### BUGGY CODE ###

k, s = map(int, input().split())
cnt = 0
for i in range(k+1):
  if i < s:
    for j in range(k+1):
      if i + j < s:
        for l in range(k+1):
          if i + j + l == s:
            cnt += 1
      elif i + j <= s:
        cnt += 1
  elif i == s:
    cnt += 1
print(cnt)

### FIXED CODE ###

def main():
  k, s = map(int, input().split())
  cnt = 0
  for i in range(k+1):
    for j in range(k+1):
      if 0 <= s - i - j <= k:
        cnt += 1
  print(cnt)

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

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]
for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = np.array([[mod,mod,mod] for i in range(N)])

# print(routes)
# def skip(now,move_cnt):
#     flag = True
#     if used[now] != mod:
#         if used[now] % 3 == 0 and move_cnt > used[now]:
#             flag = False
#     if used[now] > move_cnt:
#         if used[now] % 3 == 0 and move_cnt % 3 != 0:
#             pass
#         else:
#             used[now] = move_cnt
#     if flag:
#         for route in routes[now]:
#             skip(route,move_cnt+1)
def move2next(now,move_cnt):
    state = move_cnt % 3
    if used[now, state] <= move_cnt:
        flag = False # この条件だと前より遅いので探索ストップ
    else:
        used[now, state] = move_cnt
        for route in routes[now]:
            move2next(route, move_cnt+1)

move2next(S,0)
# print(used)
try:
    ans = used[T, 0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]

for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = [[mod,mod,mod] for i in range(N)]

from collections import deque

# q = queue.Queue()
q = deque()
q.append((S,0))
# Deep First Serch
while q:
    now, cost = q.popleft()
    for route in routes[now]:
        n_state = (cost + 1) % 3
        if used[route][n_state] == mod:
            used[route][n_state] = cost + 1
            q.append((route,cost+1))


# print(used)
try:
    ans = used[T][0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))
### BUGGY CODE ###

n, m = map(int, input().split())
ship = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1 or b == n:
        ship.append((a, b))
if len(ship) == 0:
    print("IMPOSSIBLE")
    exit()

ship.sort()
i = 0

while ship[i][0] == 1:
    i += 1
    if i == len(ship):
        print("IMPOSSIBLE")
        exit()

for j in range(i):
    for k in range(i, len(ship)):
        if ship[j][1] == ship[k][0]:
            print("POSSIBLE")
            exit()
        elif ship[j][1] < ship[k][0]:
            break

print("IMPOSSIBLE")


### FIXED CODE ###

n, m = map(int, input().split())
ship_1 = [False]*(n+1)
ship_n = [False]*(n+1)
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        ship_1[b] = True
    elif b == n:
        ship_n[a] = True

for i in range(len(ship_1)):
    if ship_1[i] and ship_n[i]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")
### BUGGY CODE ###

import bisect


def main():
    n, m = map(int, input().split(' '))
    a_s = list(sorted(map(int, input().split(' '))))
    
    for _ in range(m):
        value = int(a_s[n-1]/2)
        i = bisect.bisect_left(a_s[:n-1], value)
        a_s[i+1:n] = a_s[i:n-1]
        a_s[i] = value
    print(sum(a_s))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import heapq


def main():
    n, m = map(int, input().split(' '))
    a_s = list(sorted(map(lambda x: -1 * int(x), input().split(' '))))

    heapq.heapify(a_s)
    for _ in range(m):
        e = heapq.heappop(a_s)
        heapq.heappush(a_s, int(e/2))
    print(-1*sum(a_s))
    
    

if __name__ == '__main__':
    main()