Harryxun/stf_run huggingface dataset:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*n
    self.rank = [0]*n
    
  def find_root(self, e):
    if self.root[e] < 0:
      return e
    else:
      r = self.find_root(self.root[e])
      self.root[e] = r
      return r
    
  def combine(self, e1, e2):
    root1 = self.find_root(e1)
    root2 = self.find_root(e2)
    if root1 == root2:
      pass
    elif self.rank[root1] < self.rank[root2]:
      self.root[root1] += self.root[root2]
      self.root[root2] = root1
      self.rank[root1] = self.rank[root2] + 1
    elif self.rank[root2] < self.rank[root1]:
      self.root[root2] += self.root[root1]
      self.root[root1] = root2
      self.rank[root2] = self.rank[root1] + 1
    else:
      self.root[root2] += self.root[root1]
      self.root[root1] = root2
      self.rank[root2] += 1
      
  def in_the_same_group(self, e1, e2):
      r1 = self.find_root(e1)
      r2 = self.find_root(e2)
      if r1 == r2:
        return True
      return False
  

NMK = input().split()
N = int(NMK[0])
M = int(NMK[1])
K = int(NMK[2])
uf = UnionFind(N)
from collections import defaultdict

friend_list = defaultdict(int)
for _ in range(M):
  AB = input().split()
  A = int(AB[0])-1
  B = int(AB[1])-1
  uf.combine(A,B)
  friend_list[A] += 1
  friend_list[B] += 1

block_list = defaultdict(int)
for _ in range(K):
  CD = input().split()
  C = int(CD[0])-1
  D = int(CD[1])-1
  if uf.in_the_same_group(C, D):
    block_list[C] += 1
    block_list[D] += 1

cnt = defaultdict(int)
ans = []
for i in range(N):
  cnt[i] = -uf.root[uf.find_root(i)] - 1 - friend_list[i] - block_list[i]
  ans.append(str(cnt[i]))

print(" ".join(ans))

### FIXED CODE ###

class UnionFind():
 def __init__(self,n):
   self.n=n
   self.root=[-1]*(n+1)
   self.rank=[0]*(n+1)
 def FindRoot(self,x):
   if self.root[x]<0:
     return x
   else:
     self.root[x]=self.FindRoot(self.root[x])
     return self.root[x]
 def Unite(self,x,y):
   x=self.FindRoot(x)
   y=self.FindRoot(y)
   if x==y:
     return
   else:
     if self.rank[x]>self.rank[y]:
       self.root[x]+=self.root[y]
       self.root[y]=x
     elif self.rank[x]<=self.rank[y]:
       self.root[y]+=self.root[x]
       self.root[x]=y
       if self.rank[x]==self.rank[y]:
         self.rank[y]+=1
 def isSameGroup(self,x,y):
   return self.FindRoot(x)==self.FindRoot(y)
 def Count(self,x):
   return -self.root[self.FindRoot(x)]
 
n,m,k=map(int,input().split())
t=UnionFind(n+1)
cnt=[0]*(n+1) #各iについて、iと同一の連結成分に属する友達関係の人、ブロック関係の人の数を数える
for _ in range(m):
 a,b=map(int,input().split())
 cnt[a]+=1 #各iについて、iと同一の連結成分に属する友達関係の人の数を数える
 cnt[b]+=1
 t.Unite(a,b)
for _ in range(k):
 a,b=map(int,input().split())
 if t.isSameGroup(a,b)==True:
   cnt[a]+=1 #各iについて、iと同一の連結成分に属するブロック関係の人の数を数える
   cnt[b]+=1
ans=[0]*(n+1)
for i in range(1,n+1):
 ans[i]=(t.Count(i)-1)-cnt[i] #答えは(各iが属する連結成分のサイズ)-1-((iと同一の連結成分に含まれているiと友達関係にある人の数)+(iと同一の連結成分に含まれているiとブロック関係にある人の数)となる
print(*ans[1:])
n,q = map(int, input().split())
s=input()

for i in range(n):
    l,r=map(int, input().split())
    print(s[l-1:r].count('AC'))




### FIXED CODE ###

n,q = map(int, input().split())
s=input()
a=[0]*n
for i in range(1,n):
    a[i]+=a[i-1]
    if s[i-1]=='A' and s[i]=='C':
        a[i]+=1
for i in range(q):
    l,r=map(int, input().split())
    print(a[r-1]-a[l-1])
s1, s2, s3 = map(int, input().split())

a = 0

if s1 =1 or s2 =1 or s3 = 1:
  a += 1
else:
  a += 0

print(a)

### FIXED CODE ###

n = input()

def digitSum(n):
    s = str(n)
    array = list(map(int, list(s)))
    return array

b = digitSum(n)
a = 0
c = len(b)
for i in range(c):
    if b[i] == 1:
        a+=1
    else:
        a+=0

print(a)
n, q = map(int, input().split())
s = input()
data = []
for i in range(q):data.append(list(map(int, input().split())))
for i in data:print(len(s[i[0]-1:i[1]].split('AC'))-1)

### FIXED CODE ###

s = input()
if s=='A':print('T')
elif s=='T':print('A')
elif s=='C':print('G')
elif s=='G':print('C')
import collections
import heapq
n=int(input())
a=[-int(item) for item in input().split()]
c = [item for item in list(collections.Counter(a).items()) if item[1]>1]
#print(c)
x=heapq.heappop(c)[0]
y=heapq.heappop(c)[0]
print(x*y)

### FIXED CODE ###

import collections
import heapq
n=int(input())
a=[-int(item) for item in input().split()]
c = [item for item in list(collections.Counter(a).items()) if item[1]>1]
heapq.heapify(c)
#print(c)

if len(c)==0:
  print(0)
  exit()
if sum([item[1] for item in c])<4:
  print(0)
  exit()

x=heapq.heappop(c)
if c!=[]:
  y=heapq.heappop(c)
else:
  y=(0,0)
if x[1]>=4:
  print(x[0]*x[0])
else:
  print(x[0]*y[0])
def resolve():
    H,W = map(int,input().split())
    if H = 1 or W = 1:
        print(1)
    else:
        ans = (H * W + 1) // 2
        print(ans)
resolve()

### FIXED CODE ###

def resolve():
    H,W = map(int,input().split())
    if H == 1 or W == 1:
        print(1)
    else:
        ans = (H * W + 1) // 2
        print(ans)
resolve()
X=input()
if (X>40||X<-40):
  return 0

if(X=>30&&X=<40):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

x=input()
X=int(x)
if(X>=30 and X<=40):
  print('Yes')
elif(X>=-40 and X<30):
  print('No')
a=input()
b=input()
c=a+b

if c>=10:
  print('error')
  
  else:
    print('c')


### FIXED CODE ###

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

if a+b<10:
  print(a+b)
else:
  print("error")
K = int(input())
S = input()

if len(S) > K:
    S = s[:k] + "..."

print(s)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    k = int(input())
    s = input().rstrip()

    if len(s) <= k:
        print(s)
    else:
        print(s[:k] + '...')

if __name__ == '__main__':
    main()
import numpy as np
N,M=map(int, input().split())
tabelist = np.zeros(N)
for i in range(N):
  c=list(map(int, input().split()))
  for k in range(1,c[0]):
    tabelist[k-1] = tabelist[k-1] + 1
print(len([1 for x in tabelist if x==N]))

### FIXED CODE ###

import numpy as np
N,M=map(int, input().split())
tabelist = np.zeros(M)
for i in range(N):
  c=list(map(int, input().split()))
  for k in range(1,c[0]+1):
    tabelist[c[k]-1] = tabelist[c[k]-1] + 1
#    print(i,k,tabelist)
print(len([1 for x in tabelist if x==N]))
n = int(input())
T,A = map(int,input().split())
H = list(map(int,input().split()))
TH = []
for i in n:
  TH.append(abs(T-int(T-0.006*H[i])))
print(TH.index(min(TH))+1)

### FIXED CODE ###

n = int(input())
T,A = map(int,input().split())
H = list(map(int,input().split()))
TH = []
for i in range(n):
  TH.append(abs(A-T+0.006*H[i]))
print(TH.index(min(TH))+1)
import itertools
import math
import sympy
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from scipy.sparse.csgraph import floyd_warshall as wf
from collections import Counter
inf = 10**10

N = int(input())
if N == 1:
    print(1)
    exit()
d = {}
for i in range(2,N+1):
    a = sympy.factorint(i)
    for k,v in a.items():
        if k not in d:
            d[k] = 2
        else:
            d[k] +=v
ans = 1
for v in d.values():
    ans = (ans * v)%(10**9+7)
print(ans)

### FIXED CODE ###

N = int(input())
prime = [0]*(N+1)
ans = 1
for i in range(2,N+1):
    d = 1
    while i > 1:
        d+=1
        while i % d == 0:
            i = i//d
            prime[d]+= 1
for j in range(N+1):
    ans = ans *(prime[j]+1)%(10**9+7)
print(ans)
inputa = list(map(int(), input()))
if inputa[0] < inputa[1]:
  print("0")
else:
  print("10")

### FIXED CODE ###

inputa = list(map(int, input().split()))
if inputa[0] < inputa[1]:
  print("0")
else:
  print("10")
def main():
  n, m = map(int, input().split())
  s = input()
  left = right = 0
  mem = set()
  for _ in range(m):
    com = input()
    if com == "L++":
      left += 1
    elif com == "L--":
      left -= 1
    elif com == "R++":
      right += 1
    elif com == "R--":
      right -= 1
    mem.add(s[left:right + 1])
  print(len(mem))

main()


### FIXED CODE ###

def main():
  n, m = map(int, input().split())
  s = input()
  mem = set()
  base = ord("a") - 1
  mod1 = 1000000007
  mod2 = 2147483647
  h1 = [0]
  h2 = [0]
  for c in s:
    h1.append((h1[-1] * 27 + ord(c) - base) % mod1)
    h2.append((h2[-1] * 27 + ord(c) - base) % mod2)
  pow_mem1 = {0:1}
  pow_mem2 = {0:1}
  def my_pow1(x):
    if x in pow_mem1:return pow_mem1[x]
    pow_mem1[x] = my_pow1(x - 1) * 27 % mod1
    return pow_mem1[x]

  def my_pow2(x):
    if x in pow_mem2:return pow_mem2[x]
    pow_mem2[x] = my_pow2(x - 1) * 27 % mod2
    return pow_mem2[x]
  
  left = right = 1
  for _ in range(m):
    com = input()
    if com == "L++":
      left += 1
    if com == "L--":
      left -= 1
    if com == "R++":
      right += 1
    if com == "R--":
      right -= 1
    x = (h1[right] - h1[left - 1] * my_pow1(right - left + 1)) % mod1
    y = (h2[right] - h2[left - 1] * my_pow2(right - left + 1)) % mod2
    mem.add((x, y))

  print(len(mem))

main()
S = input()
S_o = S[::2]
S_e = S[1::2]
if 'L' in S_o or 'R' in _e:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

S = input()
S_o = S[::2]
S_e = S[1::2]
if 'L' in S_o or 'R' in S_e:
    print('No')
else:
    print('Yes')
n = input()
print(n//3)

### FIXED CODE ###

n = int(input())
print(n // 3)
import sys
input = sys.stdin.readline

n, t = map(int, input().split())
dish = [tuple(map(int, input().split())) for _ in range(n)]

dp = [[0] * (t + 1) for _ in range(n + 1)]
for i in range(n):
    for t0 in range(dish[i][0]):
        dp[i + 1][t0] = dp[i][t0]
    for t0 in range(t):
        t1 = min(t0 + dish[i][0], t)
        dp[i + 1][t1] = max(dp[i + 1][t1], dp[i][t1], dp[i][t0] + dish[i][1])

ans = max(dp[n])
# print(*dp, sep='\n')
# print([dp[i][-1] for i in range(n + 1)])
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, t = map(int, input().split())
dish = [tuple(map(int, input().split())) for _ in range(n)]
dish.sort()
# print(*dish, sep='\n')

dp = [[0] * (t + 1) for _ in range(n + 1)]
for i in range(n):
    for t0 in range(t):
        dp[i + 1][t0] = dp[i][t0]
    for t0 in range(t):
        t1 = min(t0 + dish[i][0], t)
        dp[i + 1][t1] = max(dp[i + 1][t1], dp[i][t1], dp[i][t0] + dish[i][1])

ans = max(dp[n])
# print(*dp, sep='\n')
# print([dp[i][-1] for i in range(n + 1)])
print(ans)
a = input()
S = list(a)
S_low = list(a.lower())

count = 0
if S[0] == "A":
    count += 1

vaa = 0
for j in range(2, len(S)-1):
    # print(j)
    if S[j] == "C":
        vaa += 1
        num = j
        # print(j)
if vaa == 1:
    count += 1

val = 0
for i in range(len(S)):
    for j in range(len(S)):
        if j == 0 or j == num:
            continue
        else:
            if S[i] == S[j]:
                val += 1
            else:
                continue
if val == len(S)-2:
    count +=1

if count == 3:
    print("AC")
else:
    print("WA")

### FIXED CODE ###

a = input()
S = list(a)

count = 0
if S[0] == "A":
    count += 1
    # print("OK")

vaa = 0
num=[0]
for j in range(2, len(S)-1):
    # print(j)
    if S[j] == "C":
        vaa += 1
        num.append(j)

if vaa == 1:
    count += 1
    # print("OK")

# val = 0
# for i in range(len(S)):
#     for j in range(len(S)):
#         if j == 0 or j == num:
#             print(j)
#             continue
#         else:
#             if S[i] == S_low[j]:
#                 print(S[i])
#                 print(S[j])
#                 val += 1
#             else:
#                 continue
# print("val", val)
# if val == len(S)-2:
#     count +=1
# print(num)
num = reversed(num)
S_pop = [S.pop(i) for i in num]
S_low = [i.lower() for i in S]

# print("S", S)
# print("S_low", S_low)

if S == S_low:
    count += 1

if count == 3:
    print("AC")
else:
    print("WA")
a,b,c = input().strip().split()

if a==b:
  if b==c:
    print("No")
  else:
    printf("Yes")
    
else:
  if a==c or b==c:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

a,b,c = input().strip().split()

if a==b:
  if b==c:
    print("No")
  else:
    print("Yes")
    
else:
  if a==c or b==c:
    print("Yes")
  else:
    print("No")
N = int(input())
H = list(map(int, input().split()))
for i in range(N):
    if i < N - 2:
        elif H[i] > H[i + 1] > H[i + 2]:
            print("No")
            exit()
    elif i < N - 1:
        if H[i] > H[i + 1] + 1:
            print("No")
            exit()
print("Yes")


### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
M = 0
for i in range(1, N):
    M = max(M, H[i - 1])
    if H[i] < M - 1:
        print("No")
        exit()
print("Yes")
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input().rstrip()
# if (i)th == (i-K)th: point=0
for i in range(K+K,N):
  if T[i] == T[i-K]:
    T[i] = 'o'

point = 0
for t in T:
  if t == 'r':
    point += P
  elif t == 's':
  	point += R
  elif p == 'p':
    point += S

print(point)

### FIXED CODE ###

import sys
input = sys.stdin.readline
X = int(input())

max_n = 100003
primes = [True] * (max_n+1)

for i in range(2,max_n+1):
  if primes[i] == True:
    if i >= X:
      print(i)
      break
    for j in range(i+i, max_n+1, i):
      primes[j] = False
def d(n):
  while n%2 == 0:
    n /= 2
    ans += 1
  return ans

n = int(input())
a = map(int,input().split())
ans = min(list(map(d,a)))

print(ans)
    


### FIXED CODE ###

n = input()
result = sum(list(map(int,str(n))))
print(result)
def main():
  sFlag=False
  X= int(input())
  X_table=prime_decomposition(X)
  X_table.append(1)
  for i in range(-1000,1000):
    A=i
    for j in range(-1000,1000):
      X_n=i**5-j**5
      if(X_n==X):
        print(A,B)
        sFlag=True
        break
    if(sFlag==True):
      break

if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  sFlag=False
  X= int(input())
  for i in range(-1000,1000):
    for j in range(-1000,1000):
      X_n=i**5-j**5
      if(X_n==X):
        print(i,j)
        sFlag=True
        break
    if(sFlag==True):
      break
 
if __name__=='__main__':
  main()
import math
from string import ascii_lowercase

a = int(input())
b = int(input())
c = int(input())

d = set((a, b, c))
print(len(d))


### FIXED CODE ###

import math
from string import ascii_lowercase
 
line = input()
a, b, c = [int(x) for x in line.split()]
 
d = set((a, b, c))
print(len(d))
print(a*b 2(a+b))


### FIXED CODE ###

a,b=map(int,input().split())
print(a*b,2*(a+b))
N = int(input())
A = [int(input) for _ in range(N)]
B = sorted(A, reverse=True)

for i in range(N):
    if A[i] <= B[0]:
        print(B[0])
    else:
        print(B[1])

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A, reverse=True)

for i in range(N):
    if A[i] < B[0]:
        print(B[0])
    else:
        print(B[1])
n = int(input())
x = input()

outf = {}
res = []

dec_d = {}
def get_dec(bin):
  if bin in dec_d.items():
    return dec_d[bin]
  s = 0
  seed = 2 ** (len(bin)-1)
  for el in bin:
    if el == '1':
      s += seed
    seed = seed // 2
  dec_d[bin] = s
  return s

bin_d = {}
def get_bin(dec):
  if dec in bin_d.items():
    return bin_d[dec]
  s = ''
  while dec > 0:
    if dec % 2 == 1:
      s = s + '1'
    else:
      s = s + '0'
    dec = dec // 2
  bin_d[dec] = s
  return s

pop_d = {}
def popcount(n):
  if n in pop_d.items():
    return pop_d[n]
  out = 0
  while n > 0:
    if n % 2 == 1:
      out += 1
    n = n // 2
  pop_d[n] = out
  return out

init_pop_cnt = popcount(get_dec(x))

for i in range(n):
  if x[i] == '0':
    lx = x[:i] + '1' + x[i+1:]
    ip = init_pop_cnt + 1
  else:
    lx = x[:i] + '0' + x[i+1:]
    ip = init_pop_cnt - 1
  x_dec = get_dec(lx)
  res.append(x_dec)

  kp = []
  f = 0

  # calc first op
  kp.append(x_dec)
  f += 1
  x_dec = x_dec % ip

  # calc f
  while x_dec > 0:
    st = get_bin(x_dec)
    if st in outf.items():
      f += outf[st]
      break
    kp.append(x_dec)
    f += 1
    pc = popcount(x_dec)
    x_dec = x_dec % pc

  # keep
  lf = f
  for k in kp:
    st = get_bin(k)
    outf[st] = lf
    lf -= 1


for i in res:
  st = get_bin(i)
  print(outf[st])


### FIXED CODE ###

n = int(input())
x = input()

init_pop_cnt = x.count('1')
init_pop_cnt_less = init_pop_cnt - 1
init_pop_cnt_more = init_pop_cnt + 1

valid_l = init_pop_cnt_less != 0

# x's state after f
init_res_less = 0
init_res_more = 0
seed_more = 1
seed_less = 1
for i in range(1, n+1):
  xp = x[-1 * i]
  if xp == '1':
    if valid_l:
      init_res_less += seed_less % init_pop_cnt_less
    init_res_more += seed_more % init_pop_cnt_more
  if valid_l:
    seed_less = (seed_less * 2) % init_pop_cnt_less
  seed_more = (seed_more * 2) % init_pop_cnt_more


dif_less = [0] * (2 * 10**5 + 100)
dif_more = [0] * (2 * 10**5 + 100)
if valid_l:
  dif_less[0] = 1 % init_pop_cnt_less
dif_more[0] = 1 % init_pop_cnt_more
for i in range(1, n+1):
  if valid_l:
    dif_less[i] = (dif_less[i-1] * 2) % init_pop_cnt_less
  dif_more[i] = (dif_more[i-1] * 2) % init_pop_cnt_more


def get_pc(dec):
  out = 0
  while dec > 0:
    if dec % 2 == 1:
      out+=1
    dec = dec // 2
  return out

def f(dec):
  pc = get_pc(dec)
  return dec % pc

cnt = [0] * (2 * 10**5 + 200)

for i in range(1, 2 * 10**5 + 100):
  c = 0
  cur = i
  while cur > 0:
    c += 1
    cur = f(cur)
  cnt[i] = c

for i in range(n):
  xi = x[i]

  if xi == '1':
    if valid_l:
      lx = init_res_less
      lx -= dif_less[n-i-1]
      lx %= init_pop_cnt_less
      print((cnt[lx] % init_pop_cnt_less) + 1)
    else:
      print(0)
  else:
    lx = init_res_more
    lx += dif_more[n-i-1]
    lx %= init_pop_cnt_more
    print((cnt[lx] % init_pop_cnt_more) + 1)
X=list(map(int.input().split()))
if X[2]-X[0]>0:
    p=X[2]-X[0]
    U="U"
    D="D"
else:
    p=X[0]-X[2]
    U="D"
    D="U"

if X[3]-X[1]>0:
    q=X[3]-X[1]
    R="R"
    L="L"
else:
    q=X[1]-X[3]
    R="L"
    L="R"
    
print(U*p+R*(q+1)+D*(p+1)+L*(q+1)+U+L+U*(p+1)+R*(q+1)+D*(p+1)+L*q)  

### FIXED CODE ###

sx, sy, tx, ty = map(int, input().split())

higth = ty - sy
width = tx - sx

ans = ''
ans += 'U' * higth
ans += 'R' * width
ans += 'D' * higth
ans += 'L' * width
ans += 'L' + 'U' * (higth + 1)
ans += 'R' * (width + 1) + 'D'
ans += 'R' + 'D' * (higth + 1)
ans += 'L' * (width + 1) + 'U'
print(ans)
import copy
N, M, X = map(int, input().split())


C =[]
A = {}

for i in range(N):
    ipt = list(map(int, input().split()))
    C.append(ipt[0])
    A[i] = ipt[1:]

bestscore = 99999999999
def rec(n, score, money):
    global bestscore
    if n==N: return
    s = copy.deepcopy(score)
    rec(n+1, s, money)

    money += C[n]
    for i in range(M):
        score[i] += A[n][i]
    

    for i in range(M):
        if score[i] < X:
            s = copy.deepcopy(score)
            rec(n+1, s, money)
            return
    bestscore = min(bestscore, money)

score = [0 for i in range(N)]

rec(0, score, 0)
if bestscore == 99999999999:
    print(-1)
else:
    print(bestscore)

### FIXED CODE ###

import copy
N, M, X = map(int, input().split())


C =[]
A = {}

for i in range(N):
    ipt = list(map(int, input().split()))
    C.append(ipt[0])
    A[i] = ipt[1:]

bestscore = 99999999999
def rec(n, score, money):
    global bestscore
    if n==N: return
    s = copy.deepcopy(score)
    rec(n+1, s, money)

    money += C[n]
    for i in range(M):
        score[i] += A[n][i]
    

    for i in range(M):
        if score[i] < X:
            s = copy.deepcopy(score)
            rec(n+1, s, money)
            return
    bestscore = min(bestscore, money)

score = [0 for i in range(M)]

rec(0, score, 0)
if bestscore == 99999999999:
    print(-1)
else:
    print(bestscore)
def main():
    N = int(input().strip())
    res = int(input().strip())
    if N == 1:
        return res
    for _ in range(1, N):
        t = int(input().strip())
        res = f(res, t)
    print(res)


def f(a, b):
    _gcd = gcd(a, b)
    return int(a / _gcd * b)


def gcd(a, b):
    if b == 0:
        return a
    if b == 1:
        return 1
    if b > a:
        return gcd(b, a)
    else:
        return gcd(b, a % b)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input().strip())
    res = int(input().strip())
    if N == 1:
        print(res)
        return
    for _ in range(1, N):
        t = int(input().strip())
        res = lcm(res, t)
    print(res)


def lcm(a, b):
    return (a * b) // gcd(a, b)


def gcd(a, b):
    if b == 0:
        return a
    if b == 1:
        return 1
    if b > a:
        return gcd(b, a)
    else:
        return gcd(b, a % b)

if __name__ == '__main__':
    main()
N = int(input())
S = list(map(str, input()))
f=0
i_c = j_c = k_c =1
for i in range(N):
    for j in range(N):
        for k in range(N):
            if(k+1>j+1 and
               j+1>i+1 and
               j-i=k-j and
               S[i]!=S[j] and 
               S[i]!=S[k] and
               S[j]!=S[k]):
                    f+=1
 
print(f)

### FIXED CODE ###

n=int(input())
s=input()
r=g=b=0
for i in s:
  if i=="R":r+=1
  elif i=="G":g+=1
  else:b+=1

ans=r*g*b
for i in range(n):
  for j in range(i+1,n):
    k_ = j+(j-i)
    if(k_ >=n):
      break
    ans -= int(s[i]!= s[j] and s[i] != s[k_] and s[j] != s[k_])

print(ans)
import math
a,b = [float(i) for i in input().split()]
ans = 1000000000
Flag = False

for i in range(1,10000):
    ans8 = int(math.floor(i*0.08))
    ans10 = int(math.floor(i*0.1))
#     print(ans8,ans10)
    if ans8 == a and ans10 == b:
        ans = min(ans, i)
        flag = True

if flag:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

import math
a,b = [float(i) for i in input().split()]
ans = 1000000000
flag = False

for i in range(1,10000):
    ans8 = int(math.floor(i*0.08))
    ans10 = int(math.floor(i*0.1))
#     print(ans8,ans10)
    if ans8 == a and ans10 == b:
        ans = min(ans, i)
        flag = True

if flag is True:
    print(ans)
else:
    print(-1)
o = input()
e = input()
ans = []

for i in range(len(o)):
  o.append(o[i])
  
for j in range(len(e)):
  e.append(e[j])
  
if len(o) == len(e):
  for k in range(len(o)):
    ans.append(o[k])
    ans.append(e[k])
    
  print("".join(ans))
  exit()
  
if len(o) != len(e):
  for l in range(len(e)):
    ans.append(o[l])
    ans.append(e[l])
    
  ans.append(o[-1])
  exit()
    
  

### FIXED CODE ###

O = input()
E = input()
o = []
e=[]
ans = []

for i in range(len(O)):
  o.append(O[i])
  
for j in range(len(E)):
  e.append(E[j])
  
if len(o) == len(e):
  for k in range(len(o)):
    ans.append(o[k])
    ans.append(e[k])
    
  print("".join(ans))
  exit()
  
if len(o) != len(e):
  for l in range(len(e)):
    ans.append(o[l])
    ans.append(e[l])
    
  ans.append(o[-1])
  print("".join(ans))
  exit()
x = input()
print(int(x/2))

### FIXED CODE ###

N = int(input())
print(int(N/2)+N%2)
h, w = map(int, input().split())
a = [['*' for _ in range(w+2)]]
for _ in range(h):
    a.append(['*'] + list(input()) + ['*'])
a.append(['*' for _ in range(w+2)])

q = set()

def encode(i, j):
    return i*w + j

def decode(x):
    i = x // w
    j = x % w
    return [i, j]

for i in range(1, h+1):
    for j in range(1, w+1):
        if a[i][j] == '#':
            q.add(encode(i, j))

for ans in range(h+w):
    nq = set()
    for x in q:
        i, j = decode(x)
        for k in [-1,1]:
            if a[i+k][j] == '.':
                nq.add(encode(i+k, j))
                a[i+k][j] = '#'
        for k in [-1,1]:
            if a[i][j+k] == '.':
                nq.add(encode(i, j+k))
                a[i][j+k] = '#'
    if len(nq) == 0:
        print(ans)
        exit()
    else:
        q = set()
        q = q | nq


### FIXED CODE ###

h, w = map(int, input().split())
a = [['*' for _ in range(w+2)]]
for _ in range(h):
    a.append(['*'] + list(input()) + ['*'])
a.append(['*' for _ in range(w+2)])

q = set()

def encode(i, j):
    return i*w + j-1

def decode(x):
    i = x // w
    j = x % w + 1
    return [i, j]

for i in range(1, h+1):
    for j in range(1, w+1):
        if a[i][j] == '#':
            q.add(encode(i, j))

for ans in range(h+w):
    nq = set()
    for x in q:
        i, j = decode(x)
        for k in [-1,1]:
            if a[i+k][j] == '.':
                nq.add(encode(i+k, j))
                a[i+k][j] = '#'
        for k in [-1,1]:
            if a[i][j+k] == '.':
                nq.add(encode(i, j+k))
                a[i][j+k] = '#'
    if len(nq) == 0:
        print(ans)
        exit()
    else:
        q = set()
        q = q | nq