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

N = int(input())

r = []

for i in range(N):
  r = r + [input()]

ac = 0
wa = 0
tle = 0
re = 0

for j in r:
  if j == 'AC':
    ac += 1
  elif j == 'WA':
    wa += 1
  elif j == 'TLE':
    tle += 1
  elif j == 'RE':
    re += 1
print('AC x',ac)
print('WA x',wa)
print('TLE x',tle)
print('RE x',re)

### FIXED CODE ###

N = int(input())
ac = 0
wa = 0
tle = 0
re = 0

for i in range(N):
  j = input()
  if j == 'AC':
    ac += 1
  elif j == 'WA':
    wa += 1
  elif j == 'TLE':
    tle += 1
  else:
    re += 1
print('AC x',ac)
print('WA x',wa)
print('TLE x',tle)
print('RE x',re)
### BUGGY CODE ###

# coding: utf-8
import sys
import numpy as np

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

H, W, K = lr()
S = np.array([list(map(int, sr())) for _ in range(H)])
Scum = np.cumsum(S, axis=1)
INF = 10 ** 10
answer = INF
for pattern in range(1<<H-1):
    cnt = 0
    Tcum = Scum.copy()
    for i in range(H-1):
        if pattern>>i & 1:  # 切れ目
            cnt += 1
        else:
            Tcum[i+1] += Tcum[i]
    prev = -1
    w = 0
    while w < W:
        if np.any(Tcum[:, w] - (Tcum[:, prev] if prev >= 0 else 0) > K):
            if prev == w - 1:  # 1列でKをオーバー
                break
            cnt += 1
            prev = w - 1
        else:
            w += 1
    else:
        answer = min(answer, cnt)

print(answer)


### FIXED CODE ###

import sys
from itertools import accumulate

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

H, W, K = lr()
S = [list(map(int, sr())) for _ in range(H)]
Scum = [list(accumulate(x)) for x in S]
answer = 10000
for bit in range(1<<(H-1)):
    count = 0
    for i in range(H-1):
        if bit >> i & 1:
            count += 1
    bit += 1 << H-1 # 最後の切れ目
    # 縦のラインは貪欲法
    prev = -1
    w = 0
    while w < W:
        white = 0
        cut = False
        for i in range(H):
            white += Scum[i][w] - (Scum[i][prev] if prev >= 0 else 0)
            if (bit >> i) & 1: # 切れ目が来た
                if white > K:
                    cut = True
                white = 0
        if cut:
            if prev == w-1: # 一列でKをオーバー
                break
            count += 1
            prev = w-1
        else:
            w += 1
    else:
        answer = min(answer, count)

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

def main():
    A,B,K = map(int, input().split())

    for i in range(A, B+1):
        if (i < A+K) or (i > B-K):
            print(i)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    A,B,K = map(int, input().split())

    a = []
    for i in range(A, A+K):
        if i <= B:
            a.append(i)
            print(i)
    for i in range(B-K+1, B+1):
        if ((i in a)==False)and(i>=A):
            print(i)

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

S = input()
Q = int(input())
s = 1
for _ in range(Q):
    q = input()
    if q!='1':
        if (q[2]=='1' and s==1) or (q[2]!='1' and s!=1):
            S = q[4]+S
        else:
            S = S+q[4]
    else:
        s *= -1
if s==1:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
s = 1
for _ in range(Q):
    q = input()
    if q!='1':
        if (q[2]=='1' and s==1) or (q[2]!='1' and s!=1):
            S.extendleft(q[4])
        else:
            S.extend(q[4])
    else:
        s *= -1
S = ''.join(list(S))
if s==1:
    print(S)
else:
    print(S[::-1])
### BUGGY CODE ###

# @oj:atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-04-20 10:31
# @url:https://atcoder.jp/contests/dp/tasks/dp_b
import sys
def input():
    return sys.stdin.readline().strip()

def main():
    nk=list(map(int,input().split()))
    h=list(map(int,input().split()))
    n=nk[0]
    k=nk[1]
    dp=[10**9]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for (i,x) in enumerate(dp[2:],2):
    #     dp[i]=min(dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i))
        for j in range(max(0,i-k),i):
            dp[i]=min(dp[j]+abs(h[i]-h[j]),dp[i])

    print (dp[-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    size, jumps = map(int, input().split())
    array = list(map(int, input().split()))
    dp = [999999999] * size
    dp[0]= 0
    dp[1] = abs(array[0]- array[1])
    for i in range(2,size):
        dp[i] = min(abs(array[i] - array[j]) + dp[j] for j in range(max(0, i - jumps), i))
    print(dp[size-1])

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

import numpy as np

n, q = [int(item) for item in input().split()]
s = input()
lr = [[int(item) for item in input().split()] for _ in range(q)]

is_ac = np.zeros(n)
for i in range(n-2):
  if s[i:i+2] == "AC":
    is_ac[i] = True

for item in lr:
  ans = sum(is_ac[item[0]-1: item[1]])
  if s[item[1]-1] == "A":
    if item[1] != n:
      if s[item[1]] == "C":
        ans -= 1
  print(int(ans))

### FIXED CODE ###

n, q = [int(item) for item in input().split()]
s = input()
lr = [[int(item) for item in input().split()] for _ in range(q)]

is_ac = [0] * n
count = 0
for i in range(n-1):
  if s[i] == "A":
    if s[i+1] == "C":
      count += 1
  is_ac[i+1] = count
is_ac[-1] = count
for item in lr:
  ans = is_ac[item[1]-1] - is_ac[item[0]-1]
  print(ans)
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
l=[]
l.append('@'*(w+2))
for i in range(h):
    l.append('@'+input()+'@')
l.append('@'*(w+2))
q=deque()
p=[[-1 for i in j] for j in l]
for i in range(1,h+1):
    for j in range(1,w+1):
        if l[i][j]=='#':
            q.append([i,j])
            p[i][j]=0
while len(q)>0:
    x,y=q.popleft()
    for i,j in [[1,0],[-1,0],[0,-1],[0,1]]:
        if l[x+i][y+j]=='.' and p[x+i][y+j]==-1:
            q.append([x+i,y+j])
            p[x+i][y+j]=p[x][y]+1
a=0
for i in p:
    for j in i:
        a=max(a,j)
print(a)
#print(*p,sep='\n')

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
l=[]
l.append('@'*(w+2))
for i in range(h):
    l.append('@'+input()+'@')
l.append('@'*(w+2))
q=deque()
p=[[-1 for i in j] for j in l]
for i in range(1,h+1):
    for j in range(1,w+1):
        if l[i][j]=='#':
            q.append([i,j])
            p[i][j]=0
while len(q)>0:
    x,y=q.popleft()
    for i,j in [[1,0],[-1,0],[0,-1],[0,1]]:
        if l[x+i][y+j]=='.' and p[x+i][y+j]==-1:
            q.append([x+i,y+j])
            p[x+i][y+j]=p[x][y]+1
a=0
for i in p:
    for j in i:
        a=max(a,j)
print(a)
#print(*p,sep='\n')
### BUGGY CODE ###

import itertools
r,g,b,n=map(int,input().split())
x,y=n//r,n//g
x,y=list(range(0,r*x+1,r)),list(range(0,g*y+1,g))
count=0
for i,j in list(itertools.product(x,y)):
  d=n-i-j
  if d<0:
    pass
  elif d==0:
    count+=1
  elif d%b==0:
    count+=1
print(count)

### FIXED CODE ###

import collections
import itertools
r,g,b,n=map(int,input().split())
x,y=n//r,n//g
x,y=list(range(0,r*x+1,r)),list(range(0,g*y+1,g))
l=[i+j for i,j in itertools.product(x,y) if i+j<=n]
z=collections.Counter(l)
count=0
for key,value in zip(z.keys(),z.values()):
  v=n-key
  if v==0:
    count+=value
  elif v%b==0:
    count+=value
print(count)
### BUGGY CODE ###

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


def add(j):
    for i in range(g):
        now[i] += c[i][j]
    for i in range(g):
        if now[i] > K:
            return False
    return True


ans = 10**30
for i in range(2 ** (H-1)):
    g = 0
    id = [-1]*H
    for j in range(H):  # このループが一番のポイント
        id[j] = g
        if (i >> j & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            g += 1
    g += 1

    c = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            c[id[i]][j] += S[i][j]

    num = g-1
    now = [0]*g
    for j in range(W):
        if not add(j):
            num += 1
            now = [0]*g
            if not add(j):
                num = 10**30
                continue

    ans = min(ans, num)

print(ans)


### FIXED CODE ###

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


def add(j):
    for i in range(g):
        now[i] += c[i][j]
    for i in range(g):
        if now[i] > K:
            return False
    return True


ans = 10**30
for i in range(2 ** (H-1)):
    g = 0
    id = [-1]*H
    for j in range(H):  # このループが一番のポイント
        id[j] = g
        if (i >> j & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            g += 1
    g += 1

    c = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            c[id[i]][j] += S[i][j]

    num = g-1
    now = [0]*g
    for j in range(W):
        if not add(j):
            num += 1
            now = [0]*g
            if not add(j):
                num = 10**30
                continue

    ans = min(ans, num)

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

import numpy as np
N, Q = map(int,input().split())
S= input()
ac_pos_list = []
start = 0
ret = 0
while ret != -1:
    ret = S.find('AC',start)
    if ret != -1:
        ac_pos_list.append(ret)
        start = ret + 2        
ac_pos_list = np.array(ac_pos_list)

for i in range(Q):
    l,r = map(int,input().split())
    l = l-1
    r = r-1
    ans = np.sum((ac_pos_list>=l) & (ac_pos_list<=r-1))
    print(ans)


### FIXED CODE ###

N, Q = map(int,input().split())
S= input()
lr_list = [list(map(int,input().split())) for _ in range(Q)]

# ac_tf_list = [1 if S[i:i+2]=='AC' else 0 for i in range(N-1)]
t = [0]*N
for i in range(N-1):
    if S[i:i+2]=='AC':
        t[i+1] = t[i]+1
    else:
        t[i+1] = t[i]

for i in range(Q):
    l = lr_list[i][0]-1
    r = lr_list[i][1]-1
    print(t[r]-t[l])
### BUGGY CODE ###

# 階段の段数, 壊れている階段の数
n, m = map(int, input().split())

# 壊れている階段
a = []
for i in range(m):
    a.append(int(input()))

# DPテーブル初期化値
INIT = 0
# DPテーブル(dp[i]：i番目の段に到達する移動方法の総数)
dp = [INIT for i in range(n + 1)]

# 0番目の段に到達するための移動方法は1通り
dp[0] = 1

# dp[1]～dp[n]までループ
for i in range(1, n + 1):
    # 階段が壊れている場合、到達できないので0通り
    if (i in a):
        dp[i] = 0
    # i = 1の場合、0番目の段から1つ飛びで来るパターンしかない
    elif (i <= 1):
        dp[i] = dp[i - 1]
    # それ以外の場合、1つ飛びパターンと2つ飛びパターンの合計
    else:
        dp[i] = dp[i - 1] + dp[i - 2]

# 最終地点のDPテーブルの値を1000000007で割った余りが答えとなる
print(dp[n] % 1000000007)


### FIXED CODE ###

INIT = 1
n, m = map(int, input().split())
dp = [INIT for i in range(n + 1)]

for i in range(m):
    a = int(input())
    dp[a] = 0

for i in range(2, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) * dp[i]

print(dp[n] % 1000000007)
### BUGGY CODE ###

n,m=map(int,input().split())
field=[[] for i in range(3*n)]
for i in range(m):
     x,y=map(int,input().split())
     x,y=x-1,y-1
     field[3*x].append(3*y+1)
     field[3*x+1].append(3*y+2)
     field[3*x+2].append(3*y)

s,t=map(int,input().split())
s,t=s-1,t-1
s,t=3*s,3*t

que=[s]
ok=[s]
cnt=0
flag=0
while que!=[]:
     que2=[]
     cnt+=1
     for i in que:
          if flag==1:
               break
          for j in field[i]:
               if j not in ok:
                    ok.append(j)
                    if j==t:
                         print(cnt//3)
                         flag=1
                         break
                    que2.append(j)
     que=que2
if flag==0:
     print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
def main():
     n,m=map(int,input().split())
     field=[[] for i in range(3*n)]
     for i in range(m):
          x,y=map(int,input().split())
          x,y=x-1,y-1
          field[3*x].append(3*y+1)
          field[3*x+1].append(3*y+2)
          field[3*x+2].append(3*y)
     
     s,t=map(int,input().split())
     s,t=s-1,t-1
     s,t=3*s,3*t
     
     d=[float('inf') for i in range(3*n)]
     d[s]=0
     
     que=[s]
     cnt=0
     while que!=[]:
          que2=[]
          cnt+=1
          for i in que:
               for j in field[i]:
                    if d[j]>cnt:
                         d[j]=cnt
                         que2.append(j)
          que=que2
     if d[t]==float('inf'):
          print(-1)
     else:
          print(d[t]//3)
     return 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

lst.sort(reverse=True)

for i in range(M):
    lst[lst.index(max(lst))] = max(lst) // 2 

print (sum(lst))



### FIXED CODE ###

import heapq

N,M = map(int,input().split())
#lst = list(map(int,input().split()))
lst = [-int(x) for x in input().split()]

heapq.heapify(lst)
 
for i in range(M):
    lstmin = heapq.heappop(lst)
    b = (-(lstmin) // 2)
    heapq.heappush(lst,-b)
    
print (-sum(lst))
### BUGGY CODE ###

import itertools
N,M = map(int,input().split())
A = []
X = [[0]]*M
 
for m in range(M):
  a,b = map(int,input().split())
  A.append([a,b])
  #X[m] = X[m] + [a] + [b]

ans = []
XX = [[] for _ in range(1<<len(A))]
X = A.copy()
i = 0
for _ in range(N):
  for x,v in itertools.product(X,A):   
    if x[-1] == v[0]:
      if v[1] in x:
        ans.append(x+[v[1]])
        ans[0] = [len(ans[0])-1] + ans[0]
        print(*ans[0][:-1])
        import sys
        sys.exit()
      else:
        #XX.append(x + [v[1]])
        XX[i] = x + [v[1]]
        i += 1
    X = [x for x in XX if x]


print(-1)


### FIXED CODE ###

def main():
  from collections import deque
  n,m,*t=map(int,open(0).read().split())
  i=[0]*n
  o=[[]for _ in range(n)]
  for a,b in zip(*[iter(t)]*2):
    o[a-1]+=b-1,
    i[b-1]+=1
  q=deque(v for v,f in enumerate(i)if f<1)
  r=[]
  while q:
    v=q.popleft()
    r+=v,
    for w in o[v]:
      i[w]-=1
      if i[w]==0:q+=w,
  print(-(len(r)==n))
main()
### BUGGY CODE ###

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

from decimal import *
import numpy as np


getcontext().prec = 4

L = int(input())
L = Decimal(L)

x=y=z=0
x = Decimal(x)
y = Decimal(y)
z = Decimal(z)


p = 0.01
p = Decimal(p)

maxV = 0

for x in np.arange(p,L+1,p):
    for y in np.arange(p,L+1,p):
        z = L-(x+y)

        V = x*y*z
    
        if maxV < V:
            maxV = V


print(maxV)

### FIXED CODE ###

L = int(input())

x=y=z=0

x=y=z=L/3

V = x*y*z




print(V)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

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


def solve(t):
    if len(t) <= m + 1:
        return [len(t) - 1]
    for i in reversed(range(1, m + 1)):
        if t[len(t) - 1 - i] == '0':
            cand = solve(t[:-i])
            if len(cand) != 0:
                cand.append(i)
                return cand

    return []


cnt1_continuous = 0
cnt = 0
for i in range(n + 1):
    if s[i] == '1':
        cnt += 1
        if i == n:
            cnt1_continuous = max(cnt1_continuous, cnt)
    else:
        cnt1_continuous = max(cnt1_continuous, cnt)
        cnt = 0

if cnt1_continuous >= m:
    print(-1)
else:
    print(*solve(s))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

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


def solve(t):
    if len(t) <= m + 1:
        return [len(t) - 1]
    for i in reversed(range(1, m + 1)):
        if t[len(t) - 1 - i] == '0':
            cand = solve(t[:-i])
            if len(cand) != 0:
                cand.append(i)
                return cand

    return []


cnt1_continuous = 0
cnt = 0
for i in range(n + 1):
    if s[i] == '1':
        cnt += 1
        if i == n:
            cnt1_continuous = max(cnt1_continuous, cnt)
    else:
        cnt1_continuous = max(cnt1_continuous, cnt)
        cnt = 0

if cnt1_continuous >= m:
    print(-1)
else:
    if m == 1:
        ans = [1] * n
    else:
        ans = solve(s)
    print(*ans)
### BUGGY CODE ###

from collections import deque
S=input()
S_list=deque()
for k in range(len(S)):
    S_list.append(S[k])
Q=int(input())
kouho=[input().split() for i in range(Q)]
"""for i in range(Q):
    kari=input().split()
    kouho.append(kari)"""
for j in range(Q):
    if kouho[j][0]=="1":
        S_list.reverse()
    else:
        if kouho[j][1]=="1":
            S_list.appendleft(kouho[j][2])
        else:
            S_list.append(kouho[j][2])
print(*S_list,sep="")


### FIXED CODE ###

from collections import deque
S=input()
S_list=deque()
for k in range(len(S)):
    S_list.append(S[k])
Q=int(input())
kouho=[input().split() for i in range(Q)]
"""for i in range(Q):
    kari=input().split()
    kouho.append(kari)"""
hanten=[]
count=0
flaag=["sonomama","hantai"]

for j in range(Q):
    flag=flaag[count%2]
    if kouho[j][0]=="1":
        count+=1
    else:
        if flag=="sonomama":
            if kouho[j][1]=="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
        else:
            if kouho[j][1]!="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
for k in range(count%2):
    S_list.reverse()
print(*S_list,sep="")
### BUGGY CODE ###

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

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

point = [k] * n

for _ in range(q):
    answer = int(input()) - 1
    for i in range(n):
        if i != answer:
            point[i] -= 1

for j in point:
    if j > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

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

point = [k - q] * n

for _ in range(q):
    answer = int(input()) - 1
    point[answer] += 1

for j in point:
    if j > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
input=sys.stdin.readline
from collections import defaultdict as dd
n,w=map(int,input().split())
we=[0]*n
val=[0]*n
for i in range(n):
  ww,v=map(int,input().split())
  we[i]=ww
  val[i]=v
dp=dd(lambda:-1)
def solve(i,w,we,val):
  if(i==0 or w==0):
    return 0
  if(dp[(i,w)]!=-1):
    return dp[(i,w)]
  if(we[i-1]<=w):
    if(dp[(i-1,w-we[i-1])]!=-1):
      x=dp[(i-1,w-we[i-1])]
    else:
      x=dp[(i-1,w-we[i-1])]=solve(i-1,w-we[i-1],we,val)
    if(dp[(i-1,w)]!=-1):
      y=dp[(i-1,w)]
    else:
      y=dp[(i-1,w)]=solve(i-1,w,we,val)
    dp[(i,w)]=max(val[i-1]+x,y)
    return dp[(i,w)]
  else:
    if(dp[(i-1,w)]!=-1):
      y=dp[(i-1,w)]
    else:
      y=dp[(i-1,w)]=solve(i-1,w,we,val)
    dp[(i,w)]=y
    return dp[(i,w)]
print(solve(n,w,we,val))
#print(dp)  


### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import defaultdict as dd
n,w=map(int,input().split())
maxn=10000000000000000
we=[0]*n
val=[0]*n
su=0
for i in range(n):
    ww,v=map(int,input().split())
    we[i]=ww
    val[i]=v
    su+=v
dp=[maxn]*(su+1)
dp[0]=0
for i in range(n):
    for j in range(su-val[i],-1,-1):
        dp[j+val[i]]=min(dp[j+val[i]],we[i]+dp[j])
ans=0
for i in range(len(dp)):
    if(dp[i]<=w):
        ans=max(ans,i)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

def tami(i,j,k):
  if (i == j == k == 0):
    return 0
  else:
    res = 0
    if (i > 0):
      res += dp[i-1][j][k] * i
    if (j > 0):
      res += dp[i+1][j-1][k] * j
    if (k > 0):
      res += dp[i][j+1][k-1] * k
    res += N
    res *= (1 / (i + j + k))
    dp[i][j][k] = res
    return res
  
N = int(input())
a = list(map(float,input().split()))

one = a.count(1)
two = a.count(2)
three = a.count(3)

num = max(one,two,three)

dp = [[[-1]*(N+1) for i in range(N+1)] for i in range(N+1)]

for k in range(0, N + 1):
  for j in range(0, N - k + 1):
    for i in range(0, N - k - j + 1):
      tami(i, j, k)

print(dp[one][two][three]+1)


### FIXED CODE ###

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

m = d = t = 0
for i in range(len(a)):
  if a[i] == 1:
    m += 1
  elif a[i] == 2:
    d += 1
  else:
    t += 1
    
M = t + d + m
D = [[[0] * (M + 1) for i in range(d + t + 1)] for j in range(t + 1)]

su = 0
D[t][d][m] = 1

divTable = [1]
for i in range(1, 10000):
  divTable.append(1.0 / i)


for i in range(t, -1, -1):
  for j in range(d + t - i, -1, -1):
    for k in range(M - i - j, -1, -1):
      y = D[i][j][k]
      if y != 0:
        div = y * divTable[i + j + k]
        if i + j + k != 0:
          su += N * div
        if i >= 1:
          D[i - 1][j + 1][k] += i * div
        if j >= 1: 
          D[i][j - 1][k + 1] += j * div
        if k >= 1:
          D[i][j][k - 1] += k * div

print(su)
### BUGGY CODE ###

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

ship1 =[]
shipn =[]

for ab in ABs:
    if ab[0]==1:ship1.append(ab)
    elif ab[1]==N:shipn.append(ab)

jdg=False      
      
for _, j in ship1:
    if [j, N] in shipn:jdg=True
if jdg:print('POSSIBLE')
else:print('IMPOSSIBLE')

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = map(int,input().split())
ABs = list([list(map(int,input().split())) for _ in range(M)])
 
ship1 =[]
shipn =[]
 
for ab in ABs:
    if ab[0]==1:ship1.append(ab[1])
    elif ab[1]==N:shipn.append(ab[0])
 
      
if list(set(ship1) & set(shipn)) ==[]:print('IMPOSSIBLE')
else:print('POSSIBLE')
### BUGGY CODE ###

# ABC-137-D
import heapq
import bisect
N, M = map(int, input().split())
AB = []#Aでソートをかけて利用する。
BA = []#Bでソートをかけてheapqで利用する。
heapq.heapify(BA)

for _ in range(N):
    A, B = map(int, input().split())
    AB.append((A, B))    
AB = sorted(AB)

ans = 0
check_M = 1
while check_M <= M:
    r = bisect.bisect_right(AB, (check_M+1, 0))
    for A, B in AB[:r]:
        heapq.heappush(BA, (-1*B, A))
    try:
        max_B = heapq.heappop(BA)
    except:
        check_M += 1
        AB = AB[r:]
        continue
    ans += (-1) * max_B[0]
    check_M += 1
    AB = AB[r:]

print(ans)

### FIXED CODE ###

# ABC-137-D
import heapq

N, M = map(int, input().split())
day_value = [[] for _ in range(M+1)]

for _ in range(N):
    A, B = map(int, input().split())
    if A <= M:
        day_value[A].append(B)

ans = 0
check_M = 1
BA = []
heapq.heapify(BA)

while check_M <= M:
    for item in day_value[check_M]:
        heapq.heappush(BA, -1*item)
    try:
        max_B = heapq.heappop(BA)
    except:
        check_M += 1
        continue
    ans += (-1) * max_B
    check_M += 1
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    D = sorted(map(int, input().split()))
    m = int(input())
    T = sorted(map(int, input().split()))
    ind = 0
    for t in T:
        if ind == len(D):
            print('NO')
            return
        for i, d in enumerate(D[ind:]):
            if t == d:
                ind += i + 1
                break
        else:
            print('NO')
            return
    print('YES')
main()

### FIXED CODE ###

from collections import Counter
def main():
    n = int(input())
    D = sorted(map(int, input().split()))
    m = int(input())
    T = sorted(map(int, input().split()))
    CD = Counter(D)
    CT = Counter(T).items()
    for i, c in CT:
        if CD[i] < c:
            print('NO')
            return
    print('YES')
main()
### BUGGY CODE ###

from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))

way = [[float("inf") if i != j else 0 for i in range(N + 1)] for j in range(N + 1)]
for m in range(M):
    a, b, c = map(int, input().split())
    way[a][b] = c
    way[b][a] = c

for i in range(N + 1):
    for j in range(N + 1):
        w_ji = way[j][i]
        for k, (w_ik, w_jk) in enumerate(zip(way[i], way[j])):
            if k == 0:
                continue
            tmp = w_ji + w_ik
            if w_jk > tmp:
                way[j][k] = tmp
ans = float("inf")
for path in list(permutations(r)):
    time = 0
    for i in range(len(path) - 1):
        time += way[path[i]][path[i + 1]]
    ans = min(ans, time)
print(ans)


### FIXED CODE ###

from itertools import permutations

def wfa(N):
    for i in range(N + 1):
        for j in range(N + 1):
            w_ji = way[j][i]
            for k, (w_ik, w_jk) in enumerate(zip(way[i], way[j])):
                if k == 0:
                    continue
                tmp = w_ji + w_ik
                if w_jk > tmp:
                    way[j][k] = tmp


N, M, R = map(int, input().split())
r = list(map(int, input().split()))

way = [[float("inf") if i != j else 0 for i in range(N + 1)] for j in range(N + 1)]
for m in range(M):
    a, b, c = map(int, input().split())
    way[a][b] = c
    way[b][a] = c

wfa(N)

ans = float("inf")
for path in permutations(r):
    time = 0
    for i in range(len(path) - 1):
        time += way[path[i]][path[i + 1]]
    ans = min(ans, time)
print(ans)