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

from collections import Counter

N, P = map(int,input().split())
if N == 1:
    print(P)
    exit(0)
if N == 2:
    M = P
    Q = []
    k = 2
    while k*k <= M:
        if M%k == 0:
            M //= k
            Q.append(k)
        else:
            k += 1
    if M > 1:
        Q.append(M)
    R = Counter(Q)
    ans = 1
    for k in R:
        if R[k] >= 2:
            ans *= k**(R[k]//2)
    print(ans)
    exit(0)

ans = 1
k = 1
while k**N <= P:
    if P%(k**N)==0:
        ans = k
    k += 1

print(ans)

### FIXED CODE ###

from collections import Counter
import math

N, P = map(int,input().split())
if N >= 41:
    print(1)
    exit(0)
if N >= P:
    print(1)
    exit(0)
if N == 1:
    print(P)
    exit(0)
if N == 2:
    M = P
    Q = []
    k = 2
    while k*k <= M:
        if M%k == 0:
            M //= k
            Q.append(k)
        else:
            k += 1
    if M > 1:
        Q.append(M)
    R = Counter(Q)
    ans = 1
    for k in R:
        if R[k] >= 2:
            ans *= k**(R[k]//2)
    print(ans)
    exit(0)

ans = 1
k = 1
while pow(k,N) <= P:
    if P%pow(k,N)==0:
        ans = k
    k += 1

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

def bell(edges, n):
    count = 0
    dist = [-10000000000000000 for i in range(n)]
    dist[0] = 0

    changed = True

    while changed:
        count  += 1
        if count == 500000:
            print('inf')
            exit()
        changed = False
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                changed = True
            dist[edge[1]] = max(dist[edge[0]] + edge[2], dist[edge[1]])
                
    return dist


n,m = map(int,input().split())
edges = []
for _ in range(m):
    a, b, c = (int(x) for x in input().split())
    edges.append([a-1, b-1, c])

res = bell(edges, n)

print(res[n-1])

### FIXED CODE ###

N, M = map(int, input().split())
Edges = []
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    c = -c
    Edges.append([a, b, c])
 
dist = [float('inf')] * N
dist[0] = 0
 
for i in range(N):
    for fr, to, cost in Edges:
        if (dist[fr] != float('inf')) and (dist[to] > dist[fr] + cost):
            dist[to] = dist[fr] + cost
            if (i == N - 1) & (to == N - 1):
                print('inf')
                exit()
 
print(-dist[-1])
### BUGGY CODE ###

from collections import deque
n,q=map(int,input().split())
tree=[[0]*n for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    tree[a-1][b-1]=1
    tree[b-1][a-1]=1
cnt=[0]*n
for _ in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x
colors=["white" for _ in range(n)]

stack=deque([0])
colors[0]="gray"
while stack:
    current=stack.pop()
    for i in range(n):
        if tree[current][i]==1 and colors[i]=="white":
            stack.append(i)
            colors[i]="gray"
        if tree[current][i]==1 and colors[i]!="black":
            cnt[i]+=cnt[current]
    colors[current]="black"
print(*cnt)

### FIXED CODE ###

#「探索候補スタック」「探索済みリスト」「現在地点」の３点セットでとらえる
n,q=map(int,input().split())
mat=[set() for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    mat[a-1].add(b-1)
    mat[b-1].add(a-1) # プラスした要素
count=[0]*n
for _ in range(q):
    p,score=map(int,input().split())
    count[p-1]+=score

stack=[[0,0,-1]]
while stack:
    # print(stack)
    num,cnt,pr=stack.pop()
    count[num]+=cnt
    for k in mat[num]:
        if k==pr:
            continue
        stack.append([k,count[num],num])
print(*count)
### BUGGY CODE ###

from collections import deque

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]
C = [c for b, c in BC for _ in range(b)]
A.sort()
C.sort(reverse=True)
d = deque([])
# d.extend(C[max(len(C)-N, 0):])
d.extend(C[:N])
#
# print(A)
# print(d)

i = 0
while d:
    q = d.popleft()
    if q > A[i]:
        A[i] = q
        i += 1
    else:
        break

print(sum(A))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]
BC = sorted(BC, key=lambda x: x[1])
A.sort()
i = 0
for b, c in BC[::-1]:
    for _ in range(b):
        if i == N:
            break
        if c > A[i]:
            A[i] = c
            i += 1
        else:
            break

print(sum(A))
### BUGGY CODE ###

n1 = int(input())

n2 = [int(i) for i in input().split()]

r1 = 0

for i1 in range(n1):
    if i1 == 0:
        r1 += 1 
        continue
    t1 = n2[0: i1]
    t1.sort()
    if t1[0] > n2[i1]:
        r1 += 1

print(r1)


### FIXED CODE ###

n1 = int(input())

n2 = [int(i) for i in input().split()]

r1 = 0
m1 = n1 + 1

for i1 in range(n1):
    if n2[i1] < m1:
        r1 +=1
        m1 = n2[i1]

print(r1)
### BUGGY CODE ###

# coding: utf-8

import re

def _main():
    text = input()
    count = 0

    while True:
        new_text = re.sub(r'01|10', '', text)

        if text == new_text:
            break
        else:
            count += len(text) - len(new_text)
            text = new_text

    print(count)



if __name__ == '__main__':
    _main()

### FIXED CODE ###

# coding: utf-8

def _main():
    text = input()

    zero_count = text.count('0')
    one_count = len(text) - zero_count

    ans = min(zero_count, one_count) * 2

    print(ans)



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

# 一部のTLEケースを突破できるようになった。
# 中央のシマを左右で取り合う形になるが、
# 取る要素がひとつ増えるときは、前回の値を利用するようにした。
# added.sort() を min/max_added 値で代替した。

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

a1=a[0:n]
a_m=a[n:2*n]
a2=a[2*n:3*n]

a1.sort()
a2.sort()
base_sum=sum(a1)-sum(a2)

a1_vals=[0]*(n+1)
added=[]
min_added=float("inf")
j=0
for i in range(0,n):
  val=0
  # addedの最小値を持って置き、sort()を使わないようにする。
  if min_added < a1[j] and min_added < a_m[i]:
    val=a_m[i]-min_added
    added.remove(min_added)
    added.append(a_m[i])
    min_added=min(added)
  elif a1[j] < a_m[i]:
    val=a_m[i]-a1[j]
    added.append(a_m[i])
    min_added=min(min_added,a_m[i])
    j+=1
  a1_vals[i+1]=val+a1_vals[i]

a_m.reverse()
a2_vals=[0]*(n+1)
added=[]
max_added=-float("inf")
j=-1
for i in range(0,n):
  val=0
  if max_added > a2[j] and max_added > a_m[i]:
    val=a_m[i]-max_added
    added.remove(max_added)
    added.append(a_m[i])
    max_added=max(added)
  elif a2[j] > a_m[i]:
    val=a_m[i]-a2[j]
    added.append(a_m[i])
    max_added=max(max_added,a_m[i])
    j-=1
  a2_vals[i+1]=val+a2_vals[i]

max_val=-float("inf")
for i in range(0,n+1):
  max_val=max(max_val, (a1_vals[i] - a2_vals[n-i]))

print(base_sum + max_val)


### FIXED CODE ###

# 解説を確認、このような、最大（最小値）の出し入れが頻繁にあるデータでは、
# 「優先度付きキュー」というデータ構造を用いると容易になるようだ。
# 新規要素の Push & Pop が O(N log N) でできるとのこと。

from heapq import heapify,heappush,heappop

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

a1=a[0:n]
a_m=a[n:2*n]
a2=[ -x for x in a[2*n:3*n] ] # nega_list

a1_sums=[sum(a1)]
a2_sums=[sum(a2)]
heapify(a1)
heapify(a2)

# 左のシマに真ん中のシマを徐々に追加し、都度最小値を取り出す
for aa in a_m:
  heappush(a1,aa)
  p=heappop(a1)
  a1_sums.append(a1_sums[-1]+aa-p)

# 右のシマは都度最大値を取り出す
a_m.reverse()
for aa in a_m:
  heappush(a2,-aa)
  p=heappop(a2)
  a2_sums.append(a2_sums[-1]-aa-p)

max_val=-float("inf")
for i in range(0,n+1):
  max_val=max(max_val,a1_sums[i]+a2_sums[n-i])

print(max_val)
### BUGGY CODE ###

N = int( input() )
A, B = list( map(lambda x: int(x), input().split(" ")) ), list( map(lambda x: int(x), input().split(" ")) )
#A = monsters. B = number of to be able to kill monsters.殺せる数

 
def kill_monsters(Ai, Bi):
    while 0 < Ai and 0 < Bi:
        Ai -= 1
        Bi -= 1
    
    return (Ai, Bi)
 
 
def main(local_A, local_B, lim):
 
    for i in range(lim):
        local_A[i], local_B[i] = kill_monsters(local_A[i], local_B[i])
 
        if 0 < local_B[i]:
            local_A[i+1], local_B[i] = kill_monsters(local_A[i+1], local_B[i])
 
    return [local_A, local_B]

print( sum(A) - sum(main(A, B, N)[0]) )

### FIXED CODE ###

N = int( input() )
A, B = list( map(lambda x: int(x), input().split(" ")) ), list( map(lambda x: int(x), input().split(" ")) )
#A = monsters. B = number of to be able to kill monsters.殺せる数

 
def kill_monsters(Ai, Bi):

    Ai -= Bi
    Bi = 0

    if Ai < 0:
        Bi += -1*Ai
        Ai = 0

    return (Ai, Bi)
 
def main(local_A, local_B, lim):
 
    for i in range(lim):
        local_A[i], local_B[i] = kill_monsters(local_A[i], local_B[i])
 
        if 0 < local_B[i]:
            local_A[i+1], local_B[i] = kill_monsters(local_A[i+1], local_B[i])
 
    return [local_A, local_B]

print( sum(A) - sum(main(A, B, N)[0]) )
### BUGGY CODE ###

N,M = list(map(int,input().split()))
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

a = list(map(int,input().split()))
count2 = set()
for i in a:
    prime = prime_factorize(i)
    count2.add(prime.count(2))
if len(count2) == 1:
    a2 = [int(i//2) for i in a]
    if len(a2) == 1:
        div = M//a2[0]
        print((div+1)//2)
    else:
        gcda = a2[0]*a2[1]//gcd(a2[0],a2[1])
        for i in range(2,N):
            gcda = gcda*a2[i]//gcd(gcda,a2[i])
        div = M//gcda
        print((div+1)//2)
    
else:
    print(0)

### FIXED CODE ###

N,M = list(map(int,input().split()))
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def twocount(n):
    c = 0
    while n%2 == 0:
        n //= 2
        c += 1
    return c
 
a2 = [int(i//2) for i in map(int,input().split())]
count2 = set()
for i in a2:
    tc = twocount(i)
    count2.add(tc)
if len(count2) == 1:
 
    if len(a2) == 1:
        div = M//a2[0]
        print((div+1)//2)
    else:
        gcda = a2[0]*a2[1]//gcd(a2[0],a2[1])
        for i in range(2,N):
            gcda = gcda*a2[i]//gcd(gcda,a2[i])
        div = M//gcda
        print((div+1)//2)
    
else:
    print(0)
### BUGGY CODE ###

n,k,q=map(int,input().split())
A=[int(input()) for i in range(q)]

for i in range(n):
    a=A.count(i+1)
    ans=k-q+a
    if ans>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k,q=map(int,input().split())
A=[int(input()) for i in range(q)]
li=[k-q for i in range(n)]
for i in range(q):
    li[A[i]-1]=li[A[i]-1]+1
for i in range(n):
    if li[i]>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
def sieve(m):
    N=range(1,m+2,2)
    r=int(m**.5)
    h=len(N)
    N[0]=0
    for i in range(h):
        x=N[i]
        if x>r: break
        if x and i+x<h: N[i+x:h:x]=[0] * ((h-1-i-x)/x+1)
    return N
def f0056(n):
    x=0
    if n%2==1:
        if SIEVES[(n-2)/2]!=0: x=1
    else:
        x=len([e for e in SIEVES if 0<e<=n/2 and SIEVES[(n-e)/2]!=0])
    return x
        
SIEVES=sieve(50000)
for n in sys.stdin:
    n=int(n)
    if n==0: break
    print f0056(n)

### FIXED CODE ###

import sys
def sieve(m):
    N=range(1,m+2,2)
    r=int(m**.5)
    h=len(N)
    N[0]=0
    for i in range(h):
        x=N[i]
        if x>r: break
        if x and i+x<h: N[i+x:h:x]=[0]*((h-1-i-x)/x+1)
    return N
def f0056(n):
    x=0
    if n<4:x=0
    elif n==4:x=1
    elif n%2==1:
        if S[n/2-1]: x=1
    else:
        a=n/2
        for e in PRIMES:
            if e>a: break
            if S[(n-e)/2]: x+=1
    return x

S=sieve(50000)
PRIMES=filter(None,S)
for n in sys.stdin:
    n=int(n)
    if n==0: break
    print f0056(n)
### BUGGY CODE ###

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

for i in range(2**N):
  im ="0" + str(N)
  temp = list(format(i, im+'b'))
  temp1 = list(map(int, temp))
  for k in range(1,N+1):
    if sum(temp1[k-1::k])%2 == A[k-1]:
        print()
        pass
    else:
        break
  else:
    print(sum(temp1))
    anslist = []
    for i in range(N):
        if temp1[i] == 1:
          anslist.append(i+1)
    if anslist == []:
      exit()
    else:
      print(*anslist)
      exit()

### FIXED CODE ###

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

temp = [0]*N
for i in range(N-1,-1,-1):
  for j in [0,1]:
    temp[i] = j
    if sum(temp[i::i+1])%2 == A[i]:
      break
  else:
    print(-1)
    exit()
print(sum(temp)) 
anslist = []
for i in range(N):
  if temp[i] == 1:
    anslist.append(i+1)
if anslist == []:
  exit()
else:
  print(*anslist)
  exit()
### BUGGY CODE ###

import itertools
from sys import stdin
N=int(input())
st=list(stdin.readline().strip())
count=0
stt=set(st)
stt=list(stt)
num=["0","1","2","3","4","5","6","7","8","9"]
num = [s for s in num if s in stt ]
num_list= ["".join(i) for i in itertools.product(num,repeat=3)]

for number in num_list:
    cnt = 0
    for i in range(N):
        if number[cnt]==st[i]:
            cnt+=1
            if cnt==3:
                count += 1
                break


print(count)

### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

import bisect
import itertools
n=int(input())
s=str(input())
R=[]
B=[]
G=[]
for i in range(n):
  if s[i]=='R':
    R.append(i)
  elif s[i]=='B':
    B.append(i)
  else:
    G.append(i)
ans=0
l=itertools.permutations([R,B,G])
for r,b,g in l:
  V=len(g)
  for i in r:
    index=bisect.bisect_left(b,i)
    for j in b[index:]:
      index2=bisect.bisect_left(g,j)
      tmp=V-index2
      if j+j-i in g[index2:]:
        tmp-=1
      ans+=tmp
print(ans)

### FIXED CODE ###

n=int(input())
s=str(input())
R=[]
B=[]
G=[]
for i in range(n):
  if s[i]=='R':
    R.append(i)
  elif s[i]=='B':
    B.append(i)
  else:
    G.append(i)
ans=len(R)*len(B)*len(G)

for i in range(n-1):
  for j in range(i+1,n):
    char1=s[i]
    char2=s[j]
    if char1==char2:
      pass
    else:
      if n>2*j-i>j and s[2*j-i]!=char1 and s[2*j-i]!=char2:
        ans-=1
print(ans)
### BUGGY CODE ###

N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
group_id = {i:[] for i in range(1, N+1)}
group = {}

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
    
X = set(range(1, N+1))
g = 0
while X:
    i = X.pop()
    group_id[i] = g
    x = {i}
    ch = set(child[i])
    while ch:
        c = ch.pop()
        group_id[c] = g
        ch = (ch | set(child[c])) - set(x)
        x = x | {c}
    group[g] = len(x)
    X = X - set(x)
    g += 1

for i in range(1, N+1):
    ans[i] = group[group_id[i]] - len(child[i]) - 1

for _ in range(K):
    c, d = map(int, input().split())
    if group_id[c] == group_id[d]:
        ans[c] -= 1
        ans[d] -= 1

print(*ans[1:])

### FIXED CODE ###

N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
isChecked = [0] * (N + 1)
isBlocked = [set() for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
    
for _ in range(K):
    c, d = map(int, input().split())
    isBlocked[c].add(d)
    isBlocked[d].add(c)
    
for i in range(1, N+1):
    if isChecked[i]:
        continue
    isChecked[i] = 1
    x = set([i])
    ch = child[i].copy()
    while ch:
        c = ch.pop()
        if isChecked[c]:
            continue
        isChecked[c] = 1
        x.add(c)
        ch.extend(child[c])
    for j in x:
        ans[j] = len(x) - 1 - len(child[j]) - len(x & isBlocked[j])
        
print(*ans[1:])
### BUGGY CODE ###

def main():
    N,Y = list(map(int,input().split()))

    flag = False

    loop_10000 = Y // 10000
    loop_5000 = Y // 5000
    loop_1000 = Y // 1000

    for i in range(loop_10000+1):
        for j in range(loop_5000+1):
            for k in range(loop_1000+1):
                if(i+j+k == N and 10000 * i + 5000 * j + 1000 * k == Y):
                    print(i,j,k)
                    flag = True
                    break
            if(flag):
                break
        if(flag):
            break
    if(not flag):
        print(-1,-1,-1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N,Y = list(map(int,input().split()))

    flag = False

    loop_10000 = Y // 10000
    loop_5000 = Y // 5000
    loop_1000 = Y // 1000

    for i in range(loop_10000+1):
        for j in range(loop_5000+1):
            k = N - i - j
            if(k >= 0 and i+j+k == N and 10000 * i + 5000 * j + 1000 * k == Y):
                print(i,j,k)
                flag = True
                break
            #for k in range(loop_1000+1):
            #    if(i+j+k == N and 10000 * i + 5000 * j + 1000 * k == Y):
            #        print(i,j,k)
            #        flag = True
            #        break
            #if(flag):
            #    break
        if(flag):
            break
    if(not flag):
        print(-1,-1,-1)

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

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().rstrip().split(' '))

field = []
for _ in range(H):
    temp_field = []
    for s in input():
        if s == '.':
            temp_field.append(0)
        else:
            temp_field.append(1)
    field.append(temp_field)
    
dp = [[0] * W for _ in range(H)]

def rec(i, j):
    if field[i][j] == 1:
        return 0
    
    if dp[i][j] != 0:
        return dp[i][j]
        
    dp[i][j] = H + W
        
    min_dist = H + W
    if i > 0:
        min_dist = min(min_dist, rec(i-1, j) + 1)
    if i < H - 1:
        min_dist = min(min_dist, rec(i+1, j) + 1)
    if j > 0:
        min_dist = min(min_dist, rec(i, j-1) + 1)
    if j < W - 1:
        min_dist = min(min_dist, rec(i, j+1) + 1)
        
    dp[i][j] = min_dist
    
    return min_dist
    
    
for i in range(H):
    for j in range(W):
        rec(i, j)
     
print(max([max(temp_dp) for temp_dp in dp]))

### FIXED CODE ###

# coding: utf-8
# Your code here!

from collections import deque

H, W = map(int, input().rstrip().split(' '))

field = [[0] * W for _ in range(H)]
d = deque()
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            field[i][j] = 1
            d.append([i, j, 0])

max_dist = 0
while len(d) > 0:
    cur_h, cur_w, dist = d.popleft()
    for i, (dh, dw) in enumerate([[0, 1], [0, -1], [1, 0], [-1, 0]]):
        if (cur_h + dh) >= 0 and (cur_h + dh) < H and (cur_w + dw) >= 0 and (cur_w + dw) < W:
            if field[cur_h+dh][cur_w+dw] == 0:
                field[cur_h+dh][cur_w+dw] = 1
                d.append([cur_h+dh, cur_w+dw, dist+1])
                max_dist = max(max_dist, dist+1)

print(max_dist)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
S = input()
ans = 0
# for i in range(len(S)-3):
i = 0
while i < len(S)-3:
    flag = False
    li = []
    # for j in range(i+4, len(S)+1):
    j = i+4
    while j < len(S)+1:
        if int(S[i:j]) % 2019 == 0:
            ans += 1
            li.append(j)
            flag = True
        j += 1
    if flag:
        i += max(1, min(li)-5)
    else:
        i += 1

print(ans)


### FIXED CODE ###

s = input()[::-1]
length = len(s)
a = [0] * length
d = [0] * length
ans = [0] * 2019
x = 10

a[0] = int(s[0])
d[0] = a[0]
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * x % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1
    x = x * 10 % 2019

ans_c = [i for i in ans if i != 0]

print(int(sum([ans_c[i] * (ans_c[i]-1) for i in range(len(ans_c))]) / 2) + ans[0])
### BUGGY CODE ###

import itertools
import math
import numpy as np

N = int(input())
x= []
y = []
town = []
for i in range(N):
    x_i,y_i = (int(x) for x in  input().split())
    x.append(x_i)
    y.append(y_i)
    town.append(i)

grand_sum = 0.0
for v in itertools.permutations(town):
    d_sum = 0.0
    v = list(v)
    for i in range(len(v)-1):
        n1 = np.array([x[v[i]],y[v[i]]])
        n2 = np.array([x[v[i+1]],y[v[i+1]]])
        d_sum += np.linalg.norm(n2-n1)

    grand_sum += d_sum
    
print(grand_sum / math.factorial(N))

### FIXED CODE ###

import itertools
import math
def getdis(a,b):
  return math.sqrt((b[0] - a[0])**2+(b[1]-a[1])**2)

N = int(input())

city = []
l = [i for i in range(N)]
for i in range(1,N+1):
  x,y = map(int,input().split())
  city.append([x,y])
  
l = list(itertools.permutations(l))
sum_dis = [0]*len(l)
for i in range(len(l)):
  for j in range(N-1):
    sum_dis[i]+=getdis(city[l[i][j]],city[l[i][j+1]])
print(sum(sum_dis)/len(l))
### BUGGY CODE ###

def main():
  import sys
  input=sys.stdin.buffer.readline
  n=int(input())+1
  data=[0]*n*2
  def update(i,x):
    i+=n
    data[i]=x
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
  def query(l,r):
    l+=n
    r+=n
    s=0
    while l<r:
      if l&1:
        s|=data[l]
        l+=1
      if r&1:
        r-=1
        s|=data[r]
      l//=2
      r//=2
    return sum(1for i in range(26)if s&2**i)
  for i,c in enumerate(input()[:-1]):update(i,2**(c-97))
  s=[]
  for _ in range(int(input())):
    q,a,b=input().split()
    if q[0]>49:s+=query(int(a)-1,int(b)),
    else:update(int(a)-1,2**(b[0]-97))
  print(*s)
main()

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
n=int(input())+1
data=[0]*n*2
def update(i,x):
  i+=n
  data[i]=x
  i//=2
  while i:
    data[i]=data[i*2]|data[i*2+1]
    i//=2
def query(l,r):
  l+=n
  r+=n
  s=0
  while l<r:
    if l&1:
      s|=data[l]
      l+=1
    if r&1:
      r-=1
      s|=data[r]
    l//=2
    r//=2
  return sum(map(int,bin(s)[2:]))
for i,c in enumerate(input()[:-1]):
  update(i,2**(c-97))
for _ in range(int(input())):
  q,a,b=input().split()
  if q[0]>49:print(query(int(a)-1,int(b)))
  else:update(int(a)-1,2**(b[0]-97))
### BUGGY CODE ###

def main():
    n= int(input())
    slis = tuple(input())
    total = 0
    lis_R = [n for n, v in enumerate(slis) if v == "R"]
    lis_G = [n for n, v in enumerate(slis) if v == "G"]
    lis_B = [n for n, v in enumerate(slis) if v == "B"]

    lenR = len(lis_R)
    lenG = len(lis_G)
    lenB = len(lis_B)
    total += lenR * lenG * lenB

    for i in lis_R:
        for j in lis_G:
            for k in lis_B:
                if abs(i-j) == abs(j-k) or abs(i-k)==abs(j-k) or abs(k-i)==abs(j-i):
                    total -= 1
    print(total)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import re
    n = int(input())
    s = input()
    rindex = set()
    gindex = set()
    bindex = set()
    for i in range(n):
        if s[i] == "R":
            rindex.add(i)
        elif s[i] == "G":
            gindex.add(i)
        else:
            bindex.add(i)
    ans = len(rindex) * len(gindex) * len(bindex)

    for r in rindex:
        for g in gindex:
            if r > g:
                gap = r - g
                b1 = r + gap
                b2 = g - gap
                b3 = g + (gap/2)

            elif r < g:
                gap = g - r
                b1 = g + gap
                b2 = r - gap
                b3 = r + (gap/2)
            if b1 in bindex:
                ans -= 1
            if b2 in bindex:
                ans -= 1  
            if b3 in bindex:
                ans -= 1  
    print(ans)
if __name__ == "__main__":
    main()