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

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,k = inpl()
g = [[] for i in range(n)]
seen = [-1]*n
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
def dfs(node,parent):
    cnt = 1
    for v in g[parent]:
        if seen[v] != -1:
            cnt += 1
    seen[node] = k-cnt
    for v in g[node]:
        if seen[v] == -1:
            dfs(v,node)

seen[0] = k
for i in g[0]:
    dfs(i,0)
res = 1
for x in seen:
    res *= x
    res %= mod
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

# class Combination:
#     """
#     comb = Combination(1000000)
#     print(comb(5, 3))  # 10
#     """
#     def __init__(self, n_max, mod=10**9+7):
#         self.mod = mod
#         self.modinv = self.make_modinv_list(n_max)
#         self.fac, self.facinv = self.make_factorial_list(n_max)

#     def __call__(self, n, r):
#         return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

#     def make_factorial_list(self, n):
#         # 階乗のリストと階乗のmod逆元のリストを返す O(n)
#         # self.make_modinv_list()が先に実行されている必要がある
#         fac = [1]
#         facinv = [1]
#         for i in range(1, n+1):
#             fac.append(fac[i-1] * i % self.mod)
#             facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
#         return fac, facinv

#     def make_modinv_list(self, n):
#         # 0からnまでのmod逆元のリストを返す O(n)
#         modinv = [0] * (n+1)
#         modinv[1] = 1
#         for i in range(2, n+1):
#             modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
#         return modinv


n,k = inpl()
g = [[] for i in range(n)]
seen = [-1]*n
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
def p(n,i):
    count = 1
    for _ in range(i):
        count = count * n % mod
        n -= 1
    return count
def dfs(cur,par=-1):
    res = 1
    c = 0 if par == -1 else 1
    cnt = 0
    for v in g[cur]:
        if v == par:
            continue
        cnt += 1
        res *= dfs(v,cur)
        res %= mod
    return res*p(k-c-1,cnt)
print(dfs(0,-1)*k%mod)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from operator import itemgetter

N, M = list(map(int, input().split()))
A = [0]*M
P = [0] * M
for i in range(M):
    A[i] = [0]*4
    A[i][0], A[i][1] = list(map(int, input().split()))
    A[i][2] = i
    P[i] = A[i][0]

p_unique = list(set(P))
p_unique_count = [0]*len(p_unique)
a = sorted(A, key=itemgetter(1))


def create_number(p, x):
    return str(p).zfill(6) + str(x).zfill(6)


for i in range(M):
    idx = p_unique.index(a[i][0])
    p_unique_count[idx] += 1
    number = create_number(a[i][0], p_unique_count[idx])
    a[i][3] = number

B = sorted(a, key=itemgetter(2))
for b in B:
    print(b[3])


### FIXED CODE ###

# -*- coding: utf-8 -*-
from operator import itemgetter

N, M = list(map(int, input().split()))
A = [[0] * 4 for i in range(M)]
for i in range(M):
    A[i][0], A[i][1] = list(map(int, input().split()))
    A[i][2] = i

sorted_A = sorted(A, key=itemgetter(1))

P_num = [1]*N
for a in sorted_A:
    y = a[0]
    a[3] = P_num[y-1]
    P_num[y-1] += 1

B = sorted(sorted_A, key=itemgetter(2))
for b in B:
    print("%06d%06d" % (b[0], b[3]))
### BUGGY CODE ###

n = int(input())
s = ["" for _ in range(n)]

for i in range(n):
    s[i] = input()

#print(s)

s_list = [[] for _ in range(n)]
for i in range(n):
    #listに格納
    for j in range(10):
        s_list[i].append(s[i][j])
    #ソートをかける
    s_list[i].sort()

count = 0

#s_listの要素（リスト）について、
#他の要素と同一のものがあるかチェック
for i in range(n):
    for j in range(i+1, n):
        c = (s_list[i] == s_list[j])
        if c == True:
           count += 1
           
print(count)

#重複を削除して要素数カウント


### FIXED CODE ###

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

n = int(input())
s = [input() for _ in range(n)]

dic = {}
for i in range(n):
    tmp = sorted(list(s[i]))
    tmp2 = "".join(tmp)
    if dic.get(tmp2) == None:
        dic[tmp2] = 1
    else:
        dic[tmp2] += 1

#print(dic)
ans = 0
for k, v in dic.items():
    #print(k, v)
    if v >= 2:
        num = (v-1)
        #print("num: ", num)
        #print("num//2*(num+1): ", num//2*(num+1))
        ans += num*(num+1)//2
        #print(ans)

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

s = list(str(input()))

j = len(s)-1
i = 0
ans = 0
while(i < j):
  if s[i] != s[j] :
    ans += 1
  else:
    continue
print(ans)

### FIXED CODE ###

s = list(str(input()))

j = len(s)-1
i = 0
ans = 0
while(i < j):
  if s[i] != s[j] :
    ans += 1
    i += 1
    j -= 1
  else:
    i += 1
    j -= 1
    continue
print(ans)
### BUGGY CODE ###

import queue
h, w = map(int, input().split())
m = []
for i in range(h):
  m.append(input())
#print(h, w)
#print(m)
q = queue.Queue()
a = []
def init():
  global a, q
  q = queue.Queue()
  a = []
  for i in range(h):
    a.append([-1] * w)

def bfs(cx, cy):
  nxs = [1, 0, -1, 0]
  nys = [0, -1, 0, 1]
  for i in range(4):
    nx = cx + nxs[i]
    ny = cy + nys[i]
    if 0 <= nx and nx < w and 0 <= ny and ny < h and m[ny][nx] == '.' and a[ny][nx] == -1:
      a[ny][nx] = a[cy][cx] + 1
      q.put([nx, ny])
  
def check(start_x, start_y, end_x, end_y):
  if m[start_y][start_x] == '#' or m[end_y][end_x] == '#':
    return 0
  if start_x == end_x and start_y == end_y:
    return 0
  
  global a, q
  init()
  q.put([start_x, start_y])
  a[start_y][start_x] = 0
  while not q.empty():
    cx, cy = q.get()
    bfs(cx, cy)
  return a[end_y][end_x]

ans = 0
#for start_y in range(h):
#  for start_x in range(w):
#    for end_y in range(h):
#      for end_x in range(w):
#        ans = max(ans, check(start_x, start_y, end_x, end_y))
for i in range(h * w - 1):
  for j in range(i+1, h * w):
    start_x = i % w
    start_y = i // w
    end_x = j % w
    end_y = j // w
    #print(start_x, start_y, end_x, end_y)
    ans = max(ans, check(start_x, start_y, end_x, end_y))
    
print(ans)

### FIXED CODE ###

import queue
h, w = map(int, input().split())
m = []
for i in range(h):
  m.append(input())
#print(h, w)
#print(m)
q = queue.Queue()
a = []
def init():
  global a
  a = []
  for i in range(h):
    a.append([-1] * w)

def bfs(cx, cy):
  nxs = [1, 0, -1, 0]
  nys = [0, -1, 0, 1]
  for i in range(4):
    nx = cx + nxs[i]
    ny = cy + nys[i]
    if 0 <= nx and nx < w and 0 <= ny and ny < h and m[ny][nx] == '.' and a[ny][nx] == -1:
      a[ny][nx] = a[cy][cx] + 1
      q.put([nx, ny])
  
def check(start_x, start_y):
  if m[start_y][start_x] == '#':
    return 0
  
  global a, q
  init()
  q.put([start_x, start_y])
  a[start_y][start_x] = 0
  end_x = -1
  end_y = -1
  while not q.empty():
    cx, cy = q.get()
    bfs(cx, cy)
    end_x = cx
    end_y = cy
  return a[end_y][end_x]

ans = 0
for i in range(h * w - 1):
    start_x = i % w
    start_y = i // w
    ans = max(ans, check(start_x, start_y))
    
print(ans)
### BUGGY CODE ###

import math
A, B, N = map(int, input().split())
print(max([math.floor(A*x/B) - A*math.floor(x/B) for x in range(N+1)]))

### FIXED CODE ###

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


def f(x):
    return math.floor(A*x/B) - A * math.floor(x/B)


print(f(min(B-1, N)))
### BUGGY CODE ###

N = int(input())
while True:
    judge = 1
    for i in range(2, N):
        if N % i == 0:
            judge *= N % i  #素数だとjudgeが0にならない
            break
        else:
            judge *= N % i  #素数だとjudgeが0にならない
    if judge >= 1:
        print(N)
        exit()
    N += 1

### FIXED CODE ###

import math

def is_prime(n):
    for k in range(2, int(math.sqrt(n)+1)):
        if n % k == 0:
            return False
    return True

N = int(input())
while True:
    if is_prime(N):
        print(N)
        exit()
    N += 1
### BUGGY CODE ###

import sys

INF = float('inf')


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


def LIST():
    return list(map(int, input().split()))


N, K = LIST()
h = LIST()

# DP配列を初期化
dp = [INF] * N

# 初期条件を入力
dp[0] = 0

# テーブルを更新 もらうDP
for i in range(1, N):
    for j in range(1, min(K, i) + 1):
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[N - 1])


### FIXED CODE ###

import sys

INF = float('inf')

input = sys.stdin.readline


def LIST():
    return list(map(int, input().split()))


N, K = LIST()
h = LIST()

# DP配列を初期化
dp = [INF] * N

# 初期条件を入力
dp[0] = 0

# テーブルを更新 もらうDP
for i in range(1, N):
    x = max(0, i - K)
    dp[i] = min([dp_ + abs(h[i] - h_) for dp_, h_ in zip(dp[x:i], h[x:i])])

print(dp[N - 1])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

new_S = S.replace("AC", "12")
# print(new_S)

for i in range(Q):
    left, right = map(int, input().split())
    # print(new_S[left-1:right-1], new_S[left-2:right])
    count_one = new_S[left-1:right-1].count('1')
    count_two = new_S[left-1:right].count('2')
    print(min(count_one, count_two))

### FIXED CODE ###

import collections

N, Q = map(int, input().split())
S = input()

new_S = S.replace("AC", "12")


count_one_list = [0] * len(S)
for i in range(len(S)-1):
    if new_S[i] == '1' and i == 0:
        count_one_list[i+1] += 1
    elif new_S[i] == '1':
        count_one_list[i+1] = count_one_list[i] + 1
    else:
        count_one_list[i+1] = count_one_list[i]
# count_one_list = [new_S[:i].count('1') for i in range(len(S))]
# print(count_one_list)

for i in range(Q):
    left, right = map(int, input().split())
    count_one = count_one_list[right-1] - count_one_list[left-1]
    print(count_one)
### BUGGY CODE ###

n=int(input())
count=0
A=[int(i) for i in input().split()]
if A[0]==0:
  A[0]+=1
  count+=1
elif A[0]<0:
  for i in range(len(A)):
    A[i]*=(-1)
for i in range(1,len(A)):
  if i%2==0:
    while sum(A[:i+1])<=0:
      A[i]+=1
      count+=1
  else:
    while sum(A[:i+1])>=0:
      A[i]-=1
      count+=1
print(count)

### FIXED CODE ###

n=input()
a=[int(i) for i in input().split()]
def chk(a,t):
    ans=0
    x=0
    for i in a:
        x+=i
        if t==True and x<1:
            ans+=1-x
            x=1
        elif t==False and x>-1:
            ans+=x+1
            x=-1
        t=not t
    return ans
print(min(chk(a,True),chk(a,False)))
### BUGGY CODE ###

import math

def wa(a,bl):
    if a==0:
        return 0
    if min(bl)>a:
        return math.factorial(len(bl))*a
    if len(bl)==1:
        return a%bl[0]
    else:
        re=0
        for b in bl:
            re+=wa(a%b,list(set(bl)^set([b])))
        return re%(10**9+7)

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

print(wa(a,bl))


### FIXED CODE ###

from bisect import bisect_right
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __repr__(self):
        return str(self.__x)

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7

def main():
    n,x=MI()
    ss=LI()
    ss.sort()
    dp=[0]*(x+1)
    dp[x]=mint(1)
    for i in range(x,0,-1):
        pre=dp[i]
        if pre==0:continue
        mxj=bisect_right(ss,i)
        for j in range(mxj):
            dp[i%ss[j]]+=pre/mxj

    ev=sum(dp[i]*i for i in range(ss[0]))
    fac=mint(1)
    for i in range(1,n+1):fac*=i
    print(ev*fac)

main()
### BUGGY CODE ###

#http://compro.tsutajiro.com/archive/180220_probability_dp.pdf
n = int(input())
a = list(map(int, input().split( )))
cnt =[0,0,0]
for i in range(n):
    cnt[3-a[i]] += 1
dp = [[[-1 for _ in range(n+2)] for __ in range(n+2)] for ___ in range(n+2)]
"""

for i in range(n,-1,-1):
    for j in range(n,i-1,-1):
        for k in range(n,j-1,-1):
            dp[k][j][i] = (dp[k-1][j+1][i] + 1) * k/n +(dp[k][j-1][i+1] + 1) * i/n +  (dp[k][j][i] + 1) * j/n
こういうインデックスが面倒なことになるから1枚、2枚、3枚でなく1枚以上、2枚以上、3枚以上食べた種類の数で管理する
"""
"""
for i in range(n-1,-1,-1):
    for j in range(n-1,i-1,-1):
        for k in range(n-1,j-1,-1):
            
            ???
            dp[k][j][i] = (dp[k+1][j+1][i] + 1) * k/n +(dp[k+1][j+1][i+1] + 1) * j/n +  (dp[k][j][i] + 1) * i/n
            → dp[k][j][i] = ((dp[k+1][j+1][i] + 1) * k/(n-i) +(dp[k+1][j+1][i+1] + 1) * j/(n-i)) +   n/i
            """


#上の方針だと追えないのでやり直し。
dp[n][n][n] = 0
def solve(x, y, z):
    if dp[x][y][z] != -1:
        return dp[x][y][z]
    else:
        delta = n/(n-z)#3枚以上ある皿以外を引くまで
        dp[x][y][z] = 0
        if x != n:
            dp[x][y][z] += (solve(x+1,y,z) + delta) * (n-x)/(n-z)
        if y != x:
                dp[x][y][z] += (solve(x,y+1,z) + delta) * (x-y)/(n-z)#x+1,y+1ではない
        if z != y:
            dp[x][y][z] += (solve(x,y,z+1) + delta) * (y-z)/(n-z)#x+1,y+1,z+1ではない

        return dp[x][y][z]


print(solve(cnt[1]+cnt[2], cnt[2] ,0))




### FIXED CODE ###

#http://compro.tsutajiro.com/archive/180220_probability_dp.pdf
import sys
n = int(input())
a = list(map(int, sys.stdin.readline().split( )))
cnt =[0,0,0]
for i in range(n):
    cnt[3-a[i]] += 1
dp = [[[0 for _ in range(n+1)] for __ in range(n+1)] for ___ in range(n+1)]

dp[n][n][n] = 0
divT = [1/i for i in range(1,n+1)]

for x in range(n,cnt[1]+cnt[2]-1,-1):## -2だったのを-1に
    for y in range(x,cnt[2]-1,-1):##cnt[2]
        for z in range(y,-1,-1):
            delta = n*divT[n-z-1]#2枚以下を引くまで
            if x != n:
                dp[x][y][z] += (dp[x+1][y][z] + delta) * (n-x)
            if y != x:
                dp[x][y][z] += (dp[x][y+1][z] + delta) * (x-y)#x+1,y+1ではない
            if z != y:
                dp[x][y][z] += (dp[x][y][z+1] + delta)* (y-z)#x+1,y+1,z+1ではない
            dp[x][y][z] *=divT[n-z-1]

print(dp[cnt[1]+cnt[2]][cnt[2]][0])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
M = 10**9 + 7
cnt = 0
for i in range(N):
    cnt += A[i] * sum(A[i+1:])
print(cnt%M)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
M = 10**9 + 7

S = sum(A)
S2 = sum(map(lambda x: x**2, A))
print(((S**2 - S2)// 2)%M)
### BUGGY CODE ###

import math

def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0

    while True:
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)

        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1

    for a in A:
        P.append(a)

    return P

p_list=eratosthenes(10000)

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

q = int(input())
ans = [0]*q
for i in range(q):
    l, r = map(int, input().split())
    tmp = 0
    for j in range (l,r+1,2):
        if j in p_list and (j+1)//2 in p_list: tmp+=1
    ans[i] = tmp

print(*ans, sep='\n')


### FIXED CODE ###

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

q = int(input())

def eratosthenes2(limit):
    is_prime = [1] * (limit + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]==0:
            continue
        for j in range(i * 2, limit + 1, i):
            is_prime[j] = 0
    return is_prime

limit = 10**5

is_prime = eratosthenes2(limit)
prime_list = [i for i in range(limit + 1) if is_prime[i]]

like_2017=[0]*limit

for p in prime_list:
    if is_prime[(p+1)//2]==1:
        like_2017[p] = 1

from itertools import accumulate
B = [0] + like_2017
B = list(accumulate(B))

ans=[0]*q
for i in range(q):
    l, r = map(int, input().split())
    ans[i]=B[r+1]-B[l]

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

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

counter = 1
for i in range(1, N):
    if min(P[:i+1])==P[i]:
        counter += 1
print(counter)

### FIXED CODE ###

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

counter = 1
minimum = P[0]
for i in range(1, N):
    minimum = min(minimum, P[i])
    if minimum==P[i]:
        counter += 1
print(counter)
### BUGGY CODE ###

S=input()
count=0

def search_index(l, x):
    if x in l:
        return l.index(x)
    else:
        return False

while 'BW' in S:
    ind=search_index(S,'BW')
    S=S[:ind]+'WB'+S[ind+2:]
    count=count+1

print(count)

### FIXED CODE ###

S=input()

tmp=[i for i, x in enumerate(S) if x == 'W']
print(sum(tmp)-sum(range(len(tmp))))
### BUGGY CODE ###

import bisect


I = lambda: map(int, input().split())
N = int(input())
A = list(I())
B = list(I())
C = list(I())
A.sort()
B.sort()
C.sort()

summ = 0
for ai in A:
    r = bisect.bisect_right(B, ai)
    for bi in B[r:]:
        rr = bisect.bisect_right(C, bi)
        summ += (N - rr)

print(summ)

### FIXED CODE ###

import bisect


I = lambda: map(int, input().split())
N = int(input())
A = list(I())
B = list(I())
C = list(I())
B.sort()
C.sort()

s = [0] * (N + 1)
for i, bi in enumerate(B):
    s[i + 1] = s[i] + N - bisect.bisect_right(C, bi)

print(sum(s[N] - s[bisect.bisect_right(B, ai)] for ai in A))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a_list = list(map(int, input().split()))
a_set = set(a_list)
count_list = []

if k >= len(a_set):
    print(0)
else:
    for i in a_set:
        count = a_list.count(i)
        count_list.append(count)
    count_list.sort()
    ans = sum(count_list[:len(a_set)-k])
    print(ans)


### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline

n, k = map(int, input().split())
a_tuple = tuple(map(int, input().split()))
count_dict = defaultdict(int)

for i in a_tuple:
    count_dict[i] += 1

n = len(count_dict.keys())

if n <= k:
    print(0)
else:
    ans = sum(tuple(sorted(count_dict.values()))[:n-k])
    print(ans)
### BUGGY CODE ###

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

pairwise = True
setwise = False


seki = 1
for i in range(N):
    seki *= A[i]
tmp = 0

for j in range(N):
    gcd = fractions.gcd(A[j],seki//A[j])
    if gcd != 1:
        pairwise = False
        if tmp == 0:
            tmp = gcd
        else:
            tmp = fractions.gcd(gcd,tmp)

    else:
        setwise = True

if tmp == 1:
    setwise = True

if pairwise:
    print('pairwise coprime')
elif setwise:
    print('setwise coprime')
else:
    print('not coprime')




### FIXED CODE ###

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

pairwise = True
setwise = False

M = 10**6+1

count = [0 for _ in range(M)]

for a in A:
    count[a] += 1

max_count = 0
for j in range(2,M):
    max_count = max(max_count,sum(count[j::j]))

if max_count == N:
    print('not coprime')
elif max_count >= 2:
    print('setwise coprime')
else:
    print('pairwise coprime')
### BUGGY CODE ###

import fractions
gcd = fractions.gcd
ans = 0
k = int(input())
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans += gcd(i,gcd(j,l))
print(ans)


### FIXED CODE ###

import math
gcd = math.gcd
ans = 0
k = int(input())
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans += gcd(i,gcd(j,l))
print(ans)
### BUGGY CODE ###

n = int(input())
a = [input() for i in range(n)]
for i in range(n-1):
    if i==0:
        print(max(a[1:]))
    else:
        max1 = max(a[:i])
        max2 = max(a[i+1:])
        print(max(max1, max2))
print(max(a[:n]))


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
a_sort = sorted(a.copy())
for i in range(n):
    print(a_sort[-2] if a[i] == a_sort[-1] else a_sort[-1])
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split(" ")))
L.sort() #小さい順
counter = 0

for i in range(N):
  for j in range(i+1, N):
    for k in range(j+1, N):
      if L[i] + L[j] <= L[k]:
        break
      else:
        counter += 1
       
print(counter)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split(" ")))
L.sort() #小さい順
counter = 0

for i in range(N-2):
  for j in range(i+1, N-1):
    index = bisect.bisect_left(L, L[i]+L[j], 0, N)
    counter = counter + index - j - 1
       
print(counter)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
a = [0]
for i in range(n-k+1):
    tmp = p[i:i+k]
    if sum(a) < sum(tmp):
        a = tmp
result = 0
for i in a:
    result += (i + 1) / 2
print(result)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
p = [0] * k + p
s = []
a = 0
for i in range(k, n+k):
    a += p[i];
    a -= p[i-k]
    s.append(a)
index = s.index(max(s))
result = 0
for i in p[index+1:index+k+1]:
    result += (i + 1) / 2
print(result)
### BUGGY CODE ###

N = int(input())
C = list(input())
count = 0
for i in range(N):
    if C[N-i-1] == 'R':
        for j in range(N-i-1):
            if C[j] == 'W':
                C[N-i-1] = 'W'
                C[j] = 'R'
                count += 1
                break
print(count)




### FIXED CODE ###

N = int(input())
C = list(input())
count = list()
W = 0
R = 0

for i in C:
    if i == "R":
        R += 1

if R == 0:
    count.append(0)

for i in C:

    if i == "W":
        W += 1
    else:
        R -= 1

    if W <= R:
        count.append(R)
    else:
        count.append(W)

print(min(count))