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

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

dp = [[0 for _ in range(n)] for _ in range(n)]
INF = 10**18
for i in range(n):
    for j in range(n):
        if i!=j:
            dp[i][j] = INF
for a,b,t in l:
    dp[a-1][b-1] = t
    dp[b-1][a-1] = t
#print(dp)

#最短リスト
for c in range(n):
    for f in range(n):
        for la in range(n):
            dp[f][la] = min(dp[f][la] , dp[f][c] +  dp[c][la])

#各辺が何かしらの最短ルートに含まれているか
ans = 0
for a, b, t in l:
    cou = 0
    for j in range(n):
        for k in range(n):
            #jからkの最短ルートにa,bが入ってるいるか
            if dp[j][k] != dp[j][a-1] + t + dp[b-1][k]:
                cou += 1
    if cou==n**2:
        ans += 1

print(ans)


### FIXED CODE ###

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

dp = [[0 for _ in range(n)] for _ in range(n)]
INF = 10**18
for i in range(n):
    for j in range(n):
        if i!=j:
            dp[i][j] = INF
for a,b,t in l:
    dp[a-1][b-1] = t
    dp[b-1][a-1] = t
#print(dp)

#最短リスト
for c in range(n):
    for f in range(n):
        for la in range(n):
            dp[f][la] = min(dp[f][la] , dp[f][c] +  dp[c][la])

#各辺が何かしらの最短ルートに含まれているか
ans = 0
for a, b, t in l:
    cou = 0
    for j in range(n):
        for k in range(n):
            #jからkの最短ルートにa,bが入ってるいるか
            if dp[j][k] != dp[j][a-1] + t + dp[b-1][k]:
                cou += 1
    if cou==n**2:
        ans += 1

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

n, *D  = [list(map(int, s.split())) for s in open(0)]
D = D[0]
dic = dict()
for d1 in D:
 
    if d1 not in dic:
        dic[d1] = 1
    else:
        dic[d1] += 1

for d2 in D:
    comb = 0
    dic[d2] -= 1
    for i in dic.values():
        if i >= 2:
            comb += i * (i - 1) / 2
    dic[d2] += 1
    print(int(comb))

### FIXED CODE ###

from collections import defaultdict
n, *D  = [list(map(int, s.split())) for s in open(0)]
D = D[0]
dic = defaultdict(int)
for i in D:
    dic[i] += 1

total_comb = 0
for j in dic:
    if dic[j] >= 2:
        total_comb += dic[j] * (dic[j] - 1) / 2
for k in D:
    if dic[k] >= 2:
        print(int(total_comb - dic[k] + 1))
    else:
        print(int(total_comb))
### BUGGY CODE ###

import numpy as np
N=int(input())
A=list(map(int,input().split()))
ans=np.zeros(N)
for i in A:
  ans[i-1]=A.index(i)+1
for j in ans:
  print(int(j),end=" ")

### FIXED CODE ###

import numpy as np
N=int(input())
A=list(map(int,input().split()))
ans=np.zeros(N)
count=0
for i in A:
  ans[i-1]=count+1
  count+=1
for j in ans:
  print(int(j),end=" ")
### BUGGY CODE ###

from collections import defaultdict as dd
H,W,N=map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(N)]
tpl = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)]
edge_WtoB = dd(list)
edge_BtoB = dd(list)
node_B = set(ab)
node_W = set()
res = dd(int)
# 今見てるマスが黒
for a,b in ab:
    for s,t in tpl:
        tgt = (a+s,b+t)
        # 隣接マスも黒
        if tgt in node_B:
            if not (1 < a < H and 1 < b < W):
                continue
            edge_BtoB[(a,b)].append(tgt)
        # 隣接マスは白
        else:
            if not (1 < a + s < H and 1 < b + t < W):
                continue
            edge_WtoB[tgt].append((a,b))
            node_W.add(tgt)
for tgt in node_W:
    res[len(edge_WtoB[tgt])] += 1
for tgt in node_B:
    res[len(edge_BtoB[tgt])] += 1
zero = (H-2)*(W-2)
for j in range(1,10):
    zero -= res[j]
res[0] = zero
for j in range(10):
    print(res[j])

### FIXED CODE ###

from collections import defaultdict as dd
H,W,N=map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(N)]
tpl = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)]
edge_WtoB = dd(int)
edge_BtoB = dd(int)
node_B = set(ab)
# node_W = set()
res = dd(int)
# 今見てるマスが黒
for a,b in ab:
    for s,t in tpl:
        tgt = (a+s,b+t)
        # 隣接マスも黒
        if tgt in node_B:
            if not (1 < a < H and 1 < b < W):
                continue
            edge_BtoB[(a,b)] += 1
        # 隣接マスは白
        else:
            if not (1 < a + s < H and 1 < b + t < W):
                continue
            edge_WtoB[tgt] += 1
            # node_W.add(tgt)
for val in edge_WtoB.values():
    res[val] += 1
for val in edge_BtoB.values():
    res[val] += 1
zero = (H-2)*(W-2)
for j in range(1,10):
    zero -= res[j]
res[0] = zero
for j in range(10):
    print(res[j])
### BUGGY CODE ###

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

dp = [0]*n
for i in range(1, n):
    a = []
    if i >= k:
        for j in range(1, k+1):
            a.append(dp[i-j] + abs(h[i-j]-h[i]))
    else:
        for j in range(1, i+1):
            a.append(dp[i-j] + abs(h[i-j]-h[i]))
    dp[i] = min(a)
    
print(dp[-1])

### FIXED CODE ###

# B  => TLE
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0]*n
for i in range(1, n):
    a = 10**100
    if i >= k:
        for j in range(1, k+1):
            if a > dp[i-j] + abs(h[i-j]-h[i]):
                a = dp[i-j] + abs(h[i-j]-h[i])
    else:
        for j in range(1, i+1):
            if a > dp[i-j] + abs(h[i-j]-h[i]):
                a = dp[i-j] + abs(h[i-j]-h[i])
    dp[i] = a
    
print(dp[-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
VW = [[int(x) for x in input().split()] for _ in range(Q)]

if N == 1:
    answer = [str(min(v,w)) for v,w in VW]
else:
    answer = []
    for v,w in VW:
        while v != w:
            if v > w:
                v,w = w,v
            w = (w+N-2)//N
        answer.append(str(v))

print('\n'.join(answer))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N,Q = map(int,input().split())
V,W = np.array([input().split() for _ in range(Q)],dtype=np.int64).T

if N == 1:
    answer = np.minimum(V,W)
else:
    for _ in range(50):
        V[V>W] = (V[V>W]+N-2)//N
        W[W>V] = (W[W>V]+N-2)//N
    answer = V

print('\n'.join(answer.astype(str)))
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import numpy as np
# from itertools import *
# from collections import *

# S = input().split()
# N = int(input().split())
# N, K = [int(x) for x in input().split()]

N = int(input())
A = [int(x) for x in input().split()]

number = range(1, N+1)
numhei = [0] * N
for n in range(N):
    numhei[n] = number[n] + A[n]

numhei = np.array(numhei)

count = 0
for n in number:
    count += sum(n - A[n-1] == numhei[0:n-1])

print(count)


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

# import numpy as np
# from itertools import *
# from collections import *
from collections import Counter

# S = input().split()
# N = int(input().split())
# N, K = [int(x) for x in input().split()]

N = int(input())
A = [int(x) for x in input().split()]

number = range(1, N+1)
numhei = [0] * N
for n in range(N):
    numhei[n] = number[n] + A[n]

c = Counter(numhei)
count = 0
for n in number:
    count += c[n - A[n-1]]

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

import collections
N = int(input()) 
S = [0]*N
for i in range(N):
    S[i] = input()
c = collections.Counter(S)
values,counts = zip(*c.most_common())
X = c.most_common()[0][1]
list = []
for i in range(0,len(c.most_common())):
    if c.most_common()[i][1] == X:
        list.append(c.most_common()[i][0])
    else:
        break
list.sort()
for i in range(len(list)):
    print(list[i])

### FIXED CODE ###

import collections
N = int(input()) 
S = [0]*N
m = 0
for i in range(N):
    S[i] = input()
c = collections.Counter(S)
values,counts = zip(*c.most_common())
X = c.most_common()[0][1]
list = []
for i in range(0,len(c.most_common())):
    if counts[i] == X:
        list.append(values[i])
        m+=1
    else:
        break
list.sort()
for i in range(0,m):
    print(list[i])
### BUGGY CODE ###

# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
INF = 10 ** 10
from collections import deque
# 頂点、親、距離
dist = [INF] * N
for i in range(N):
  if dist[i] != INF:
    continue
  q = deque()
  q.append([i,-1,0])
  while q:
    v,parent,d = q.popleft()
#    print("v",v,"dist[v]",dist[v],"d",d)
    if dist[v] == INF:
      # 初めてくる場所
      dist[v] = d
    else:
      # 初めてではない場合
      if dist[v] != d:
        print("No")
        exit(0)
      else:
        continue
    for child in E[v]:
      if child == parent:
        continue
      q.append([child[0],v,d + child[1]])
else:
  print("Yes")


### FIXED CODE ###

# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
from collections import deque
# 頂点、親、距離
INF = 10 ** 10
dist = [INF] * N
for i in range(N):
  if dist[i] != INF:
    continue
  dist[i] = 0
  q = deque()
  q.append(i)
  while q:
    v = q.popleft()
    for child in E[v]:
      if dist[child[0]] == INF:
        dist[child[0]] = dist[v] + child[1]
        q.append(child[0])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

n, q = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(n-1)]
px = [tuple(map(int,input().split())) for i in range(q)]

es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)


# visited = [0]*n
ans = [0]*n

# DFS for tree
def dfs(v, parent = -1):# どこからきたかの情報を入れとく
    for to in es[v]:
        if to == parent: continue # 今回はcontinue

        # if visited[to]: continue # 今回はcontinueしない方がいいな

        ans[to] += ans[v]
        dfs(to, v)


for p, x in px:
    ans[p-1] += x

dfs(0)

print(*ans, sep=' ')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, q = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(n-1)]
px = [tuple(map(int,input().split())) for i in range(q)]

es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

ans = [0]*n

# DFS for tree (再帰はpypyの方が遅かったりするので注意)
def dfs(v=0, parent=-1):# どこからきたかの情報を入れとく
    for to in es[v]:
        if to == parent: continue # 今回はcontinue

        ans[to] += ans[v]
        dfs(to, v)


for p, x in px:
    ans[p-1] += x

dfs(0)

print(*ans, sep=' ')
### BUGGY CODE ###

import collections

n, m = map(int, input().split())
dic = collections.defaultdict(lambda:[])
for _ in range(m):
  a, b = map(int, input().split())
  dic[a].append(b)
  dic[b].append(a)
  
ans = [None] * n
bfs = [(1,0)]
visited = set()
while bfs:
  now, prev = bfs.pop(0)
  if now in visited:
    continue
  visited.add(now)
  if ans[now-1] == None:
    ans[now-1] = prev
  bfs.extend([(i, now) for i in dic[now]])

print('Yes')  
for i in range(1, n):
  print(ans[i])

### FIXED CODE ###

import collections

n, m = map(int, input().split())
dic = collections.defaultdict(lambda:[])
for _ in range(m):
  a, b = map(int, input().split())
  dic[a].append(b)
  dic[b].append(a)
  
ans = [None] * n
bfs = [(1,dic[1])]
visited = set()
get = 0
while bfs and get < n:
  now, nexts = bfs.pop(0)

  for i in nexts:
    if i in visited:
      continue
    ans[i-1] = now
    get += 1
    bfs.append((i,dic[i]))
    visited.add(i)
      
print('Yes')  
for i in range(1, n):
  print(ans[i])
### BUGGY CODE ###

import sys
def dfs(L,start):
    stack = [start]

    path =[-1]*len(L)
    path[start] = 0
    while stack:
        node = stack.pop()
        for n in L[node]:
            if path[n[0]] < 0:
                path[n[0]] = path[node]  + n[1]
                stack.append(n[0])

    return path

#input
input = sys.stdin.readline
N = int(input())
p = []
node = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)
    if l[0] not in node:
        node.append(l[0])
    if l[1] not in node:
        node.append(l[1])

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))

#neigher list
L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

d = dfs(L,K)

for i in range(Q):
    print(d[xy[i][0]]+ d[xy[i][1]])



### FIXED CODE ###

import sys
def dfs(L,start):
    stack = [start]

    path =[-1]*len(L)
    path[start] = 0
    while stack:
        node = stack.pop()
        for n in L[node]:
            if path[n[0]] < 0:
                path[n[0]] = path[node]  + n[1]
                stack.append(n[0])

    return path

#input
input = sys.stdin.readline
N = int(input())
p = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))

#neigher list
L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

d = dfs(L,K)

for i in range(Q):
    print(d[xy[i][0]]+ d[xy[i][1]])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
while all( A%2 == 0 for A in a ):
	    A = [ i/2 for i in a ]
	    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
while all(A%2 == 0 for A in a):
	a = [i/2 for i in a ]
	ans += 1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
s=sys.stdin.readlines()
n,q=map(int,s[0].split())
G=[[]*n for i in range(n)]
P=[0]*n
V=[0]*n
R=[0]*n
for e in s[1:n]:
    a,b=map(int,e.split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for e in s[n:]:
    c,d=map(int,e.split())
    P[c-1]+=d

def dsf(i,p):
    V[i]=1
    R[i]+=p+P[i]
    p=0
    if G[i]!=[]:
        for j in G[i]:
            if V[j]!=1:
                dsf(j,R[i])
dsf(0,0)
print(' '.join(map(str,R)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
s=sys.stdin.readlines()
n,q=map(int,s[0].split())
G=[[]*n for i in range(n)]
P=[0]*n
V=[0]*n
R=[0]*n
for e in s[1:n]:
    a,b=map(int,e.split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for e in s[n:]:
    c,d=map(int,e.split())
    P[c-1]+=d

def dsf(i,p):
    V[i]=1
    R[i]+=p+P[i]
    p=0
    for j in G[i]:
        if V[j]!=1:
            dsf(j,R[i])
dsf(0,0)
print(' '.join(map(str,R)))
### BUGGY CODE ###

h,w,m=map(int, input().split())
hw=[list(map(int, input().split())) for _ in range(m)]

tate=[]
yoko=[]

for i in range(m):
    tate.append(hw[i][0])
    yoko.append(hw[i][1])

from collections import Counter
tatec=Counter(tate).most_common()
yokoc=Counter(yoko).most_common()

c_1_max=tatec[0][1]
c_1s=[]
for t in tatec:
    if t[1]==c_1_max:
        c_1s.append(t[0])
    else:
        break

c_2_max=yokoc[0][1]
c_2s=[]
for y in yokoc:
    if y[1]==c_2_max:
        c_2s.append(y[0])
    else:
        break

flag=False

for c_1 in c_1s:
    for c_2 in c_2s:
        tmp_flag=0
        for i in range(m):
            h_i=hw[i][0]
            w_i=hw[i][1]
            if h_i!=c_1 or w_i!=c_2:
                tmp_flag+=1
        if tmp_flag==m:
            flag=True
        if flag:
            break

print(max(tatec[0][1]+yokoc[0][1], 1) if flag else max(tatec[0][1]+yokoc[0][1]-1, 1))


### FIXED CODE ###

h,w,m=map(int, input().split())
hw=[list(map(int, input().split())) for _ in range(m)]

y_list=[0]*h
x_list=[0]*w

for h_i, w_i in hw:
    y_list[h_i-1]+=1
    x_list[w_i-1]+=1

my_cnt=max(y_list)
mx_cnt=max(x_list)

y_cnt=0
x_cnt=0

my_set=set()
mx_set=set()

for h_i, w_i in hw:
    if y_list[h_i-1]==my_cnt:
        my_set.add(h_i-1)
    if x_list[w_i-1]==mx_cnt:
        mx_set.add(w_i-1)

cnt=0
for h_i, w_i in hw:
    if y_list[h_i-1]==my_cnt and x_list[w_i-1]==mx_cnt:
        cnt+=1

print(my_cnt+mx_cnt-1 if cnt==len(my_set)*len(mx_set) else my_cnt+mx_cnt)
### BUGGY CODE ###

def main():
    S = str(input())
    K = int(input())

    N = len(S)
    lst = []
    lst_append = lst.append
    s = set()
    s_add = s.add
    for i in range(N):
        for j in range(i + 1, N + 1):
            if S[i:j] in s:
                continue
            else:
                s_add(S[i:j])
                lst_append(S[i:j])

    lst.sort()
    print (lst[K - 1])
    # print (lst)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S = str(input())
    K = int(input())
    N = len(S)

    tmp = [[] for _ in range(26)]
    for i in range(N):
        tmp[ord(S[i]) - ord('a')].append(i)

    lst = []
    lst_append = lst.append
    s = set()
    s_add = s.add
    for num in tmp:
        for i in num:
            for j in range(i + 1, min(N, i + K) + 1):
                if S[i:j] in s:
                    continue
                else:
                    s_add(S[i:j])
                    lst_append(S[i:j])
        if len(s) >= K:
            lst.sort()
            print (lst[K - 1])
            # print (lst)
            return

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

N = int(input()) 
A=list(map(int,input().split())) 
s=[]
for i in range(N):
    s.append(A.count(i+1))
    print(s[i])

### FIXED CODE ###

import collections
n = int(input())
base = map(int,input().split())
c = collections.Counter(base)
for i in range(1,n):
    print(c[i])
print(0)
### BUGGY CODE ###

import copy
Q = int(input())
lis = []
minimam = 10**5
maximam = 1
for _ in range(Q):
    l, r = map(int, input().split())
    lis.append((l, r))
    minimam = min(minimam, l)
    maximam = max(maximam, r)
flag_lis = [1] * (maximam+1)
flag_lis[0] = 0
flag_lis[1] = 0
for i in range(2, int((maximam-1)/2)+1):
    if flag_lis[i] != 0:
        for j in range(2*i,maximam+1,i):
            flag_lis[j] = 0
fin_lis = copy.copy(flag_lis)
for i in range(2, int((maximam+1)/2)+1):
    if flag_lis[i] == 0:
        fin_lis[2*i-1] = 0
for (l, r) in lis:
    count = 0
    for num in range(l,r+1,2):
        if fin_lis[num]==1:
            count += 1
    print(count)

### FIXED CODE ###

import copy
Q = int(input())
lis = []
maximam = 1
for _ in range(Q):
    l, r = map(int, input().split())
    lis.append((l, r))
    maximam = max(maximam, r)
flag_lis = [1] * (maximam+1)
flag_lis[0] = 0
flag_lis[1] = 0
for i in range(2, int((maximam-1)/2)+1):
    if flag_lis[i] != 0:
        for j in range(2*i,maximam+1,i):
            flag_lis[j] = 0
fin_lis = [0]*(maximam+1)
count = 0
for i in range(3, maximam+1, 2):
    if flag_lis[i] == 1 and flag_lis[int((i+1)/2)] == 1:
        count += 1
    fin_lis[i] = count
for (l, r) in lis:
    if l == 1:
        print(fin_lis[r] - 0)
    else:
        print(fin_lis[r] - fin_lis[l-2])
### BUGGY CODE ###

def gcd(M, m):
	q = m
	r = M % m
	while r != 0:
		p = q
		q = r
		r = p % q
	return q
	
K = int(input())
gcd_sum = 0
for a in range(1, K+1):
	for b in range(1, K+1):
		for c in range(1, K+1):
			ab = gcd(b,a)
			gcd_sum += gcd(c, ab)
print(gcd_sum)

### FIXED CODE ###

def gcd(a, b):
  if a < b:
    a_init = a
    a = b
    b = a_init
  while b != 0:
    r = a % b
    a = b
    b = r
  return a
	
K = int(input())
count = 0
temp = []
for a in range(1, K+1):
	for b in range(1, a):
		temp.append(gcd(a, b))
for c in range(1, K+1):
	for j in range(len(temp)):
		count += gcd(c, temp[j]) * 2
	for k in range(1, K+1):
		count += gcd(c, k)
print(count)
### BUGGY CODE ###

n,m = map(int,input().split(" "))
q_list = []
res_list = []
for i in range(m):
    a,b = input().split(" ")
    q_list.append(int(a))
    res_list.append(b)
    


ac = 0
wa = 0
ac_list = []

for i,j in enumerate(res_list):
    if i == 0:
        if j == "AC":
            ac += 1
            ac_list.append(q_list[i])
        else:
            wa += 1
    elif q_list[i] not in ac_list:
        if j == "AC":
            ac += 1
            ac_list.append(q_list[i])
        else:
            wa += 1

for i,j in enumerate(res_list):
    if q_list[i] not in ac_list:
        wa -= 1



print(ac,wa)

### FIXED CODE ###

# coding: utf-8

n,m = map(int,input().split(" "))
ac_list = [0] * n
wa_list = [0] * n


wa = 0

for i in range(m):
    a,b = input().split(" ")
    if ac_list[int(a) - 1]:
        continue
    if b == "AC":
        ac_list[int(a) - 1] = 1
        wa += wa_list[int(a)-1]
    else:
        wa_list[int(a)-1] += 1
        
print(sum(ac_list),wa)
### BUGGY CODE ###

# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

INF = 1 << 62
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

dp = [[INF] * (N + 1) for _ in range(N)]

for i in range(N):
    dp[i][i + 1] = 0

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        subcost = min(dp[i][k] + dp[k][j] for k in range(i + 1, j))
        dp[i][j] = subcost + acc[j] - acc[i]

print(dp[0][N])


### FIXED CODE ###

# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

INF = 1 << 62
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

dp = [[INF] * (N + 1) for _ in range(N)]

for i in range(N):
    dp[i][i + 1] = 0

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        subcost = min(dp[i][k] + dp[k][j] for k in range(i + 1, j))
        dp[i][j] = subcost + acc[j] - acc[i]

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

h,w = map(int,input().split())
a = [input() for _ in range(h)]
ans = 0
queue = []
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            queue.append([i,j])
from collections import deque
queue = deque(queue)
dxy = [(0,1), (0,-1), (1,0), (-1,0)]
dp = [[10**4]*w for _ in range(h)]
for i,j in queue:
    dp[i][j] = 0
while len(queue):
    y,x = queue.popleft()
    d = dp[y][x]
    for dx,dy in dxy:
        nx, ny = x+dx, y+dy
        if not 0<=nx<=w-1:
            continue
        elif not 0<=ny<=h-1:
            continue
        elif dp[ny][nx]<=d+1:
            continue
        dp[ny][nx] = d+1
        queue.append((ny,nx))
print(max([max(dp[row]) for row in range(h)]))

### FIXED CODE ###

h,w = map(int,input().split())
a = [input() for _ in range(h)]
ans = 0
queue = []
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            queue.append([i,j])
from collections import deque
queue = deque(queue)
dxy = [(0,1), (0,-1), (1,0), (-1,0)]
dp = [[10**4]*w for _ in range(h)]
for i,j in queue:
    dp[i][j] = 0
while len(queue):
    y,x = queue.popleft()
    d = dp[y][x]
    for dx,dy in dxy:
        nx, ny = x+dx, y+dy
        if not 0<=nx<=w-1:
            continue
        elif not 0<=ny<=h-1:
            continue
        elif dp[ny][nx]<=d+1:
            continue
        dp[ny][nx] = d+1
        queue.append((ny,nx))
print(max([max(dp[row]) for row in range(h)]))
### BUGGY CODE ###

import sys
import copy
import re
n, k = [int(i) for i in sys.stdin.readline().split()]
s = input()
s_origi = copy.deepcopy(s)
def _reverse(text):
    res = text[::-1]
    res = ["R" if i == "L" else "L" for i in res]
    res = "".join(res)
    return res
for i in range(k):
    left = s.find("R")
    left = 0 if left == -1 else left
    right = s.rfind("R") + 1

    s = s[:left] + _reverse(s[left:right]) + s[right:]
    #s = copy.deepcopy(s_new)
cnt = sum([len(i) - 1 for i in re.findall(r"R{2,}|L{2,}", s)])
s = copy.deepcopy(s_origi)
for i in range(k):
    left = s.find("LR") + 1
    left = 0 if left == -1 else left
    right = s.rfind("RL") + 1
    if left > right:
        break

    s = s[:left] + _reverse(s[left:right]) + s[right:]
    #s = copy.deepcopy(s_new)
cnt = max(cnt, sum([len(i) - 1 for i in re.findall(r"R{2,}|L{2,}", s)]))
print(cnt)

### FIXED CODE ###

import re
n, k = [int(i) for i in input().split()]
s = input()
cnt = sum([1 for i in range(n-1) if s[i+1] == s[i]])
flg = (s[-1] == "R") + (s[0] == "R")
s += "L"
red_ls = re.findall(r"RL", s)
if len(red_ls) > k:
    print(cnt + k * 2)
else:
    if flg > 0:
        print(cnt + (len(red_ls) - flg) * 2 + flg)
    else:
        print(cnt + len(red_ls) * 2)