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

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,q=map(int,input().split())
c=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  c[a].append(b)
  c[b].append(a)
px=[0]*n
for I in range(q):
    p,x=map(int,input().split())
    px[p-1]+=x 
ans=[0]*n
def dfs(g,h=-1):
  ans[g]=ans[h]+px[g]
  for i in c[g]:
    if i==h:
      continue
    dfs(i,g)
dfs(0)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,q=map(int,input().split())
c=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  c[a].append(b)
  c[b].append(a)
px=[0]*n
for I in range(q):
    p,x=map(int,input().split())
    px[p-1]+=x 
ans=[0]*n
def dfs(g,h=-1):
  ans[g]=ans[h]+px[g]
  for i in c[g]:
    if i==h:continue
    dfs(i,g)
dfs(0)
print(*ans)
### BUGGY CODE ###


def main():
    N = int(input())

    A = [tuple(map(int, input().split())) for _ in range(N)]

    # check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
    check = [0] * N #i番目の次の相手のindex

    ans = 0
    i = 0
    tmp = 0
    count = 0
    while tmp < 2 * N + 2:
        if i % N == 0:
            ans += 1
            flag  = [True] * N #試合をしたかどうかチェック
            i = 0
            
        if check[i] >= N - 1 or flag[i] == False:
            i += 1
            tmp += 1
            continue
        b = A[i][check[i]]
        # print (b)
        if A[b - 1][check[b - 1]] - 1 == i and flag[b - 1]: #試合できる時
            check[i] += 1
            check[b - 1] += 1
            flag[i] = False
            flag[b - 1] = False
            tmp = 0
            count += 1
            if count == (N * (N - 1))//2:
                print (ans)
                exit()
        i += 1
        tmp += 1
    print (-1)
    return 
            
if __name__ == '__main__':
    main()


### FIXED CODE ###

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

N = int(input())
A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
B = {i: row for i, row in enumerate(A)}

# print (A)
# print (B)

end = 0

for k in range(8000):
    used = set()
    dels = []
    for i, q in B.items():
        if not q:
            continue
        if i in used:
            continue
        j = q[-1]
        if j in used:
            continue
        if A[j][-1] == i:
            A[j].pop()
            A[i].pop()
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.append(j)
    if not used:
        print (-1)
        exit()
    
    if end == N:
        print (k + 1)
        exit()
    
    for i in dels:
        del B[i]
        
print (N * (N - 1) // 2)
### BUGGY CODE ###

from collections import deque

h,w=map(int,input().split())
S=[]
pos=[]
for i in range(h):
  l=input()
  L=[]
  for j in range(w):
    if l[j]=='.':
      L.append('.')
      pos.append((i,j))
    else:
      L.append('#')
  S.append(L)
      
def bfs(h,w,S,sy,sx,gy,gx):
    maze=[[float('inf')]*w for i in range(h)]
    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que: #キューの中に入っているということはまだ調べる余地有り
        y,x=que.popleft()
        for (i,j) in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if 0<=nexty<=h-1 and 0<=nextx<=w-1:
              dist=maze[nexty][nextx]
              if S[nexty][nextx]!='#':
                if dist>maze[y][x]+1: #今の経路から(nexty,nextx)に進む方が距離が短くなるなら
                    maze[nexty][nextx]=maze[y][x]+1
                    que.append([nexty,nextx])

    return maze[gy][gx]
M=0
for (sy,sx) in pos:
  for (gy,gx) in pos:
    if bfs(h,w,S,sy,sx,gy,gx)>M:
      M=bfs(h,w,S,sy,sx,gy,gx)
      (Sx,Sy)=(sx,sy)
      (Gx,Gy)=(gx,gy)
      
print(M)     


### FIXED CODE ###

from collections import deque

h,w=map(int,input().split())
S=[]
pos=[]
for i in range(h):
  l=input()
  L=[]
  for j in range(w):
    if l[j]=='.':
      L.append('.')
      pos.append((i,j))
    else:
      L.append('#')
  S.append(L)
Maze=[[float('inf')]*w for i in range(h)]
def bfs(h,w,S,Maze,sy,sx):
    maze=Maze
    maze=[[float('inf')]*w for i in range(h)]
    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que: #キューの中に入っているということはまだ調べる余地有り
        y,x=que.popleft()
        for (i,j) in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if 0<=nexty<=h-1 and 0<=nextx<=w-1:
              dist=maze[nexty][nextx]
              if S[nexty][nextx]!='#':
                if dist>maze[y][x]+1: #今の経路から(nexty,nextx)に進む方が距離が短くなるなら
                    maze[nexty][nextx]=maze[y][x]+1
                    que.append([nexty,nextx])
    m=0
    for i in range(h):
      for j in range(w):
        if maze[i][j]!=float('inf'):
          if m<maze[i][j]:
            m=maze[i][j]
            
    return m
        
M=0
for (sy,sx) in pos:
  if bfs(h,w,S,Maze,sy,sx)>M:
    M=bfs(h,w,S,Maze,sy,sx)

print(M)
### BUGGY CODE ###

K=int(input())
number=7
if K%2 == 0 or K%5 == 0:
    print(-1)
else:
    s=1
    while True:
        if number%K == 0:
            print(s)
            break
        else:
            number=int(str(number)+"7")
            s += 1

### FIXED CODE ###

k=int(input())
count=1
num=7
for _ in range(k):
    if num%k == 0:
        print(count)
        break
    else:
        count += 1
        num = (num % k)*10 + 7
else:
    print(-1)
### BUGGY CODE ###

#167
#d
n,k = map(int, input().split())
ln = list(map(int, input().split()))# まちi にいるとき次に町ln[i-1]へいく
visit = [0]*n 
now= 1
visit[0] =1
before =[1]
while max(visit) <= 1:
    now = ln[now -1]
    before.append(now)
    visit[now-1] += 1
roops = before.index(now)
roop_ln = before[roops:-1]
mae = before[:roops]
if k <len(mae):
    print(mae[k])
elif len(mae) <= k :
    t = k- len(mae)
    print(roop_ln[t%len(roop_ln)])

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
pos = 0
visit = [0] * N
move = []
roop = []
while visit[pos]!=2:
    if visit[pos]==0:
        move.append(pos)
    else:
        roop.append(pos)
    visit[pos] += 1
    pos = A[pos] - 1
if len(move)>K:
    print(move[K]+1)
else:
    print(roop[(K-(len(move)-len(roop)))%len(roop)]+1)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
history = []

pos = 0
cnt = 0
while pos not in history and cnt < k:
  history.append(pos)
  pos = a[pos] - 1
  cnt += 1

if cnt == k:
  print(pos + 1)
else:
  cnt_before = history.index(pos)
  print(history[cnt_before + (k - cnt_before) % (cnt - cnt_before)] + 1)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
history = []
mark = set()

pos = 0
cnt = 0
while pos not in mark and cnt < k:
  history.append(pos)
  mark.add(pos)
  pos = a[pos] - 1
  cnt += 1

if cnt == k:
  print(pos + 1)
else:
  cnt_before = history.index(pos)
  print(history[cnt_before + (k - cnt_before) % (cnt - cnt_before)] + 1)
### BUGGY CODE ###

n=int(input())
for i in range(1,n):
    n=n*i
print(n%(pow(10,9)+7))

### FIXED CODE ###

n=int(input())
p=1
for i in range(1,n+1):
    p=p%(pow(10,9)+7)*i
print(p%(pow(10,9)+7))
### BUGGY CODE ###

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

for i in range(N):
    A[i] -= i + 1

min_sum = 10 ** 9 * 2 * 10 ** 5
for i in range(min(A), max(A) + 1):
    summ = 0
    for j in range(N):
        summ += abs(A[j] - i)
    min_sum = min(min_sum, summ)
print(min_sum)


### FIXED CODE ###

import math

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

for i in range(N):
    A[i] -= i + 1

A.sort()
start_index = math.floor(N / 2)

min_sum = 10 ** 9 * 2 * 10 ** 5
for i in range(A[start_index], A[start_index] + 1):
    summ = 0
    for j in range(N):
        summ += abs(A[j] - i)
    min_sum = min(min_sum, summ)
print(min_sum)
### BUGGY CODE ###

def main():
    L, R = map(int, input().split())
    R = min(R, L + 4038)
    ans = 2018

    for i in range(L, R + 2020):
        for j in range(i + 1, R + 1):
            ans = min(ans, (i*j) % 2019)

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    L, R = map(int, input().split())
    R = min(R, L + 4038)
    ans = 2018

    for i in range(L, R + 2020):
        for j in range(i + 1, R + 1):
            ans = min(ans, (i*j) % 2019)

    print(ans)

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

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod


n,a,b =map(int,input().split())
mod = 10**9 +7

total = 2**n -1

total-=comb(n,a,mod)
total-=comb(n,b,mod)


print(total%mod)

### FIXED CODE ###

n,a,b =map(int,input().split())
mod =pow(10,9) +7

def comb(n,x):
    numerator = 1
    for i in range(n-x+1,n+1):
        numerator=  numerator * i  % mod
    
    denominator = 1
    for j in range(1,x+1):
        denominator = denominator * j % mod
    
    d = pow(denominator,mod-2,mod)

    return numerator * d

a = comb(n,a)
b =  comb(n,b)

print( (pow(2,n,mod) - 1  - a - b) %mod)
### BUGGY CODE ###

n = int(input())
ListP =[int(i) for i in input().split()]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i + 1
#print(ListPos2)
ListPos = [0, 0] + [ListPos2[n]] + [n+1, n+1]
for i in reversed(range(1, n)):
	SetPos = set(ListPos)
	SetDiff = set(range(0, ListPos2[i]))
	pos = ListPos.index(min(SetPos - SetDiff))
	ListPos.insert(pos, ListPos2[i])
	#print(SetDiff)
	#print(SetPos-SetDiff)
	#print(pos)
	#print(ListPos)
	low1 = ListPos[pos] - ListPos[pos-1]
	low2 = ListPos[pos-1] - ListPos[pos-2]
	high1 = ListPos[pos+1] - ListPos[pos]
	high2 = ListPos[pos+2] - ListPos[pos+1]
	points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

### FIXED CODE ###

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

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)
### BUGGY CODE ###

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

trees = {}
for _ in range(N - 1):
    id1, id2 = map(int, input().split())
    if id1 not in trees:
        trees[id1] = []
    trees[id1].append(id2)

counters = {}
for _ in range(Q):
    nid, val = map(int, input().split())
    stack = [nid]
    while len(stack) > 0:
        myid = stack.pop()
        if myid not in counters:
            counters[myid] = 0
        counters[myid] += val
        if myid in trees:
            stack.extend(trees[myid])

ret = []
for myid in range(1, N + 1):
    if myid not in counters:
        ret.append(str(0))
    else:
        ret.append(str(counters[myid]))
        
print(' '.join(ret))

### FIXED CODE ###

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

trees = {}
for _ in range(N - 1):
    id1, id2 = map(int, input().split())
    if id1 not in trees:
        trees[id1] = []
    trees[id1].append(id2)

from collections import defaultdict
values = defaultdict(int)
for _ in range(Q):
    nid, val = map(int, input().split())
    values[nid] += val

counters = defaultdict(int)
stack = [[1, 0]] # id, value from parent
while len(stack) > 0:
    myid, parent_val = stack.pop()
    current_val = parent_val + values[myid]
    counters[myid] = current_val
    if myid in trees:
        for cid in trees[myid]:
            stack.append([cid, current_val])

print(' '.join(map(str, [counters[myid] for myid in range(1, N + 1)])))
### BUGGY CODE ###

def main():
    S = input()
    con = 10**9 + 7

    def get_mod(S):
        c = {}
        iii = 1
        for i in range(len(S)):
            if S[len(S) - i - 1] != "?":
                c[i] = {(int(S[len(S) - i - 1]) * iii) % 13: 1}
                iii *= 10
                iii %= 13
                continue
            c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
            iii *= 10
            iii %= 13
        return c
    c = get_mod(S)

    def get_tdp(pdp):
        tdp = {i: 0 for i in range(13)}
        for r in v.keys():
            for _r, _v in pdp.items():
                tdp[(_r + r) % 13] += _v
        for i in range(13):
            tdp[i] %= con
        return tdp

    it = iter(c.items())
    pdp = next(it)[-1]
    for k, v in it:
        pdp = get_tdp(pdp)

    ans = pdp.get(5, 0)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

S = input()
con = 10**9 + 7

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            tdp[(_r + r) % 13] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)
### BUGGY CODE ###

from collections import Counter
import sys

input = sys.stdin.readline

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2:
        return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            app(p)
            n //= p
        p += 2
    if n > 1:
        app(n)
    return Counter(result)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = Counter()
for a in A: lcm |= prime_factorization(a)
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)

### FIXED CODE ###

from collections import Counter

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2:
        return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            app(p)
            n //= p
        p += 2
    if n > 1:
        app(n)
    return Counter(result)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = {}
for a in A:
    for x, y in prime_factorization(a).items():
        if x not in lcm.keys():
            lcm[x] = y
        else:
            lcm[x] = max(lcm[x], y)
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

x, y = map(int,input().split())
p = list(map(int,input().split()))
ans = 0

for i in range(x-y+1):
    z = 0
    for j in range(y):
        z += (p[i+j]+1)/2
    if z > ans:
        ans = z

print(ans)

### FIXED CODE ###

x, y = map(int,input().split())
p = list(map(int,input().split()))
ans = 0

for i in range(x-y+1):
    if i == 0:
        z = sum(p[:y])
    else:
        z = z - n + p[i+y-1]
    n = p[i]
    if z > ans:
        ans = z

print((ans+y)/2)
### BUGGY CODE ###

from itertools import groupby

input()
a = []
r = 0
for k, g in groupby(sorted(map(int, input().split()))):
  try:
    next(x for x in a if k % x == 0)
  except StopIteration:
    a.append(k)
    if len(list(g)) == 1:
      r += 1
print(r)

### FIXED CODE ###

N = 1000001
a = [0]* N
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  for j in range(i + i, N, i):
    if a[i]:
      a[j] = 0
print(a.count(1))
### BUGGY CODE ###

from random import randint, getrandbits
import time
import sys
input = sys.stdin.readline
start = time.time()

def scoring():
    last = [0] * 26
    res = 0
    penalty = 0
    for i in range(D):
        t = out[i]
        res += S[i][t]
        penalty += sc - (i + 1 - last[t]) * C[t]
        res -= penalty
        last[t] = i + 1
    return res

D = int(input())
C = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(D)]
out = [randint(0, 25) for _ in range(D)]
sc = sum(C)
score = scoring()
while time.time() < start + 1.98:
    if getrandbits(1):
        d = randint(0, D - 1)
        q = randint(0, 25)
        old = out[d]
        out[d] = q
        tmp = scoring()
        if tmp > score:
            score = tmp
        else:
            out[d] = old
    else:
        d1 = randint(0, D - 2)
        d2 = randint(d1 + 1, min(d1 + 16, D - 1))
        out[d1], out[d2] = out[d2], out[d1]
        tmp = scoring()
        if tmp > score:
            score = tmp
        else:
            out[d1], out[d2] = out[d2], out[d1]
for i in out:
    print(i + 1)

### FIXED CODE ###

def scoring(d, t):
    arr = [l for l in last]
    arr[t] = d
    return S[d][t] - sum((d - l) * c for l, c in zip(arr, C))

D = int(input())
C = list(map(int, input().split()))
S = []
for _ in range(D):
    s = list(map(int, input().split()))
    S.append(s)
last = [-1] * 26
ans = []
for i in range(D):
    res = -10 ** 6
    idx = -1
    for j in range(26):
        tmp = scoring(i, j)
        if tmp > res:
            res = tmp
            idx = j
    last[idx] = i
    ans.append(idx+1)
print(*ans, sep='\n')
### BUGGY CODE ###

def solve():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    INF=float('inf')
    n,m=map(int,input().split())
    l=[list(map(int,input().split())) for _ in range(m)]
    d=[INF]*n
    nbr=[[] for _ in range(n)]
    used=[False]*m
    for x in l:
        x[0]-=1
        x[1]-=1
    #print(l)
    for i in range(m):
        nbr[l[i][0]].append(i)
        nbr[l[i][1]].append(i)
    #print(nbr)
    def sol(i):
        for x in nbr[i]:
            if used[x]:continue
            used[x]=True
            if l[x][0]==i:
                if d[l[x][1]]==INF:
                    d[l[x][1]]=d[i]+l[x][2]
                elif d[l[x][1]]!=d[i]+l[x][2]:
                    print('No')
                    exit()
                sol(l[x][1])
            else:
                if d[l[x][0]]==INF:
                    d[l[x][0]]=d[i]-l[x][2]
                elif d[l[x][0]]!=d[i]-l[x][2]:
                    print('No')
                    exit()
                sol(l[x][0])
    for i in range(n):
        if d[i]==INF:
            d[i]=0
            sol(i)
    #print(d)
    print('Yes')
solve()

### FIXED CODE ###

def solve():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    INF=float('inf')
    n,m=map(int,input().split())
    l=[list(map(int,input().split())) for _ in range(m)]
    d=[INF]*n
    nbr=[[] for _ in range(n)]
    used=[False]*m
    for x in l:
        x[0]-=1
        x[1]-=1
    #print(l)
    for i in range(m):
        nbr[l[i][0]].append(i)
        nbr[l[i][1]].append(i)
    #print(nbr)
    def sol(i):
        for x in nbr[i]:
            if used[x]:continue
            used[x]=True
            i1=l[x][0]^l[x][1]^i
            dd=d[i]+l[x][2]*(2*(l[x][0]==i)-1)
            if d[i1]!=dd and d[i1]!=INF:
                print('No')
                exit()
            elif d[i1]==INF:
                d[i1]=dd
                sol(i1)
    for i in range(n):
        if d[i]==INF:
            d[i]=0
            sol(i)
    #print(d)
    print('Yes')
solve()
### BUGGY CODE ###

n = int(input())
s = input()
count = 0

r = []
g = []
b = []
for i in range(n):
  if s[i] == 'R':
    r.append(i)
  elif s[i] == 'G':
    g.append(i)
  else:
    b.append(i)
    


for i in range(n):
  if i in r:
    for j in g:
      for k in b:
        if k < j:
          continue
        if 2*j != i+k:
          count += 1
    for j in b:
      for k in g:
        if k < j:
          continue
        if 2*j != i+k:
          count += 1      
  if i in g:
    for j in r:
      for k in b:
        if k < j:
          continue
        if 2*j != i+k:
          count += 1
    for j in b:
      for k in r:
        if k < j:
          continue
        if 2*j != i+k:
          count += 1
  if i in b:
    for j in g:
      for k in r:
        if k < j:
          continue
        if 2*j != i+k:
          count += 1
    for j in r:
      for k in g:
        if k < j:
          continue
        if 2*j != i+k:
          count += 1
  if i in r:
    r = r[1:]
  elif i in g:
    g = g[1:]
  else:
    b = b[1:]

print(count)

### FIXED CODE ###

n = int(input())
s = input()
r = []
g = []
b = []

ans = s.count("R")*s.count("G")*s.count("B")

for i in range(n):
    for j in range(i+1,n):
        k = 2*j-i
        if k>=n:
          break
        ans -= s[k] != s[i] != s[j] != s[k]

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

from collections import deque
N,M=list(map(int,input().split()))
even_list=[list(map(int,input().split())) for _ in range(M)]
#リストVのN番目には頂点Nがあり、そこには頂点Nとつながっている頂点が入っている。
    
#seen[i]は、頂点iを訪問済みの場合はTrue、未訪問の場合はFalse
seen=[False for i in range(N+1)]


count=0
graph=[[] for _ in range(N+1)]
for i in even_list:
    graph[i[0]].append(i[1])
    graph[i[1]].append(i[0])

def StackBFS(s):
    #graphのN番目には頂点Nがあり、そこには頂点Nとつながっている頂点が入っている。
    S=deque([s])
    C=set()
    
    while S:
        v=S.pop()
        seen[v]=True #訪問済みの頂点をTrueにする
        if v not in C:
            C=C|{v}
            for i in graph[v]:
                S.append(i)

for i in range(1,N+1):
    if seen[i]==False:
        StackBFS(i)
        count+=1

print(count)

### FIXED CODE ###

from collections import deque


N,M=list(map(int,input().split()))
graph=[[] for _ in range(N+1)]
for _ in range(M):
    a,b,c=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
#seen[i]は、頂点iを訪問済みの場合はTrue、未訪問の場合はFalse
seen=[False]*(N+1)


count=0

for i in range(1,N+1):
    if seen[i]==False:
        seen[i]=True
        S=deque([i])
        
        while S:
            v=S.popleft()
            #訪問済みの頂点をTrueにする
            for i in graph[v]:
                if seen[i]==False:
                    seen[i]=True
                    S.append(i)
        count+=1

print(count)