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

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

from collections import deque 
s=s0()
n=n0()
q=s2(n)

d=deque("###")

f=False
for a in q:
    if a[0]=="1":
        f=not(f)
        d.reverse()
    else:
        if a[2]=="1":
            d.appendleft(a[4])
        else:
            d.append(a[4])
a,b=(''.join(list(d))).split("###")
print(a+s[::-1]+b if f else a+s+b)

### FIXED CODE ###

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

from collections import deque 
s=s0()
n=n0()
q=s2(n)

d1=deque()
d2=deque()

f=False
for a in q:
    if a[0]=="1":
        f=not(f)
    else:
        if a[2]=="1":
            if f==False:
                d1.appendleft(a[4])
            else:
                d2.append(a[4])                
        else:
            if f==False:
                d2.append(a[4])
            else:
                d1.appendleft(a[4])
ss=''.join(list(d1))+s+''.join(list(d2))
print(ss[::-1] if f else ss)
### BUGGY CODE ###

from fractions import gcd
N = int(input())
TA = [list(map(int, input().split())) for i in range(N)]

ans = 0
pre_t = 0
pre_a = 0

for t, a in TA:
    gcdd = gcd(t, a)

    t = t * gcdd
    a = a * gcdd

    first_t = t
    first_a = a

    while (pre_t > t) or(pre_a > a):
        t += first_t
        a += first_a

    pre_t = t
    pre_a = a

print(t + a)


### FIXED CODE ###

N = int(input())
TA = [list(map(int, input().split())) for i in range(N)]
T, A = 1, 1

for t, a in TA:
    z = max(T//t, A//a)
    if (T > t*z) or (A > a*z):
        z += 1

    T = t * z
    A = a * z

print(T+A)
### BUGGY CODE ###

import sys
import itertools

sys.setrecursionlimit(3 * 10**5)


class Node:
  def __init__(self, tpl):
    self.id = tpl[0] + 1
    self.c = int(tpl[1])
    self.relations = []

  def add_relation(self, node):
    self.relations.append(node)

  def dfs(self, prev_id):
    result = {self.id}
    for node in self.relations:
      if node.id != prev_id:
        result |= node.dfs(self.id)

    return result


def prepare_nodes(n):
  node_dict = {
    node.id: node
    for node in map(Node, enumerate(input().split()))
  }

  for _ in range(n - 1):
    a, b = map(int, input().split())
    node_dict[a].add_relation(node_dict[b])
    node_dict[b].add_relation(node_dict[a])

  return node_dict


def main():
  n = int(input())
  nodes = list(prepare_nodes(n).values())

  paths_dict = {k: set() for k in range(1, n + 1)}

  for node in nodes:
    id_sets = [relation.dfs(node.id) for relation in node.relations]

    paths = {(node.id, node.id)}
    for id_set in id_sets:
      paths |= {tuple(sorted((node.id, id))) for id in id_set}

    cmbs = itertools.combinations(range(len(id_sets)), 2)
    for i, j in cmbs:
      paths |= {
        tuple(sorted((a, b)))
        for a in id_sets[i]
        for b in id_sets[j]
      }

    paths_dict[node.c] |= paths


  for paths in paths_dict.values():
    print(len(paths))


main()


### FIXED CODE ###

import sys
import itertools

sys.setrecursionlimit(3 * 10**5)


class Node:
  def __init__(self, color):
    self.color = int(color) - 1
    self.children = []

  def add_child(self, node):
    self.children.append(node)

  @staticmethod
  def prepare_nodes(n):
    nodes = tuple(map(Node, input().split()))
    for _ in range(n - 1):
      a, b = map(lambda x: int(x) - 1, input().split())
      nodes[a].add_child(nodes[b])
      nodes[b].add_child(nodes[a])

    return nodes


def main():
  n = int(input())
  nodes = Node.prepare_nodes(n)

  dp = [0 for _ in range(n)]
  ans_list = [n*(n + 1) // 2 for _ in range(n)]

  def update_ans(s, color):
    ans_list[color] -= (s + dp[color]) * (s + dp[color] + 1) // 2

  def dfs(s, node, parent):
    color = node.color
    pre_s = s + dp[color]
    for child in node.children:
      if child == parent: continue

      dp[color] = -s
      s = dfs(s, child, node)
      update_ans(s, color)

    s += 1
    dp[color] = pre_s - s

    return s

  s = dfs(0, nodes[0], Node(-1))

  for i in range(n):
    update_ans(s, i)
    print(ans_list[i])


main()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

    ans = -float('inf')
    for n in range(N):
        m = n
        ans_tmp = 0
        for k in range(K):
            nxt = P[m]
            score = C[nxt-1]
            ans_tmp += score
            ans = max(ans, ans_tmp)
            m = nxt-1

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

    ans = -float('inf')
    for n in range(N):
        m = n
        ans_tmp = 0
        cnt = 0
        repeat_flag = False
        for k in range(K):
            nxt = P[m]
            score = C[nxt-1]
            ans_tmp += score
            ans = max(ans, ans_tmp)
            m = nxt-1
            cnt += 1
            if m == n:
                repeat_flag = True
                break
        if not repeat_flag:
            continue
        if K%cnt == 0:
            divK = K//cnt - 1
            r = cnt
        else:
            divK = K//cnt
            r = K%cnt
        if ans_tmp <= 0:
            continue
        repeat_ans_tmp = ans_tmp * divK
        for k in range(r):
            nxt = P[m]
            score = C[nxt-1]
            repeat_ans_tmp += score
            ans = max(ans, repeat_ans_tmp)
            m = nxt-1

    print(ans)


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

import itertools
from collections import Counter

n = int(input())
s = [input() for _ in range(n)]
l = [k for k in range(n)]

count = []
for i in range(n)[::-1]:
    count.append(Counter(s[i]))

ans = 0
for j in itertools.combinations(l, 2):
    if count[j[0]] == count[j[1]]:
        ans += 1

print(ans)


### FIXED CODE ###

n = int(input())

element = {}
count = 0
for i in range(n):
    s = ''.join(sorted(input()))
    if s in element:
        element[s] += 1
        count += element[s]
    else:
        element[s] = 0

print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

n,m,q=MI()
strs=[[[] for i in range(m)] for i in range(n)]
for i in range(m):
    strs[0][i].append(str(i))
#print(strs)
for i in range(n-1):
    for j in range(m):
        for k in range(j,m):
            for s in strs[i][k]:
                strs[i+1][j].append(str(j)+s)
#print(strs)

L=strs[n-1]
#print(L)
lis=[]
for i in range(m):
    for s in L[i]:
        lis.append(s)
#print(lis)
mx=0
zyou=[LI() for i in range(q)]
for u in lis:
    po=0
    for k in range(q):
        a,b,c,d=zyou[k]
        if int(u[b-1])-int(u[a-1])==c:
            po+=d
    if po>mx:
        mx=po
print(mx)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

n,m,q=MI()
strs=[[[] for i in range(m)] for i in range(n)]
for i in range(m):
    strs[0][i].append(str(i))
#print(strs)
for i in range(n-1):
    for j in range(m):
        for k in range(j,m):
            for s in strs[i][k]:
                strs[i+1][j].append(str(j)+s)
#print(strs)

L=strs[n-1]
#print(L)
lis=[]
for i in range(m):
    for s in L[i]:
        lis.append(s)
#print(lis)
mx=0
zyou=[LI() for i in range(q)]
for u in lis:
    po=0
    for k in range(q):
        a,b,c,d=zyou[k]
        if int(u[b-1])-int(u[a-1])==c:
            po+=d
    if po>mx:
        mx=po
print(mx)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

mod = 10**9+7
fact = [1] * (N+1)
fact_inv = [1] * (N+1)
inv = lambda x : pow(x, mod-2, mod)
for i in range(1, N+1):
    fact[i] = i * fact[i-1] % mod
    fact_inv[i] = inv(fact[i])
comb = lambda n, k : fact[n] * fact_inv[k] * fact_inv[n-k] % mod

value = [0] * (N+1)
count = [0] * (N+1)
def dfs1(par, v):
    value[v] = 1
    count[v] = 0
    for u in G[v]:
        if par == u:
            continue
        dfs1(v, u)
        count[v] += count[u]
        value[v] = value[v] * value[u] * comb(count[v], count[u]) % mod
    count[v] += 1

ans = [0] * (N+1)
def dfs2(par, val_par, cnt_par, v):
    val = val_par * value[v] * comb(N-1, cnt_par) % mod
    ans[v] = val
    for u in G[v]:
        if par == u:
            continue
        val2 = val * inv(value[u]) * inv(comb(N-1, count[u])) % mod
        dfs2(v, val2, N-count[u],  u)

dfs1(0, 1)
dfs2(0, 1, 0, 1)

print(*ans[1:], sep='\n')

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x : int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)

mod = 10**9+7
fact = [1] * N
fact_inv = [1] * N
inv = lambda x : pow(x, mod-2, mod)
for i in range(1, N):
    fact[i] = i * fact[i-1] % mod
    fact_inv[i] = inv(fact[i])
comb = lambda n, k : fact[n] * fact_inv[k] * fact_inv[n-k] % mod

value = [1] * N
count = [0] * N
def dfs(par, v):
    for u in G[v]:
        if par == u:
            continue
        dfs(v, u)
        count[v] += count[u]
        value[v] = value[v] * value[u] * comb(count[v], count[u]) % mod
    count[v] += 1

ans = [0] * N
def reroot(par, val_par, cnt_par, v):
    ans[v] = val_par * value[v] * comb(N-1, cnt_par) % mod
    for u in G[v]:
        if par == u:
            continue
        val = ans[v] * inv(value[u] * comb(N-1, count[u])) % mod
        reroot(v, val, N-count[u],  u)

dfs(-1, 0)
reroot(-1, 1, 0, 0)
print(*ans, sep='\n')
### BUGGY CODE ###

from collections import deque


H, W = map(int, input().split())
A = [input() for _ in range(H)]
m = [[3000] * W for _ in range(H)]


def bfs(i, j):
    queue = deque()
    queue.append((i, j))
    while queue:
        p, q = queue.popleft()
        if 0 < p and A[p - 1][q] == '.' and m[p - 1][q] > m[p][q] + 1:
            m[p - 1][q] = m[p][q] + 1
            queue.append((p - 1, q))
        if 0 < q and A[p][q - 1] == '.' and m[p][q - 1] > m[p][q] + 1:
            m[p][q - 1] = m[p][q] + 1
            queue.append((p, q - 1))
        if p < H - 1 and A[p + 1][q] == '.' and m[p + 1][q] > m[p][q] + 1:
            m[p + 1][q] = m[p][q] + 1
            queue.append((p + 1, q))
        if q < W - 1 and A[p][q + 1] == '.' and m[p][q + 1] > m[p][q] + 1:
            m[p][q + 1] = m[p][q] + 1
            queue.append((p, q + 1))


for i, s in enumerate(A):
    for j, c in enumerate(s):
        if c == '#':
            m[i][j] = 0
            bfs(i, j)
_max = 0
for r in m:
    _max = max(_max, max(r))
print(_max)


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
m = [[0 if c == '#' else 3000 for c in input()] for _ in range(H)]
queue = deque()
for i, r in enumerate(m):
    for j, n in enumerate(r):
        if n == 0:
            queue.append((i, j))
while queue:
    p, q = queue.popleft()
    if 0 < p and m[p - 1][q] > m[p][q] + 1:
        m[p - 1][q] = m[p][q] + 1
        queue.append((p - 1, q))
    if 0 < q and m[p][q - 1] > m[p][q] + 1:
        m[p][q - 1] = m[p][q] + 1
        queue.append((p, q - 1))
    if p < H - 1 and m[p + 1][q] > m[p][q] + 1:
        m[p + 1][q] = m[p][q] + 1
        queue.append((p + 1, q))
    if q < W - 1 and m[p][q + 1] > m[p][q] + 1:
        m[p][q + 1] = m[p][q] + 1
        queue.append((p, q + 1))
_max = 0
for r in m:
    _max = max(_max, max(r))
print(_max)
### BUGGY CODE ###

N,M=map(int,input().split())
list1=list(map(int,input().split()))
list2=[1]
for _ in range(M):
  B,C=map(int,input().split())
  if C>=min(list2):
    list2+=[C]*B
    list2.sort(reverse=True)
    list2=list2[:N]
list3=list1+list2
list3.sort(reverse=True)
list5=list3[:N]
SUM=sum(list5)
print(SUM)

### FIXED CODE ###

N,M = map(int, input().split())
listA = list(map(int, input().split()))
listA.sort()
 
listBC = [list(map(int, input().split())) for i in range(M)]
listBC = sorted(listBC, key=lambda x: x[1], reverse=True)
countB = 0
 
for i in range(M):
  B, C = listBC[i][0], listBC[i][1]
  listA += [C]*B
  countB += B
  if countB >= N:
    break

listA.sort(reverse=True)
print(sum(listA[:N]))
### BUGGY CODE ###

import math
N,M = list(map(int,input().split()))
a = [-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
b = []
c = []
fac_N =[1]
ans = 1
for i in range(M+1):
    b.append(a[i+1]-a[i]-2)
for i in range(1,max(b)+1):
    fac_N.append(fac_N[-1]*i)
 
 
for i in range(len(b)):
    counter= 0
    for num2 in range(b[i]//2+1):
        bi = b[i]-2*num2
        counter += fac_N[num2+bi]//fac_N[num2]//fac_N[bi]
    ans*=counter%1000000007
print(ans%1000000007)


### FIXED CODE ###

n,m = map(int,input().split())
a = [ int(input()) for _ in range(m)]
M=10**9+7
lis = [1] + [0]*n

for i in a:
  lis[i]=-1
lis[1] += 1
for i in range(n-1):
  if lis[i+2]<0:
    lis[i+2]= 0
  else:
    lis[i+2] = (lis[i+1] + lis[i])%M
print(lis[n])
### BUGGY CODE ###

import sys
from itertools import combinations
input = sys.stdin.readline

def main():
    h, w, n = map(int, input().split())
    grid = [0]*n
    mod = 10**9
    for i in range(n):
        a, b = map(int, input().split())
        grid[i] = a*mod+b
    
    ans = [0]*10
    already = dict()
    key = 0
    for value in combinations(grid, r=1):
        a, b = divmod(value[0], mod)
        for i in range(-1, 2):
            for j in range(-1, 2):
                if  a+i <= 1 or a+i >= h or b+j <= 1 or b+j >= w:
                    continue
                if (a+i, b+j) in already:
                    continue
                already[(a+i, b+j)] = 1
                key += 1
                count = 0
                for p in range(-1, 2):
                    for q in range(-1, 2):
                        if (a+i+p)*mod+b+j+q in grid:
                            count += 1
                ans[count] += 1
    
    for i in range(10):
        if i == 0:
            print((h-2)*(w-2)-key+ans[0])
            continue
        print(ans[i])

    
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from itertools import combinations
input = sys.stdin.readline

def main():
    h, w, n = map(int, input().split())
    grid = [0]*n
    mod = 10**9
    judge = dict()
    for _ in range(n):
        a, b = map(int, input().split())
        for i in range(-1, 2):
            for j in range(-1, 2):
                if a+i <= 1 or a+i >= h or b+j <= 1 or b+j >= w:
                    continue
                if (a+i, b+j) in judge:
                    judge[(a+i, b+j)] += 1
                else:
                    judge[(a+i, b+j)] = 1
   
    ans = [0]*10
    
    for v in judge.values():
        ans[v] += 1
    ans[0] = (h-2)*(w-2)-sum(ans[1:])
    
    for a in ans:
        print(a)

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

s = input()
n = len(s)

count=0

for i in range(n):
    for j in range(i+1,n+1):
        if int(s[i:j])%2019==0:
            count+=1

print(count)

### FIXED CODE ###

import collections
s = input()
u = collections.deque([0])
for i in range(len(s)):
    u.append((u[i]+int(s[-i-1])*10**(i%224))%2019)
u2 = collections.Counter(u)
sum = 0
for i in u2.values():
    sum += i*(i-1)/2
print(int(sum))
### BUGGY CODE ###

def try_int(s):
    try:
        return int(s)
    except:
        return s

s = input()
nq = int(input())
flg = 0
for i in range(nq):
    q = [try_int(p) for p in input().split()]

    if len(q) == 1:
        flg += 1
    else:
        if flg % 2 == 0:
            if q[1] == 1:
                s = q[2]+s
            else:
                s = s+q[2]
        else:
            if q[1] == 1:
                s = s+q[2]
            else:
                s = q[2]+s
if flg % 2 == 1:
    s = s[::-1]
print(s)

### FIXED CODE ###

from sys import stdin
 
def main():
    S = list(stdin.readline().rstrip())
    Q = int(input())
    rev = 0
    head = []
    tail = []
 
    for _ in range(Q):
        q = stdin.readline()
        if q[0] == "1":
            rev = (rev+1)%2
        else:
            if q[2] == "1":
                if rev == 0:
                    head.append(q[4])
                else:
                    tail.append(q[4])
            else:
                if rev ==0:
                    tail.append(q[4])
                else:
                    head.append(q[4])
 
    if rev == 0:
        ans = "".join(head[::-1] + S + tail)
    else:
        ans = "".join(tail[::-1] + S[::-1] + head)
    
    print(ans)
    
main()
### BUGGY CODE ###

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

counter = 0

for a in A:
    for b in B:
        if a < b:
            for c in C:
                if b < c:
                    counter = counter + 1
                else:
                    pass
        else:
            pass

print(counter)


### FIXED CODE ###

import bisect

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

A = sorted(A)
C = sorted(C)

counter = 0

for k in range(N):
    i = bisect.bisect_left(A, B[k])
    j = N - bisect.bisect_right(C, B[k])
    counter += i * j

print(counter)
### BUGGY CODE ###

M = 1046527
def h1(key):
    return key % M

def h2(key):
    return 1 + (key %(M-1))

def h3(key, i):
    return (h1(key) + i*h2(key)) % M

word_dic = {'A': 1, 'T': 2, 'G': 3, 'C': 4}
def getkey(text):
    sum = 0
    p = 1
    for c in text:
        sum += p*word_dic[c]
        p *= 5
    return sum

dict = {}
def find(text):
    global dict
    key = getkey(text)
    i = 0
    while i < M:
        h = h3(key, i)
        if dict.get(h) == None:
            break
        elif dict[h] == text:
            return True
        i += 1
    return False

def insert(text):
    global dict
    key = getkey(text)
    i = 0
    while i < M:
        j = h3(key, i)
        if dict.get(j) == None:
            dict[j] = text
            break
        else:
            i += 1

n = int(input())
for i in range(n):
    op, text = input().split(' ')
    if op == 'insert':
        insert(text)
    elif op == 'find':
        rst = find(text)
        if rst:
            print('yes')
        else:
            print('no')


### FIXED CODE ###

import sys

M = 1046527
def h1(key):
    return key % M

def h2(key):
    return 1 + (key %(M-1))

def h3(key, i):
    return (h1(key) + i*h2(key)) % M

word_dic = {'A': 1, 'T': 2, 'G': 3, 'C': 4}
def getkey(text):
    sum = 0
    p = 1
    for c in text:
        sum += p*word_dic[c]
        p *= 5
    return sum

dict = [None for i in range(M)]
def find(text):
    key = getkey(text)
    i = 0
    while i < M:
        h = h3(key, i)
        if dict[h] == None:
            break
        elif dict[h] == text:
            return True
        i += 1
    return False

def insert(text):

    key = getkey(text)
    i = 0
    while i < M:
        j = h3(key, i)
        if dict[j] == None:
            dict[j] = text
            break
        else:
            i += 1

n = int(input())
operations = sys.stdin.readlines()
for ope in operations:
    op, text = ope.rstrip().split(' ')
    if op == 'insert':
        insert(text)
    elif op == 'find':
        rst = find(text)
        if rst:
            print('yes')
        else:
            print('no')
### BUGGY CODE ###

a = list(map(int,input().split(" ")))
b = list(map(int,input().split(" ")))
c = list(map(int,input().split(" ")))
bs = sorted(b)
cs = sorted(c)

x = 0

f = range(a[0])
g = range(a[1])

for i in range(a[0]):
    for ii in range(i,a[0]):
        for j in range(a[1]):
            for jj in range(j,a[1]):
                x = x + ((bs[ii] - bs[i]) * (cs[jj] - cs[j]))
                if x > (10**9 + 7):
                    x = x % (10**9 + 7)

ans = x

print(ans)

### FIXED CODE ###

a = list(map(int,input().split(" ")))
b = list(map(int,input().split(" ")))
c = list(map(int,input().split(" ")))

x = 0
y = 0

for i in range(1,a[0]):
    x = x + b[i] - b[0]
    
xx = x
for i in range(1,a[0]-1):
    xx = xx - ((b[i] - b[i - 1]) * (a[0] - i))
    x = x + xx

for i in range(1,a[1]):
    y = y + c[i] - c[0]
    
yy = y
for i in range(1,a[1]-1):
    yy = yy - ((c[i] - c[i - 1]) * (a[1] - i))
    y = y + yy

ans = x * y
ans = ans % (10**9 + 7)

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

N=int(input())
S=input()
ans=S.count("R")*S.count("G")*S.count("B")

for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if j-i==k-j and S[j]!=S[i] and S[j]!=S[k] and S[k]!=S[i]:
        ans-=1
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
ans=S.count("R")*S.count("G")*S.count("B")

for i in range(N):
  for j in range(i+1,N):
    k=j+(j-i)
    if k<=N-1:
      if S[j]!=S[i] and S[j]!=S[k] and S[k]!=S[i]:
          ans-=1
print(ans)
### BUGGY CODE ###

from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*k)%2019
      k*=10
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

if __name__ == '__main__':
  main()


### FIXED CODE ###

from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*k)%2019
      k*=10
      k=k%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

if __name__ == '__main__':
  main()