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

import itertools
from collections import deque
from sys import stdin
input = stdin.readline


def main():
  H, W = list(map(int, input().split()))

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    is_visited = [[0]*W for _ in range(H)]
    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      is_visited[now_h][now_w] = 1
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (is_visited[next_h][next_w] == 1) or \
           M[next_h][next_w] == '#':
           # (dist[next_h][next_w] != float('inf')) or \
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

  max_ = 0
  for h in range(H):
    for w in range(W):
      if M[h][w] == '.':
        max_ = max(bfs((h, w)), max_)

  print(max_)


if(__name__ == '__main__'):
  main()


### FIXED CODE ###

import itertools
from collections import deque
from sys import stdin
input = stdin.readline


def main():
  H, W = list(map(int, input().split()))

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (dist[next_h][next_w] != float('inf')) or \
           M[next_h][next_w] == '#':
          continue

        temp = dist[now_h][now_w] + 1
        dist[next_h][next_w] = temp
        if max_ < temp:
          max_ = temp
        q.append((next_h, next_w))
    return max_

  max_ = 0
  for h in range(H):
    for w in range(W):
      if M[h][w] == '.':
        max_ = max(bfs((h, w)), max_)

  print(max_)


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

#  --*-coding:utf-8-*--

def sumOfDigits(n):
    a = 0

    while n > 0:
        a += n%10
        n //= 10

    return a


def f(n):
    while n%2 == 0:
        n //= 2

    while n%5 == 0:
        n //= 5

    vs = [None]*n
    qs = set()
    x = sumOfDigits(n)

    for i in range(1, min(n, 10)):
        vs[i] = i
        qs.add(i)

    while len(qs) > 0:
        q = qs.pop()
        q2 = q*10
        v = vs[q]
        
        for i in range(0, min(x-v, 10)):
            q3 = (q2 + i)%n
            v2 = v + i
            v3 = vs[q3]

            if v3 == None or v2 < v3:
                vs[q3] = v2
                qs.add(q3)
                    
            if q3 == 0 and v2 < x:
                x = v2

    return x


def test():
    assert f(6) == 3
    assert f(41) == 5
    assert f(79992) == 36


def main():
    n = int(input())
    print(f(n))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#  --*-coding:utf-8-*--

import heapq

def sumOfDigits(n):
    a = 0

    while n > 0:
        a += n%10
        n //= 10

    return a


def f(n):
    while n%2 == 0:
        n //= 2

    while n%5 == 0:
        n //= 5

    vs = [None]*n
    qs = []
    x = sumOfDigits(n)

    for i in range(1, min(n, 10)):
        vs[i] = i
        heapq.heappush(qs, (i, i))

    while len(qs) > 0:
        _, q = heapq.heappop(qs)
        q2 = q*10
        v = vs[q]
        
        for i in range(0, min(x-v, 10)):
            q3 = (q2 + i)%n
            v2 = v + i
            v3 = vs[q3]

            if v3 == None or v2 < v3:
                vs[q3] = v2
                heapq.heappush(qs, (v2, q3))
                    
            if q3 == 0 and v2 < x:
                x = v2

    return x


def test():
    assert f(6) == 3
    assert f(41) == 5
    assert f(79992) == 36


def main():
    n = int(input())
    print(f(n))


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

N=int(input())
S=list(input())
ans=0
R=[]
G=[]
B=[]
for i in range(N):
    if S[i]=="R":
        R.append(i+1)
    elif S[i]=="G":
        G.append(i+1)
    else:
        B.append(i+1)
lenb=len(B)
for r in R:
    for g in G:
        flag=0
        left=max(min(r,g)-abs(r-g),0)
        right=max(r,g)+abs(r-g)
        if (r+g)%2==0:
            middle=(r+g)//2
        else:
            middle=0
        for b in B:
            if b>right:
                break
            if b==right or b==left or b==middle:
                flag=flag+1
        ans=ans+lenb-flag
print(ans)

### FIXED CODE ###

N=int(input())
S=list(input())
ans=0
R=0
G=0
B=0
for i in range(N):
    if S[i]=="R":
        R=R+1
    elif S[i]=="G":
        G=G+1
    else:
        B=B+1
ans=R*G*B
for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i]!=S[j]:
            k=2*j-i
            if N<=k:
                continue
            if S[i]!=S[k] and S[k]!=S[j]:
                ans=ans-1
print(ans)
### BUGGY CODE ###

N = int(input())
count = 0

for i in range(1, N+1):
    ii = str(i)
    if "0" in ii or "1" in ii or "2" in ii or "4" in ii or "6" in ii or "8" in ii or "9" in ii:
        pass
    elif "3" in ii and "5" in ii and "7" in ii:
        count += 1
    else:
        pass

print(count)


### FIXED CODE ###

N = int(input())

def dfs(s):
    if int(s) > N:
        return 0
    ans = 1 if all (s.count(c) > 0 for c in "753") else 0
    
    for c in "753":
        ans += dfs(s+c)
    return ans
print(dfs('0'))
### BUGGY CODE ###

n = int(input())
List = list(map(int, input().split()))
count = 0

for i in range(n):
  if List[i] <= min(List[0:i+1:]):
    count += 1
print(count)

### FIXED CODE ###

n = int(input())
List = list(map(int, input().split()))
count = 1
min = List[0]

for i in range(n):
  if min > List[i]:
    min =List[i]
    count += 1
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
E - Roadwork
https://atcoder.jp/contests/abc128/tasks/abc128_e

"""
import sys


def solve(N, Q):
    events = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    events.sort(reverse=True)
    D = [int(input()) for _ in range(Q)]

    blocked = set()
    ans = []
    for d in D:
        while events and events[-1][0] <= d:
            t, e, x = events.pop()
            if e == -1:
                blocked.discard(x)
            else:
                blocked.add(x)
        if blocked:
            ans.append(min(blocked))
        else:
            ans.append(-1)
    return ans


def main(args):
    N, Q = map(int, input().split())
    ans = solve(N, Q)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
E - Roadwork
https://atcoder.jp/contests/abc128/tasks/abc128_e

"""
import sys

from heapq import heappop, heappush

def solve(N, Q):
    events = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    events.sort(reverse=True)
    D = [int(input()) for _ in range(Q)]

    blocked = set()
    ans = []
    hq = []
    for d in D:
        while events and events[-1][0] <= d:
            t, e, x = events.pop()
            if e == -1:
                blocked.discard(x)
            else:
                blocked.add(x)
                heappush(hq, x)
        if blocked:
            while hq and hq[0] not in blocked:
                heappop(hq)
            ans.append(hq[0] if hq else -1)
        else:
            ans.append(-1)
    return ans


def main(args):
    N, Q = map(int, input().split())
    ans = solve(N, Q)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

n=int(input())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
tlist=[0]
for val in arr1:
  tlist.append(tlist[-1]+val)
t=tlist[-1]
ans=0
vlist=[0]
for i in range(1,2*t):
  tt=i/2
  tmp=10**18
  for j in range(n):
    if tt<=tlist[j]:
      tmp=min(tmp,arr2[j]+(tlist[j]-tt))
    elif tlist[j+1]<=tt:
      tmp=min(tmp,arr2[j]+(tt-tlist[j+1]))
    else:
      tmp=min(tmp,arr2[j])
  tmp=min(tmp,tt)
  tmp=min(tmp,t-tt)
  vlist.append(tmp)
vlist.append(0)
for i in range(len(vlist)-1):
  ans+=(vlist[i]+vlist[i+1])/4
print(ans)

### FIXED CODE ###

def solve():
  n=int(input())
  arr1=list(map(int,input().split()))
  arr2=list(map(int,input().split()))
  tlist=[0]
  for val in arr1:
    tlist.append(tlist[-1]+val)
  t=tlist[-1]
  ans=0
  for i in range(1,2*t):
    tt=i/2
    tmp=10**18
    for j in range(n):
      if tt<=tlist[j]:
        tmp=min(tmp,arr2[j]+(tlist[j]-tt))
      elif tlist[j+1]<=tt:
        tmp=min(tmp,arr2[j]+(tt-tlist[j+1]))
      else:
        tmp=min(tmp,arr2[j])
    tmp=min(tmp,tt)
    tmp=min(tmp,t-tt)
    ans+=tmp
  print(ans/2)
solve()
### BUGGY CODE ###

def C_Good_Sequence():
    N=int(input())
    a=list(map(int, input().split()))
    b=set(a)
    b=list(b)
    count=0
    ans=0 
    c=[]
    
    for i in b:
        for j in range(N):
            if a[j]==i:
                count += 1
        c.append(count)
        count=0

    for i in range(len(b)):
        if c[i]<b[i]:
            ans += c[i]
        elif c[i] >b[i]:
            ans += c[i]-b[i]
    print(ans)
   
C_Good_Sequence()

### FIXED CODE ###

def C_Good_Sequence():
    N=int(input())
    a=list(map(int, input().split()))
    count={}
    ans=0
    
    for num in a:
        count[num]= count.get(num,0)+1

    for num in count:
        if num > count[num]:
            ans += count[num]
        elif num < count[num]:
            ans += count[num]-num
    
    print(ans)
   
C_Good_Sequence()
### BUGGY CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
for k in range(41):
    B = [0] * N
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        B[l] += 1
        if r + 1 < N: B[r + 1] -= 1
    for i in range(1, N): B[i] += B[i-1]
    A = B
    if k == K - 1: break
print(*A)

### FIXED CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
for k in range(41):
    B = [0] * N
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        B[l] += 1
        if r + 1 < N: B[r + 1] -= 1
    for i in range(1, N): B[i] += B[i-1]
    A = B
    if k == K - 1: break
print(*A)
### BUGGY CODE ###

n=int(input())
s=input()

rgb=['R','G','B']
cnt=0
for i in range(len(s)):
  if s[i]==rgb[0]:
    for j in range(i+1,len(s)):
      if s[j]==rgb[1]:
        for h in range(j+1,len(s)):
          if h-j!=j-i:
            if s[h]==rgb[2]:
              cnt+=1
        
      elif s[j]==rgb[2]:
        for h in range(j+1,len(s)):
          if h-j!=j-i:
            if s[h]==rgb[1]:
              cnt+=1
              
  elif s[i]==rgb[1]:
    for j in range(i+1,len(s)):
      if s[j]==rgb[0]:
        for h in range(j+1,len(s)):
          if h-j!=j-i:
            if s[h]==rgb[2]:
              cnt+=1
        
      elif s[j]==rgb[2]:
        for h in range(j+1,len(s)):
          if h-j!=j-i:
            if s[h]==rgb[0]:
              cnt+=1
              
  elif s[i]==rgb[2]:
    for j in range(i+1,len(s)):
      if s[j]==rgb[1]:
        for h in range(j+1,len(s)):
          if h-j!=j-i:
            if s[h]==rgb[0]:
              cnt+=1
        
      elif s[j]==rgb[0]:
        for h in range(j+1,len(s)):
          if h-j!=j-i:
            if s[h]==rgb[1]:
              cnt+=1
              
print(cnt)

### FIXED CODE ###


n=int(input())
s_=input()
r, g, b = s_.count("R"), s_.count("G"), s_.count("B")
rgb = r * g * b
cnt=0
for i in range(len(s_)):
  for j in range(i+1,len(s_)):
    h=j-i+j
    if h<n:
      if s_[i]!=s_[j] and s_[h]!=s_[j] and s_[i]!=s_[h]:
        cnt+=1

print(rgb-cnt)
### BUGGY CODE ###



S = input()
l = len(S)
S = S[::-1]
dp =[[0 ] * 13 for _ in range(l + 1)]
kurai = 1
MOD = (10 ** 9) + 7
dp[0][0] = 1

for keta in range(len(S)):
    c =S[keta]

    if c == "?":
        for j in range(0,10):
            kurai %= 13
            temp = (j * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13] += (dp[keta][i] )
                dp[keta + 1][(temp + i) % 13] %= MOD
    else:
        temp = (int(c) * kurai) % 13
        for i in range(13):
            dp[keta + 1][(temp + i) % 13]  += (dp[keta][i] )
            dp[keta + 1][(temp + i) % 13] %= MOD
    kurai *= 10
    keta %= MOD
print(dp[-1][5] % MOD)



### FIXED CODE ###


import sys

S =  sys.stdin.readline()[:-1]
l = len(S)
# S = S[::-1]
S = list(reversed(S))

dp =[[0 ] * 13 for _ in range(l + 1)]
kurai = 1
MOD = (10 ** 9) + 7
dp[0][0] = 1

for keta in range(len(S)):
    c =S[keta]

    if c == "?":
        for j in range(0,10):
            kurai %= 13
            temp = (j * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13] += (dp[keta][i] )
                dp[keta + 1][(temp + i) % 13] %= MOD
    else:
        kurai %= 13

        temp = (int(c) * kurai) % 13
        for i in range(13):
            dp[keta + 1][(temp + i) % 13]  += (dp[keta][i] )
            dp[keta + 1][(temp + i) % 13] %= MOD
    kurai *= 10
    keta %= MOD
print(dp[-1][5] )
### BUGGY CODE ###

import sys
import copy
sys.setrecursionlimit(10**6)
N,M=map(int,input().split())

D=[]
P=[[i,0]for i in range(N+1)]
C=[1 for i in range(N+1)]
A=[0]

for i in range(M):
    l,r,d=map(int,input().split())
    P[r]=[l,d]
    D.append([l,r,d])
#print(P)
def find(a,b):
    if c[a]==0:
        return a,b
    elif a==P[a][0]:
        return a,b
    else:
        c[a]=0
        return find(P[a][0],b+P[a][1])
for i in range(1,N+1):
    c=copy.deepcopy(C)
    A.append(find(i,0))
#print(A)
for i in range(M):
    if A[D[i][1]][1]-A[D[i][0]][1]!=D[i][2]:
        print("No")
        exit()
print("Yes")


### FIXED CODE ###

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

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

L=[[]for i in range(N+1)]
D=dict()
for i in range(M):
    l,r,d=map(int,input().split())
    L[l].append([r,d])
    L[r].append([l,-d])
    D[i]=(l,r,d)
    
C=["N" for i in range(N+1)]

def dfs(x):
    for i,j in L[x]:
        if C[i]=="N":
            C[i]=C[x]+j
            dfs(i)

for i in range(1,N+1):
    if C[i]=="N":
        C[i]=0
        dfs(i)
#print(C)
#print(D)
for i in range(M):
    l,r,d=D[i]
    if C[r]-C[l]!=d:
        print("No")
        exit()
print("Yes")
### BUGGY CODE ###

import numpy as np
in1=list(map(int,input().split(" ")))
#print(in1)
#arr=np.zeros((in1[0],in1[1]))
d={}
for i in range(in1[0]):
    #arr[i]=input().split(" ")
    for n,k in enumerate(input().split(" ")):
        d[int(k)]=[i,n]
#print(arr)
Q=int(input())
test=[]
out=[]
route={}
for k in range(Q):
    ans=0
    start,end=list(map(int,input().split(" ")))
    #place=np.where(arr==start)
    place=d[start]
    #print(start,end)
    while start != end:
        #print("ans",ans)
        #nextplace=np.where(arr==start+in1[2])#[1][0]
        if start in route:
            nextplace=d[start+in1[2]]
        else:
            nextplace=d[start+in1[2]]
            ans1=abs(int(nextplace[0])-int(place[0]))
            ans2=abs(int(nextplace[1])-int(place[1]))
            route[start]=ans1+ans2
        ans+=route[start]
        start+=in1[2]
        place=nextplace

    print(ans)
    #out.append(ans)
#for i in out:
    #print(i)


### FIXED CODE ###

import numpy as np
H, W, D=list(map(int,input().split(" ")))
#print(in1)
#arr=np.zeros((in1[0],in1[1]))
d={}
for i in range(H):
    #arr[i]=input().split(" ")
    for n,k in enumerate(input().split(" ")):
        d[int(k)]=[i,n]
#print(arr)
Q=int(input())
out=[]

cost={}

for i in range(1,D+1):
    now = i + D
    cost[i]=0
    #cost[i]=abs(d[now][0] - d[now - D][0]) + abs(d[now][1] - d[now - D][1])
    while now <= H * W:
        cost[now] = cost[now - D] + abs(d[now][0] - d[now - D][0]) + abs(d[now][1] - d[now - D][1])
        now += D


out=[]
for k in range(Q):
    start,end=list(map(int,input().split(" ")))
    out.append(cost[end]-cost[start])

for i in out:
    print(int(i))
### BUGGY CODE ###

#!/usr/bin/env python3

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))[::-1]

if N == 1:
    print(A[0]//2**M)
    exit()

cnt = 0
while M > 0:
    m = 1
    while True:
        if A[0]//2**m < A[1]:
            break
        else:
            m += 1
    if M-m >= 0:
        A.append(A[0]//2**m)
        M -= m
        cnt += m
    else:
        A.append(A[0]//2**M)
        M = 0
        cnt += M
    A.pop(0)
    A = sorted(A)[::-1]

print(sum(A))


### FIXED CODE ###

#!/usr/bin/env python3
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: x*(-1), A))  # 各要素を-1倍

heapq.heapify(A)

if N == 1:
    MAX = heapq.heappop(A)//2**M 
    if MAX < 0:
        print(0)
    else:
        print(MAX)
    exit()

cnt = 0
while M > 0:
    MAX = heapq.heappop(A)
    if MAX % 2 == 0:
        heapq.heappush(A, MAX//2)
    else:
        heapq.heappush(A, MAX//2+1)

    M -= 1

print(-sum(A))
### BUGGY CODE ###

from bisect import bisect
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    S = input()

    rgb = {'R': [], 'G': [], 'B': []}
    apnd_r = rgb['R'].append
    apnd_g = rgb['G'].append
    apnd_b = rgb['B'].append
    for i, s in enumerate(S):
        if s == 'R':
            apnd_r(i)
        elif s == 'G':
            apnd_g(i)
        else:
            apnd_b(i)

    def count_(s1, s2):
        ret = 0
        x = bisect(rgb[s1], i)
        for j in rgb[s1][x:]:
            y = bisect(rgb[s2], j)
            d = j - i
            if j + d < N and S[j+d] == s2:
                ret += len_[s2] - y - 1
            else:
                ret += len_[s2] - y
        return ret

    ans = 0
    len_ = {'R': len(rgb['R']), 'G': len(rgb['G']), 'B': len(rgb['B'])}
    for i, s in enumerate(S):
        if s == 'R':
            for s1, s2 in (('G', 'B'), ('B', 'G')):
                ans += count_(s1, s2)
        elif s == 'G':
            for s1, s2 in (('R', 'B'), ('B', 'R')):
                ans += count_(s1, s2)
        else:
            for s1, s2 in (('R', 'G'), ('G', 'R')):
                ans += count_(s1, s2)
    print(ans)


main()


### FIXED CODE ###

from bisect import bisect
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    S = input()

    rgb = {'R': [], 'G': [], 'B': []}
    for i, s in enumerate(S):
        rgb[s].append(i)

    def count_(s1, s2):
        ret = 0
        x = bisect(rgb[s1], i)
        for j in rgb[s1][x:]:
            y = bisect(rgb[s2], j)
            d = j - i
            if j + d < N and S[j+d] == s2:
                ret += len_[s2] - y - 1
            else:
                ret += len_[s2] - y
        return ret

    ans = 0
    len_ = {'R': len(rgb['R']), 'G': len(rgb['G']), 'B': len(rgb['B'])}
    for i, s in enumerate(S):
        if s == 'R':
            for s1, s2 in (('G', 'B'), ('B', 'G')):
                ans += count_(s1, s2)
        elif s == 'G':
            for s1, s2 in (('R', 'B'), ('B', 'R')):
                ans += count_(s1, s2)
        else:
            for s1, s2 in (('R', 'G'), ('G', 'R')):
                ans += count_(s1, s2)
    print(ans)


main()
### BUGGY CODE ###

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

b = [str(a[0])]
if (n == 1):
    print(a[0])
    exit()

a = a[1:]

for i in a:
    b.append(str(i))
    b.reverse()


print(' '.join(b))


### FIXED CODE ###

n = int(input())
a = list(map(str, input().split()))
b = []
'''
b = [str(a[0])]
if (n == 1):
    print(a[0])
    exit()

a = a[1:]

for i in a:
    b.append(str(i))
    b.reverse()
'''
'''
loop = int(n / 2)
loop_rest = n - loop

for i in range(loop):
    tar_index = (n - 1) - 2 * i
    tar = a[tar_index]

    b.append(str(tar))


if (n % 2 == 0):
    tar_index = 0
else:
    tar_index = 1

for i in range(loop_rest):
    b.append(str(a[tar_index]))
    tar_index += 2
'''

# 一つおきでListを取る場合。
# a[0::2]
# 1つ目：起点。
# 2つ目：Step

# a[::-1]
# > -1step,つまりReverse

if n % 2 == 1:
    print(" ".join((a[0::2][::-1] + a[1::2])))
else:
    print(" ".join((a[1::2][::-1] + a[0::2])))
### BUGGY CODE ###

s = input()
q = int(input())
X = [list(input().split()) for _ in range(q)]

flag = 0
for x in X:
    if int(x[0]) == 1:
        # s = s[::-1]
        if flag ==0:
            flag = -1
        else:
            flag = 0
        continue
    if int(x[1]) +flag == 1:
        s = x[2] +s
    else:
        s = s +x[2]
if flag == -1:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())

header = []
footer = []
flag = 0
for i in range(q):
    x = list(input().split())
    if int(x[0]) == 1:
        if flag ==0:
            flag = -1
        else:
            flag = 0
        continue
    if int(x[1]) +flag == 1:
        header.append(x[2])
        # s2 = deque(s)
        # # s.insert(0, x[2])
        # s2.appendleft(x[2])
        # s = list(s2)
    else:
        # s.append(x[2])
        footer.append(x[2])
# ans = ''.join(s)
head = ''.join(reversed(header))
ans = head +s + ''.join(footer)
if flag == -1:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect

mod = 10**9 + 7

if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    ans = 0
    for i in range(n):
        for j in range(i+1,n):
            d = a[i]*a[j]
            d = d%mod
            ans += d
            ans%=mod
    print(ans)

### FIXED CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect

mod = 10**9 + 7

if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    a.sort()
    prefix = [a[0]]
    for i in range(1,n):
        prefix.append(prefix[i-1] + a[i])
    ans = 0
    for i in range(n-1):
        d = (a[i]*(prefix[-1] - prefix[i]))%mod
        ans = ans + d
        ans = ans%mod
    print(ans)
### BUGGY CODE ###

a, b = (int(i) for i in input().split())
 
for i in range(0, 10**9):
  if (a-i) == (b-i):
    print(i)
    break
    
print("IMPOSSIBLE")

### FIXED CODE ###

a, b = (int(i) for i in input().split())
 
if a % 2 != b % 2:
  print("IMPOSSIBLE")
else:
  print(int((a+b) / 2))
### BUGGY CODE ###

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

L = [0,0,0]
for i in range(N):
    if S[i] == "R":
        L[0] +=1
    elif S[i] == "G":
        L[1] +=1
    else:
        L[2] +=1

Ans = L[0]*L[1]*L[2]

for i in range(N):
  s = S[i]
  for j in range(i+1,N):
    t = S[j]
    if s != t:
      k = 2*j-i
      if k <= N-1:
        u = S[k]
        if t != u and u != s:
          Ans -=1
print(Ans)

### FIXED CODE ###

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

L = [0,0,0]
for i in range(N):
    if S[i] == "R":
        L[0] +=1
    elif S[i] == "G":
        L[1] +=1
    else:
        L[2] +=1

Ans = L[0]*L[1]*L[2]

for i in range(N):
  s = S[i]
  n = min(N, (N+i)//2 + 1)
  for j in range(i+1,n):
    t = S[j]
    if s != t:
      k = 2*j-i
      if k <= N-1:
        u = S[k]
        if t != u and u != s:
          Ans -=1
print(Ans)