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

import sys
input = sys.stdin.readline
S = []
s = list(input().rstrip())
K = int(input())
for i in range(len(s)):
    for j in range(i+1, i+K+1):
        if s[i:j] not in S:
            S.append(s[i:j])
S.sort()
print("".join(S[K-1]))


### FIXED CODE ###

import sys
input = sys.stdin.readline
S = set()
s = list(input().rstrip())
K = int(input())
for i in range(len(s)):
    for j in range(i+1, i+K+1):
        if "".join(s[i:j]) not in S:
            S.add("".join(s[i:j]))
S = list(S)
S.sort()
print("".join(S[K-1]))
### BUGGY CODE ###

import itertools

n = int(input())
L = list(map(int,input().split()))

ans = 0

for a,b,c in itertools.combinations(L, 3):
  if a<b+c and b<a+c and c<a+b:
    ans += 1
print(ans)

### FIXED CODE ###

import bisect

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

L.sort()

ans = 0

for a in range(N-2):
  for b in range(a+1,N-1):
    c = bisect.bisect_left(L, L[a]+L[b])
    ans += c - (b+1)
print(ans)
### BUGGY CODE ###

import itertools
N = int(input())
L = sorted(list(map(int,input().split())),reverse = True)

ans = 0

for i in range(N-2):
  c = itertools.combinations(L[i+1:],2)
  for j in c:
    if sum(j) > L[i]:
      ans += 1
print(ans)
  
         

### FIXED CODE ###

import bisect
N = int(input())
L = sorted(list(map(int,input().split())))
ans = 0

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

# A - Darker and Darker
import numpy as np

H,W = map(int,input().split())
h,w = np.arange(H,dtype=int),np.arange(W,dtype=int)
B = -1 * np.ones((H,W),dtype=int)

queue = []

for i in h:
    A = input()
    for j in w:
        if A[j]=='#':
            B[i][j] = 0
            queue.append((i,j))

while queue!=[]:
    I,J = queue.pop(0)
    for i,j in [(I-1,J),(I+1,J),(I,J-1),(I,J+1)]:
        if (i in h) and (j in w) and B[i][j]<0:
            B[i][j] = B[I][J]+1
            queue.append((i,j))

print(np.max(B))

### FIXED CODE ###

# A - Darker and Darker
from collections import deque

H,W = map(int,input().split())
B = [[-1] * W for _ in range(H)]

queue = deque([])

for i in range(H):
    A = input()
    for j in range(W):
        if A[j]=='#':
            B[i][j] = 0
            queue.append((i,j))

ans = 0

while queue:
    I,J = queue.popleft()
    for di,dj in ((-1,0),(1,0),(0,-1),(0,1)):
        i,j = I+di,J+dj
        if 0<=i<H and 0<=j<W:
            if B[i][j]<0:
                B[i][j] = B[I][J]+1
                ans = max(ans,B[i][j])
                queue.append((i,j))

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

N,M = map(int,input().split())
xs,ys,zs =[],[],[]
comps = []
for i in range(N):
    x,y,z = map(int,input().split())
    raw = [x+y+z,x+y-z,x-y+z,x-y-z,-x+y+z,-x+y-z,-x-y+z,-x-y-z,]
    comps.append(raw)

dp = [[[0]*8 for _ in range(M+1)] for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        for k in range(8):
            dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-1][k]+comps[i-1][k] )
print(max(dp[N][M]))

### FIXED CODE ###

N,M = map(int,input().split())
comp = [[] for _ in range(8)]
for i in range(N):
    x,y,z = map(int,input().split())
    raw = [x+y+z,x+y-z,x-y+z,x-y-z,-x+y+z,-x+y-z,-x-y+z,-x-y-z]
    for j in range(8):
        comp[j].append(raw[j])
ans = 0
for k in range(8):
    comp[k].sort(reverse=True)
    sum = 0
    for l in range(M):
        sum += comp[k][l]
    ans = max(ans,sum)


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

from collections import deque

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

Q = deque()
f = 0
if Maze[0][0] == '#':
    f += 1
Q.append((0, 0, f))
ans = 0
while Q:
    x, y, f = Q.popleft()
    if x == W - 1 and y == H - 1:
        ans = f
        break
    for d in range(2):
        nx = x + (0, 1)[d]
        ny = y + (1, 0)[d]
        if nx >= W or ny >= H:
            continue
        if Maze[y][x] == '.' and Maze[ny][nx] == '#':
            Q.append((nx, ny, f + 1))
        else:
            Q.appendleft((nx, ny, f))


print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
Maze = [[1 if a == "#" else 0 for a in input()] for _ in range(H)]

DP = [[float('inf')] * W for _ in range(H)]

if Maze[0][0] == 1:
    DP[0][0] = 1
else:
    DP[0][0] = 0

for i in range(H):
    for j in range(W):
        if Maze[i][j] == 1:
            if i + 1 < H:
                DP[i+1][j] = DP[i][j]
            if j + 1 < W:
                DP[i][j+1] = min(DP[i][j+1], DP[i][j])
        if Maze[i][j] == 0:
            if i + 1 < H:
                if Maze[i+1][j] != 1:
                    DP[i + 1][j] = DP[i][j]
                else:
                    DP[i + 1][j] = DP[i][j] + 1
            if j + 1 < W:
                if Maze[i][j + 1] != 1:
                    DP[i][j + 1] = min(DP[i][j + 1], DP[i][j])
                else:
                    DP[i][j + 1] = min(DP[i][j + 1], DP[i][j]+1)

print(DP[H-1][W-1])
### BUGGY CODE ###

import numpy as np
n = int(input())
a = [int(i) for i in input().split()] 
ls = np.array(a)

for ind in range(int(n/2), 0, -1):
    tmp = list(range(2*ind-1, n, ind))
    s = ls[tmp].sum()%2
    if a[ind-1] == s:
        ls[ind-1] = 0
    else:
        ls[ind-1] = 1
        
print(ls.sum())
ans = np.where(ls==1)[0] + 1
print(' '.join(map(str, ans)))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()] 
ls = a

st = int(n/2)
ans =  [i+st+1 for i, n in enumerate(a[st:]) if n ==1] 
for ind in range(st, 0, -1):
    tmp = [ls[i] for i in range(2*ind-1, n, ind)]
    s = sum(tmp)%2
    if a[ind-1] == s:
        ls[ind-1] = 0
    else:
        ls[ind-1] = 1
        ans.append(ind)
        
print(sum(ls))
print(' '.join(map(str, ans)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N = int(input())
uvw = []
for _ in range(N-1):
    uvw.append(tuple(map(int, input().split())))

G=[[0]*(N+1) for _ in range(N+1)]
for el in uvw:
    G[el[0]][el[1]]=el[2]
    G[el[1]][el[0]] = el[2]
#print(G)

H=[[] for _ in range(N+1)]
for el in uvw:
    H[el[0]].append(el[1])
    H[el[1]].append(el[0])
#print(H)

seen=[False]*(N+1)
color=[0]*(N+1)
def dfs(n):
    seen[n]=True
    for nxt in H[n]:
        if seen[nxt] == False:
            if G[n][nxt] % 2 == 0:
                color[nxt]=color[n]
            else:
                color[nxt]=color[n] ^ 1
            dfs(nxt)

dfs(1)
#print(distance)
#print(seen)

for i in range(1,N+1):
    print(color[i])



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N = int(input())
uvw = []
for _ in range(N-1):
    uvw.append(tuple(map(int, input().split())))


H=[[] for _ in range(N+1)]
for el in uvw:
    H[el[0]].append((el[1], el[2]))
    H[el[1]].append((el[0], el[2]))
#print(H)

seen=[False]*(N+1)
color=[0]*(N+1)
def dfs(n):
    seen[n]=True
    for nxt in H[n]:
        if seen[nxt[0]] == False:
            if nxt[1] % 2 == 0:
                color[nxt[0]]=color[n]
            else:
                color[nxt[0]]=color[n] ^ 1
            dfs(nxt[0])

dfs(1)
#print(distance)
#print(seen)

for i in range(1,N+1):
    print(color[i])
### BUGGY CODE ###

# D - Checker

import numpy as np

N, K = map(int, input().split())
g = np.zeros((K,K), np.int64) # PDF解説通り2K*2K範囲でやると市松模様の処理が大変なのでK*Kの範囲で計算

for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    tmp = (x//K + y//K) % 2
    x %= K
    y %= K
    if (tmp == 0 and c == "B") or (tmp == 1 and c == "W"):
        g[x][y] += 1
    else:
        g[x][y] -= 1 # 白希望の点を-1で記録する

np.cumsum(g, axis=0, out=g)
np.cumsum(g, axis=1, out=g)

# [i,j]を黒範囲の左下の点とする。[0,i] * [0,j] の範囲または[i+1,K-1] * [j+1,K-1]の範囲にある黒希望点の個数を足し、白希望の点の個数を引く
# 上記範囲外にある白希望の点の個数を足し、黒希望の点の個数を引く
ans = 0
for i in range(K):
    for j in range(K):
        n_satisfied = g[-1][-1] -2*(g[-1][j] + g[i][-1]) + 4*g[i][j]
        ans = max(ans, (N + n_satisfied)//2, (N - n_satisfied)//2) # ((希望通りの点 + 希望通りでない点) + (希望通りの点 - 希望通りでない点))//2

print(ans)

### FIXED CODE ###

# D - Checker

N, K = map(int, input().split())
g = [[0]*K for _ in range(K)] # PDF解説通り2K*2K範囲でやると市松模様の処理が大変なのでK*Kの範囲で計算

for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    tmp = (x//K + y//K) % 2
    x %= K
    y %= K
    if (tmp == 0 and c == "B") or (tmp == 1 and c == "W"):
        g[x][y] += 1
    else:
        g[x][y] -= 1 # 白希望の点を-1で記録する

for i in range(K):
    for j in range(1,K):
        g[i][j] += g[i][j-1]

for i in range(1,K):
    for j in range(K):
        g[i][j] += g[i-1][j]

# [i,j]を黒範囲の左下の点とする。[0,i] * [0,j] の範囲または[i+1,K-1] * [j+1,K-1]の範囲にある黒希望点の個数を足し、白希望の点の個数を引く
# 上記範囲外にある白希望の点の個数を足し、黒希望の点の個数を引く
ans = 0
for i in range(K):
    for j in range(K):
        n_satisfied = g[-1][-1] -2*(g[-1][j] + g[i][-1]) + 4*g[i][j]
        ans = max(ans, (N + n_satisfied)//2, (N - n_satisfied)//2) # ((希望通りの点 + 希望通りでない点) + (希望通りの点 - 希望通りでない点))//2

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

s = input()
K = int (input())


def sort_here(ll):  # バブルソート
    for m in range(len(ll)):
        for n in range(len(ll)-1-m):
            A, B = compare(ll[n], ll[n+1])
            ll[n] = A
            ll[n + 1] = B
    return ll


def compare_(A, B):
    # このゲームにおける比較
    # 小、大の順で返す
    a = len(A)
    b = len(B)

    if a > b:
        if A[:b] == B:
            return B, A
    elif b > a:
        if B[:a] == A:
            return A, B

    for i in range(len(min(A, B))):
        if A[i] > B[i]:
            return B, A
        elif A[i] < B[i]:
            return A, B

def compare(A, B):
    # このゲームにおける比較
    # 小、大の順で返す
    for i in range(len(min(A, B))):
        if A[i] > B[i]:
            return B, A
        elif A[i] < B[i]:
            return A, B

    if len(A) < len(B):
        return A, B
    elif len(B) < len(A):
        return B, A
    else:
        raise Exception


# まずは長さが5以下で存在しうるsubstringを準備
i_list = []
for i in range(1, K+1):
    # i文字数のsutringをまずは作る
    for j in range(len(s) - i + 1):
        cand = s[j:j+i]
        if cand not in i_list:
            i_list.append(s[j:j+i])

#print(i_list)

# 並び替え
i_list = sort_here(i_list)
#print(i_list)


# 出力
print(i_list[K-1])








### FIXED CODE ###

s = input()
l = len(s)
k = int(input())


def compare(a, b):
    ll = [a, b]
    ll = sorted(ll)
    return ll[0] == a


db = []
for length in range(1, k + 1):
    for start in range(l + 1 - length):
        candidate = s[start:start+length]
        if len(db) >= 5:
            if compare(candidate, db[-1]):
                if candidate not in db:
                    db.append(candidate)
                    db = sorted(db)
                    db = db[:5]
        else:
            if candidate not in db:
                db.append(candidate)
                db = sorted(db)

print(sorted(db)[k-1])
### BUGGY CODE ###

import sys
import math
from collections import deque
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
def I(): 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 LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h,w): return [[i for j in range(w)] for k in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N = I()
S = input()
cnt = 0
l = [S[i] for i in range(N)]
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if l[i]==l[j] or l[j]==l[k] or l[k]==l[i] or j-i==k-j:
                continue
            cnt += 1

print(cnt)


### FIXED CODE ###

import sys
import math
from collections import deque
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
def I(): 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 LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h,w): return [[i for j in range(w)] for k in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

input = sys.stdin.readline


N = I()
S = input().rstrip()
R = S.count('R')
G = S.count('G')
B = N-R-G

ans = R*G*B
for i in range(N):
    for j in range(i+1,N):
        if 2*j-i < N and S[i]!=S[j] and S[j]!=S[2*j-i] and S[2*j-i]!=S[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

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

S_deque = list(input())
S_deque = deque(S_deque[:-1])
Q = int(input())

for _ in range(Q):
  item = list(input().split())
  if item[0] == '1':
    S_deque = deque(reversed(S_deque))

  else:
    if item[1] == '1':
      S_deque.appendleft(item[2])

    else:
      S_deque.append(item[2])

S = list(S_deque)
print(''.join(S))

### FIXED CODE ###

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

S_deque = list(input())
S_deque = deque(S_deque[:-1])
Q = int(input())

top_flag = 1 # 0なら末尾、1なら最初

for _ in range(Q):
  item = list(input().split())
  if item[0] == '1':
    if top_flag == 0:
      top_flag = 1
    else:
      top_flag = 0

  else:
    in_flag = top_flag + int(item[1])
    if in_flag % 2 == 0:
      S_deque.appendleft(item[2])
    else:
      S_deque.append(item[2])

if top_flag == 0:
  S_deque.reverse()
else:
  pass

print(''.join(S_deque))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
ans = 1
flg = True
for i in range(N):
    ans *= A[i]
    if A[-1] != 0:
        if ans > 10**18:
            flg = False
            break
if flg == False:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
ans = 1
flg = True
for i in range(N):
    ans *= A[i]
    if A[-1] != 0:
        if ans > 10**18:
            flg = False
            break
    if A[-1] == 0:
        ans = 0
        break
if flg == False:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
from bisect import bisect_left

n = int(readline())
a = list(map(int,readline().split()))
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
que = deque()
L = [a[0]]
que.append((0,1,L))
chk = [False]*n
chk[0] = True
cnt = 1
ans = [1]*n
while que:
  now,m,L = que.popleft()
  if cnt == n:
    break
  for i in g[now]:
    if not chk[i]:
      newL = L.copy()
      ind = bisect_left(L,a[i])
      if m == ind:
        newm = m+1
        newL.append(a[i])
      else:
        newm = m
        newL[ind] = a[i]
      ans[i] = newm
      chk[i] = True
      cnt += 1
      que.append((i,newm,newL))

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

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
from bisect import bisect_left

n = int(readline())
A = list(map(int,readline().split()))
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
que = deque()
inf = 10**9+1
dp = [inf]*n
que.append((0,-1))
chk = [False]*n
chk[0] = True
cnt = 0
ans = [1]*n

while que:
  now,d = que.pop()
  if d != -1:
    dp[now] = d
  else:
    ind = bisect_left(dp,A[now])
    que.append((ind,dp[ind]))
    dp[ind] = A[now]
    ans[now] = bisect_left(dp,inf)
    cnt += 1
    for i in g[now]:
      if not chk[i]:
        chk[i] = True
        que.append((i,-1))
  if cnt == n:
    break
        
print(*ans,sep='\n')
### BUGGY CODE ###

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

cntli = []
for i in range(q):
    si = s[lr[i][0]-1:lr[i][1]]
    si2 = [n for n in si if n in ("A","C")]
    cnt = 0
    for j in range(len(si2)-1):
        if si2[j] == "A":
            if si2[j+1] == "C":
                cnt += 1
    else:
        cntli.append(cnt)

for p in cntli:
    print(p)

### FIXED CODE ###

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

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

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N - 1 + M)]

G = [set() for _ in range(N + 1)]
P_cand = [set() for _ in range(N + 1)]
for a, b in AB:
    G[a].add(b)
    P_cand[b].add(a)
for p in range(1, N):
    if len(P_cand[p]) == 0:
        break
D = [-1] * (N + 1)
P = [-1] * (N + 1)


def bfs(p):
    H = [[p, 0, 0]]
    while H:
        c, p, d = heapq.heappop(H)
        if D[c] < d:
            D[c] = d
            P[c] = p
            for c2 in G[c]:
                heapq.heappush(H, [c2, c, d + 1])


bfs(p)
[print(_) for _ in P[1:]]


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N - 1 + M)]

G = [set() for _ in range(N + 1)]
count = [0] * (N + 1)
ans = [0] * (N + 1)
for a, b in AB:
    G[a].add(b)
    count[b] += 1
for i in range(1, N):
    if count[i] == 0:
        root = collections.deque([i])
        break
while root:
    p = root.popleft()
    for c in G[p]:
        count[c] -= 1
        if count[c] == 0:
            ans[c] = p
            root.append(c)
print(*ans[1:], sep='\n')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
string = input()
n = len(string)

# 文字列を反転する
string = string[::-1]

# 2019と10は互いに素
# 累積和に対してmod 2019をとったものの配列
S = [0]
for i in range(n):
    t = int(string[i])*(10**i)+S[i]
    t = t % 2019
    S.append(t)

# Sの中で要素が一致する時の組み合わせの数を数える
count = 0
d = defaultdict(int)
for key in S:
    d[key] += 1

# print(S, d.values())

for j in d.values():
    if j >=2:
        count += j*(j-1)//2

# 愚直に探すと時間が足りない
# n=int(s)//2019
# for i in range(6, n+1):
#     count += s.count(str(2019 * i))
#     print(str(2019 * i))
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
string = input()
n = len(string)

# 文字列を反転する
string = string[::-1]

# 2019と10は互いに素
# 累積和に対してmod 2019をとったものの配列
S = [0]
d = 10
for i in range(n):
    t = int(string[i])*d+S[i]
    t = t % 2019
    S.append(t)
    d = (d * 10) % 2019

# Sの中で要素が一致する時の組み合わせの数を数える
count = 0
d = defaultdict(int)
for key in S:
    d[key] += 1

# print(S, d.values())

for j in d.values():
    if j >=2:
        count += j*(j-1)//2

# 愚直に探すと時間が足りない
# n=int(s)//2019
# for i in range(6, n+1):
#     count += s.count(str(2019 * i))
#     print(str(2019 * i))
print(count)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = []
for a in A:
    for b in B:
        AB.append(a + b)
AB = sorted(AB, reverse=True)[:k]

ABC = []
for c in C:
    for ab in AB:
        ABC.append(ab + c)
ABC = sorted(ABC, reverse=True)[:k]

for abc in ABC:
    print(abc)

### FIXED CODE ###

import heapq

x, y, z, k = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

# A+B+Cが大きい順になるようにリストに入れていく
ABC = []

# heapqに任意の値が入っているか確認する
from collections import defaultdict
d = defaultdict(int)

que = []

def HeapPush(a, b, c):
    if d[(a, b, c)] == 0:
        heapq.heappush(que, ((A[a] + B[b] + C[c])*-1, a, b, c))  # -1を掛ける
        d[(a, b, c)] += 1


HeapPush(0, 0, 0)

while len(ABC) < k:
    
    abc, a, b, c = heapq.heappop(que)
    ABC.append(abc*-1)  # -1を掛け直す
    
    if a + 1 < x:
        HeapPush(a+1, b, c)
    if b + 1 < y:
        HeapPush(a, b+1, c)
    if c + 1 < z:
        HeapPush(a, b, c+1)
   

for abc in ABC:
    print(abc)
### BUGGY CODE ###

n = int(input())
s = input()

ans = 10 ** 6
for i in range(1, n+1):
    ans = min(ans, s[:i-1].count("W") + s[i:].count("E"))

print(ans)

### FIXED CODE ###

n = int(input())
s = input()

l = [0]
r = [0]

for i in s:
    if i == "W":
        l.append(l[-1] + 1)
    else:
        l.append(l[-1])

for i in s[::-1]:
    if i == "E":
        r.append(r[-1] + 1)
    else:
        r.append(r[-1])

l = l[1:]
r = r[1:][::-1]

ans = 10 ** 9

for i in zip(l, r):
    ans = min(sum(i), ans)

print(ans-1)
### BUGGY CODE ###

N,V = map(int,input().split())
cnt = 0

a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
d = list(map(int,input().split()))

for alist in a:
    for blist in b:
        for clist in c:
            for dlist in d:
                if alist + blist + clist + dlist == V:
                    cnt += 1

print(cnt)

### FIXED CODE ###

from collections import Counter

N,V = map(int,input().split())
cnt = 0

a = tuple(map(int,input().split()))
b = tuple(map(int,input().split()))
c = tuple(map(int,input().split()))
d = tuple(map(int,input().split()))

ab = Counter(ai+bi for ai in a for bi in b)
cd = Counter(ci+di for ci in c for di in d)

cnt = sum(ab[V-i]*t for i,t in cd.items() if V-i in ab)

print(cnt)
### BUGGY CODE ###

n = int(input())
plist = list(map(int,input().split()))


counter = 0

for i in range(len(plist)):
    islow = True
    for j in range(plist.index(plist[i])):
        if plist[i] <= plist[j]:
            continue
        else:
            islow = False
    if islow:
        counter += 1

print(counter)

### FIXED CODE ###

n = int(input())
plist = list(map(int,input().split()))

islow = True
counter = 0
min = 0

for i in range(len(plist)):
    islow = True
    if i == 0:
        counter += 1
        min = plist[i]
        current_min = i
    elif min > plist[i]:
        counter += 1
        min = plist[i]
        current_min = i
        
print(counter)
### BUGGY CODE ###

n, m = map(int, input().split())
v = [[] for i in range(n+1)]
path = [0 for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    v[b].append(a)
for i in range(n+1):
    if v[i] == []:
        continue
    m = max(v[i])
    found = 0
    for e in path[m:i]:
        if e == 1:
            found = 1
            break
    if found == 0:
        path[i - 1] = 1
s = 0
for p in path:
    s += p
print(s)

### FIXED CODE ###

n, m = map(int, input().split())
v = [0 for i in range(n+1)]
path = [0 for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    if v[b] < a:
        v[b] = a

last = 0

for i in range(n+1):
    if v[i] == 0:
        continue
    m = v[i]

    if last < m:
        path[i - 1] = 1
        last = i - 1


s = 0
for p in path:
    s += p
print(s)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
cnt = 0

for i in range(n + 1):
    for j in range(n + 1):
        tmp = n - i * r  - j * g
        if 0 <= tmp and tmp % b == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

r, g, b, n = map(int, input().split())
cnt = 0

for i in range(n + 1):
    for j in range(n + 1):
        tmp = n - i * r  - j * g
        if 0 <= tmp and tmp % b == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

def gcd(a,b):
	if a==0:
		return(b)
	return(gcd(b%a,a))
a,b=map(int,input().split())
g=gcd(a,b)
divide=2

ans=1
while(g!=1):
	if g%divide==0:
		ans+=1
		while(g%divide==0):
			g//=divide
	else:
		divide+=1
print(ans)

### FIXED CODE ###

from math import sqrt
def gcd(a,b):
	if a==0:
		return(b)
	return(gcd(b%a,a))
a,b=map(int,input().split())
g=gcd(a,b)
ans=1
if g%2==0:
	ans+=1
	while(g%2==0):
		g//=2
for divide in range(3,int(sqrt(g))+1,2):
	if g%divide==0:
		ans+=1
		while(g%divide==0):
			g//=divide
if g>2:
	ans+=1
print(ans)