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

S = list(map(int, input()))
n = len(S)
 
fl = [False]*(n+1)
res = 0
 
for i in range(n-3):
    if fl[i]:
        continue
    
    x = 0
    cnt = 0
    for j in range(i, n):
        x = (x*10+S[j])%2019
        
        if x == 0:
            cnt += 1
            fl[j+1] = True
            
    
    res += (cnt+1)*cnt//2
 
print(res)

### FIXED CODE ###

S = list(map(int, list(input())))
S.reverse()
a = [0]*len(S)
y = 2019
x = 1
t = 0
cnt = [0]*y
res = 0
for i in range(len(S)):
    cnt[t] += 1
    t += S[i]*x
    t %= y
    res += cnt[t]
    x = x*10%y
print(res)
### BUGGY CODE ###

N = int(input())
L = sorted([int(l) for l in input().split()])

num = 0
for na in range(N-2):
    for nb in range(na+1, N - 1):
        for nc in range(nb+1, N):
            if L[nc] < L[na] + L[nb]:
                num += 1

print(num)

### FIXED CODE ###

N = int(input())
L = sorted([int(l) for l in input().split()])
INF = 10**8
L.append(INF)
L.append(INF)

num = 0
for na in range(N-2):
    for nb in range(na+1, N - 1):
        r = N+1
        l = nb
        while r - l > 1:
            c = (l + r) // 2
            if L[c] < L[na] + L[nb]:
                l = c
            else:
                r = c
        num += l - nb

print(num)
### BUGGY CODE ###

s = input()
q = int(input())

inv = False
for _ in range(q):
    com, *query = input().split()
    if com == "1":
        if not inv:
            inv = True
        else:
            inv = False
    else:
        f, c = query
        if not inv:
            if f == "1":
                s = c + s
            else:
                s = s + c
        else:
            if f == "1":
                s = s + c
            else:
                s = c + s


print(s if not inv else s[::-1])

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())

inv = False
for _ in range(q):
    com, *query = input().split()
    if com == "1":
        if not inv:
            inv = True
        else:
            inv = False
    else:
        f, c = query
        if not inv:
            if f == "1":
                s.appendleft(c)
            else:
                s.append(c)
        else:
            if f == "1":
                s.append(c)
            else:
                s.appendleft(c)


s = "".join(s)
print(s if not inv else s[::-1])
### BUGGY CODE ###

s = input()
q = int(input())
for _ in range(q):
  t = input()
  if t[0]=='1':
    s = s[::-1]
  else:
    if t[2]=='1':
      s = t[4:] + s
    else:
      s = s + t[4:]
print(s)

### FIXED CODE ###

s=input();q=int(input());r,a=0,[[],[]]
for _ in range(q):
  t=input()
  if t=='1':r=-(-~r%2)
  else:a[~-r+int(t[2])].append(t[4])
print(''.join(a[~-r+1][::-1])+s[::r or 1]+''.join(a[~-r+2]))
### BUGGY CODE ###

from numpy import *
N,K = map(int,input().split())
LR = [list(map(int,input().split())) for k in range(K)]
D = (N+2)*[0]
dp = (N+1)*[0]
dp[1] = 1
mod = 998244353

for L,R in LR:
  D[L]+=1
  D[R+1]-=1

D = cumsum(D)

for i in range(1,N+1):
  for j in range(1,i):
    if D[j]==1:
      dp[i] = (dp[i]+dp[i-j])%mod

print(dp[N])

### FIXED CODE ###

N,K = map(int,input().split())
LR = [list(map(int,input().split())) for k in range(K)]

dp = (3*N)*[0]
dp[0] = 1
dp[1] = -1

for n in range(N):
  for L,R in LR:
    dp[L+n]+=dp[n]
    dp[n+R+1]-=dp[n]
  dp[n+1] = (dp[n]+dp[n+1])%998244353

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

import random
import copy

d = int(input())
dd = d * (d + 1) // 2
*C, = map(int, input().split())
S = [list(map(int, input().split())) for i in range(d)]
T = [random.choice(range(26)) for i in range(d)]
score = 0

for _ in range(10**5):
    p = random.choice(range(d))
    q = random.choice(range(26))
    TT = copy.copy(T)
    TT[p] = q
    L = [-1 for j in range(26)]
    X = [0 for j in range(26)]
    tmp = 0
    for i in range(d):
        tmp += S[i][TT[i]]
        X[TT[i]] += (d - i) * (i - L[TT[i]])
        L[TT[i]] = i
    for j in range(26):
        tmp -= C[j] * (dd - X[j])
    if tmp > score:
        score = tmp
        T = TT
for t in T:
    print(t)


### FIXED CODE ###

import random

d = int(input())
dd = d * (d + 1) // 2
*C, = map(int, input().split())
S = [list(map(int, input().split())) for i in range(d)]
T = [random.choice(range(26)) for i in range(d)]
score = 0

for _ in range(10**5):
    p = random.choice(range(d))
    q = random.choice(range(26))
    memo = T[p]
    T[p] = q
    L = [-1 for j in range(26)]
    X = [0 for j in range(26)]
    tmp = 0
    for i in range(d):
        tmp += S[i][T[i]]
        X[T[i]] += (d - i) * (i - L[T[i]])
        L[T[i]] = i
    for j in range(26):
        tmp -= C[j] * (dd - X[j])
    if tmp > score:
        score = tmp
    else:
        T[p] = memo

for t in T:
    print(t + 1)
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()

    return

#B
def B():
    def dfs(d,x,c):
        if dp[(d,x)] != None:
            return
        dp[(d,x)] = 1
        if d == 0:
            f[x] = c
        else:
            dfs(d-1,x,c)
            for y in v[x]:
                dfs(d-1,y,c)
    n,m = LI()
    f = [0]*n
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    dp = defaultdict(lambda : None)
    q = I()
    l = LIR(q)
    l = l[::-1]
    for x,d,c in l:
        x -= 1
        dfs(d,x,c)
    for i in f:
        print(i)
    return

#C
def C():
    n = I()

    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    B()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()

    return

#B
def B():
    def dfs(d,x,c):
        if d <= dp[x]:
            return
        dp[x] = d
        if not f[x]:
            f[x] = c
        for y in v[x]:
            dfs(d-1,y,c)
    n,m = LI()
    f = [0]*n
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    dp = defaultdict(lambda : -1)
    q = I()
    l = LIR(q)
    l = l[::-1]
    for x,d,c in l:
        x -= 1
        dfs(d,x,c)
    for i in f:
        print(i)
    return

#C
def C():
    n = I()

    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    B()
### BUGGY CODE ###

from itertools import combinations

cpList = []

def canProd(a,x):
    if x in cpList:
        return True
    for i in range(1,len(a)+1):
        comba = combinations(a,i)
        for j in comba:
            if sum(j) == x:
                cpList.append(x)
                return True
    return False


n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
m = [int(x) for x in input().split()]

for i in m:
    if canProd(a,i):
        print("yes")
    else:
        print("no")

### FIXED CODE ###

from functools import lru_cache

@lru_cache(maxsize = None)
def canProd(i,m):
     
    if m == 0:
        return True
    if i >= n:
        return False
 
    res = canProd(i+1,m) or canProd(i+1,m-a[i])
    return res
 
 
n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
m = [int(x) for x in input().split()]

rs = [None]*2001

maxm = max(m)
minm = min(m)

for i in range(minm,maxm+1):
    if canProd(0,i):
        rs[i] = "yes"
    else:
        rs[i] = "no"

for i in m:
    print(rs[i])
### BUGGY CODE ###

s=input()
n=len(s)
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-(int(s[i-1])*(pow(10,n-i)))
    t[i]%=2019
t.sort()
t2=sorted(list(set(t)))
tcnt=[0]*len(t2)
f=0
for i in range(n+1):
    if t2[f]==t[i]:
        tcnt[f]+=1
    else:
        f+=1
        tcnt[f]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)


### FIXED CODE ###

s=input()
n=len(s)
s_int=[0]*n
x=(pow(10,n-1))%2019
for i in range(n):
    s_int[i]=(int(s[i])*x)%2019
    x=(x*202)%2019
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-s_int[i-1]
    t[i]%=2019
t.sort()
t_set=sorted(list(set(t)))
tcnt=[0]*len(t_set)
num=0
for i in range(n+1):
    if t_set[num]==t[i]:
        tcnt[num]+=1
    else:
        num+=1
        tcnt[num]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)
### BUGGY CODE ###

N,M,L=map(int,input().split())
d=[[10**20 for i in range(0,N+1)] for i in range(0,N+1)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a][b]=c
    d[b][a]=c

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if d[i][j]>d[i][k]+d[k][j]:
                d[i][j]=d[i][k]+d[k][j]

e=[[10**20 for i in range(0,N+1)] for i in range(0,N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        if L>=d[i][j]:
            e[i][j]=1

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if e[i][j]>e[i][k]+e[k][j]:
                e[i][j]=e[i][k]+e[k][j]

Q=int(input())
ans=[]
for i in range(Q):
    s,t=map(int,input().split())
    if e[s][t]!=10**20:
        ans.append(e[s][t]-1)
    else:
        ans.append(-1)

for i in range(0,Q):
    print(ans[i])

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

N,M,L=map(int,input().split())
d=[[0 for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c

csr1=csr_matrix(d)

a=floyd_warshall(csr1)

d=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    for j in range(0,N):
        if L>=a[i][j]:
            d[i][j]=1


csr2=csr_matrix(d)

data=floyd_warshall(csr2)
ans=[]
Q=int(input())
for i in range(0,Q):
    s,t=map(int,input().split())
    if data[s-1][t-1]!=float('inf'):
        ans.append(int(data[s-1][t-1])-1)
    else:
        ans.append(-1)

for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

import itertools
n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
sv=[]
sum=0
sumc=0
for L in range(0, len(v)+1):
    for subset in itertools.combinations(v, L):
      for i in range(len(subset)):
        sum=sum+int(subset[i])
        for j in range(n):
          if int(subset[i])==v[j]:
            sumc=sumc+c[j]
      sv.append(sum-sumc)
      sum=0
      sumc=0
print(max(sv))

### FIXED CODE ###

import itertools
n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
vc=[]
for i in range(n):
  vc.append(v[i]-c[i])
sv=[]
for L in range(0, len(v)+1):
    for subset in itertools.combinations(vc, L):
      sv.append(sum(subset))
print(max(sv))
### BUGGY CODE ###

n=int(input())
al=list(map(int,input().split()))
ac=0
ans=set()
for i in range(n,0,-1):
    t=0
    for j in ans:
        if j%i==0:
            t+=1
    if t%2!=al[i-1]:
        ac+=1
        ans.add(i)
print(ac)
if ac>0:
    print(' '.join(map(str,ans)))

### FIXED CODE ###

n=int(input())
al=list(map(int,input().split()))
ac=0
ans=set()
tl=[0]*n
for i in range(n,0,-1):
    if tl[i-1]%2!=al[i-1]:
        ac+=1
        ans.add(i)
        for j in range(1,int(i**0.5)+1):
            if i%j==0:
                tl[j-1]+=1
                if j**2==i:
                    continue
                tl[i//j-1]+=1
print(ac)
if ac>0:
    print(' '.join(map(str,ans)))
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
bc=[]
for i in range(q):
    bc.append([int(x) for x in input().split()])
a_cnt=[0]*(10**7)
for i in range(max(a)+1):
	a_cnt[i]=a.count(i)

a_goukei=sum(a)

for gyou in range(q):
	a_goukei+=(bc[gyou][1]-bc[gyou][0])*a_cnt[bc[gyou][0]]
	print(a_goukei)
	a_cnt[bc[gyou][1]]+=a_cnt[bc[gyou][0]]
	a_cnt[bc[gyou][0]]=0

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
bc=[]
for i in range(q):
    bc.append([int(x) for x in input().split()])

a_cnt=[0]*(10**5+1)

for i in range(len(a)):
	a_cnt[a[i]]+=1

a_goukei=sum(a)

for gyou in range(q):
	a_goukei+=(bc[gyou][1]-bc[gyou][0])*a_cnt[bc[gyou][0]]
	print(a_goukei)
	a_cnt[bc[gyou][1]]+=a_cnt[bc[gyou][0]]
	a_cnt[bc[gyou][0]]=0
### BUGGY CODE ###

from _collections import deque
h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    s[i+1]=x
s[0]=s[-1]=["#"]*(w+2)




dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy,0]])
while len(data)>0:
  xy=data.popleft()
  x,y=xy[0],xy[1]
  if xy[2]==dep[x][y]:
    if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
        dep[x-1][y]=dep[x][y]
        data.append([x-1,y,dep[x][y]])
    if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
        dep[x+1][y] = dep[x][y]
        data.append([x + 1,y,dep[x][y]])
    if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
        dep[x][y-1] = dep[x][y]
        data.append([x,y-1,dep[x][y]])
    if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
        dep[x][y+1] = dep[x][y]
        data.append([x,y+1,dep[x][y]])

    for i in range(5):
        for j in range(5):
            if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                dep[x-2+i][y-2+j]=dep[x][y]+1
                data.append([x-2+i,y-2+j,dep[x][y]+1])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)



### FIXED CODE ###

from _collections import deque


h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    s[i+1]=x
s[0]=s[-1]=["#"]*(w+2)




dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy]])
while len(data)>0:
    xy=data.popleft()
    x,y=xy[0],xy[1]

    if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
        dep[x-1][y]=dep[x][y]
        data.appendleft([x-1,y])
    if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
        dep[x+1][y] = dep[x][y]
        data.appendleft([x + 1,y])
    if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
        dep[x][y-1] = dep[x][y]
        data.appendleft([x,y-1])
    if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
        dep[x][y+1] = dep[x][y]
        data.appendleft([x,y+1])

    for i in range(5):
        for j in range(5):
            if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                dep[x-2+i][y-2+j]=dep[x][y]+1
                data.append([x-2+i,y-2+j])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

odd = False
count = 0

while True:
    for i in A:
        if i%2 != 0:
            odd = True

    if odd:
        break

    for i in A:
        i = int(i/2)

    count += 1

print(count)


### FIXED CODE ###

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

count = -1
flag = True

while flag == True:
    count += 1
    for i in range(N):
        if A[i]%2 == 0:
            A[i] /= 2

        else:
            flag = False
            break



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

N, T = map(int, input().split())
data = []
for i in range(N):
  a, b = map(int, input().split())
  data.append((a,b))
data.sort()

#print(data)

dp = [0] * T
ans = 0
for a, b in data:
  ans = max(ans, dp[-1]+b)
  if a < T:
    eatable = dp[:T-a]
    j = 0
    for i in range(a, T, 1):
      if dp[i] < eatable[j] + b:
        dp[i] = eatable[j] + b
      j += 1
print(ans)

### FIXED CODE ###

import numpy as np

N, T = map(int, input().split())
data = []
for i in range(N):
  a, b = map(int, input().split())
  data.append((a,b))
data.sort()
data = np.array(data)

#print(data)

dp = np.zeros(T)
ans = 0
for a, b in data:
  ans = max(ans, dp[-1]+b)
  if a < T:
    newtable = dp[:T-a] + b
    dp[a:] = np.maximum(dp[a:], newtable)
print(int(ans))
### BUGGY CODE ###

n = int(input())
d = list(map(int, input().split()))
way = 0
for k in range(1,max(d)+1):
    arc = 0
    abc = 0
    for di in d:
        if di >= k:
            arc += 1
        else:
            abc += 1
    if arc == abc:
        way += 1
print(way)


### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
d.sort()
print(d[int(n/2)] - d[int(n/2)-1])
### BUGGY CODE ###

import itertools
import heapq


def main():
    INF = 10 ** 7
    H, W = list(map(int, input().split()))
    CH, CW = list(map(lambda x: int(x) - 1, input().split()))
    DH, DW = list(map(lambda x: int(x) - 1, input().split()))
    S = [input() for _ in range(H)]
    if S[DH][DW] == '#':
        print(-1)
        return
    # 使うワープの最小回数
    cnt = [[INF for _ in range(W)] for _ in range(H)]

    que = [(0, DH, DW)]
    cnt[DH][DW] = 0
    while len(que) > 0:
        c, h, w = heapq.heappop(que)
        for dh, dw in itertools.product(range(-2, 3), repeat=2):
            nh, nw = h + dh, w + dw
            if dh == dw == 0 or not (0 <= nh < H) or \
                not (0 <= nw < W) or S[nh][nw] == '#':
                continue
            nc = c
            if [dh, dw] not in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
                nc += 1
            if cnt[nh][nw] > nc:
                cnt[nh][nw] = nc
                heapq.heappush(que, (nc, nh, nw))

    if cnt[CH][CW] == INF:
        print(-1)
    else:
        print(cnt[CH][CW])


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque


def main():
    INF = 10 ** 7
    H, W = list(map(int, input().split()))
    CH, CW = list(map(lambda x: int(x) - 1, input().split()))
    DH, DW = list(map(lambda x: int(x) - 1, input().split()))
    S = [input() for _ in range(H)]
    if S[DH][DW] == '#':
        print(-1)
        return
    # 歩き
    walk_list = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    # ワープ
    warp_list = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], \
            [-1, -2], [-1, -1], [-1, 1], [-1, 2], \
            [0, -2], [0, 2], \
            [1, -2], [1, -1], [1, 1], [1, 2], \
            [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]
    # 使うワープの最小回数
    cnt = [[INF for _ in range(W)] for _ in range(H)]

    warp_checked = [[0 for _ in range(W)] for _ in range(H)]
    warp_que = deque([(DH, DW)])
    c = 0
    while len(warp_que) > 0:
        # warp_queから歩きのみでいける範囲の探索
        walk_que = deque()
        while len(warp_que) > 0:
            h, w = warp_que.pop()
            cnt[h][w] = c
            walk_que.append((h, w))
            tmp_walk_que = deque([(h, w)])
            while len(tmp_walk_que) > 0:
                h, w = tmp_walk_que.pop()
                for dh, dw in walk_list:
                    nh, nw = h + dh, w + dw
                    if 0 <= nh < H and 0 <= nw < W and \
                        S[nh][nw] == '.' and cnt[nh][nw] == INF:
                        cnt[nh][nw] = c
                        tmp_walk_que.append((nh, nw))
                        walk_que.append((nh, nw))
        # ワープでしかいけない範囲の探索
        while len(walk_que) > 0:
            h, w = walk_que.pop()
            for dh, dw in warp_list:
                nh, nw = h + dh, w + dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and \
                    warp_checked[nh][nw] == 0 and cnt[nh][nw] == INF:
                    warp_checked[nh][nw] = 1
                    warp_que.append((nh, nw))
        c += 1

    if cnt[CH][CW] == INF:
        print(-1)
    else:
        print(cnt[CH][CW])


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

n = int(input())
s = list(str(input()))

ans = 0
for i in range(n-3):
    for j in range(i+1,n-1):
        if s[i] != s[j]:
            for k in range(j+1,n):
                if s[i] != s[k] and s[j] != s[k] and j-i != k-j:
                    ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = list(str(input()))

ans = 0
for i in range(1,n-1):
    sr = 0
    sg = 0
    sb = 0
    er = 0
    eg = 0
    eb = 0

    for j in range(i):
        if s[j] != s[i]:
            if s[j] == "R":
                sr += 1
            elif s[j] == "G":
                sg += 1
            else:
                sb += 1
        pass
    for j in range(i+1,n):
        if s[j] != s[i]:
            if s[j] == "R":
                er += 1
            elif s[j] == "G":
                eg += 1
            else:
                eb += 1
    ans += sr*eb + sr*eg + sg*eb + sg*er + sb*er + sb*eg
    for j in range(min(i,n-i-1)):
        if s[i+j+1] != s[i-j-1] and s[i+j+1] != s[i] and s[i] != s[i-j-1]:
            ans -= 1
    # print(i,ans)

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

n = int(input())
a = [int(input()) for _ in range(n)]
b = [-1]
c = 1


def bi(a, x):
    i, j = 0, len(a) - 1
    while i != j:
        k = (i + j) // 2+1
        if a[k] < x:
            i = k
        else:
            j = k - 1
    if a[0] >= x:
        i -= 1
    return i


for i in a:
    j = bi(b, i)
    if j == -1:
        b = [i] + b
        c += 1
    else:
        b[j] = i
print(c)


### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
b = [-1]
c = 1


def bi(a, x):
    i, j = 0, len(a) - 1
    while i != j:
        k = (i + j) // 2
        if a[k] >= x:
            i = k+1
        else:
            j = k
    if a[-1] >= x:
        i =-1
    return i


for i in a:
    j = bi(b, i)
    if j == -1:
        b.append(i)
        c += 1
    else:
        b[j] = i
print(c)
### BUGGY CODE ###

n,m = map(int,input().split())
A = list(map(int,input().split()))
for i in range(m):
  b,c = map(int,input().split())
  A.extend([c for j in range(b)])
A.sort(reverse=True)
print(sum(A[:n]))

### FIXED CODE ###

n,m = map(int,input().split())
A = list(map(int,input().split()))
CntA = [1 for i in range(n)]
for i in range(m):
  b,c = map(int,input().split())
  A.append(c)
  CntA.append(b)
Z = list(zip(A,CntA))
Z.sort(reverse=True)
ans = 0
for z in Z:
  if n>z[1]:
    ans+=z[1]*z[0]
    n-=z[1]
  else:
    ans+=n*z[0]
    break
print(ans)
### BUGGY CODE ###

n = int(input())
count = 0
for i in range(1,n+1):
    s = list(str(i))
    se = sorted(list(set(s)))
    #print(se)
    if se == ['3','5','7']:
        #print(i)
        count += 1
print(count)

### FIXED CODE ###

import itertools

n = int(input())
count = 0
for i in range(3,10):
    li = list(itertools.product(range(3), repeat=i))
    #print(li)
    for l in li:
        st = ''
        for ll in l:
            if ll == 0:
                st += '3'
            elif ll == 1:
                st += '5'
            else:
                st += '7'
        if len(set(list(st))) == 3 and int(st)<=n:
            count += 1
print(count)