Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(100000)

n, k = map(int,input().split())
nck = {}

def c(n,k):
    if k == 0 or n==k:
        return 1
    elif k == 1:
        return n  
    elif (n,k) in nck:
        return nck[(n,k)]
    else:
        nck[n,k] = c(n-1,k-1)+c(n-1,k)
        return nck[n,k]

for j in range(1,k+1):
    r = (c(n-k+1,j)*c(k-1,j-1))%(10**9+7)
    print(r)

### FIXED CODE ###



import sys
sys.setrecursionlimit(10000)

n, k = map(int,input().split())
nck = {}

def c(n, r):
    
    if n<r: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

for j in range(1,k+1):
    r = (c(n-k+1,j)*c(k-1,j-1))%(10**9+7)
    print(r)
n=int(input())
g=[[] for i in range(n)]
ro=[0]*n
c=list(map(int,input().split()))
c.sort(reverse=True)
for i in range(n-1):
    a,b=map(int,input().split())
    ro[a-1]+=1
    ro[b-1]+=1
    g[a-1].append(b-1)
    g[b-1].append(a-1)
m=max(ro)
mi=ro.index(m)
q=[mi]
ans=[0]*n
v=[0]*n
v[mi]=1
ans[mi]=c.pop()
while len(q)>0:
    s=q.pop()
    for i in g[s]:
        if v[i]==0:
            v[i]=1
            ans[i]=c.pop()
            q.append(i)
print(sum(ans)-max(ans))
print(*ans)

### FIXED CODE ###

n=int(input())
g=[[] for i in range(n)]
ro=[0]*n
for i in range(n-1):
    a,b=map(int,input().split())
    ro[a-1]+=1
    ro[b-1]+=1
    g[a-1].append(b-1)
    g[b-1].append(a-1)
c=list(map(int,input().split()))
c.sort(reverse=True)
m=max(ro)
mi=ro.index(m)
q=[mi]
ans=[0]*n
v=[0]*n
v[mi]=1
ans[mi]=c.pop(0)
while len(q)>0:
    s=q.pop()
    for i in g[s]:
        if v[i]==0:
            v[i]=1
            ans[i]=c.pop(0)
            q.append(i)
print(sum(ans)-max(ans))
print(*ans)
def solve(string):
    s, k = string.split()
    if len(s) == 1:
        return s
    counter = 0
    for _s in str(s):
        if _s == "1":
            counter += 1
            continue
        break
    return "1" if len(k) < 4 and int(k) < counter else s[counter]


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))


### FIXED CODE ###

def solve(string):
    s, k = string.split()
    if len(s) == 1:
        return s
    counter = 0
    for _s in str(s):
        if _s == "1":
            counter += 1
            continue
        break
    return "1" if len(k) < 4 and int(k) <= counter else s[counter]


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))
N, M = map(int, input().split())

A = [input() for n in range(N)]
B = [input() for m in range(M)]

ans = "Yes"
for a in A:
    for b in B:
        print(a, b)
        if b not in a:
            ans = "No"
print(ans)


### FIXED CODE ###

a, b = map(int, input().split())


if a == b:
    print("Draw")
elif a == 1:
    print("Alice")
elif b == 1:
    print("Bob")
elif a > b:
    print("Alice")
elif a < b:
    print("Bob")
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q):
    now,cnt = q.popleft()
    step = cnt % 3
    vis[now][step] = cnt
    if now == T and step  == 0:  
        print(cnt//3)
        exit()
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            q.append((x,cnt+1))
print(-1)
exit()



### FIXED CODE ###

N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q):
    now,cnt = q.popleft()
    step = cnt % 3
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            vis[x][(step+1)%3] = cnt
            q.append((x,cnt+1))

if vis[T][0] == -1:
    print(-1)
else:
    print(vis[T][0]//3+1)
a,b = map(int, input().split())
ans=′Yay!′
if a>=9 or b>=9:
  ans=′:(′
print(ans)

### FIXED CODE ###

a,b = map(int, input().split())
ans=':('
if a<=8 and b<=8:
  ans = 'Yay!'
print(ans)
s=list(input())



for i in range(len(s)):
    if s[i]=="A" or s[i]=="T" or s[i]=="G" or s[i]=="C":
        s[i]=1
    else:
        s[i]=0
list=[]
for i in range(len(s)):
    for j in range(len(s)-i):
        if s[i+j]==0:
            list.append(j)
            break

print(max(list))


### FIXED CODE ###


s=list(input())



for i in range(len(s)):
    if s[i]=="A" or s[i]=="T" or s[i]=="G" or s[i]=="C":
        s[i]=1
    else:
        s[i]=0
list_s=[]
for i in range(len(s)):
    flag=1
    for j in range(len(s)-i):
        if s[i+j]==0:
            list_s.append(j)
            flag=0
            break
    if flag:
        list_s.append(len(s)-i)

print(max(list_s))
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import deque
import pprint

inf = 10**18
mod = 10**9+7

n = int(input())
a = list(map(int, input().split()))
a.sort()
b = []
pre = a[0]
if a[0] != a[1]:
    b.append(a[0])
    if pre == 1:
        print(1)
        sys.exit()
else:
    if pre == 1:
        print(0)
        sys.exit()

for num in a:
    if pre != num:
        b.append(num)
        pre = num

judge = [False for i in range(10**6+1)]
for num in b:
    judge[num] = True
for i in range(1,int(math.sqrt(10**6+1))):
    if judge[i] == True:
        for j in range(i*2,10**6+1,i):
            judge[j] = False
ans = 0
for i in range(1,10**6+1):
    if judge[i]:
        ans+=1
print(ans)

### FIXED CODE ###

# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import deque
import pprint

inf = 10**18
mod = 10**9+7

n = int(input())
a = list(map(int, input().split()))
a.sort()
if n == 1:
    print(1)
    sys.exit()
if n == 2:
    if a[0] == a[1]:
        print(0)
    elif a[1]%a[0] == 0:
        print(1)
    else:
        print(2)
    sys.exit()

b = []
pre = a[0]
if a[0] != a[1]:
    if pre == 1:
        print(1)
        sys.exit()
else:
    if pre == 1:
        print(0)
        sys.exit()

judge = [False for i in range(10**6+1)]
for num in a:
    judge[num] = True
for i in range(1,(10**6)):
    if judge[i]:
        for j in range(i*2,10**6+1,i):
            judge[j] = False
ans = 0
for i in range(1,10**6+1):
    if judge[i]:
        ans+=1
subans = 0
c = collections.Counter(a)
for k,v in c.items():
    if v > 1 and judge[k]:
        subans+=1
print(ans-subans)
N = int(input())
H = list(map(int, input().split()))
ans = 0
start = 0

while ( start < N ):
    tmp_ans = 0
    for j in range(start, N-1):
        if (H[j] >= H[j+1]):
            tmp_ans += 1
        else:
            start += tmp_ans
            break
            
    ans = max(ans, tmp_ans)
    start += 1
    
print(ans)

### FIXED CODE ###

S = input()
T = input()

ans = 0

for i in range(3):
    if (S[i] == T[i]):
        ans += 1

print(ans)
N,M,X=map(int,input().split())
A=list(map(int,input().split()))
import numpy as np
A=np.Array(A)
print(min(A.np.count_nonzero(A<X),A.np.count_nonzero(A>X)))

### FIXED CODE ###

n,m,x=map(int,input().split())
s=sum(int(i)<x for i in input().split())
print(min(s,m-s))
K = int(input())
S = input()
if len(S) > K:
  s = s[:k] + "..."
  print(S)
else:
  print(S)

### FIXED CODE ###

K = int(input())
S = input()
if len(S) > K:
  S = S[:K] + "..."
  print(S)
else:
  print(S)
n = input()
a = map(int,input().split())
print(max(a)-min(a))

### FIXED CODE ###

n = input()
a = list(map(int,input().split()))
print(max(a)-min(a))
input_line = input()
l = input().split(' ')
l = [int(x) for x in l]

if l[0] < l[1]:
    print(0)
else:
    print(10)


### FIXED CODE ###

input_line = input()
l = input_line.split(' ')
l = [int(x) for x in l]

if l[0] < l[1]:
    print(0)
else:
    print(10)
a = input()
b = a.split()
N = int(b[0])
S = list(b[1])
K = int(b[2])
lit = S[K-1]
for i in range(N):
  if S[i] != lit:
    S[i] = '*'
print(''.join(S))  

### FIXED CODE ###

N = int(input())
S = list(input())
K = int(input())
lit = S[K-1]
for i in range(N):
  if S[i] != lit:
    S[i] = '*'

print(''.join(S))
import sys
N,K = map(int, input().split())
lis = [int(i) for i in input().split()]
if N == 1:
  print(1)
  sys.exit()
ind = lis.index(1)+1
print(ind)
pre = ind-1
pos = l-ind-1
if pre%(K-1)==0:
  a = pre//(K-1)
else:
  a = pre//(K-1)+1
if pos%(K-1)==0:
  b = pos//(K-1)
else:
  b = pos//(K-1)+1
print(1+a+b)

### FIXED CODE ###

import sys
N,K = map(int, input().split())
lis = [int(i) for i in input().split()]
if N == 1:
  print(0)
  sys.exit()
if N<=K:
  print(1)
  sys.exit()
ind = lis.index(1)+1
if (N-1)%(K-1)==0:
  print(int((N-1)/(K-1)))
else:
  print(int((N-1)//(K-1))+1)
from fractions import gcd
n = int(raw_input())
a = []
for i in range(n):
    a.append(int(raw_input()))
result = a[0]
for i in range(1, n):
    result = result * a[i] / gcd(result, a[i])
print result / g

### FIXED CODE ###

from fractions import gcd
n = int(raw_input())
a = []
for i in range(n):
    a.append(int(raw_input()))
result = a[0]
for i in range(1, n):
    result = result * a[i] / gcd(result, a[i])
print result
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

# FFT
# use python3
# a = np.array([a1,a2,a3]), b= np.array([b1,b2,b3])
# c = np.array([a1b1,a1b2+a2b1,a1a3+a2b2+a3b1,a2b3+a3b2,a3b3])
import numpy as np
def Convolution(a,b):
    bit = (len(a)+len(b)-2).bit_length()
    L = 2**bit
    fa,fb = np.fft.rfft(a,L), np.fft.rfft(b,L)
    c = np.rint(np.fft.irfft(fa*fb,L)).astype(np.int64)
    return c[:len(a)+len(b)-1]

N,M = II()
A = III()

print('time test')

h = [0]*(max(A))
for a in A:
    h[a-1] += 1

conv = np.append([0,0],Convolution(h,h))
ans = 0
count = 0
'''
for k in range(2,2*max(A)+1)[::-1]:
    if conv[k]:
        num = min(M-count,conv[k])
        count += num
        ans += k*num
    if count==M:
        break
'''
print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

S,T = map(str, input().split())
print(T+S)
print(["YES","NO"][bool(len(list(multiset(input.split())-multiset([5,5,7]))))])

### FIXED CODE ###

l=input().split();list.sort(l);print(["NO","YES"][l==["5","5","7"]])
a b = input()
print(a*b 2*(a+b))

### FIXED CODE ###

nums = input().split(" ")
a =int( nums[0])
b = int(nums[1])

print(a*b, (a+b)*2)
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    a, b = iim()

    if a > b:
        a, b = b, a
    print(f"{a}"*b)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    a, b = iim()

    if a > b:
        a, b = b, a
    print("{0}".format(a)*b)

if __name__ == "__main__":
    resolve()
A = imput()
a,b = int(A.split' ')
if 0 < a < 11:
   print('b')
else:
   print('b+1000-100a')

### FIXED CODE ###

A = input()
b,c = (A.split(' '))
d = int(b)
e = int(c)
f = e - d * 100 + 1000

if 0 < d < 11:
    print(f)
else:
    print(e)
n, k = map(int, input().split())
A = input().split()

tentosu_f = 0
tentosu_l = 0

for i in range(len(n)):
    for j in range(i+1, len(n)):
        if A[i] > A[j]:
            tentosu_f += 1

for i in range(n):
    for j range(n):
        if A[i] > A[j]:
            tentosu_l += 1
            
ans = ((tentosu_f * k) + ((k* (k-1)) / 2) * tentosu_l) % (10**9 + 7)
print(ans)

### FIXED CODE ###

mod = (10 ** 9) + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))

ten_f = 0
ten_l = 0

for i in range(N):
    for j in range(i + 1, N):
        if A[i] > A[j]:
            ten_f += 1

for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            ten_l += 1

ans = (ten_f * (K)) + ((K * ((K - 1)) // 2) * ten_l)
print(ans % mod)
n=int(input())

X=list(map(int,input()))

print(sum(X)-n)

### FIXED CODE ###

n=int(input())

X=list(map(int,input().split()))

print(sum(X)-n)
n=int(input())
h=[int(x) for x in input().split()]

ans_list=[]

def A(i,n,h,ans_list):
    ans=0
    for j in range(i,n-1):
        if h[j]>=h[j+1]:
            ans+=1
            if j==n-2:
                ans_list.append(ans)
                break
        else:
            ans_list.append(ans)
            A(j+1,n,h,ans_list)
            break
        
A(0,n,h,ans_list)
print(max(ans_list))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
n=int(input())
h=[int(x) for x in input().split()]

ans_list=[]

def A(i,n,h,ans_list):
    ans=0
    for j in range(i,n-1):
        if h[j]>=h[j+1]:
            ans+=1
            if j==n-2:
                ans_list.append(ans)
                break
        else:
            ans_list.append(ans)
            A(j+1,n,h,ans_list)
            break
        
if n==1:
    print(0)
else:
    A(0,n,h,ans_list)
    print(max(ans_list))
N, M = map(int, input().split())

#無向行列
path_matrix = [[False]*N for _ in range(M)]

for _ in range(M):
  line = map(int, input().split())
  paths = [x-1 for x in line]
  path_matrix[paths[0]][paths[1]] = True
  path_matrix[paths[1]][paths[0]] = True
  
visited = [False]*N

def dfs(now, depth):
  if visited[now]:
    return 0
  if depth == N-1:
    return 1
  
  visited[now] = True
  total_paths = 0
  for i in range(N):
    if path_matrix[now][i]:
      total_paths += dfs(i, depth+1)
  
  visited[now] = False
  
  return total_paths
print(dfs(0,0))

### FIXED CODE ###

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

#無向行列
path_matrix = []

#無向行列の初期化
for _ in range(N):
    path_matrix.append([False] * N)

for _ in range(M):
  line = map(int, input().split())
  paths = [x-1 for x in line]
  path_matrix[paths[0]][paths[1]] = True
  path_matrix[paths[1]][paths[0]] = True
  
visited = [False]*N

def dfs(now, depth):
  if visited[now]:
    return 0
  if depth == N-1:
    return 1
  
  visited[now] = True
  total_paths = 0
  for i in range(N):
    if path_matrix[now][i]:
      total_paths += dfs(i, depth+1)
  
  visited[now] = False
  
  return total_paths
print(dfs(0,0))
n = int(input())
al = list(map(int,input().split()))

al.sort()
table = [False]*100001
table2 = [False]*100001

for a in al:
    if table2[a]:
        table[a]=True
    if not table[a]:
        table2[a] = True
        for i in range(a+a,100000,a):
            table[i]=True
    

cnt=0
for a in al:
    if not table[a]:
        cnt+=1
print(cnt)

### FIXED CODE ###

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

al.sort()
table = [False]*1000001
table2 = [False]*1000001

for a in al:
    if table2[a]:
        table[a]=True
    if not table[a]:
        table2[a] = True
        for i in range(a+a,1000001,a):
            table[i]=True
    

cnt=0
for a in al:
    if not table[a]:
        cnt+=1
print(cnt)
a,b=input().split()
a=int(a)
b=int(b[0])*100+int(b[2])*10+int(b[3])
ans=a*b
print(int(ans/100))

### FIXED CODE ###

a,b = map(int,input().split())
print(a*b)
import math
x,y=map(int,input().split())
print(math.ceil(math.log2((y-x)/x))+1)

### FIXED CODE ###

x,y=map(int,input().split())
print(len(bin(y//x))-2)
n, l = int(input())
s = [int(input()) for i in range(n) ]
print(sorted(s))

### FIXED CODE ###

n, l = map(int, input().split())
s = [input() for i in range(n)]
s.sort()
print("".join(s))
n.k=map(int,input().split())
print(n%k)

### FIXED CODE ###

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

if n%k==0:
    print("0")
else:
    print("1")
n,m,l = input().split()

n = int(n)
m = int(m)
l = int(l)

matrix_A = [[0]*m for i in range(n)]
matrix_B = [[0]*n for j in range(l)]
matrix_C = [[0]*l for k in range(n)]
box_a = []
box_b = []
box_c = 0

for a in range(n):
    
    box_a = input().split()
    
    for b in range(m):
        
        matrix_A[a][b] = int(box_a[b])
        
    
for c in range(m):
    
    box_b = input().split()
    
    for d in range(l):
        
        matrix_B[c][d] = int(box_b[d])
        
            
for e in range(n):
    
    for f in range(l):
        
        for g in range(m):
            box_c += matrix_A[e][g] * matrix_B[g][f]
        
        
        matrix_C[e][f] = box_c
        box_c = 0
    
    print(" ".join(map(str,matrix_C[e])))


### FIXED CODE ###

n,m,l = input().split()

n = int(n)
m = int(m)
l = int(l)

matrix_A = [[0]*m for i in range(n)]
matrix_B = [[0]*l for j in range(m)]
matrix_C = [[0]*l for k in range(n)]
box_a = []
box_b = []
box_c = 0

for a in range(n):
    
    box_a = input().split()
    
    for b in range(m):
        
        matrix_A[a][b] = int(box_a[b])
        
    
for c in range(m):
    
    box_b = input().split()
    
    for d in range(l):
        
        matrix_B[c][d] = int(box_b[d])
        
            
for e in range(n):
    
    for f in range(l):
        
        for g in range(m):
            box_c += matrix_A[e][g] * matrix_B[g][f]
        
        
        matrix_C[e][f] = box_c
        box_c = 0
    
    print(" ".join(map(str,matrix_C[e])))
inputs = split(input())
ans = inputs[0] - inputs[1] if inputs[3] % 2 == 0 else inputs[1] - inputs[0]
if ans > 10**18:
  print("Unfair")
else:
  print(ans)

### FIXED CODE ###

inputs = [int(c) for c in input().split()]
ans = inputs[0] - inputs[1] if inputs[3] % 2 == 0 else inputs[1] - inputs[0]
if ans > 10**18:
  print("Unfair")
else:
  print(ans)
from math import ceil()
H, A = map(int,input().split())

print(ceil(H/A))

### FIXED CODE ###

from math import ceil
H, A = map(int,input().split())

print(ceil(H/A))
n=int(input())
lis=list(map(int,input().split()))
count=1
if 0 in lis:
  print(0)
  exit()
for i in lis:
    count *= i
	if count > 10**18:
    	print(-1)
        exit()
print(count)


### FIXED CODE ###

n = int(input())
lis = list(map(int,input().split()))
ans = 1
if 0 in lis:
  print(0)
  exit()
for num in lis:
  ans *= num
  if ans > 10 ** 18:
    print(-1)
    exit()
print(ans)
r = int(input(''))
print (R*R)

### FIXED CODE ###

r = int(input(''))
print (r*r)
import sys
import math
from collections import deque
import heapq
import itertools
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

X = I()

a = [0,1]
for i in range(2,70):
  a.append(i**5)
#print(a)

for i,j in itertools.combinations(a, 2):
  #print(i,j)
  for k in [-1,1]:
    if j - i*k == X:
      print(int(j**0.2), int(i**0.2)*k)
      exit()
print(error)

### FIXED CODE ###

import sys
import math
from collections import deque
import heapq
import itertools
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

X = I()

a = [0,1]
for i in range(2,300):
  a.append(i**5)
#print(a)

for i,j in itertools.combinations(a, 2):
  #print(i,j)
  for k in [-1,1]:
    if j - i*k == X:
      print(int(j**0.2), int(i**0.2)*k)
      exit()
print(error)
w,h,n=map(int,input().split())
record=[]
xmin=[]
xmax=[]
ymin=[]
ymax=[]
for i in range(n):
    x,y,a=list(map(int,input().split()))
    record.append([x,y,a])
for i in range(n):
    if record[i][2] == 1:
        xmin.append(record[i][0])
    elif record[i][2] == 2:
        xmax.append(record[i][0])
    elif record[i][2] == 3:
        ymin.append(record[i][1])
    else:
        ymax.append(record[i][1])
if xmax==[]:
    X=w-max(xmin)
elif ymax==[]:
    X=min(xmax)-0
else:
    X=min(xmax)-max(xmin)

if ymax==[]:
    Y=h-max(ymin)
elif ymin==[]:
    Y=min(ymax)-0
else:
    Y=min(ymax)-max(ymin)
    
print(X*Y) if (X > 0 and Y > 0) else print(0) 


### FIXED CODE ###

w,h,n=map(int,input().split())
record=[]
xmin=[]
xmax=[]
ymin=[]
ymax=[]

for i in range(n):
    x,y,a=list(map(int,input().split()))
    record.append([x,y,a])
    
for i in range(n):
    if record[i][2] == 1:
        xmin.append(record[i][0])
    elif record[i][2] == 2:
        xmax.append(record[i][0])
    elif record[i][2] == 3:
        ymin.append(record[i][1])
    else:
        ymax.append(record[i][1])

if xmax==[] and xmin==[]:
    X=w
elif xmax==[]:
    X=w-max(xmin)
elif xmin==[]:
    X=min(xmax)-0
else:
    X=min(xmax)-max(xmin)

if ymax==[] and ymin==[]:
    Y=h
elif ymax==[]:
    Y=h-max(ymin)
elif ymin==[]:
    Y=min(ymax)-0
else:
    Y=min(ymax)-max(ymin)
    
print(X*Y) if (X > 0 and Y > 0) else print(0)
from itertools import permutations 
inf=10**9
n, m, r1 = map(int, input().split())
r=list(map(int, input().split()))
abc=[list(map(int, input().split())) for _ in range(m)]
d=[[inf]*n for i in range(n)]
for ai, bi, ci in abc:
    d[ai-1][bi-1]=ci
    d[bi-1][ai-1]=ci
for k in range(n):
    for i in range(n-1):
        for j in range(i, n):
            dk=d[i][k]+d[k][j]
            if d[i][j]>dk:
                d[j][i]=dk
                d[i][j]=dk
permutations(r)
ans=inf
p=list(permutations(r))
for pi in p:
    res=0
    for i in range(r1-1):
        res+=d[pi[i]-1][pi[I+1]-1]
    if ans>res:
        ans=res
print(ans)

### FIXED CODE ###

from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
E = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 9
d = [[INF for j in range(N)] for i in range(N)]
for i, j, c in E:
    d[i - 1][j - 1] = c
    d[j - 1][i - 1] = c
for k in range(N):
    for i in range(N - 1):
        for j in range(i, N):
            dk = d[i][k] + d[k][j]
            if d[i][j] > dk:
                d[i][j] = dk
                d[j][i] = dk
ans = 10 ** 9
for ri in permutations(r):
    x = 0
    for i in range(R - 1):
        x += d[ri[i] - 1][ri[i + 1] - 1]
    if ans > x:
        ans = x
print(ans)
from collections import Counter


N = int(input())
S = input()

# 等間隔に並んでいる
count = 0

for start in range(N):
  offset = 1
  while True: 
      middle = start + offset
      end = middle + offset

      if end >= N:
          break

      s = {S[start], S[middle], S[end]}

      if len(s) == 3:
          count += 1

      offset += 1


x, y, z = Counter(S).values()

print(x * y * z - count)


### FIXED CODE ###

from collections import Counter


N = int(input())
S = input()

# 等間隔に並んでいる
count = 0

for start in range(N):
  offset = 1
  while True: 
      middle = start + offset
      end = middle + offset

      if end >= N:
          break

      s = {S[start], S[middle], S[end]}

      if len(s) == 3:
          count += 1

      offset += 1

c = Counter(S)

if len(c) != 3:
  print(0)
else:  
  x, y, z = c.values()
  print(x * y * z - count)