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

# -*- coding: utf-8 -*-
"""
Created on Tue Jun 23 21:04:33 2020

@author: naoki
"""

N = int(input()) # input the row A length "N" 
A = list(map(int,input().split())) # input the row of A 
Q = int(input()) # input the number of trying operation 
BC = [list(map(int,input().split())) for i in range(Q)]
S = 0 
for i in A:
    S += i# Sum of all conponents of the row "A"
for B,C in BC:
    count = 0 # renewing count 
    count = A.count(B) # counting the number of "B"
    A = [C if i == B else i for i in A]   # changing B to C  
    S = S + (C - B) * count 
    print(S)



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jun 23 21:04:33 2020

@author: naoki
"""

N = int(input()) # input the row A length "N" 
A = list(map(int,input().split())) # input the row of A 
Q = int(input()) # input the number of trying operation 
BC = [list(map(int,input().split())) for i in range(Q)]
S = 0
num = [0 for i in range(100001)] 
for i in A:
    S += i # Sum of all conponents of the row "A"
    num[i]+=1 

for B,C in BC:
    S = S + (C - B) * num[B]
    num[C] += num[B]
    num[B] = 0 
    print(S)
### BUGGY CODE ###

[n,k] = [int(i) for i in input().split()]
p = [(int(i)+1)/2 for i in input().split()]
ls = [0]
ex = [0]
mx = 1001

a = []
#print(a)
ans = -1
ruiseki = []
for i in range(n-k+1):
    ruiseki.append(sum(p[i:i+k]))
print(max(ruiseki))


### FIXED CODE ###

[n,k] = [int(i) for i in input().split()]
p = [(int(i)+1)/2 for i in input().split()]
sm_l = [0]
#sm_r = [0]
for i in range(n):
	sm_l.append(sm_l[-1] + p[i])
	#sm_r.append(sm_r[-1] + p[-i-1])
ans = 0
for i in range(n-k+1):
	ans = max(ans,sm_l[i+k]-sm_l[i])
print(ans)
### BUGGY CODE ###

import itertools

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)

cnt = 0

for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if L[i] < L[j] + L[k]:
                cnt += 1
            else:
                break

print(cnt)

### FIXED CODE ###

import math
import itertools
import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
cnt = 0
for i in range(N):
    for j in range(i+1, N):
        cnt += bisect.bisect_left(L[j+1:N], L[i]+L[j])
        
print(cnt)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
 
    N = int(input())
 
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        G[u].append(v)
        G[v].append(u)
 
    connect = [len(g) for g in G]
 
    #根を0として木を構築
    root = 0
    stack = [root]
    order = []
    lst = [0] * N
    while len(stack) != 0:
        tmp = stack.pop()
        order.append(tmp)
        for to in G[tmp]:
            if to == lst[tmp]:
                continue
            lst[to] = tmp
            stack.append(to)
        
    dp1 = [0] * N
    for v in order[::-1]:
        d = connect[v]
        if v != root and d == 1:
            continue
        x = sum(dp1[c] for c in G[v])
        if v == root:
            dp1[v] = x/connect[v] + 1
        else:
            dp1[v] = x/(connect[v] - 1) + 1
 
    dp2 = [0] * N
    for v in order:
        d = connect[v]
        n_child = d if v == root else d - 1
        S = dp1[v] * n_child
        if v != root:
            S += dp2[v] + 1
        for c in G[v]:
            if c == lst[v]:
                continue
            if d == 1:
                dp2[c] = 0
            else:
                dp2[c] = (S - dp1[c] - 1)/(d - 1)
 
    ans = []
    for v in range(N):
        d = connect[v]
        n_child = d if v == root else d - 1
        S = dp1[v] * n_child
        if v != root:
            S += dp2[v] + 1
        ans.append(S/d)
 
    print (*ans, sep = '\n')
 
    # print (dp1)
    # print (dp2)
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
 
    N = int(input())
 
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        G[u].append(v)
        G[v].append(u)
 
    connect = [len(g) for g in G]
 
    #根を0として木を構築
    root = 0
    stack = [root]
    order = []
    lst = [0] * N
    while len(stack) != 0:
        tmp = stack.pop()
        order.append(tmp)
        for to in G[tmp]:
            if to == lst[tmp]:
                continue
            lst[to] = tmp
            stack.append(to)
        
    dp1 = [0] * N
    for v in order[::-1]:
        d = connect[v]
        if v != root and d == 1:
            continue
        x = sum(dp1[c] for c in G[v])
        if v == root:
            dp1[v] = x/connect[v] + 1
        else:
            dp1[v] = x/(connect[v] - 1) + 1
 
    dp2 = [0] * N
    for v in order:
        d = connect[v]
        n_child = d if v == root else d - 1
        S = dp1[v] * n_child
        if v != root:
            S += dp2[v] + 1
        for c in G[v]:
            if c == lst[v]:
                continue
            if d == 1:
                dp2[c] = 0
            else:
                dp2[c] = (S - dp1[c] - 1)/(d - 1)
 
    ans = []
    for v in range(N):
        d = connect[v]
        n_child = d if v == root else d - 1
        S = dp1[v] * n_child
        if v != root:
            S += dp2[v] + 1
        ans.append(S/d)
 
    print (*ans, sep = '\n')
 
    # print (dp1)
    # print (dp2)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,K=map(int,input().split())
T=str(bin(K))
S=len(T)-2
A = list(map(int,input().split()))
lst=[[0 for e in range(N+1)] for f in range(S)]
for i in range(1,N+1):
 lst[0][i]=A[i-1]
for j in range(1,S):
 for i in range(1,N+1):
  lst[j][i]=lst[j-1][lst[j-1][i]]
ans=1
for k in range(S):
 if int(T[k+2])==1:
  ans=lst[S-1-k][ans]
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
T=str(bin(K))
S=len(T)-2
A = list(map(int,input().split()))
lst=[[0 for e in range(N+1)] for f in range(S)]
for i in range(1,N+1):
 lst[0][i]=A[i-1]
for j in range(1,S):
 for i in range(1,N+1):
  lst[j][i]=lst[j-1][lst[j-1][i]]
ans=[[e for e in range(N+1)] for f in range(S+1)]
for k in range(S):
 if int(T[k+2])==1:
  for l in range(1,N+1):
   ans[k+1][l]=lst[S-1-k][ans[k][l]]
 else:
  for l in range(1,N+1):
   ans[k+1][l]=ans[k][l]
print(ans[S][1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import itertools
def main():
    N = int(input())
    A  = [int(i) for i in input().split()]
    ax = itertools.combinations(A, 2)
    ans = 0
    for a,b in ax:
        ans = (ans + a*b) % 1000000007
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
def main():
    N = int(input())
    A  = [int(i) for i in input().split()]
    #N = 100000
    #A = [i for i in range(1,100000)]
    sum_a = sum(A)% 1000000007
    ans = 0
    for i in range(N):
        sum_a = (sum_a - A[i])% 1000000007
        ans = (ans + sum_a*A[i] ) % 1000000007
        #print((sum_a-A[i])*A[i]/2 ,ans)
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
s = [i for i in range(1, N+1)]
s.sort(reverse=True)

print(sum(s[1:]))

### FIXED CODE ###

def main():
    N = int(input())
    res = N*(N-1)//2
    print(res)
    
main()
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
    tmp = a[i]
    a[i] = 0
    print(max(a))
    a[i] = tmp

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
sorted_a = []
for item in a:
    sorted_a.append(item)
sorted_a.sort(reverse=True)
for num in a:
    if num == sorted_a[0]:
        print(sorted_a[1])
    else:
        print(sorted_a[0])
### BUGGY CODE ###

R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
for i in range(1, R + 1):
    for j in range(1, C + 1):
        # k=0, horizontal and vertical transitions are allowed
        dp[i][j][0] = max(dp[i][j - 1][0], dp[i - 1][j][0], dp[i - 1][j][1],
                          dp[i - 1][j][2], dp[i - 1][j][3])

        # k=1~3, horizontal transition and picking up are allowed
        dp[i][j][3] = max(dp[i][j - 1][3], dp[i][j - 1][2] + items[i][j],
                          dp[i][j][2] + items[i][j])

        dp[i][j][2] = max(dp[i][j - 1][2], dp[i][j - 1][1] + items[i][j],
                          dp[i][j][1] + items[i][j])

        dp[i][j][1] = max(dp[i][j - 1][1], dp[i][j - 1][0] + items[i][j],
                          dp[i][j][0] + items[i][j])

print(max(dp[-1][-1]))


### FIXED CODE ###


R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

dp = [[0] * 4 for _ in range(C + 1)]
for i in range(1, R + 1):
    # Vertical transition
    for j in range(1, C + 1):
        dp[j][0] = max(dp[j])
        for k in range(1, 4):
            dp[j][k] = 0

    # Horizontal or picking-up transition
    for j in range(1, C + 1):
        for k in reversed(range(4)):
            dp[j][k] = max(dp[j][k], dp[j - 1][k])
            if items[i][j] and k < 3:
                dp[j][k + 1] = max(dp[j][k + 1], dp[j][k] + items[i][j])

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

import sys
sys.setrecursionlimit(2000000)


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

visited = [[-1] *(len(a[0])) for i in range(n)]
memo = [[0] * (n) for i in range(n)]
for i in range(n):
    for j in range(len(a[0])):
        memo[i][a[i][j]-1] = j
        
def solve(i, j, rec_times):
    if rec_times >= 10000:
        print(-1)
        exit()
    i_me = i
    j_me = j
    i_you = a[i_me][j_me] - 1
    j_you = memo[i_you][i_me]
    if j_me == 0 and j_you == 0:
        visited[i_me][j_me] = 1
        visited[i_you][j_you] = 1
        return 1
    
    if visited[i_me][j_me] > 0 and not visited[i_you][j_you] > 0:
        return max(visited[i_me][j_me], visited[i_you][j_you])
 
    if j_you == 0:
        day = solve(i_me, j_me - 1, rec_times + 1) + 1
    elif j_me == 0:
        day = solve(i_you, j_you - 1, rec_times + 1) + 1    
    else:
        day = max(solve(i_me, j_me - 1, rec_times + 1), solve(i_you, j_you - 1, rec_times + 1)) + 1
    visited[i_me][j_me] = day
    visited[i_you][j_you] = day
    return day
    
for i in range(n):
    solve(i, len(a[0]) - 1, 0)
ans = 0
for i in range(n):
    ans = max(ans,visited[i][-1])
print(ans)


### FIXED CODE ###

import time
s_time = time.time()


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

memo = {}
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    visited = [False] * n
    flag = False
    for i in range(n):
        if memo[i] == len(a[0]):
            continue
        if visited[i] or visited[a[i][memo[i]] - 1]:
            continue
        visited[i] = True
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            visited[a[i][memo[i]] - 1] = True
            flag = True
            tmp = memo[i]
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print(-1)
                exit()
        break
    if abs(s_time - time.time()) > 1.7:
        print(n*(n-1) //2)
        exit()
print(cnt)
### BUGGY CODE ###

def my_gcd(x, y):
    if x >= y:
        m = x
        n = y
    else:
        m = y
        n = x
    r = m % n
    while r:
        m = n
        n = r
        r = m % n
    return n

def _is_prime(n):
    for i in range(n - 1):
        if (i + 1) ** (n - 1) % n != 1:
            return False
    return True

a, b = map(int, input().split())
g = my_gcd(a, b)
count = 1
num = g
d = 2
while num > 1:
    if _is_prime(d):
        flag = True
        while not num % d:
            if flag:
                count += 1
                num = num // d
                flag = False
            else:
                num = num // d
        d += 1
    else:
        d += 1
print(count)

### FIXED CODE ###

def prime_decomposition(n):
    i = 2
    result = []
    while i ** 2 <= n:
        while not n % i:
            result.append(i)
            n //= i
        i += 1
    if n > 1:
        result.append(n)
    return result

a, b = map(int, input().split())
s = set(prime_decomposition(a))
t = set(prime_decomposition(b))
print(len(s & t) + 1)
### BUGGY CODE ###

import sys


def main():
    input = sys.stdin.readline
    n, q = map(int, input().split())
    s = input()
    li = [list(map(int, input().split())) for i in range(q)]

    for i, j in li:
        count = 0
        cache = s[i-1]
        for k in range(i, j):
            if cache == "A" and s[k] == "C":
                count += 1
            cache = s[k]
        print(count)



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.readline
    n, q = map(int, input().split())
    s = input()
    li = [map(int, input().split()) for i in range(q)]
    count = [0]*len(s)

    for i in range(1, len(s)):
        if s[i] == "C" and s[i-1] == "A":
            count[i] = count[i-1] + 1
        else:
            count[i] = count[i-1]
   
    for i, j in li:
        print(count[j-1] - count[i-1])


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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,K=map(int,readline().split())
A=list(map(lambda x: int(x)-1,readline().split()))

visited=[True]*N
visitednum=[]
now=0
cnt=0
while True:
    if visited[now]==False:
        break
    else:
        visited[now]=False
        visitednum.append(now)
        now=A[now]
        cnt+=1
loop=[]
while True:
    if now in loop:
        break
    loop.append(now)
    now=A[now]
if K<cnt:
    print(visitednum[K]+1)
else:
    t=(K-(len(visitednum)+len(loop)))%len(loop)
    print(loop[t]+1)

### FIXED CODE ###

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

num = 1
li = [1]
flag = [True] * n
flag[0] = False

for i in range(k):
    num = a[num-1]
    if flag[num-1]:
        li.append(num)
        flag[num-1] = False
    else:
        break

d = li.index(num)
ans = (k-d)%(len(li)-d)+d

print(li[ans])
### BUGGY CODE ###

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

MOD=int(10**9+7)

g=A[0]
for i in range(1, N):
    g = (g*A[i])//fractions.gcd(g, A[i])
ans=0
for i in range(N):
  ans+=(g//A[i])%MOD
  ans%=MOD
print(ans)

### FIXED CODE ###

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

MOD=10**9+7

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

g=A[0]
for i in range(1, N):
    g = g*A[i]//fractions.gcd(g, A[i])
ans=0
g%=MOD
for i in range(N):
  ans+=g*modinv(A[i],MOD)
  ans%=MOD
print(ans)
### BUGGY CODE ###

a, b = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
n = gcd(a, b)

def cd(num):
    k = []
    if num%2 == 0:
        k.append(2) 
    for i in range(1,num+1,2):
        if num%i == 0:
            if is_prime(i):
                k.append(i) 
    return k

def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True


gc = gcd(a,b)
c = cd(gc)

print(len(c))

### FIXED CODE ###

def f(n):
    res = set()
    for i in range(2, int(n ** 0.5)):
        if n % i: continue
        while not n % i: n //= i
        res.add(i)
    return res | {n}
 
a, b = map(int,input().split())
print(len(f(a) & f(b) | {1}))
### BUGGY CODE ###

maxd = 5000000001
nv, ne, r = [int(n) for n in input().split(' ')]
vertices = {k: {} for k in range(nv)}
for i in range(ne):
    s, t, w = [int(n) for n in input().split(' ')]
    vertices[s][t] = w

q = {v for v in vertices}
dist = {v: maxd for v in vertices}
dist[r] = 0

while len(q):
    min = maxd
    u = nv
    for v in q:
        if dist[v] <= min:
            min = dist[v]
            u = v

    q.remove(u)
    for v in vertices[u]:
        alt = dist[u] + vertices[u][v]
        if alt < dist[v]:
            dist[v] = alt

[print(d) if d < maxd else print("INF") for v, d in dist.items()]

### FIXED CODE ###

import heapq

nv, ne, r = map(int, input().split(' '))
vertices = [[] for i in range(nv)]
for i in range(ne):
    s, t, w = map(int, input().split(' '))
    vertices[s].append((t, w))

q = []
heapq.heappush(q, (0, r))

dist = [float('inf')] * nv
dist[r] = 0

while len(q):
    u = heapq.heappop(q)[1]

    for t, w in vertices[u]:
        alt = dist[u] + w
        if alt < dist[t]:
            dist[t] = alt
            heapq.heappush(q, (alt, t))

[print(d) if d < float('inf') else print("INF") for d in dist]
### BUGGY CODE ###

from collections import deque

n,k = map(int,input().split())
p = list(map(int,input().split()))
ave = deque([])
ans = 0

for i in range(n):
  ave.append((p[i]+1)/2)
  if len(ave) == k:
    ans = max(ans,sum(ave))
    ave.popleft()


print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
ave = []
ans = 0
tmp = 0

for i in range(n):
  ave.append((p[i]+1)/2)

for j in range(n):
  tmp += ave[j]
  if j >= k:
    tmp -= ave[j-k]
    
  ans = max(ans,tmp)


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

n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
h.sort()
ans=float("inf")
for i in range(len(h)-k+1):
	ma = max(h[i:i+k])
	mi = min(h[i:i+k])
	ans = min(ans,ma-mi)

print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
h.sort()
ans=float("inf")
for i in range(len(h)-k+1):
	ma = h[i+k-1]
	mi = h[i]
	ans = min(ans,ma-mi)

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

#https://atcoder.jp/contests/abc071/tasks/arc081_a
N = int(input())
A = list(map(int, input().split()))
A.sort()
tmp = [0,0]
for i in range(len(A)-1):
    if A[i] == A[i+1] and not A[i] in tmp:
        tmp.append(A[i])
ans = tmp[-1]*tmp[-2]
if A.count(tmp[-1]) >=4:
        ans = tmp[-1]*tmp[-1]
print(ans)

### FIXED CODE ###

#https://atcoder.jp/contests/abc071/tasks/arc081_a
N = int(input())
A = list(map(int, input().split()))
A.sort()
tmp = [0,0]
for i in range(len(A)-1):
    if A[i] == A[i+1] and not A[i] in tmp:
        tmp.append(A[i])
ans = tmp[-1]*tmp[-2]
if A.count(tmp[-1]) >=4:
        ans = tmp[-1]*tmp[-1]
print(ans)
### BUGGY CODE ###

s = input()
t = input()

LS = len(s)
LT = len(t)

dp = [['' for _ in range(LT + 1)] for _ in range(LS + 1)]
for i in range(1, LS + 1):
    for j in range(1, LT + 1):
        if s[i - 1] == t[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + s[i - 1]
        else:
            if len(dp[i - 1][j]) < len(dp[i][j - 1]):
                dp[i][j] = dp[i][j - 1]
            else:
                dp[i][j] = dp[i - 1][j]

print(dp[LS][LT])


### FIXED CODE ###

s = input()
t = input()

ls = len(s)
lt = len(t)

dp = [[0 for _ in range(lt + 1)] for _ in range(ls + 1)]  # dp[ls][lt] = LCS_length

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])

res = ''
i = ls
j = lt
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        res = s[i - 1] + res
        i -= 1
        j -= 1
print(res)
### BUGGY CODE ###

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

ans = 1

for i in range(N):
    ans *= A[i]

if ans > 1000000000000000000:
    ans = -1

print(ans)


### FIXED CODE ###

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

ans = 1

if 0 in A:
    print(0)
    exit()

for i in range(N):
    ans *= A[i]

    if ans > 10**18:
        ans = -1
        break

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

from functools import reduce

n = int(input())
a = [int(arg) for arg in input().split()]
res = reduce(lambda x, y: x*y, a)
print(res if res <= 10**18 else -1)


### FIXED CODE ###

n = int(input())
a = [int(arg) for arg in input().split()]
res = 1
if 0 in a:
    print(0)
    exit()

for i in a:
    res *= i
    if res > 10**18:
        res = -1
        break
print(res)
### BUGGY CODE ###

n=int(input())
s=input()
r=[]
g=[]
b=[]
for i in range(n):
  if s[i]=='R':
    r.append(i)
  elif s[i]=='G':
    g.append(i)
  else:
    b.append(i)
ans=len(r)*len(g)*len(b)
for i in g:
  for j in b:
    a=i+j
    if a%2==0 and (a//2 in r):
      ans-=1
for i in r:
  for j in b:
    a=i+j
    if a%2==0 and (a//2 in g):
      ans-=1
for i in g:
  for j in r:
    a=i+j
    if a%2==0 and (a//2 in b):
      ans-=1
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
s=input()
r=[]
g=[]
b=[]
for i in range(n):
  if s[i]=='R':
    r.append(i)
  elif s[i]=='G':
    g.append(i)
  else:
    b.append(i)
ans=len(r)*len(g)*len(b)
r.append(n*4)
g.append(n*4)
b.append(n*4)
for i in g:
  for j in b:
    a=i+j
    if a%2==0 and r[bisect.bisect_left(r, a//2)]==a//2:
      ans-=1
for i in r:
  for j in b:
    a=i+j
    if a%2==0 and g[bisect.bisect_left(g, a//2)]==a//2:
      ans-=1
for i in g:
  for j in r:
    a=i+j
    if a%2==0 and b[bisect.bisect_left(b, a//2)]==a//2:
      ans-=1
print(ans+3)
### BUGGY CODE ###

S = input()
ans = 0
if S.count('W') == 0 or S.count('B') == 0:
    print(0)
    exit()
a = S[0]
while True:
    for i, s in enumerate(S):
        if s != a: break
    S = S[i:]
    a = S[0]
    ans += 1
    if S.count('W') == 0 or S.count('B') == 0:break
print(ans)

### FIXED CODE ###

from collections import Counter
S = input()
ans = 0
c = Counter(S)
if c['W'] == 0 or c['B'] == 0:
    print(0)
    exit()
a = S[0]
while True:
    for i, s in enumerate(S):
        if s != a: break
    S = S[i:]
    c[a] -= i
    a = S[0]
    ans += 1
    if c['W'] == 0 or c['B'] == 0:break
print(ans)
### BUGGY CODE ###

n, p = map(int, input().rstrip().split())
s = input().rstrip()

if p == 2 or p == 5:
    ans = 0
    s = map(int, s)
    for i, c in enumerate(s):
        if c % p == 0:
            ans += i + 1
    print(ans)
else:
    s = s[::-1]
    cnt = [0] * p
    k = 0
    cnt[k] = 1
    w = 1
    for i, c in enumerate(map(int, s)):
        k = (c * w + k) % p
        cnt[k] += 1
        w *= 10

    ans = 0
    for i in range(p):
        ans += cnt[i] * (cnt[i] - 1) // 2
    print(ans)


### FIXED CODE ###

n, p = map(int, input().rstrip().split())
s = input().rstrip()

if p == 2 or p == 5:
    ans = 0
    s = map(int, s)
    for i, c in enumerate(s):
        if c % p == 0:
            ans += i + 1
    print(ans)
else:
    s = s[::-1]
    cnt = [0] * p
    k = 0
    cnt[k] = 1
    w = 1
    for i, c in enumerate(map(int, s)):
        k = c * w + k
        w *= 10
        while k >= p:
            k -= p
        while w >= p:
            w -= p
        cnt[k] += 1

    ans = 0
    for i in range(p):
        ans += cnt[i] * (cnt[i] - 1) // 2
    print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [0 for _ in range(m)]
b = [0 for _ in range(m)]

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

go = []

for i in range(len(a)):
    if (a[i] == 1):
        go.append(b[i])
        a[i],b[i] == 0,0
u = 0
t = len(a)
while(u < t):
    if a[u] == 0:
        del(a[u])
        del(b[u])
        t -= 1
    if b[u] != n:
        del(a[u])
        del(b[u])
        t -= 1
    u += 1

for i in range(len(go)):
    for j in range(len(a)):
        if(go[i] == a[j]):
            if(b[j] == n):
                print("POSSIBLE")
                exit()

print("IMPOSSIBLE")

### FIXED CODE ###

n,m = map(int,input().split())
a = [0 for _ in range(m)]
b = [0 for _ in range(m)]

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

go = []
goal = []

for i in range(len(a)):
    if a[i] == 1:
        go.append(b[i])
    if b[i] == n:
        goal.append(a[i])

count = [0 for i in range(n)]
for i in range(len(go)):
    count[go[i]-1] = 1
for i in range(len(goal)):
    count[goal[i]-1] += 1
for i in range(len(count)):
    if count[i] > 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")