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

import itertools
def f(a, b):
    return max(len(str(a)), len(str(b)))
def p(n):
    l = []
    a, b = 0, 2
    while b * b <= n:
        if n % b == 0:
            n //= b
            l += [b]
        else:
            b += 1 + a
            a = 1
    if n > 1 : l += [n]
    return l

def main():
    N = int(input())
    l = p(N)
    if len(l) < 2:
        print(f(N, 1))
    else:
        w = len(l)
        ans = len(str(N))
        for i in itertools.product([0, 1], repeat=w):
            a = b = 1
            for j in range(w):
                if i[j] == 0:
                    a *= l[j]
                else:
                    b *= l[j]
            ans = min(ans, f(a, b))
        print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools
def f(a, b):
    return max(len(str(a)), len(str(b)))
def p(n):
    l = []
    a, b = 0, 2
    while b * b <= n:
        if n % b == 0:
            n //= b
            l += [b]
        else:
            b += 1 + a
            a = 1
    if n > 1 : l += [n]
    return l

def main():
    N = int(input())
    l = p(N)
    if len(l) < 2:
        print(f(N, 1))
    else:
        w = len(l)
        ans = len(str(N))
        for i in itertools.product([0, 1], repeat=w):
            a = b = 1
            for j in range(w):
                if i[j] == 0:
                    a *= l[j]
                else:
                    b *= l[j]
            ans = min(ans, f(a, b))
        print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

L,R = map(int,input().split())

if L-R > 672:
    print(0)
else:
    minMod = 100000000
    for i in range(L,R):
        for j in range(i+1,R+1):
            tmp = (i*j)%2019
            if minMod > tmp:
                minMod = tmp
    print(minMod)


### FIXED CODE ###

L,R = map(int,input().split())

if R-L > 672:
    print(0)
else:
    minMod = 2019
    for i in range(L,R):
        for j in range(i+1,R+1):
            tmp = (i*j)%2019
            if tmp == 0:
                minMod = 0
                break
            minMod = min(tmp,minMod)
    print(minMod)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
l = [1,a[0]]
tp = a[0]-1
while True:  
  if a[tp] not in l: 
    l.append(a[tp])
    tp = a[tp] -1
  else:
    l.append(a[tp])
    break
    
last = l[-1]

loop = len(l[l.index(last):-1])
first = len(l[:l.index(last)])
if len(l)>k:
  print(l[k])
  exit()
k -=first
k %=loop
if k==0:
  k+=loop
print(l[k+first])

### FIXED CODE ###

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

for i in range(n):
  l.append(a[l[i]-1])
p = l.index(l[n])
#print(p,l[n])
if k<=n:
  print(l[k])
else:
  x = (k-n+1)%(n-p)
  if x ==0:
    x += (n-p)
    print(l[x-1])
  else:
    print(l[x+p-1])
### BUGGY CODE ###

N = int(input())
A = input().split(' ')

c = {}
for i in range(N):
    c.update({str(A[i]): i + 1})

res = ''

for i in range(1, N + 1):
    res = res + str(c[str(i)]) + ' '

print(res.strip())


### FIXED CODE ###

N = int(input())
A = input().split(' ')

t = []
for i in range(N):
    t.append(0)

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

print(' '.join(t))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().strip().split())
hs = list(map(int, input().strip().split()))

dp = [0] * n

for i in range(1, n):
    min_cost = 1e19
    for j in range(1, min(k + 1, i + 1)):
        cost = dp[i - j] + abs(hs[i] - hs[i - j])
        min_cost = min(cost, min_cost)
    dp[i] = min_cost

print(dp[n - 1])


### FIXED CODE ###

n, k = map(int, input().strip().split())
hs = list(map(int, input().strip().split()))

dp = [0] * n

for i in range(1, n):
    costs = []
    for j in range(1, k + 1):
        if i - j >= 0:
            cost = dp[i - j] + abs(hs[i] - hs[i - j])
            costs.append(cost)
    dp[i] = min(costs)

print(dp[n - 1])
### BUGGY CODE ###

#G
import pprint
H,W,K=map(int,input().split())
import copy
x1,y1,x2,y2=map(int,input().split())
#raw=["#"]+["."]*(601)+["#"]
lastraw=["@"]*(W+2)
field=[["@"]*(W+2)]
for i in range(H):
  field.append(["@"]+list(input())+["@"])

field.append(lastraw)

#print(field)

goal_point=(y2,x2)

[sy,sx]=[y1,x1]
[gy,gx]=[y2,x2]

field[x1][y1]=0
queue=[[sy,sx]]
tests = ((-1,0),(0, 1),(1, 0),(0, -1))
moves=0

while True:
  if len(queue)==0:
    moves=-1
    break
  queue_next = []
  moves += 1
  #pprint.pprint(field)
  for y, x in queue:
    for ny, nx in tests:
      ty, tx = y + ny, x + nx
      if field[tx][ty] == '.' or field[tx][ty] ==moves:
        field[tx][ty] = moves
        queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            k=0
          else:
            break
      elif field[tx][ty] ==moves:
        #field[tx][ty] = moves
        #queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            pass
          else:
            break
  queue = queue_next
  if goal_point in queue:
    break
#pprint.pprint(field)
print(moves)

### FIXED CODE ###

#G
import pprint
H,W,K=map(int,input().split())
import copy
x1,y1,x2,y2=map(int,input().split())
#raw=["#"]+["."]*(601)+["#"]
lastraw=["@"]*(W+2)
field=[["@"]*(W+2)]
for i in range(H):
  field.append(["@"]+list(input())+["@"])

field.append(lastraw)

#print(field)

goal_point=(y2,x2)

[sy,sx]=[y1,x1]
[gy,gx]=[y2,x2]

field[x1][y1]=0
queue=[[sy,sx]]
tests = ((-1,0),(0, 1),(1, 0),(0, -1))
moves=0

while True:
  if len(queue)==0:
    moves=-1
    break
  queue_next = []
  moves += 1
  #pprint.pprint(field)
  for y, x in queue:
    for ny, nx in tests:
      ty, tx = y + ny, x + nx
      if field[tx][ty] == '.':
        field[tx][ty] = moves
        queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            pass
          else:
            break
      elif field[tx][ty] ==moves:
        #field[tx][ty] = moves
        #queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            pass
          else:
            break
  queue = queue_next
  if goal_point in queue:
    break
#pprint.pprint(field)
print(moves)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp=[0]+[1000000000]*(n-1)

for i in range(1,n):
    for j in range(1,k+1):
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))

print(dp[-1])


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp=[0]+[1000000000]*(n-1)

for i in range(1,n):
    for j in range(1,k+1):
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))

print(dp[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(K):

    g = defaultdict(dict)
    for i in range(1, K+1):
        g[i % K][(i+1) % K] = 1
        g[i % K][(i*10) % K] = 0

    q = [(1, 0)]
    vis = {}
    while q:
        # print(len(q))
        u, cc = q.pop(0)
        if u == 0:
            return cc + 1
        vis[u] = True
        for v, c in g[u].items():
            if v in vis:
                continue
            if c == 0:
                q.insert(0, (v, cc))
            else:
                q.append((v, cc+c))


def main():
    K = read_int()
    print(slv(K))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(K):

    g = defaultdict(dict)
    for i in range(1, K+1):
        g[i % K][(i+1) % K] = 1
        g[i % K][(i*10) % K] = 0

    q = deque()
    q.append((1, 0))

    vis = {}
    while q:
        u, cc = q.popleft()
        if u == 0:
            return cc + 1
        vis[u] = True
        for v, c in g[u].items():
            if v in vis:
                continue
            if c == 0:
                q.appendleft((v, cc))
            else:
                q.append((v, cc+c))


def main():
    K = read_int()
    print(slv(K))


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

arr = input().split(" ")
N = int(arr[0])
K = int(arr[1])

input_arr = input().split(" ")
arr = []


max = 0
tmp = 0
for i in range(N):
    pi = int(input_arr[i])
    ex = (1+pi)/2
    arr.append(ex)
    tmp += ex
    if(i >= K-1):
        if(max <= tmp):
            max = tmp
        tmp -= arr[0]
        arr.pop(0)

print(max)


### FIXED CODE ###

arr = input().split(" ")
N = int(arr[0])
K = int(arr[1])

input_arr = input().split(" ")
arr = []


max = 0
tmp = 0
if(K > 1):
    for i in range(N):
        pi = int(input_arr[i])
        ex = (1+pi)/2
        arr.append(ex)
        tmp += ex
        if(i >= K-1):
            if(max <= tmp):
                max = tmp
            tmp -= arr[i-K+1]
else:
    for i in range(N):
        pi = int(input_arr[i])
        ex = (1+pi)/2
        if(ex > max):
            max = ex
print(max)
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
s = 0
for i in range(M):
  b, c = map(int, input().split())
  A += [c for j in range(b)]
  s += b
heapq.heapify(A)
for i in range(s):
  heapq.heappop(A)
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
exc = []

for i in range(M):
  exc.append(list(map(int, input().split())))
exc.sort(key=lambda x: x[1], reverse=True)
e = []
count = 0
for i in range(M):
  e += [exc[i][1]] * exc[i][0]
  count += exc[i][0]
  if count >= N:
    break
cards = sorted(A+e, reverse=True)
print(sum(cards[:N]))
### BUGGY CODE ###

import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))

    dist = [[float('inf')] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        dist[a-1][b-1] = dist[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = dist[i][j] if dist[i][j] < dist[i][k] + dist[k][j] else dist[i][k] + dist[k][j]

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i] - 1
            b = r[i+1] - 1
            move += dist[a][b]
        ans = ans if ans < move else move

    print(ans)

main()


### FIXED CODE ###

import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf')] * (N + 1) for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
        dist[a][a] = dist[b][b] = 0
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
        ans = min(ans, move)

    print(ans)

main()
### BUGGY CODE ###

s = str(input())

n = len(s)
dp = [[0]*13 for i in range(n)]
      
for i in range(n):
  if i != 0:
    if s[i] == '?':
      for k in range(10):
        for j in range(13):
          x = (j+k*10**(n-1-i))%13
          dp[i][x] += dp[i-1][j]
    else:
      for j in range(13):
        x = (j+int(s[i])*10**(n-1-i))%13
        dp[i][x] += dp[i-1][j]
  else:
    if s[i] == '?':
      for k in range(10):
        x = (k*10**(n-1-i))%13
        dp[i][x] += 1
    else:
      x = (int(s[i])*10**(n-1-i))%13
      dp[i][x] += 1

print(dp[-1][5]%(10**9+7))    

  

### FIXED CODE ###

import itertools
 
s = str(input())
 
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1

M = 1
INF = 10 ** 9 + 7
      
for i in range(n):
  if s[n-1-i] == '?':
    for k, j in itertools.product(range(10), range(13)):
      x = (j+k*M)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  else:
    for j in range(13):
      x = (j+int(s[n-1-i])*M)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  M = (M*10)%13

print(dp[-1][5])
#print(dp[-1][5]%(10**9+7))
#print(dp)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

n= int(input())
a=list(input())

v=a.count('1')

ans=[0]*n
A=[0]*n
# n以下の残り回数を記録
for i in range(n):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(19):
            if (x>>j)&1:
                r+=1
        x=x%r
    ans[i]=cnt

# 各桁をv＋１で割ったあまり
q = [0]*n
# 各桁をv-1で割ったあまり
r = [0]*n
for i in range(n):
    if a[i]=='1':
        if v!=0:
            q[i] = pow(2, n-i-1) % (v + 1)
        if v!=1:
            r[i] += pow(2, n-i-1) % (v - 1)
qq=sum(q)
rr=sum(r)

for i in range(n):
    if a[i]=='1':
        if v!=1:
            z = rr - pow(2,n-i-1)%(v-1)
            cnt = z % (v - 1)
            A[i] = 1 + ans[cnt]
    else:
        z=qq+pow(2,n-i-1)%(v+1)
        cnt=z%(v+1)
        A[i]=1+ans[cnt]

for i in A:
    print(i)

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

n= int(input())
a=list(input())

v=a.count('1')

ans=[0]*n
A=[0]*n
# n以下の残り回数を記録
for i in range(n):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(19):
            if (x>>j)&1:
                r+=1
            if x>>j==0:
                break
        x=x%r
    ans[i]=cnt

# 各桁をv＋１で割ったあまり
q = [0]*n
# 各桁をv-1で割ったあまり
r = [0]*n
for i in range(n):
    if a[i]=='1':
        if v!=0:
            q[i] = pow(2, n-i-1,v+1) 
        if v!=1:
            r[i] += pow(2, n-i-1,v-1) 
qq=sum(q)
rr=sum(r)

for i in range(n):
    if a[i]=='1':
        if v!=1:
            z = rr - pow(2,n-i-1,v-1)
            cnt = z % (v - 1)
            A[i] = 1 + ans[cnt]
    else:
        z=qq+pow(2,n-i-1,v+1)
        cnt=z%(v+1)
        A[i]=1+ans[cnt]

for i in A:
    print(i)
### BUGGY CODE ###

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

cnt = 0
for i in range(1000):
    key = str(i).zfill(3)
    ki = 0
    for j in range(N):
        if key[ki] == S[j]: ki += 1
        if ki == 3:
            cnt += 1
            break

print(cnt)


### FIXED CODE ###

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

cnt = 0
for i in range(1000):
    key = str(i).zfill(3)
    ki = 0
    for j in range(N):
        if key[ki] == S[j]: ki += 1
        if ki == 3:
            cnt += 1
            break

print(cnt)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
  for j in range(i+1,n):
    ans=(ans+a[i]*a[j])%(10**9+7)
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
wa=sum(a)
for i in range(n):
  wa-=a[i]
  ans=(ans+(wa*a[i]))%(10**9+7)
print(ans)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

S = input()
T = input()
ls = len(S)
lt = len(T)
dp = [['' for _ in range(lt+5)] for i in range(ls+5)]
for i in range(ls):
    for j in range(lt):
        if S[i] == T[j]:
            if len(dp[i][j])+1 == max(len(dp[i][j])+1, len(dp[i+1][j]), len(dp[i][j+1])):
                dp[i+1][j+1] = dp[i][j] + S[i]
            elif len(dp[i+1][j]) == max(len(dp[i][j]+1), len(dp[i+1][j]), len(dp[i][j+1])):
                dp[i+1][j+1] = dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]
        else:
            if len(dp[i+1][j]) == max(len(dp[i+1][j]), len(dp[i][j+1])):
                dp[i+1][j+1] = dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]
print(dp[ls][lt])

### FIXED CODE ###

from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

S = input()
T = input()
ls = len(S)
lt = len(T)
dp = [[0 for _ in range(lt+5)] for i in range(ls+5)]
#最大値を求める
for i in range(ls):
    for j in range(lt):
        if S[i] == T[j]:
            dp[i+1][j+1] = max(dp[i][j]+1, dp[i+1][j], dp[i][j+1])
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

#復元部分
i = ls
j = lt
ans = ''
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        ans = S[i-1] + ans
        i -= 1
        j -= 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        # for j in range(1, max_capacity + 1):
        #     if w <= j:
        #         dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
        #     else:
        #         dp[i][j] = dp[i - 1][j]
    return dp[max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


### FIXED CODE ###

# DP
def main():
    N, W = map(int, input().split())

    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))


main()
### BUGGY CODE ###

a=int(input())
moji=input()
r=[]
g=[]
b=[]
for i in range(a):
    if moji[i]=="R":
        r.append(i)
    elif moji[i]=="G":
        g.append(i)
    else:
        b.append(i)
res=len(r)*len(g)*len(b)
if len(r)==0 or len(g)==0 or len(b)==0:
    print(0)
else:
    min_len={0:r,1:g,2:b}
    if len(min_len[0])>len(min_len[1]):
        tmp=min_len[0]
        min_len[0]=min_len[1]
        min_len[1]=tmp
    if len(min_len[1])>len(min_len[2]):
        tmp=min_len[1]
        min_len[1]=min_len[2]
        min_len[2]=tmp
    if len(min_len[0])>len(min_len[1]):
        tmp=min_len[0]
        min_len[0]=min_len[1]
        min_len[1]=tmp
    a1=[]
    for i in range(3):
        a1.append(min_len[i])
    I=a1[0]
    J=a1[1]
    K=a1[2]
    for i in I:
        for j in J:
            dif=abs(i-j)
            min_i_j=min(i,j)
            max_i_j=max(i,j)
            if -dif+min_i_j in K:
                res-=1
            if dif+max_i_j in K:
                res-=1
            if dif%2==0 and  int(dif/2)+min_i_j in K:
                res-=1
    print(res)

### FIXED CODE ###

a=int(input())
moji=input()
r=[]
g=[]
b=[]
for i in range(a):
    if moji[i]=="R":
        r.append(i)
    elif moji[i]=="G":
        g.append(i)
    else:
        b.append(i)
res=len(r)*len(g)*len(b)
if len(r)==0 or len(g)==0 or len(b)==0:
    print(0)
else:
    for i in range(0,a-2):
      for j in range(i+1,a-1):
        if 2*j-i<a and moji[i]!=moji[j] and moji[j]!=moji[2*j-i] and moji[2*j-i]!=moji[i]:
          res-=1
    print(res)
### BUGGY CODE ###

from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1 for _ in range(Q)]
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    for i, ans in enumerate(time[left:right]):
        if ans == -1:
            time[i+left] = x

for t in time:
    print(t)


### FIXED CODE ###

from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1 for _ in range(Q)]
jump = [-1 for _ in range(Q)]
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)