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

s = input()
n = int(input())
qs = [list(input().split()) for i in range(n)]
for q in qs:
    if len(q) == 1:
        s = s[::-1]
    else:
        if int(q[1]) == 1:
            s = q[2]+s
        else:
            s = s+q[2]
print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
n = int(input())
qs = [list(input().split()) for i in range(n)]
pre = deque()
suf = deque()
frag = True
for q in qs:
    if len(q) == 1:
        frag = not frag
    else:
        if (frag, q[1]) == (True, "1") or (frag, q[1]) == (False, "2"):
            pre.appendleft(q[2])
        else:
            suf.append(q[2])
if frag is True:
    print("".join(list(pre)+list(s)+list(suf)))
else:
    suf.reverse()
    s.reverse()
    pre.reverse()
    print("".join(list(suf)+list(s)+list(pre)))
### BUGGY CODE ###

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

def is_ok(k):
    length = 0
    mem = {}
    for a in A:
        if a > length:
            length = a
            continue
        dels = []
        for b in mem.keys():
            if b > a:
                dels.append(b)
        while a > 0:
            if a in mem and mem[a] >= k-1:
                dels.append(a)
            else:
                break
            a -= 1
        if a in mem:
            mem[a] += 1
        else:
            mem[a] = 1
        if a == 0 or mem[a] >= k:
            return False
        length = a
        for b in dels:
            del mem[b]
    return True

ng = 0
ok = N
while ok-ng > 1:
    m = (ok+ng+1)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

### FIXED CODE ###

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

def is_ok(k):
    length = 0
    mem = {}
    for a in A:
        if a > length:
            length = a
            continue
        dels = []
        for b in mem.keys():
            if b > a:
                dels.append(b)
        while a > 0:
            if a in mem and mem[a] >= k-1:
                dels.append(a)
            else:
                break
            a -= 1
        if a in mem:
            mem[a] += 1
        else:
            mem[a] = 1
        if a == 0 or mem[a] >= k:
            return False
        length = a
        for b in dels:
            del mem[b]
    return True

ng = 0
ok = N
while ok-ng > 1:
    m = (ok+ng+1)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)
### BUGGY CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

N,Q = [int(x) for x in input().split()]
S = list(input())
lrlist =[]
for _ in range(Q):
    l,r = [int(x) for x in input().split()]
    lrlist.append((l,r))
countls=[]
for x in lrlist:
    count = 0
    Spart = S[x[0]-1:x[1]]
    for i in range(len(Spart)-1):
        if Spart[i] =='A' and Spart[i+1] =='C':
            count+= 1
    countls.append(count)

for _ in range(Q):
    print(countls[_])    

### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

N,Q = [int(x) for x in input().split()]
S = list(input())
lrlist =[]
for _ in range(Q):
    l,r = [int(x) for x in input().split()]
    lrlist.append((l,r))

sumls =[0]*(N+1)
for i in range (N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        sumls[i+1] = sumls[i] + 1
    else:
        sumls[i+1] = sumls[i]

for _ in range (Q):
    l = lrlist[_][0]
    r = lrlist[_][1]
    ans = sumls[r-1]-sumls[l-1]
    print(ans)
### BUGGY CODE ###

# coding: utf-8
MOD = int(1e9 + 7)

def f(N, M, s, t):
    dp = [[0] * M for _ in range(N)]
    cums = [[0] * (M + 1) for _ in range(N + 1)]

    for i in range(N):
        for j in range(M):
            num = 0
            if s[i] == t[j]:
                num = (cums[i][j] + 1) % MOD
            cums[i+1][j+1] = \
                (cums[i+1][j] + cums[i][j+1] + MOD - cums[i][j] + num) % MOD
    return((cums[N][M] + 1) % MOD)

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
print(f(n, m, s, t))


### FIXED CODE ###

# coding: utf-8
MOD = int(1e9 + 7)

def f(N, M, s, t):
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    cums = [[0] * (M + 1) for _ in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(1, M + 1):
            dp[i][j] = 0 if s[i-1] != t[j-1] else (cums[i-1][j-1] + 1) % MOD
            cums[i][j] = cums[i-1][j] + cums[i][j-1] - cums[i-1][j-1] + dp[i][j]
    return((cums[N][M] + 1) % MOD)

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
print(f(n, m, s, t))
### BUGGY CODE ###

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

# print(N)
# print(M)

A = list(map(int, input().split()))
# print(A)

A = sorted(A, reverse=True)
# print(A)

for i in range(M):
    # print(i)
    A[0] = int(A[0] / 2)
    A = sorted(A, reverse=True)
    
print(sum(A))

### FIXED CODE ###

import heapq

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

hq = []
A = list(map(int, input().split()))
for x in A:
    heapq.heappush(hq, -x)
    
# print(hq)

for i in range(M):
    x = heapq.heappop(hq)
    x = int(x / 2)
    # print(x)
    heapq.heappush(hq, x)

# print(hq)
ans = 0
for x in hq:
    ans += -x
print(ans)
### BUGGY CODE ###

from collections import defaultdict

N,Q=map(int,input().split())
l=[ tuple( map(int,input().split()) ) for i in range(N-1) ]
p=[ tuple( map(int,input().split()) ) for i in range(Q) ]
d=defaultdict(list)
for vert,childs in l:
    d[vert].append(childs)


d_2=defaultdict(int)
for i in range(1,N+1):
    d_2[i]=0

for p,x in p:
    d_2[p]+=x

for n in d_2.keys():
    for m in d[n]:
        d_2[m]+=d_2[n]

ans=d_2.values()
print(*ans)

### FIXED CODE ###

from collections import defaultdict

N,Q=map(int,input().split())
l=[ tuple( map(int,input().split()) ) for i in range(N-1) ]
p=[ tuple( map(int,input().split()) ) for i in range(Q) ]
d=defaultdict(list)
for vert,childs in l:
    d[vert].append(childs)


d_2=defaultdict(int)
for i in range(1,N+1):
    d_2[i]=0

for p,x in p:
    d_2[p]+=x

for n in d_2.keys():
    for m in d[n]:
        d_2[m]+=d_2[n]

ans=d_2.values()
print(*ans)
### BUGGY CODE ###

def solve(x, a):
    if len(a) == 0:
        return 0

    if len(a) == 1:
        if a[0] == x:
            return 1
        else:
            return 0

    if x < a[0]:
        return solve(x, a[1:])
    else:
        m = solve(x - a[0], a[1:]) + 1
        n = solve(x, a[1:])
        return max(m, n)

def main():
    n, x = [int(s) for s in input().split()]
    a = [int(s) for s in input().split()]

    print(solve(x, a))

main()


### FIXED CODE ###

def main():
    n, x = [int(s) for s in input().split()]
    a = [int(s) for s in input().split()]
    a.sort()

    cnt = 0
    for i, y in enumerate(a):
        if x < y:
            break
        x -= y
        cnt += 1
    else:
        # distribute to all child
        if x != 0:
            cnt -= 1
    print(cnt)

main()
### BUGGY CODE ###

#!/usr/bin/env python3

import functools

MOD = 1000000007
fact = []

def main():
    h, w, a, b = map(int, input().split())
    init_fact(200000, MOD)
    mp = get_list_middle_points(h, w, a, b)
    res = 0
    for y, x in mp:
        res += count(1, 1, x, y) * count(x, y, w, h)
        res %= MOD
    print(res)

def count(x1, y1, x2, y2):
    dx = abs(x1 - x2)
    dy = abs(y1 - y2)
    count = combi(dx + dy, dx, MOD)
    return count

def get_list_middle_points(h, w, a, b):
    li = []
    y = h - a
    x = b + 1
    while (y >= 1 and x <= w):
        li.append((y, x))
        y -= 1
        x += 1
    return li

def combi(n, k, mod):
    numera = fact[n]
    denomi = (fact[n - k] * fact[k]) % mod
    return (numera * inv(denomi, mod)) % mod

def init_fact(maxn, mod):
    assert len(fact) == 0
    fact.append(1)
    for i in range(1, maxn + 1):
        fact.append((fact[i - 1] * i) % mod)

def inv(n, mod):
    return pow(n, mod - 2, mod)

def pow(n, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 0:
        x = pow(n, p // 2, mod)
        return (x * x) % mod
    else:
        x = pow(n, p - 1, mod)
        return (x * n) % mod

main()


### FIXED CODE ###

#!/usr/bin/env python3
 
import functools
 
MOD = 1000000007
fact = []
 
def main():
    h, w, a, b = map(int, input().split())
    init_fact(200000, MOD)
    mp = get_list_middle_points(h, w, a, b)
    res = 0
    for y, x in mp:
        res += count(1, 1, x, y) * count(x, y, w, h)
        res %= MOD
    print(res)
 
def count(x1, y1, x2, y2):
    dx = abs(x1 - x2)
    dy = abs(y1 - y2)
    count = combi(dx + dy, dx, MOD)
    return count
 
def get_list_middle_points(h, w, a, b):
    li = []
    y = h - a
    x = b + 1
    while (y >= 1 and x <= w):
        li.append((y, x))
        y -= 1
        x += 1
    return li
 
def combi(n, k, mod):
    numera = fact[n]
    denomi = (fact[n - k] * fact[k]) % mod
    return (numera * inv(denomi, mod)) % mod
 
def init_fact(maxn, mod):
    assert len(fact) == 0
    fact.append(1)
    for i in range(1, maxn + 1):
        fact.append((fact[i - 1] * i) % mod)
 
def inv(n, mod):
    return pow(n, mod - 2, mod)
 
def pow(n, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 0:
        x = pow(n, p // 2, mod)
        return (x * x) % mod
    else:
        x = pow(n, p - 1, mod)
        return (x * n) % mod
 
main()
### BUGGY CODE ###

N,K=map(int,input().split())
a=True
while a:
    if abs(N-K)<N:
        N=abs(N-K)
    else:
        a=False
print(N)

### FIXED CODE ###

N,K=map(int,input().split())
N=N%K
ans=min(N,abs(N-K))
print(ans)
### BUGGY CODE ###

N = int(input())

count = 0
for i in range(1, N):
  for j in range(1, N):
    if i * j < N:
      count += 1
    else:
      break
print(count)

### FIXED CODE ###

N = int(input())

count = 0

for i in range(1, N):
  count += int(N / i)
  if N % i == 0:
    count -= 1
print(count)
### BUGGY CODE ###

X,Y,Z,K = 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)
cor = []
for i in range(X):
    for j in range(Y):
        cor.append(A[i]+B[j])

cor.sort(reverse = True)
if K <= X*Y:
    cor = cor[:K]
anslist = []
for i in range(min(K,X*Y)):
    for j in range(Z):
        anslist.append(C[j]+cor[i])
        if len(anslist) == K:
            break

anslist.sort(reverse = True)
for i in range(K):
    print(anslist[i])

### FIXED CODE ###

from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
Mod = 1000000007




def main(): #startline--------------------------------------------
    X,Y,Z,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort(reverse = True)
    A = A[:min(K,X)]
    B = list(map(int,input().split()))
    B.sort(reverse = True)
    B = B[:min(K,X)]
    C = list(map(int,input().split()))
    C.sort(reverse = True)
    C = C[:min(K,X)]
    Pre = []
    for i in range(min(X,K)):
        for j in range(min(Y,K)):
            Pre.append(A[i]+B[j])
    Pre.sort(reverse = True)
    Pre = Pre[:K]
    ans = []
    for i in range(min(Z,K)):
        for j in Pre:
            ans.append(j+C[i])
    ans.sort(reverse = True)
    for i in range(K):
        print(ans[i])



if __name__ == "__main__":
    main() #endline===============================================





def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n < 2 is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))):
        if prime[i] == 1:
            for j in range(2*i,n):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n):
        if prime[i] == 1:
            res.append(i)
    return res

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
### BUGGY CODE ###

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

LL, MM = map(int, input().split())
gate = [LL + i for i in range(MM-LL+1)]

for _ in range(M-1):
    LL, MM = map(int, input().split())
    tmp = [LL + i for i in range(MM-LL+1)]
    gate = list(set(gate) & set(tmp))

print(len(gate))


### FIXED CODE ###

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

min_, max_ = map(int, input().split())

for _ in range(M-1):
    LL, MM = map(int, input().split())
    min_ = max(min_, LL)
    max_ = min(max_, MM)


if min_ <= max_:
    print(max_ - min_ + 1)
else:
    print(0)
### BUGGY CODE ###


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

dp = [[[False] * 1000 for _ in range(4)] for _ in range(N + 1)]
dp[0][0][0] = True
for i in range(N):
    for j in range(4):
        for k in range(1000):
            if not dp[i][j][k]:
                continue

            dp[i + 1][j][k] = dp[i][j][k]
            to = k * 10 + int(S[i])
            if j < 3 and to < 1000:
                dp[i + 1][j + 1][to] = dp[i][j][k]

print(sum(dp[-1][-1]))


### FIXED CODE ###

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

ctr = [0] * 1000
ans = 0
for i in range(1000):
    v1 = i // 100
    v2 = i // 10 - v1 * 10
    v3 = i - v1 * 100 - v2 * 10
    
    p1 = S.find(str(v1))
    if p1 < 0:
        continue
        
    p2 = S[p1+1:].find(str(v2))
    if p2 < 0:
        continue
        
    p3 = S[p1+p2+2:].find(str(v3))
    ans += int(p3 >= 0)
    
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0

for i in range(N):
    for j in range(i, N):
        for k in range(j, N):
            if j - i == k - j:
                continue
            elif len(set([S[i], S[j], S[k]])) == 3:
                ans += 1

print(ans)

### FIXED CODE ###

import collections

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

count = collections.Counter(S)

ans = count['R'] * count['G'] * count['B']

for distance in range(1, (N - 1) // 2 + 1):
    for i in range(N):
        if i + 2 * distance >= N:
            break
        
        if len({S[i], S[i + distance], S[i + 2 * distance]}) == 3:
             ans -= 1
    

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

def main():
  n, k, offset=0, 0, 0
  while k < K:
    if n >= offset and S[n]=='o':
      L.append(n+1)
      k+=1
      offset = n + C + 1
    n+=1
  S_Reversed=S[::-1]
  n, k, offset=0, 0, 0
  while k < K:
    if n >= offset and S_Reversed[n]=='o':
      R.append(N - n)
      k+=1
      offset = n + C + 1
    n+=1
  
  
  for l in L:
    if l in R:
      print(l)

if __name__=='__main__':
  N, K, C=map(int, input().split())
  S = input()
  L,R=[],[]
  main()


### FIXED CODE ###

def main():
  N, K, C=map(int, input().split())
  S = input()

  R=[0]*K
  n, k=N-1, 0
  while k < K:
    if S[n]=='o':
      R[k]=n+1
      k+=1
      n -= C
    n-=1
  R=R[::-1]
  
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      if n+1 == R[k]:
        print(n+1)
      k+=1
      n += C
    n+=1
  #print(L)
  

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

import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = [IL()[::-1] for i in range(N)]

used = [-1]*N
total = N*(N-1)//2
flag = 1
cnt = 0
days = 0
while flag:
  flag = 0
  for i in range(N-1,-1,-1):
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        flag = 1
        cnt += 1
  else:
    if flag == 1:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)

### FIXED CODE ###

import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = [IL()[::-1] for i in range(N)]

used = [-1]*N
updatelist = [i for i in range(N)]
total = N*(N-1)//2
cnt = 0
days = 0
ul = []
while updatelist:
  ul = []
  for i in updatelist:
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        ul.append(i)
        ul.append(numIND)
        cnt += 1
  else:
    updatelist = ul[:]
    if len(ul) != 0:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)
### BUGGY CODE ###

num=int(input())
date=list(map(int,input().split(" ")))
sum=0
for i in range(num):
    for j in range(num-i-1):
        sum+=date[i]*date[i+j+1]
print(sum%(10**9+7))

### FIXED CODE ###

num=int(input())
date=list(map(int,input().split(" ")))
sum0=0
sum1=0
for i in range(num):
    sum0+=date[i]
for i in range(num):
    sum0-=date[i]
    sum1+=date[i]*sum0
print(sum1%(10**9+7))
### BUGGY CODE ###

import math
N = int(input())
L = []
for _ in range(N):
    t, a = map(int, input().split())
    L.append([t, a])

t = 0
a = 0
for i in range(N):
    if i == 0:
        t += L[i][0]
        a += L[i][1]
        continue
    if (L[i][0] >= t and L[i][1] >= a):
        t = L[i][0]
        a = L[i][1]
        continue

    max_ta = max(t, a)
    g = math.gcd(t, a)
    tg, ag = t // g, a // g
    if (L[i][0], L[i][1]) != (tg, ag):
        sum_t, sum_a = L[i][0] * max_ta, L[i][1] * max_ta
        # print(sum_t, sum_a)
        while True:
            sum_t -= L[i][0]
            sum_a -= L[i][1]
            if sum_t < t or sum_a < a:
                sum_t += L[i][0]
                sum_a += L[i][1]
                break
        t = sum_t
        a = sum_a
        continue

print(t + a)


### FIXED CODE ###

import math
N = int(input())

t = 0
a = 0
for i in range(N):
    T, A = map(int, input().split())
    if i == 0:
        t += T
        a += A
        continue
    if (T >= t and A >= a):
        t = T
        a = A
        continue

    max_ta = max(t, a)
    g = math.gcd(t, a)
    tg, ag = t // g, a // g
    if (T, A) != (tg, ag):
        sum_t, sum_a = T * max_ta, A * max_ta
        # print(sum_t, sum_a)

        cout_sn = min((sum_t - t) // T, (sum_a - a) // A)
        # while True:
        sum_t -= T * cout_sn
        sum_a -= A * cout_sn
        # if sum_t < t or sum_a < a:
        #     sum_t += T
        #     sum_a += A
        #     break
        t = sum_t
        a = sum_a
        continue

print(t + a)
### BUGGY CODE ###

# 解法 全探索をする，上から読んでる冊数をi,jとしてKを超えない範囲で最大のものを週つ力すれば良い
# 全探索だったらだめだったN^2になるから
# まずAを最大限選ぶ，次にその時選べる最大のBを選ぶ
N,M,K = map(int,input().split())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
# 累積和
sumb = 0
Bs = [0]*M
for i,b in enumerate(B):
    sumb += B[i]
    Bs[i] = sumb
sum_time=0
max_count = 0
count = 0
# i,jは実際に読んでいる数とする
import bisect
for i in range(N+1):
    count = 0
    if i ==0:
        sum_time=0
    else:
        sum_time=sum(A[:i])
        count += i
    if sum_time>K:
        continue
    ind = bisect.bisect_right(Bs,K-sum_time)
    count += ind
    max_count = max(max_count,count)

print(max_count)

### FIXED CODE ###

# 解法 全探索をする，上から読んでる冊数をi,jとしてKを超えない範囲で最大のものを週つ力すれば良い
# 全探索だったらだめだったN^2になるから
# まずAを最大限選ぶ，次にその時選べる最大のBを選ぶ
N,M,K = map(int,input().split())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
# 累積和
suma = 0
sumb = 0

As = [0]*N
for i,a in enumerate(A):
    suma += A[i]
    As[i] = suma

Bs = [0]*M
for i,b in enumerate(B):
    sumb += B[i]
    Bs[i] = sumb
sum_time=0
max_count = 0
count = 0
# i,jは実際に読んでいる数とする
import bisect
for i in range(N+1):
    count = 0
    if i ==0:
        sum_time=0
    else:
        sum_time=As[i-1]
        count += i
    if sum_time>K:
        continue
    ind = bisect.bisect_right(Bs,K-sum_time)
    count += ind
    max_count = max(max_count,count)

print(max_count)
### BUGGY CODE ###

import heapq


class Work(object):
    def __init__(self, a, b):
        self.a = a
        self.b = b
        self.is_used = False


(n, m) = map(int, input().split())
works = []
for _ in range(n):
    (a, b) = map(int, input().split())
    works.append(Work(a, b))
sorted_works = sorted(works, key=lambda x: x.a)

sum = 0
for i in range(1, m + 1):
    options = []
    for j, work in enumerate(sorted_works):
        if work.a > i:
            break
        if work.is_used:
            continue
        heapq.heappush(options, (-work.b, j))
    if 0 == len(options):
        continue
    target = heapq.heappop(options)
    sum += -1 * target[0]
    sorted_works[target[1]].is_used = True
print(sum)


### FIXED CODE ###

import heapq

(n, m) = map(int, input().split())
jobs = {}
for _ in range(n):
    (a, b) = map(int, input().split())
    if not a in jobs:
        jobs[a] = []
    jobs[a].append(-b)

heap = []
sum = 0
for i in range(1, m + 1):
    if i in jobs:
        for j in jobs[i]:
            heapq.heappush(heap, j)
    if 0 < len(heap):
        sum -= heapq.heappop(heap)
print(sum)
### BUGGY CODE ###

n = int(input())
s = list(input())
ans = 0
r = [0 for i in range(n)]
g = [0 for i in range(n)]
b = [0 for i in range(n)]
for i in range(n):
    if s[i] == "R":
        r[i] += 1
    elif s[i] == "G":
        g[i] += 1
    else:
        b[i] += 1
    if i > 0:
        r[i] += r[i-1]
        g[i] += g[i-1]
        b[i] += b[i-1]
ju = [0,0,0]
ju2 = ["R","G","B"]
for i in range(n-2):
    for j in range(3):
        if s[i] == ju2[j]:
            ju[j] += 1
    for j in range(i+1,n-1):
        #print(ans)
        for k in range(3):
            if s[j] == ju2[k]:
                ju[k] += 1
                key = k
        if ju[key] == 1:
            if ju[0] == 0:
                ans += r[n-1] - r[j]
                if j + (j-i) < n:
                    if r[j+(j-i)] > r[j+(j-i)-1]:
                        ans -= 1
            
            elif ju[1] == 0:
                ans += g[n-1] - g[j]
                if j + (j-i) < n:
                    if g[j+(j-i)] > g[j+(j-i)-1]:
                        ans -= 1
            else:
                ans += b[n-1] - b[j]
                if j + (j-i) < n:
                    if b[j+(j-i)] > b[j+(j-i)-1]:
                        ans -= 1
        ju[key] -= 1
    ju = [0,0,0]
print(ans)
            

### FIXED CODE ###

n = int(input())
s = list(input())
ans = 0
r = [0 for i in range(n)]
g = [0 for i in range(n)]
b = [0 for i in range(n)]
for i in range(n):
    if s[i] == "R":
        r[i] += 1
    elif s[i] == "G":
        g[i] += 1
    else:
        b[i] += 1
    if i > 0:
        r[i] += r[i-1]
        g[i] += g[i-1]
        b[i] += b[i-1]
ju = [0,0,0]
ju2 = ["R","G","B"]
for i in range(n-2):
    for j in range(3):
        if s[i] == ju2[j]:
            ju[j] += 1
    for j in range(i+1,n-1):
        #print(ans)
        for k in range(3):
            if s[j] == ju2[k]:
                ju[k] += 1
                key = k
        if ju[key] == 1:
            if ju[0] == 0:
                ans += r[n-1] - r[j]
                if j + (j-i) < n:
                    if r[j+(j-i)] > r[j+(j-i)-1]:
                        ans -= 1
            
            elif ju[1] == 0:
                ans += g[n-1] - g[j]
                if j + (j-i) < n:
                    if g[j+(j-i)] > g[j+(j-i)-1]:
                        ans -= 1
            else:
                ans += b[n-1] - b[j]
                if j + (j-i) < n:
                    if b[j+(j-i)] > b[j+(j-i)-1]:
                        ans -= 1
        ju[key] -= 1
    ju = [0,0,0]
print(ans)