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

from collections import defaultdict
from heapq import heapify, heappop
import heapq
n,m,s,t =list(map(int,input().split()))

MAX_VAL = 10**20
uvab =  [list(map(int,input().split())) for _ in range(m)]
jpy_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))
snuke_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))


for u,v,a,b in uvab:
    u=u-1
    v=v-1
    jpy_cost[u][v] = a
    jpy_cost[v][u] =a
    snuke_cost[u][v]=b
    snuke_cost[v][u]=b


# Dijktra's shortest path algorithm. Prints the path from source to target.


def dijkstra(adj, source):
    INF = ((1 << 63) - 1) // 2
    pred = {x: x for x in range(n)}
    dist = {x: INF for x in range(n)}
    dist[source] = 0
    PQ = []
    heapq.heappush(PQ, [dist[source], source])

    while (PQ):
        u = heapq.heappop(PQ)  # u is a tuple [u_dist, u_id]
        u_dist = u[0]
        u_id = u[1]
        if u_dist == dist[u_id]:
            # if u_id == target:
            #    break
            for v in adj[u_id]:
                v_id = v
                w_uv = adj[u_id][v]
                if dist[u_id] + w_uv < dist[v_id]:
                    dist[v_id] = dist[u_id] + w_uv
                    heapq.heappush(PQ, [dist[v_id], v_id])
                    pred[v_id] = u_id

    return dist


jpy_dijk =  dijkstra(jpy_cost,s-1)
snuke_dijk = dijkstra(snuke_cost,t-1)
#
# print(s,t)
# print(jpy_dijk)
# print(snuke_dijk)
# print([jpy_dijk[i]+snuke_dijk[i] for i in range(n)])

#ord n
res = []
min_val = MAX_VAL
for i in reversed(range(n)):
    #都市  i で両替
    val = jpy_dijk[i]+ snuke_dijk[i]
    assert val < MAX_VAL
    min_val=min(min_val,val)
    res.append(min_val)
#ord n
for x in reversed(res):
    print(10**15-  x)


### FIXED CODE ###

from collections import defaultdict
from heapq import heapify, heappop
import heapq
n,m,s,t =list(map(int,input().split()))

MAX_VAL = 10**20
uvab =  [list(map(int,input().split())) for _ in range(m)]
jpy_cost = defaultdict(dict)
snuke_cost = defaultdict(dict)


for u,v,a,b in uvab:
    u=u-1
    v=v-1
    jpy_cost[u][v] = a
    jpy_cost[v][u] =a
    snuke_cost[u][v]=b
    snuke_cost[v][u]=b


# Dijktra's shortest path algorithm. Prints the path from source to target.


def dijkstra(adj, source):
    INF = MAX_VAL
    dist = [INF for x in range(n)]
    dist[source] = 0
    PQ = []
    heapq.heappush(PQ, [dist[source], source])

    while (PQ):
        u_dist,u_id = heapq.heappop(PQ)  # u is a tuple [u_dist, u_id]
        if u_dist == dist[u_id]:
            for v in adj[u_id]:
                w_uv = adj[u_id][v]
                if dist[u_id] + w_uv < dist[v]:
                    dist[v] = dist[u_id] + w_uv
                    heapq.heappush(PQ, [dist[v], v])
    return dist


jpy_dijk =  dijkstra(jpy_cost,s-1)
snuke_dijk = dijkstra(snuke_cost,t-1)
#
# print(s,t)
# print(jpy_dijk)
# print(snuke_dijk)
# print([jpy_dijk[i]+snuke_dijk[i] for i in range(n)])

#ord n
res = []
min_val = MAX_VAL
for i in reversed(range(n)):
    #都市  i で両替
    val = jpy_dijk[i]+ snuke_dijk[i]
    assert val < MAX_VAL
    min_val=min(min_val,val)
    res.append(min_val)
#ord n
for x in reversed(res):
    print(10**15-  x)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
L = list(map(int,input().split()))
count = 0

L.sort()
for i in range(0,N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if L[k] >= L[i] +L[j]:
                break
            if L[i] < L[j] +L[k] and L[j] < L[k] + L[i]:
                count += 1
            else: 
                break
                
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect

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

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

x,y,z,k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse = True)
b.sort(reverse = True)
c.sort(reverse = True)

li = []
ans = []

for i in a:
    for j in b:
        li.append(i + j)
        
li.sort(reverse = True)
li = li[:min(k,x*y)]

for i in li:
    for j in c:
        ans.append(i + j)
        
ans.sort(reverse = True)

for i in range(k):
    print(ans[i])

### FIXED CODE ###

x,y,z,k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse = True)
b.sort(reverse = True)
c.sort(reverse = True)
li = []
box = []
for i in a:
    for j in b:
        li.append(i + j) 
li.sort(reverse = True)
li = li[:min(k,x*y)]
for i in c:
    for j in li:
        box.append(i + j)
box.sort(reverse = True)
for i in range(k):
    print(box[i])
### BUGGY CODE ###

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

ans = 0

for i in range(N):
    count = 0
    for j in range(i+1):
        if A[i] <= A[j]:
            count += 1
        else:
            break

    if count == i+1:
        ans += 1

print(ans)


### FIXED CODE ###

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

minv = 10 ** 9
ans = 0

for i in P:
    if i < minv:
        ans += 1
        minv = i

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

mod = int(1e9) + 7


def power(x, y):
    if y == 0       : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod


def div(a, b):
    return a * power(b, mod-2) % mod


fact = [1] * int(1e5)
for i in range(1, int(1e5)):
    fact[i] = (i * fact[i-1]) % mod


def combination(n, r):
    return div(div(fact[n], fact[r]), fact[n-r])


def main():
    S = input()
    cumsum_A = [0] * len(S)
    cumsum_B = [0] * len(S)
    cumsum_C = [0] * len(S)
    cumsum_Q = [0] * len(S)
    for i in range(len(S)):
        cumsum_A[i] = cumsum_A[i-1] if i > 0 else 0
        cumsum_B[i] = cumsum_B[i-1] if i > 0 else 0
        cumsum_C[i] = cumsum_C[i-1] if i > 0 else 0
        cumsum_Q[i] = cumsum_Q[i-1] if i > 0 else 0
        s = S[i]
        if s == "A":
            cumsum_A[i] += 1
        if s == "B":
            cumsum_B[i] += 1
        if s == "C":
            cumsum_C[i] += 1
        if s == "?":
            cumsum_Q[i] += 1
    retval = 0
    for i in range(len(S)):
        s = S[i]
        if s == "B" or s == "?":
            a = cumsum_A[i]
            aq = cumsum_Q[i]
            c = cumsum_C[-1] - cumsum_C[i]
            cq = cumsum_Q[-1] - cumsum_Q[i]
            if s == "?":
                aq -= 1
            asum = 0
            for j in range(aq+1):
                asum += (a + j) * power(2, aq-j) * combination(aq, j)
                asum %= mod
            csum = 0
            for j in range(cq+1):
                csum += (c + j) * power(2, cq-j) * combination(cq, j)
                csum %= mod
            retval = (retval + asum * csum) % mod
    print(retval)

if __name__ == "__main__":
    main()


### FIXED CODE ###

mod = int(1e9) + 7


def main():
    S = input()
    a_sum = 0
    ab_sum = 0
    abc_sum = 0
    pattern = 1
    for i in range(len(S)):
        s = S[i]
        if s == "A":
            a_sum = (a_sum + pattern) % mod
        if s == "B":
            ab_sum = (ab_sum + a_sum) % mod
        if s == "C":
            abc_sum = (abc_sum + ab_sum) % mod
        if s == "?":
            abc_sum = (abc_sum * 3 + ab_sum) % mod
            ab_sum = (ab_sum * 3 + a_sum) % mod
            a_sum = (a_sum * 3 + pattern) % mod
            pattern = pattern * 3 % mod
    print(abc_sum)


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

def func(x,y,z):
    return x**2+y**2+z**2+x*y+y*z+z*x

n = int(input())

ans = 0
arr = []
for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            arr.append(func(x,y,z))
for i in range(n):
    print(arr.count(i+1))

### FIXED CODE ###

import itertools
import math
import collections
def main():
    n = int(input())
    s = int(math.sqrt(n))
    a = list(itertools.product(range(1,s),repeat=3))
    ans = []
    for i in range(len(a)):
        t = a[i][0] ** 2 + a[i][1] ** 2 + a[i][2] ** 2 + a[i][0] * a[i][1] + a[i][1] * a[i][2] + a[i][2] * a[i][0]
        ans.append(t)
        # print(ans)
    c = collections.Counter(ans)
    for i in range(1,n+1):
        print(c[i])
        
        
main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    K,S = (int(x) for x in input().split())

    count = 0

    for x in range(K+1):
        for y in range(K+1):
            for z in range(K+1):
                if x+y+z == S:
                    count += 1
                    
    print(count)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    K,S = (int(x) for x in input().split())

    count = 0

    for x in range(K+1):
        for y in range(K+1):
            z = S - (x + y)
            if z >= 0 and z <= K:
                count += 1

    print(count)

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

N=int(input())
A=list(map(int,input().split()))
M=1
for i in range(len(A)):
    M*=A[i]
if M <= 10**18:
    print(int(M))
else:
    print('-1')

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
M=1
if 0 in A:
    print('0')
else:
    for i in range(len(A)):
        M*=A[i]
        if M > 10**18:
            break
    if M > 10**18:
        print('-1')
    else:
        print(int(M))
### BUGGY CODE ###

def kitaichi(a):
    sum = ((1+a)*a/2)/a
    return sum

n, k = map(int, input().split())
p = [int(_) for _ in input().split()]

ans = 0
ans_index = 0
for i in range(0, n-k+1):
    val = 0
    for j in range(k):
        val += p[i+j]
    if val > ans:
        ans = val
        ans_index = i

sum = 0
for i in range(ans_index, ans_index+k):
    sum += kitaichi(p[i])

print(sum)

### FIXED CODE ###

def kitaichi(a):
    return ((1+a)*a/2)/a

n, k = map(int, input().split())
p = [int(_) for _ in input().split()]
dp = [0] * n
dp[0] = p[0]
cnt = 1

maxi = 0
idx = 0

for i in range(1, n):
    if cnt < k:
        dp[i] = p[i] + dp[i-1]
        cnt += 1
    else:
        dp[i] = p[i] + dp[i-1] - p[i-k]
    if maxi < dp[i]:
        maxi = dp[i]
        idx = i

ans = 0
for i in range(idx-k+1, idx+1):
    ans += kitaichi(p[i])

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

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    d={}
    c=0
    edge1=[[] for _ in range(N*(N-1)//2)]
    edge2=[[] for _ in range(N*(N-1)//2)]
    for i in range(N):
        l=list(map(lambda x: int(x)-1,input().split()))
        prev=-1
        for x in l:
            a=min(i,x)*10**3+max(i,x)
            if a in d:
                z=d[a]
                if prev!=-1:
                    edge1[prev].append(z)
                    edge2[z].append(prev)
                prev=z
            else:
                d[a]=c
                if prev!=-1:
                    edge1[prev].append(c)
                    edge2[c].append(prev)
                c+=1
                prev=d[a]
    stack=[]
    days=[-1]*(N*(N-1)//2)
    for i,l in enumerate(edge2):
        if not l:
            stack.append(i)
            days[i]=1
    while stack:
        v=stack.pop()
        for x in edge1[v]:
            days[x]=max(days[x],days[v]+1)
            stack.append(x)
    print(max(days))
        

    

        
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=[[] for _ in range(N)]
    for i in range(N):
        A[i]=deque(list(map(lambda x: int(x)-1,input().split())))
    days=1
    c=0
    pre=[]
    tmp=[]
    for i in range(N):
        if A[i] and A[A[i][0]][0]==i:
            tmp.append(i)
            tmp.append(A[i][0])
    tmp=list(set(tmp))
    for i in tmp:
        A[i].popleft()
        c+=1
    pre=tmp
    if c<N*(N-1):
        while c<N*(N-1):
            tmp=[]
            for i in pre:
                if A[i] and A[A[i][0]][0]==i:
                    tmp.append(i)
                    tmp.append(A[i][0])
            tmp=list(set(tmp))
            for i in tmp:
                A[i].popleft()
                c+=1
            pre=tmp
            days+=1
            if days>N*(N-1)//2:
                print(-1)
                exit()
    print(days)
                
            
        
    
        
        

    

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

def invalid(a, b):
    if a > b:
        a, b = b, a
    return (b % a == 0 and ((b - a) // 2) % a != 0)

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    A.sort()
    if len(A) == 1:
        l = A[0]
    else:
        if invalid(A[0], A[1]):
            return 0
        l = lcm(A[0], A[1])
        for i in A[2:]:
            if invalid(l, i):
                return 0
            l = lcm(l, i)
    return (M + l // 2) // l

print(main())


### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

def invalid(a, b):
    if a > b:
        a, b = b, a
    return (b % a == 0 and ((b - a) // 2) % a != 0)

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    A.sort(reverse=True)
    if len(A) == 1:
        l = A[0]
    else:
        if invalid(A[0], A[1]):
            return 0
        l = lcm(A[0], A[1])
        for i in A[2:]:
            if invalid(l, i):
                return 0
            if l % i == 0:
                continue
            if l // 2 > M:
                return 0
            l = lcm(l, i)
    return (M + l // 2) // l

print(main())
### BUGGY CODE ###

import sys
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
#a=map(int,sys.stdin)
dp=[0]*(n+1)
dp[0]=1
if 1 not in a:dp[1]=1
for i in range(2,n+1):
    if i in a:continue
    if dp[i-1]==dp[i-2]==0:break
    dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1])

### FIXED CODE ###

import sys
n,m=map(int,input().split())
a=set(map(int,sys.stdin))
dp=[0]*(n+1)
dp[0]=1
if 1 not in a:dp[1]=1
for i in range(2,n+1):
    if i in a:continue
    if dp[i-1]==dp[i-2]==0:break
    dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1])
### BUGGY CODE ###

n,m = input().split()
plist = []
ylist = []
n = int(n)
m = int(m)
anslist = [0 for i in range(m)]
list = [[] for i in range(n+1)]
for i in range(m):
    p,y = input().split()
    p = int(p)
    y = int(y)
    plist.append(p)
    ylist.append(y)
for i in range(m):
    for j in range(n+1):
        if plist[i] == j + 1:
            list[j].append([ylist[i],i])
for i in range(n):
    list[i].sort()
    for j in range(len(list[i])):
        mtem = list[i][j][1]
        ans1 = str(plist[mtem])
        while len(ans1) < 6:
            ans1 = "0" + ans1
        ans2 = str(j+1)
        while len(ans2) < 6:
            ans2 = "0" + ans2
        anslist[mtem] = ans1 + ans2
for i in range(m):
    print(anslist[i])

### FIXED CODE ###

n,m = input().split()
plist = []
ylist = []
n = int(n)
m = int(m)
anslist = [0 for i in range(m)]
list = [[] for i in range(n+1)]
for i in range(m):
    p,y = input().split()
    p = int(p)
    y = int(y)
    plist.append(p)
    ylist.append(y)
    list[p-1].append([ylist[i],i])
for i in range(n):
    list[i].sort()
    for j in range(len(list[i])):
        mtem = list[i][j][1]
        ans1 = str(plist[mtem])
        while len(ans1) < 6:
            ans1 = "0" + ans1
        ans2 = str(j+1)
        while len(ans2) < 6:
            ans2 = "0" + ans2
        anslist[mtem] = ans1 + ans2
for i in range(m):
    print(anslist[i])
### BUGGY CODE ###

S = input()
p = 0
A = '0'
Q = int(input())
for _ in range(Q):
  Qr = list(input().split())
  if int(Qr[0])==1:
    p = not p
  else:
    if int(Qr[1])==1:
      if p:
        A += Qr[2]
      else:
        A = Qr[2]+A
    else:
      if p:
        A = Qr[2]+A
      else:
        A += Qr[2]
S = A.replace('0',S)
if p:
  print(S[::-1])
else:
  print(S)

### FIXED CODE ###

S = input()
p = 0
head = ''
end = ''
Q = int(input())
for _ in range(Q):
  Qr = list(input().split())
  if int(Qr[0])==1:
    p = not p
  else:
    if int(Qr[1])==1:
      if p:
        end += Qr[2]
      else:
        head = Qr[2]+head
    else:
      if p:
        head = Qr[2]+head
      else:
        end += Qr[2]
S = head + S + end
if p:
  print(S[::-1])
else:
  print(S)
### BUGGY CODE ###

N,M = list(map(int,input().split()))
l_n = list(input())
for i in range(N-1):
    if l_n[i] == "A" and l_n[i+1] == "C":
        l_n[i] = "a"
for i in range(M):
    B = list(map(int,input().split()))
    C = l_n[B[0]-1:B[1]-1].count("a")
    print(C)

### FIXED CODE ###

N,M = list(map(int,input().split()))
l_n = input()
l_a = [0] * (N+1)
for i in range(N):
    l_a[i+1] = l_a[i] + (1 if l_n[i:i+2] == 'AC' else 0)
for i in range(M):
    l,r = map(int,input().split())
    print(l_a[r-1]-l_a[l-1])
### BUGGY CODE ###

N = int(input())
S = []
ans = N
#for i in range(N):
#    S.append(input())
S = [input() for i in range(N)]
for i in range(N):
    flg = 0
    j  = 0
    while(flg == 0 and j < i):
        if i != j:
            if len(S[j]) == len(S[i]):
                if S[j][0] == S[i][0]:
                    if S[j] == S[i]:
                        S[j] = ''
                        ans = ans - 1
                        flg = 1
        j = j+1
print(ans)

### FIXED CODE ###

N = int(input())
S = []
ans = N
S = [input() for i in range(N)]
#for i in range(N):
#    S.append(input())
S.sort()
for i in range(N-1):
    if S[i] == S[i+1]:
        ans = ans - 1
print(ans)
### BUGGY CODE ###

import numpy as np

def calc_intersection(z1, z2, R):
  d = np.linalg.norm(z1 - z2)
  if R < d/2:
    return None
  else:
    m = (z1 + z2) / 2
    v = np.sqrt(R**2/d**2 - 0.25) * np.array([z2[1]-z1[1], z1[0]-z2[0]])
    return np.r_[(m+v)[None, :], (m-v)[None, :]]


def check(R):
  intersections = np.empty([0, 2])
  for i in range(N):
    for j in range(i+1, N):
      points = calc_intersection(xy[i], xy[j], R)
      if points is None:
        return False
      else:
        intersections = np.r_[intersections, points]
  D = np.linalg.norm(intersections[None,:] - xy[:,None], axis=2)
  if (D <= R).prod(axis=0).any():
    return True
  else:
    return False


N = int(input())
xy = []
for i in range(N):
  xy.append(list(map(int, input().split())))

xy = np.array(xy)
left = 0 # False
right = 500 * 2**0.5 # True
while right - left > 0.000001:
  mid = (left + right) / 2
  if check(mid):
    right = mid
  else:
    left = mid

print(right)

### FIXED CODE ###

def calc_intersection(z1, z2, R):
  d2 = (z1[0]-z2[0])**2 + (z1[1]-z2[1])**2
  d = d2 ** 0.5
  if R < d/2:
    return None
  else:
    m = [(z1[0]+z2[0])*0.5, (z1[1]+z2[1])*0.5]
    l = (R**2/d2 - 0.25)**0.5
    v = [l*(z2[1]-z1[1]), l*(z1[0]-z2[0])]
    return [[m[0]+v[0], m[1]+v[1]], [m[0]-v[0], m[1]-v[1]]]


def check(R):
  intersections = []
  for i in range(N):
    for j in range(i+1, N):
      points = calc_intersection(xy[i], xy[j], R)
      if points is None:
        return False
      else:
        intersections.extend(points)
  
  for px, py in intersections:
    res = True
    for x, y in xy:
      res *= ((x-px)**2 + (y-py)**2 <= R**2+0.000001)
      if not res:
        break
    if res:
      return True
  return False


N = int(input())
xy = [list(map(int, input().split())) for i in range(N)]
left = 0 # False
right = 500 * 2**0.5 # True
while right - left > 0.000001:
  mid = (left + right) / 2
  if check(mid):
    right = mid
  else:
    left = mid

print(right)
### BUGGY CODE ###

s = [i for i in input()]
n =len(s)
A=13
data=[4,3,12,9,10,1]*n
data=data[-n:]

dp=[[0 for i in range(A+1)] for j in range(n+1)]
dp[0][0]=1

def benri(a,i):
	return a*data[i]%A


for i in range(n):
	for j in range(A+1):
		if s[i]!="?":
			if j-benri(int(s[i]),i)>=0:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)]
			else:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)+13]

		else:
			for c in range(10):
				if j-benri(c,i)>=0:
					dp[i+1][j]+=dp[i][j-benri(c,i)]
				else:
					# print(j-c%13+13)
					dp[i+1][j]+=dp[i][j-benri(c,i)+13]

			
			
# print(data)
print(dp[n][5]%(10**9+7))
				


### FIXED CODE ###

S = input()
dp = [[0]*13 for i in range(len(S))]
MOD = 10**9+7
 
if S[0]=='?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(S[0])] = 1
 
for i,c in enumerate(S[1:]):
    for j in range(13):
        if c=='?':
            for k in range(10):
                nj = (j*10 + k) % 13
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
        else:
            nj = (j*10 + int(c)) % 13
            dp[i+1][nj] += dp[i][j]
            dp[i+1][nj] %= MOD
 
print(dp[-1][5])
### BUGGY CODE ###

s = [len(i) for i in input().split("T")]
x,y  = (int(i) for i in input().split())
xl,yl,flag = [],[],False
for i in range(len(s)):
	if i%2==0: xl.append(s[i])
	else: yl.append(s[i])
x,y,xl = abs(x-xl[0]),abs(y),xl[1:]
xs,ys,lenx,leny,xl2,yl2 = sum(xl),sum(yl),len(xl),len(yl),[0],[0]
a,b = [[0 for i in range(xs+1)] for i in range(len(xl)+1)],[[0 for i in range(ys+1)] for i in range(len(yl)+1)]
a[0][0],b[0][0] = 1,1
if xs>=x and (xs-x)%2==0 and ys>=y and (ys-y)%2==0: x2,y2,flag = (xs-x)//2,(ys-y)//2,True
else: print("No")
if flag:
	for i in range(lenx): xl2.append(xl2[-1]+xl[i])
	for i in range(leny): yl2.append(yl2[-1]+yl[i])
	for i in range(lenx):
		for j in range(xl2[i+1]+1):
			if xl[i]<=j: a[i+1][j] = a[i][j-xl[i]] | a[i][j]
			else: a[i+1][j] = a[i][j]
	for i in range(leny):
		for j in range(yl2[i+1]+1):
			if yl[i]<=j: b[i+1][j] = b[i][j-yl[i]] | b[i][j]
			else: b[i+1][j] = b[i][j]
	if a[-1][x2] and b[-1][y2]: print("Yes")
	else: print("No")

### FIXED CODE ###

s = [len(i) for i in input().split("T")]
x,y  = (int(i) for i in input().split())
xl,yl,flag = [],[],False
for i in range(len(s)):
	if i%2==0: xl.append(s[i])
	else: yl.append(s[i])
x,y,xl = abs(x-xl[0]),abs(y),xl[1:]
xs,ys,lenx,leny,xl2,yl2 = sum(xl),sum(yl),len(xl),len(yl),[0],[0]
a,b = [[0 for i in range(xs+1)] for i in range(lenx+1)],[[0 for i in range(ys+1)] for i in range(leny+1)]
a[0][0],b[0][0] = 1,1
if xs>=x and (xs-x)%2==0 and ys>=y and (ys-y)%2==0: x2,y2,flag = (xs-x)//2,(ys-y)//2,True
else: print("No")
if flag:
	for i in range(lenx):
		for j in range(x2+1):
			if xl[i]<=j: a[i+1][j] = a[i][j-xl[i]] | a[i][j]
			else: a[i+1][j] = a[i][j]
	for i in range(leny):
		for j in range(y2+1):
			if yl[i]<=j: b[i+1][j] = b[i][j-yl[i]] | b[i][j]
			else: b[i+1][j] = b[i][j]
	if a[-1][x2] and b[-1][y2]: print("Yes")
	else: print("No")
### BUGGY CODE ###

import sys
from collections import Counter
N = int(input())
S = list(input())
Sc = Counter(S)
R = Sc["R"]
G = Sc["G"]
B = Sc["B"]
if R == 0 or G == 0 or B == 0:
    print(0)
    sys.exit()
else:
    ans = R*G*B
for i in range(1, N//2+2):
    for j in range(N):
        if j+i+i >= N:
            break
        RGB = S[j]+S[j+i]+S[j+i+i]
        if RGB == "RGB" or RGB == "RBG" or RGB == "GRB" or RGB == "GBR" or RGB == "BRG" or RGB == "BGR":
            ans -= 1
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
ans = r*g*b
for x in range(N):
    for a in range(N):
        y = x+a
        z = y+a
        if z >= N:
            continue
        if S[x] == S[y]:
            continue
        if S[y] == S[z]:
            continue
        if S[x] == S[z]:
            continue
        ans = ans-1
print(ans)