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

import sys
sys.setrecursionlimit(int(1e+6))
N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]

branch = [[] for _ in range(N)]
for i in range(N-1):
    branch[ab[i][0]-1].append(ab[i][1]-1)
    branch[ab[i][1]-1].append(ab[i][0]-1)

counters = [0 for _ in range(N)]
for i in range(Q):
    counters[px[i][0]-1] += px[i][1]

results = [0 for _ in range(N)]

def repeat(node, counter, pre_node):
    counter += counters[node]
    for candidate in branch[node]:
        if candidate == pre_node:
            continue
        else:
            repeat(candidate, counter, node)
    results[node] = counter
    return
    
repeat(0, 0, 0)

print((" ").join([str(i) for i in results]))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]

branch = [[] for _ in range(N)]
for i in range(N-1):
    branch[ab[i][0]-1].append(ab[i][1]-1)
    branch[ab[i][1]-1].append(ab[i][0]-1)

counters = [0 for _ in range(N)]
for i in range(Q):
    counters[px[i][0]-1] += px[i][1]
results = [0 for _ in range(N)]

seen = [False for _ in range(N)]
from collections import deque
seen[0] = True
todo = deque([0])
results[0] = counters[0]

while len(todo)>0:
    checking = todo.pop()
    candidates = branch[checking]
    for candidate in candidates:
        if seen[candidate] == False:
            todo.append(candidate)
            seen[candidate] = True
            results[candidate] = results[checking]+counters[candidate]


print((" ").join([str(i) for i in results]))
### BUGGY CODE ###

# coding: utf-8

N, Q = [int(i) for i in input().split()]
S = input()
is_AC = [S[i:i+2] == "AC" for i in range(N)]

for i in range(Q):
  l, r = [int(i) for i in input().split()]
  print(sum(is_AC[(l-1):r]) - is_AC[r-1])


### FIXED CODE ###

# coding: utf-8
import sys
import numpy as np
input = sys.stdin.readline

N, Q = [int(i) for i in input().split()]
S = input()
is_AC = [False] * N
AC_csum = [0] * N
for i in range(N):
  is_AC[i] = S[i:i+2] == "AC"
  AC_csum[i] = AC_csum[i-1] + is_AC[i]

for i in range(Q):
  l, r = [int(i) for i in input().split()]
  ans = AC_csum[r-1] - AC_csum[l-1] - is_AC[r-1] + is_AC[l-1]
  print(ans)
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = {}
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count > N + 100 : break
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

class Item:
  def __init__(self, w, v):
    self.w = w
    self.v = v

N, W = map(int, input().split())
items = [Item(0, 0)] + [Item(*map(int, input().split())) for i in range(N)]
dp = [[0]*(W+1) for i in range(N+1)]

for i in range(1, N+1):
  item = items[i]
  for w in range(1, W+1):
    if w - item.w < 0:
      dp[i][w] = dp[i-1][w]
    else:
      dp[i][w] = max(dp[i-1][w], dp[i-1][w-item.w]+item.v)

print(dp[N][W])


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
def main():
    N,W = map(int,input().split())
    dp = [-1 for _ in range(W+1)]
    dp[W] = 0
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(nm,W+1):
            a = nm
            if dp[j] == -1:
                continue
            if dp[j-a] < dp[j] + nv:
                dp[j-a] = dp[j] + nv
    print(max(dp))
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    import collections
    N, K = [int(item) for item in input().split()]
    A_list = [int(item) for item in input().split()]

    bit_k = bin(K)[2:]

    telepo_list = [A_list]

    for _ in range(len(bit_k)-1):
        temp_list = telepo_list[-1]
        new_telep = []
        for i in temp_list:
            new_telep.append(temp_list[i-1])

        telepo_list.append(new_telep)

    # print(telepo_list)

    goto = 1
    for i in range(len(bit_k)):
        temp_list = telepo_list[i]
        if ((K >> i) & 1): 
            goto = temp_list[goto -1]
            # print(i, goto)

    print(goto)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    import collections
    N, K = [int(item) for item in input().split()]
    A_list = [int(item) for item in input().split()]
    order_dict = dict(zip(range(1,N+1),A_list))

    foot_print = [-1 for _ in range(N+1)]
    loop_que = collections.deque([1])

    goto = 1

    while foot_print[goto] == -1:
        foot_print[goto] = 1
        goto = order_dict[goto]
        loop_que.append(goto) 

    loop_start = loop_que.index(goto) + 1
    loop_len = len(loop_que) - loop_start

    # print(loop_que)
    # print(loop_start, loop_len)


    data_list = list(loop_que)
    if K >= len(loop_que):
        temp_K = K - loop_start + 1
        temp_K %= loop_len
        temp_loop = data_list[loop_start-1:-1]
        print(temp_loop[temp_K])
    else:

        print(data_list[K])

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

X, Y, Z, K = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

c.sort(reverse=True)

ablst = [m + n for n in b for m in a]

ablst.sort(reverse=True)
ablst1 = ablst[:K]

abclst = []

for m in ablst1:
    for n in c:
        abclst.append(m + n)

abclst.sort(reverse=True)

print(*abclst[:K], sep='\n')


### FIXED CODE ###

import sys
input = sys.stdin.readline

X, Y, Z, K = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

a.sort(reverse=True)
b.sort(reverse=True)

ablst = [m + n for n in b for m in a]

ablst.sort(reverse=True)

c.sort(reverse=True)

abclst = [m + n for n in c[:K] for m in ablst[:K]]

abclst.sort(reverse=True)

print(*abclst[:K], sep='\n')
### BUGGY CODE ###

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

import numpy as np
# t = time.time()
ans = 0
mut_ori = n//k
for a in range(1, k + 1):
    b_cand = list(range(k - a%k,n+1,k))
    for b in b_cand:
        c_cand = list(range(k - b%k,n+1,k))
        for c in c_cand:
            if a <= n%k:
                mut = mut_ori + 1
            else:
                mut = mut_ori
            if (a + c) % k == 0:
                ans += mut
#             print(a,b,c,mut)
print(ans)
# print(time.time() - t)

### FIXED CODE ###

import numpy as np
n, k = list(map(int,input().split()))

ans = 0
mut_ori = n//k
for a in range(1, k + 1):
    b_cand = list(range(k - a%k,k+1,k))
    for b in b_cand:
        c_cand = list(range(k - b%k,n+1,k))
        for c in c_cand:
            if a <= n%k:
                mut = mut_ori + 1
            else:
                mut = mut_ori
            if b <= n%k:
                mut *= (mut_ori + 1)
            else:
                mut *= mut
            if (a + c) % k == 0:
                ans += mut
#             print(a,b,c,mut)
print(ans)
### BUGGY CODE ###

from sys import exit
n, m = map(int, input().split())
s = input()

if n <= m:
    print(n)
    exit()

one_sequence = 0
for i in range(n+1):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos != 0:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos -= i
            break
print(ans.strip())


### FIXED CODE ###

from sys import exit
n, m = map(int, input().split())
s = input()

one_sequence = 0
for i in range(1, n):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos != 0:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos -= i
            break
print(ans)
### BUGGY CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


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

lr = []
for i in range(Q):
    l, r = map(int, input().split())
    lr.append([l, r, i])

lr.sort(key=lambda x: x[1])
# print("lr", lr)
rightest = [-1] * (N + 1)
current_q = 0
bit = Bit(N)
ans = [0] * Q

for i in range(N):
    if rightest[c[i]] != -1:
        bit.add(rightest[c[i]] + 1, -1)
    rightest[c[i]] = i
    bit.add(i + 1, 1)
    # print(bit.tree)

    while current_q < Q and lr[current_q][1] == i + 1:
        ans[lr[current_q][2]] = bit.sum(lr[current_q][1]) - bit.sum(lr[current_q][0] - 1)
        current_q += 1

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


### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


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

lr = []
for i in range(Q):
    l, r = map(int, input().split())
    lr.append([l, r, i])

lr.sort(key=lambda x: x[1])
# print("lr", lr)
rightest = [-1] * (N + 1)
current_q = 0
bit = Bit(N)
ans = [0] * Q

for i in range(N):
    if rightest[c[i]] != -1:
        bit.add(rightest[c[i]] + 1, -1)
    rightest[c[i]] = i
    bit.add(i + 1, 1)
    # print(bit.tree)

    while current_q < Q and lr[current_q][1] == i + 1:
        ans[lr[current_q][2]] = bit.sum(lr[current_q][1]) - bit.sum(lr[current_q][0] - 1)
        current_q += 1

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

S = input()
Q = int(input())

rev = True
for _ in range(Q):
    s = input()
    if s[0] == "1":
        rev = not(rev)
    else:
        t = int(s[0])
        f = int(s[2])
        c = str(s[4])
        if rev:
            if f == 1:
                S = c+S
            else:
                S = S+c
        else:
            if f == 1:
                S = S+c
            else:
                S = c+S

if rev:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

from collections import deque

ans = deque(input())
Q = int(input())
state = True
for _ in range(Q):
    Query = input().split()
    if int(Query[0]) == 1:
        state = not state
    else:
        if int(Query[1]) == 1:
            if state:
                ans.appendleft(Query[2])
            else:
                ans.append(Query[2])
        if int(Query[1]) == 2:
            if state:
                ans.append(Query[2])
            else:
                ans.appendleft(Query[2])

if state:
    print("".join(map(str, ans)))
else:
    print("".join(map(str, reversed(ans))))
### BUGGY CODE ###

def resolve():
    h, n = map(int, input().split())
    w = []
    v = []
    for i in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    dp = [[0 for i in range(h + 1)] for j in range(n + 1)]
    for i in range(1, h + 1):
        # dp[0][i] = v[0] * ((w[0]+i-1)//w[0])
        dp[0][i] = float("inf")
    for i in range(n):
        # print(dp[i])
        # print(dp[i][::-1][::w[i]]+[0])
        for j in range(h + 1):
            if j >= w[i]:
                dp[i + 1][j] = min([x + y * v[i]
                                    for y, x in enumerate(dp[i][:j+1][::-1][::w[i]]+[0])])
            else:
                dp[i + 1][j] = min(dp[i][j], v[i])
    # print(dp[n])
    print(dp[n][h])


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

def resolve():
    h, n = map(int, input().split())
    w = []
    v = []
    for i in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    dp = [[0 for i in range(h + 1)] for j in range(n + 1)]
    for i in range(1, h + 1):
        dp[0][i] = float("inf")
    for i in range(n):
        for j in range(h + 1):
            if j >= w[i]:
                dp[i + 1][j] = min(dp[i + 1][j - w[i]] + v[i], dp[i][j])
            else:
                dp[i + 1][j] = min(dp[i][j], v[i])
    # print(dp[n])
    print(dp[n][h])


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


h, w = map(int, input().split())
maze = []

for i in range(h):
    maze.append(list(input()))


def bfs(start: list):
    global h, w, maze
    length = [[-1 for _ in range(w)] for _ in range(h)]
    check = set()
    queue = [start]
    depth = 0
    while len(queue) > 0:
        [x, y, bx, by] = queue.pop(0)
        check.add((x, y))
        length[x][y] = length[bx][by] + 1

        depth += 1
        target = []
        if x != 0:
            target.append((x - 1, y))
        if x != h - 1:
            target.append((x + 1, y))
        if y != 0:
            target.append((x, y - 1))
        if y != w - 1:
            target.append((x, y + 1))

        for t in target:
            if t not in check:
                if maze[t[0]][t[1]] == ".":
                    queue.append([t[0], t[1], x, y])
    res = -1
    for i in range(h):
        for j in range(w):
            res = max(res, length[i][j])

    return res


ans = -1

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs([i, j, i, j]))

print(ans)


### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
maze = []

for i in range(h):
    maze.append(list(input()))

move = [[-1, 0], [1, 0], [0, -1], [0, 1]]


def bfs(start: list):
    global h, w, maze
    length = [[-1 for _ in range(w)] for _ in range(h)]
    check = [[False for _ in range(w)] for _ in range(h)]
    check[start[0]][start[1]] = True
    queue = deque([start])
    res = -1
    while len(queue) > 0:
        [x, y, bx, by] = queue.popleft()

        length[x][y] = length[bx][by] + 1
        res = max(res, length[x][y])

        for p in move:
            next_x = x + p[0]
            next_y = y + p[1]
            if (next_x < 0)or(next_x == h)or(next_y < 0)or(next_y == w):
                continue
            if not check[next_x][next_y]:
                check[next_x][next_y] = True
                if maze[next_x][next_y] == ".":
                    queue.append([next_x, next_y, x, y])

    return res


ans = -1

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs([i, j, i, j]))

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

N,K = [int(x) for x in input().split()]
S = input()

DP = [0]
ans = 0

for index,x in enumerate(S):
    if(index==0):
        if(x=='0'):
            DP.append(0)
            DP.append(1)
        else:
            DP.append(1)
    else:
        if(S[index-1]!=x):
            DP.append(DP[-1]+1)
        else:
            DP[-1]+=1
    if(index==N-1):
        if(x=='1'):
            DP.append(DP[-1])
        DP.append(DP[-1])

for i in range(K+1):
    l=0
    while(1+2*i+l<len(DP)):
        ans = max(DP[2*i+1+l]-DP[l],ans)
        l+=2

if(not '0' in S):
    ans = len(S)
elif(not '1' in S):
    ans = len(S)

print(ans)


### FIXED CODE ###

N,K = [int(x) for x in input().split()]
S = input()

DP = [0]
ans = 0
l = 0

for index,x in enumerate(S):
    if(index==0):
        if(x=='0'):
            DP.append(0)
            DP.append(1)
        else:
            DP.append(1)
    else:
        if(S[index-1]!=x):
            DP.append(DP[-1]+1)
        else:
            DP[-1]+=1
    if(index==N-1):
        if(x=='1'):
            DP.append(DP[-1])
        DP.append(DP[-1])

l=0
i = min(int((len(DP))/2)-1,K)
while(1+2*i+l<len(DP)):
    ans = max(DP[2*i+1+l]-DP[l],ans)
    l+=2

if(not '0' in S):
    ans = len(S)
elif(not '1' in S):
    ans = len(S)

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

from collections import defaultdict

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

S1 = S[:N]
S2 = S[N:][::-1]
D = defaultdict(int)
ans = 0

for i in range(2**N):
    bit = bin(2**N+i)[3:]
    red1 = tuple([d for d, s in zip(S1, bit) if s == "1"])
    blue1 = tuple([d for d, s in zip(S1, bit) if s == "0"])
    D[(red1, blue1)] += 1

for i in range(2 ** N):
    bit = bin(2 ** N + i)[3:]
    red2 = tuple([d for d, s in zip(S2, bit) if s == "1"])
    blue2 = tuple([d for d, s in zip(S2, bit) if s == "0"])
    ans += D[(blue2, red2)]

print(ans)


### FIXED CODE ###

from collections import defaultdict

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

S1 = S[:N]
S2 = S[N:][::-1]
D = defaultdict(int)
ans = 0

for i in range(2**N):
    bit = bin(2**N+i)[3:]
    red1 = "".join([d for d, s in zip(S1, bit) if s == "1"])
    blue1 = "".join([d for d, s in zip(S1, bit) if s == "0"])
    D[(red1, blue1)] += 1

for i in range(2 ** N):
    bit = bin(2 ** N + i)[3:]
    red2 = "".join([d for d, s in zip(S2, bit) if s == "1"])
    blue2 = "".join([d for d, s in zip(S2, bit) if s == "0"])
    ans += D[(blue2, red2)]

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

import math
a, b, n = map(int, input().split())
ans = []
for i in range (n):
  s = math.floor((a * (i + 1)) / b) - a * math.floor((i + 1) / b)
  ans.append(s)
  if max(ans) > s:
    break
print (max(ans))

### FIXED CODE ###

import math
a, b, n = map(int, input().split())
ans = []

def Calcf(i):
  return math.floor((a * i) / b) - a * math.floor(i / b)
    
print (Calcf(min(b - 1, n)))
### BUGGY CODE ###

N = int(input())


for h in range(1, 3500):
    for n in range(1, 3500):
        x = 4 * h * n - N * h - N * n
        if x != 0:
            w = N * h * n / (4 * h * n - N * h - N * n)
            if int(w) == w and w > 0:
                print(h, n, int(w))
                exit()


### FIXED CODE ###

N = int(input())


for h in range(1, 3500):
    for n in range(1, 3500):
        x = 4 * h * n - N * h - N * n
        if x != 0:
            w = N * h * n / (4 * h * n - N * h - N * n)
            if int(w) == w and w > 0:
                print(h, n, int(w))
                exit()
### BUGGY CODE ###

def isPrime(num):
    if num == 1:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False
    else:
        for i in range(3, int(num ** 0.5) + 1, 2):
            if num % i == 0:
                return False

        return True


while True:
    try:
        n = int(input())
    except EOFError:
        break

    count = 0
    for i in range(1, n + 1):
        count += 1 if isPrime(i) else 0

    print(count)



### FIXED CODE ###

# coding: utf-8

LIMIT = 999999

prime = [0, 1] + [0 if i % 2 == 0 else 1 for i in range(3, LIMIT + 1)]

for i in range(3, int(LIMIT ** 0.5) + 1):
    if prime[i - 1]:
        for j in range(i ** 2, LIMIT + 1, i):
            prime[j - 1] = 0

while True:
    try:
        n = int(input())
    except EOFError:
        break

    print(sum(prime[:n]))
### BUGGY CODE ###

import collections
import sys
input = sys.stdin.readline
n = int(input())
s = []
for i in range(n):
  s.append(input())
#print(s)
c = collections.Counter(s)
#print(c.most_common())
m = c.most_common()[0][1]
l = len(c.most_common())
ans = []
for i in range(l):
  if c.most_common()[i][1] == m:
    ans.append(c.most_common()[i][0])
  else:
    break
ans0 = sorted(ans)
for i in range(len(ans0)):
  print(ans0[i],end="")

### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline
n = int(input())
s = []
for i in range(n):
  s.append(input())
#print(s)
c = collections.Counter(s)
#print(c.most_common())
x = c.most_common()
m = x[0][1]
l = len(x)
ans = []
for i in range(l):
  if x[i][1] == m:
    ans.append(x[i][0])
  else:
    break
ans0 = sorted(ans)
for i in range(len(ans0)):
  print(ans0[i],end="")
### 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)]

n=n0()
s=s0()
r=[]
g=[]
b=[]
c=0
for x in s:
    if x=="R":
        r.append(c)
    elif x=="G":
        g.append(c)
    else:
        b.append(c)
    c+=1
ans=0
for r1 in r:
    for g1 in g:
        for b1 in b:
            k=max(r1,g1,b1)
            i=min(r1,g1,b1)
            j=[x for x in [r1,g1,b1] if x!=k and x!= i][0]
            if j-i!=k-j:
                ans+=1
print(ans)

### 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 math import comb
def comb(n,r):
    if r==2:
        return n*(n-1)//2
    else:
        return n*(n-1)*(n-2)//6
n=n0()
s=s0()
r=s.count("R")
g=s.count("G")
b=s.count("B")
ans=0
for i in range(1,(n-1)//2+1):
    for j in range(0,n-2*i):
        ans+=1
        if s[j]==s[j+i]==s[j+2*i]:
            ans-=1
        elif s[j]==s[j+i] or s[j]==s[j+2*i] or s[j+i]==s[j+2*i]:
            ans-=1
            
ans+=comb(r,3)+comb(g,3)+comb(b,3)+comb(r,2)*(g+b)+comb(g,2)*(r+b)+comb(b,2)*(r+g)
print(comb(n,3)-ans)
### BUGGY CODE ###

N = int(input())
S = input()
l = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        f = True
        for k in range(0, min(j - i, N - j )):
            if S[i + k] == S[j + k]: # ここがスライスの時はkの範囲がrange(1, min(j - i, N - j ) + 1)
                pass
            else:
                f = False
                break
        if f:
            l = max(l, k + 1)
        else:
            l = max(l, k)
print(l)

### FIXED CODE ###

N = int(input())
S = input()
r = 1
ans = 0
for i in range(N):
    while True:
        if S.rfind(S[i : r + 1]) >= r + 1:
            r += 1
            ans = max(ans, r - i)
        else:
            break
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

a2 = []
for _ in range(m):
    b, c = map(int, input().split())
    a2 += [c]*b
a2.sort()

for i in range(min(n, len(a2))):
    if a[i] < a2[-1-i]:
        a[i] = a2[-1-i]
    else:
        break

print(sum(a))


### FIXED CODE ###

n, m = map(int, input().split())
a = [(1, int(x)) for x in input().split()]

for _ in range(m):
    b, c = map(int, input().split())
    a += [(b, c)]

from operator import itemgetter
a = sorted(a, key=itemgetter(1))

ans = 0
t = 0
while n-t > 0:
    (k, x) = a.pop()
    ans += x * min(k, n-t)
    t += k

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

n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]

h = sorted(h)

ans = max(h[0:k]) - min(h[0:k])
for i in range(1, n-k+1):
    ans = min(ans, max(h[i:i+k]) - min(h[i:i+k]))
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
 
h = sorted(h)
 
ans = h[k-1] - h[0]
for i in range(1, n-k+1):
    ans = min(ans, h[i+k-1] - h[i])

print(ans)