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

# coding: utf-8
import sys
sysread = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10**6)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        to[a].append(b)
        to[b].append(a)
    block = [[] for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        block[c].append(d)
        block[d].append(c)

    stack = defaultdict(lambda:[])
    visited = [False] * (N+1)

    def dfs(n, tree= None):
        visited[n] = True
        if tree==None:
            tree = n
        stack[tree].append(n)
        for next in to[n]:
            if not visited[next]:
                dfs(next, tree)
        return None

    while True:
        k = -1
        for i in range(1,N+1):
            if not visited[i]:
                k = i
                break
        if k == -1:break
        dfs(k)

    candidates = [0] * (N+1)

    for tree in stack.keys():
        for k in stack[tree]:
            check_list = to[k] + block[k] + [k]
            s = [k_ for k_ in stack[tree] if not k_ in check_list]
            candidates[k] = len(s)

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10**7)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    n_to = [0 for _ in range(N + 1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        #a,b = AB[i]
        to[a].append(b)
        n_to[a] += 1
        to[b].append(a)
        n_to[b] += 1

    stack = defaultdict(lambda:0)
    visited = [False] * (N+1)
    belong = [None] * (N+1)


    def dfs(n):
        _stack = [n]
        visited[n] = True
        while _stack:
            node = _stack.pop()
            stack[n] += 1
            belong[node] = n
            for next in to[node]:
                if not visited[next]:
                    _stack.append(next)
                    visited[next] = True
        return None


    for i in range(1,N+1):
        if not visited[i]:
            dfs(i)

    block = [0 for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        #c, d = CD[i]
        if belong[c] == belong[d]:
            block[c] += 1
            block[d] += 1

    candidates = [0] * (N+1)

    for k in range(1,N+1):
        tr = belong[k]
        candidates[k] = stack[tr] - 1 - n_to[k] - block[k]

    print(' '.join(map(str, candidates[1:])))

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

MOD = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0 for j in range(13)] for i in range(n + 1)]
dp[0][0] = 1
dpi = dp[0]
for i, si in enumerate(s):
    dpi1 = dp[i + 1]
    if si == '?':
        k_list = range(10)
    else:
        k_list = [int(si)]
    for j in range(13):
        xij = dpi[j]
        for k in k_list:
            dpi1[(j * 10 + k) % 13] += xij
    for j in range(13):
        dpi1[j] %= MOD
    dpi = dpi1
print(dp[-1][5])


### FIXED CODE ###

MOD = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0 for j in range(13)] for i in range(n + 1)]
dp[0][0] = 1
dpi = dp[0]
for i, si in enumerate(s):
    dpi1 = dp[i + 1]
    if si == '?':
        k_list = range(10)
    else:
        k_list = [int(si)]
    for j in range(13):
        xij = dpi[j]
        for k in k_list:
            dpi1[(j * 10 + k) % 13] += xij
    for j in range(13):
        dpi1[j] %= MOD
    dpi = dpi1
print(dp[-1][5])
### BUGGY CODE ###

import sys

N, M, K = [int(s) for s in sys.stdin.readline().split()]
n = 0
A = [0]
for s in sys.stdin.readline().split():
    n = n + int(s)
    A.append(n)

n = 0
B = [0]
for s in sys.stdin.readline().split():
    n = n + int(s)
    B.append(n)

ans = 0
for i in range(N + 1):
    if A[i] > K:
        break
    for j in range(M, -1, -1):
        if A[i] + B[j] <= K:
            ans = max(ans, i + j)
            break

print(ans)

### FIXED CODE ###

import sys

N, M, K = [int(s) for s in sys.stdin.readline().split()]
n = 0
A = [0]
for s in sys.stdin.readline().split():
    n = n + int(s)
    A.append(n)

n = 0
B = [0]
for s in sys.stdin.readline().split():
    n = n + int(s)
    B.append(n)

ans = 0
for i in range(N + 1):
    if A[i] > K:
        break
    for j in range(M, -1, -1):
        if A[i] + B[j] <= K:
            ans = max(ans, i + j)
            M = j
            break

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

a = int(input())

x = dict()
x[0] = 0
x[1] = 1
x[2] = 2
x[3] = 3
x[4] = 4
x[5] = 5
x[6] = 5
x[7] = 4
x[8] = 3
x[9] = 2
x[10] = 1
x[11] = 2
x[12] = 3
x[13] = 4
x[14] = 5
x[15] = 6
x[16] = 6
x[17] = 5
x[18] = 4
x[19] = 3
x[20] = 2

def dp(n):
    if n in x:
        return x[n]
    else:
        if 10**len(str(n)) - n < n:
            x[n] = min(dp(10**len(str(n)) - n) + 1, int(str(n)[0]) + dp(int(str(n)[1:])))
        else:
            x[n] = int(str(n)[0]) + dp(int(str(n)[1:]))
        return x[n]

print(dp(a))

### FIXED CODE ###

S = input()
n = len(S)
dp = [[0] * 2 for _ in range(n+1)]
 
dp[0][0] = 0
dp[0][1] = 1
for i in range(n):
    dp[i+1][0] = min(int(S[i]) + dp[i][0], 10 - int(S[i]) + dp[i][1])
    dp[i+1][1] = min(int(S[i]) + 1 + dp[i][0], 10 - int(S[i]) - 1 + dp[i][1])    
 
print(dp[n][0])
### BUGGY CODE ###

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

t = [0] * q
f = [0] * q
c = [""] * q

for i in range(q):
    lis = list(input().split())
    t[i] = int(lis[0])
    if t[i] == 2:
        f[i] = int(lis[1])
        c[i] = lis[2]

idx = 0
while idx < q:
    if t[idx] == 1:
        flip = True
        while idx + 1 < q and t[idx + 1] == 1:
            idx += 1
            flip = not flip
        if flip:
            s = s[::-1]
    else:
        if f[idx] == 1:
            ch = c[idx]
            while idx + 1 < q and t[idx + 1] == 2 and f[idx + 1] == 1:
                idx += 1
                ch = c[idx] + ch
            s = ch + s
        else:
            ch = c[idx]
            while idx + 1 < q and t[idx + 1] == 2 and f[idx + 1] == 2:
                idx += 1
                ch = ch + c[idx]
            s = s + ch
    idx += 1

print(s)



### FIXED CODE ###

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

t = [0] * q
f = [0] * q
c = [""] * q

for i in range(q):
    lis = list(input().split())
    t[i] = int(lis[0])
    if t[i] == 2:
        f[i] = int(lis[1])
        c[i] = lis[2]

idx = 0

p = ""
while idx < q:
    if t[idx] == 1:
        s, p = p, s
    else:
        if f[idx] == 1:
            p += c[idx]
        else:
            s += c[idx]
    idx += 1

p = p[::-1]
s = p + s
print(s)
### BUGGY CODE ###

N,Q=map(int,input().split())
Ss=[i for i in input()]
#S = input()
for i in range(Q):
    l,r = map(int,input().split())
    count = 0
    Sscopy = Ss[l-1:r]
    ans=0
    while True:
        #print(count)
        #print(ans)
        #print(Sscopy)
        if "A" not in Sscopy[ans:]:
            break
        else:
            indexnumber = Sscopy.index("A",ans)
            if indexnumber == len(Sscopy)-1:
                break
            if Sscopy[indexnumber+1]=="C":
                ans = indexnumber+1
                count+=1
        #print("========================")
    print(count)

### FIXED CODE ###

N,Q=map(int,input().split())
Ss=[i for i in input()]
counterlist=[0]*N
for s in range(len(Ss)-1):
    if Ss[s]=="A" and Ss[s+1]=="C":
        counterlist[s+1]=1
for c in range(len(counterlist)-1):
    counterlist[c+1]+=counterlist[c]
for i in range(Q):
    l,r = map(int,input().split())
    print(counterlist[r-1]-counterlist[l-1])
### BUGGY CODE ###

n=int(input())
hoge=list(map(int,input().split()))
for i in range(n):
  print(1+hoge.index(i+1),end=" ")
print(" ")

### FIXED CODE ###

n=int(input())
hoge=list(map(int,input().split()))
huga=[0]*n
for i in range(n):
  huga[hoge[i]-1]=i+1
for i in huga:
  print(i,end=" ")
print(" ")
### BUGGY CODE ###

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

for i in range(N-1):
    Q = P[0:i+2]
    if P[i+1] <= min(Q):
        c = c+1
    else:
        c = c
print(c)


### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
count = 0
leftmin = P[0]
for i in range(0, N):
    if leftmin >= P[i]:
        count += 1

    if leftmin > P[i]:
        leftmin= P[i]

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

n, m, _ = map(int, input().split())
n0 = n
exem = [1] * n0
i = 0

for a in map(int, input().split()):
    is_even = not a & 1
    a %= n
    if is_even: a = n - a
    c = 0
    while a:
        c += 1
        if exem[i - c]:
            a -= 1
    exem[i - c] = 0
    i = (i - c + 1) % n0
    n -= 1

for q in map(int, input().split()):
    print(exem[q])

### FIXED CODE ###

n, m, _ = map(int, input().split())
exem = list(range(n))
i = 0

for a in map(int, input().split()):
    is_odd = a & 1
    i += -a if a & 1 else a
    i %= n
    exem.pop(i)
    n -= 1

exem = set(exem)
for q in map(int, input().split()):
    print(int(q in exem))
### BUGGY CODE ###

N, M = map(int, input().split())
ab = []
for i in range(M):
    a, b = map(int, input().split())
    ab.append((a,b))
    
check_N = []
check_1 = []
for i in ab:
    if i[1] == N:
        check_N.append(i[0])
    if i[0] == 1:
        check_1.append(i[1])
        
flag = False
for i in check_1:
    if check_N.count(i) >= 1:
        flag = True
        break
        
if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

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

check_1 = []
check_N = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        check_1.append(b)
    if b == N:
        check_N.append(a)
        
if len(list(set(check_1) & set(check_N))) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

import math
n = int(input())
ls = list(map(int, input().split()))
ans = math.prod(ls)
if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

ans = 1
if 0 in num:
    print(0)
    exit()
else:
    for i in num:
        ans *= i
        if ans > 10**18:
            print(-1)
            exit()

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

from numba import jit
N, M = map(int, input().split())
def func(N, M):
  group = []
  tf = []
  for i in range(M):
    A, B = map(int, input().split())
    if A not in tf and B not in tf:
      tf.append(A)
      tf.append(B)
      group.append([A,B])
    else:
      if A in tf and B in tf:
        a, b = 0, 0
        for j in range(len(group)):
          if A in group[j]:
            a = j
            if b!=0:
              break
          elif B in group[j]:
            b = j
            if a!=0:
              break
        group[a].extend(group[b])
        del group[b]
      elif A not in tf:
        tf.append(A)
        for j in range(len(group)):
          if B in group[j]:
            group[j].append(A)
            break
      elif B not in tf:
        tf.append(B)
        for j in range(len(group)):
          if A in group[j]:
            group[j].append(B)
            break
  num = N - len(tf) 
  return len(group)+num-1
print(func(N,M))

### FIXED CODE ###

# Connect Cities
# Union Findデータ構造（素集合データ構造）
 
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())
 
#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
 
class UnionFind():
	"""docstring for UnionFind"""
	def __init__(self, n):
		self.parents = [-1]*n
 
	def find(self,x):
		if self.parents[x] < 0: #自分が親である時
			return x
		else: #自分が子供である時
			self.parents[x]=self.find(self.parents[x])
			return self.parents[x]
 
	def union(self,x,y):
		# 各要素の親要素を返す
		x=self.find(x)
		y=self.find(y)
 
		if x==y:
			return
		if self.parents[x] > self.parents[y]:
			x,y=y,x
 

		self.parents[y]=x

n,m=input2()
AB=[input_array() for _ in range(m)]
 
uf = UnionFind(n)
for ab in AB:
	a=ab[0]
	b=ab[1]
	uf.union(a-1,b-1)

ans=0
for i in uf.parents:
	if i < 0:
		ans+=1

print(ans-1)
### BUGGY CODE ###

import sys
n = int(input())
buttons = [0]
pushed = [0] * (n + 1)
ans = 0
for i in range(n):
  buttons.append(int(input()))
push = 1
while(push != 2):
  if ((buttons[push] not in buttons) or (pushed[push] == 1)):
    print(-1)
    sys.exit()
  else:
    pushed[push] = 1
    push = buttons[push]
    ans += 1
print(ans)

### FIXED CODE ###

import sys
n = int(input())
b = [0]
pushed = [0] * (n + 1)
for i in range(n):
  b.append(int(input()))
push = 1
cnt = 0
while(push != 2):
  if (pushed[push] != 1):
    pushed[push] = 1
    cnt += 1
    push = b[push]
  else:
    print(-1)
    sys.exit()
print(cnt)
### BUGGY CODE ###

a, b, n = map(int, input().split())
ans = 0
for i in range(n + 1):
    floor = int(a * i / b) - a * int(i / b)
    ans = max(ans,floor)
print(ans)

### FIXED CODE ###

a, b, n = map(int, input().split())
x = min(n, b - 1)
ans = int(a * x / b) - a * int(x / b)
print(ans)
### BUGGY CODE ###

s = list(input())
k = int(input())
n = len(s)
substring = []

for i in range(n):
    tmp = ""
    for l in s[i::]:
        tmp += l
        if tmp in substring:
            continue

        else:
            substring.append(tmp)

substring.sort()

print(substring[k - 1])


### FIXED CODE ###

s = list(input())
k = int(input())
n = len(s)
substring = []

for i in range(n):
    tmp = ""
    for l in s[i:i + k:]:
        tmp += l
        if tmp in substring:
            continue

        else:
            substring.append(tmp)

substring.sort()

print(substring[k - 1])
### BUGGY CODE ###

input_list = list(map(int, input().split()))
count = input_list[0]
y = input_list[1]

from math import floor

l_lim = floor(y / 10000)
m_lim = floor(y / 5000)
n_lim = floor(y / 1000)

flag = False
for l in range(l_lim + 1):
    for m in range(count - l + 1):
        for n in range(count - l - m + 1):
            if (l+m+n == count)&(10000 * l + 5000 * m + 1000 * n == y):
                print(l, m, n)
                flag = True
                break
        if flag:
            break
    if flag:
        break
if flag == False:
    print(-1, -1, -1)

### FIXED CODE ###

input_list = list(map(int, input().split()))
count = input_list[0]
y = input_list[1]
flag = False
for l in range(count + 1):
    for m in range(count - l + 1):
        n = count - l - m
        if 10000 * l + 5000 * m + 1000 * n == y:
            print(l, m, n)
            flag = True
            break
        if flag:
            break
    if flag:
        break
if flag == False:
    print(-1, -1, -1)
### BUGGY CODE ###

n = int(input())
# n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
# abc = [int(input()) for i in range(5)]
a.sort()
for i in range(1, n):
    a[i] %= a[0]
a.sort(reverse=True)
while a[1] != 0:
    min_idx = a.index(min(a))
    m = min(a[0:min_idx])
    for i in range(min_idx-1):
        a[i] %= m
    a.sort(reverse=True)
    
print(a[0])


### FIXED CODE ###

from fractions import gcd
from functools import reduce
# from collections import deque
# from math import factorial
# import collections
import math
import sys
sys.setrecursionlimit(2000000)
# import itertools
# import statistics
# import numpy as np
n = int(input())
# n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
# abc = [int(input()) for i in range(5)]


def gcd_list(numbers):
    return reduce(gcd, numbers)


print(gcd_list(a))
### BUGGY CODE ###

N=int(input())
count=0
a=list(map(int,input().split()))
for i in range(N-1):
  for j in range(i+a[i]+1,N):
    if j-i==a[i]+a[j]:
      count+=1
print(count)

### FIXED CODE ###

N=int(input())
count=0
a=list(map(int,input().split()))
w=[]
s=[]
num=[0]*N
maxi=max(a)
for i in range(N):
  s.append(1+i-a[i])
  if 1+i+a[i]<N:
    num[1+i+a[i]]+=1
for i in range(N):
  if s[i]>=0:
    count+=num[s[i]]
print(count)
### BUGGY CODE ###

r1,c1,r2,c2=map(int,input().split())

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p=10**9+7
N=10**7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

print((cmb(r2+1+c2+1,c2+1,p)-cmb(r1+c2+1,c2+1,p)-cmb(r2+1+c1,c1,p)+cmb(r1+c1,c1,p))%p)

### FIXED CODE ###

r1,c1,r2,c2=map(int,input().split())

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p=10**9+7
N=2*10**6+10
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

print((cmb(r2+1+c2+1,c2+1,p)-cmb(r1+c2+1,c2+1,p)-cmb(r2+1+c1,c1,p)+cmb(r1+c1,c1,p))%p)
### BUGGY CODE ###

#16D8101012J 伊藤惇 dj Python3

def Maximum_Profit(n,A):
    Max=(min(A)-max(A))
    for i in range(n-1):
        if Max<(max(A[i+1:])-A[i]):
            Max=(max(A[i+1:])-A[i])
    return Max

if __name__ == "__main__":
    n=int(input())
    A=[]
    for i in range(n):
        A.append(int(input()))
    Max=Maximum_Profit(n,A)
    print(Max)



### FIXED CODE ###

#16D8101012J 伊藤惇 dj Python3

def Maximum_Profit(n,A):
    Max=A[1]-A[0]
    Min=A[0]
    for j in range(1,n):
        Max=max(Max,A[j]-Min)
        Min=min(Min,A[j])
    return Max

if __name__ == "__main__":
    n=int(input())
    A=[]
    for i in range(n):
        A.append(int(input()))
    Max=Maximum_Profit(n,A)
    print(Max)
### BUGGY CODE ###

game_num, k = map(int, input().split())
r_score, s_score, p_score = map(int, input().split())
game = input()
score = 0
waste_r, waste_s, waste_p = [], [], []
count_waste_r = count_waste_s = count_waste_p = 0

for i in range(game_num):
    if i < k:
        pass
    elif game[i] == 'r' and game[i - k] == 'r' and not (i - k) in waste_r:
        count_waste_r += 1
        #if len(waste_r) > 2 * k:
        #    waste_r.pop()
        waste_r.append(i)
    elif game[i] == 's' and game[i - k] == 's' and not (i - k) in waste_s:
        count_waste_s += 1
        #if len(waste_s) > 2 * k:
        #    waste_s.pop()
        waste_s.append(i)
    elif game[i] == 'p' and game[i - k] == 'p' and not (i - k) in waste_p:
        count_waste_p += 1
        #if len(waste_p) > 2 * k:
        #    waste_p.pop()
        waste_p.append(i)

r_count, s_count, p_count = map(lambda x: game.count(x), ['r', 's', 'p'])

score += r_count * p_score + s_count * r_score + p_count * s_score
score -= count_waste_r * p_score + count_waste_s * r_score + count_waste_p * s_score
print(score)

### FIXED CODE ###

game_num, k = map(int, input().split())
r_score, s_score, p_score = map(int, input().split())
game = input()
score = 0
waste_r, waste_s, waste_p = [], [], []
count_waste_r = count_waste_s = count_waste_p = 0

for i in range(game_num):
    if i < k:
        pass
    elif game[i] == 'r' and game[i - k] == 'r' and not (i - k) in waste_r:
        count_waste_r += 1
        if len(waste_r) > k:
            waste_r.pop(0)
        waste_r.append(i)
    elif game[i] == 's' and game[i - k] == 's' and not (i - k) in waste_s:
        count_waste_s += 1
        if len(waste_s) > k:
            waste_s.pop(0)
        waste_s.append(i)
    elif game[i] == 'p' and game[i - k] == 'p' and not (i - k) in waste_p:
        count_waste_p += 1
        if len(waste_p) >  k:
            waste_p.pop(0)
        waste_p.append(i)

r_count, s_count, p_count = map(lambda x: game.count(x), ['r', 's', 'p'])

score += r_count * p_score + s_count * r_score + p_count * s_score
score -= count_waste_r * p_score + count_waste_s * r_score + count_waste_p * s_score
print(score)
### BUGGY CODE ###

n = int(input())
a=[]
c=1

for i in input().split():
  if c % 2 ==1:
    a=a+[i]
  else:
    a=[i]+a
  c+=1
  
if c % 2 ==1:
  print(*a)
else:
  print(*a[::-1])

### FIXED CODE ###

n = int(input())
a=input().split()
l=n - n %2-1
e=[i for i in a[l::-2]]  
o=[i for i in a[::2]]
e.extend(o)
if n==1:
  print(*a)
elif n % 2 ==0:
  print(*e)
else:
  print(*e[::-1])
### BUGGY CODE ###

# import numpy as np
# import math as np
import copy
import sys
sys.setrecursionlimit(10000000)

f_inf = float("inf")

N, M, P = map(int, input().split())
ABC_d = {}
for m in range(M):
    A, B, C = map(int, input().split())
    if A in ABC_d:
        ABC_d[A].append([B, C - P])
    else:
        ABC_d[A] = [[B, C - P]]

cost = [-f_inf] * N
# cost = np.empty(N, dtype = int) - f_inf
cost[0] = 0

def solve(pos, already):
    global cost

    if not(pos in ABC_d): return

    for B, C in ABC_d[pos]:
        if already[B - 1] == True:
            if cost[B - 1] == f_inf:
                pass
            elif cost[pos-1] == f_inf or cost[B - 1] < cost[pos - 1] + C:
                cost[B-1] = f_inf
                solve(B, already)
        elif cost[B - 1] < cost[pos - 1] + C:
            cost[B - 1] = cost[pos - 1] + C
            already2 = copy.copy(already)# already.copy()
            already2[B - 1] = True
            solve(B, already2)


# already = np.zeros(N, dtype = bool)
already = [False] * N
already[0] = True
solve(1, already)

if (cost[-1] == f_inf):
    print (-1)
else:
    print (max(0, int(cost[-1])))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

f_inf = sys.maxsize

N, M, P = map(int, input().split())
ABC_d = {}
for m in range(M):
    A, B, C = map(int, input().split())
    if A in ABC_d:
        ABC_d[A].append([B, C - P])
    else:
        ABC_d[A] = [[B, C - P]]

cost = [-f_inf] * N
cost[0] = 0

def solve(pos, cnt):
    global cost

    if not(pos in ABC_d): return
    if cnt > N: cost[pos-1] = f_inf;

    for B, C in ABC_d[pos]:
        if cost[B - 1] == f_inf or cost[B - 1] >= cost[pos - 1] + C:
            pass
        elif cost[pos-1] == f_inf:
            cost[B-1] = f_inf
            solve(B, cnt + 1)
        elif cost[B - 1] < cost[pos - 1] + C:
            cost[B - 1] = cost[pos - 1] + C
            solve(B, cnt + 1)

solve(1, 1)

if (cost[-1] == sys.maxsize):
    print (-1)
else:
    print (max(0, int(cost[-1])))
### BUGGY CODE ###

N = int(input())

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

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

if answer>10**18:
  print(-1)
else:
  print(answer)

### FIXED CODE ###

N = int(input())

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

answer=1
if 0 in A:
  print(0)
else:
  for i in range(N):
    answer = answer*A[i]
    if answer>10**18:
      print(-1)
      break
  else:
    print(answer)
### BUGGY CODE ###

s=input()
q=int(input())
dir=True
ans=s
query=[]
for i in range(q):
  temp=input()
  if temp[0] == "1":
    dir = dir ^ True
  if temp[0] == "2":
    t,f,c = temp.split()

    if (f == "1" and dir) or (f=="2" and not dir):
      ans=c+ans
    else:
      ans=ans+c
      
if dir:
  print(ans)
else:
  print(ans[::-1])


### FIXED CODE ###

s=input()
q=int(input())
dir=True
ans=s
right=""
left=""
query=[]
for i in range(q):
  temp=input()
  if temp[0] == "1":
    dir = dir ^ True
  if temp[0] == "2":
    t,f,c = temp.split()

    if (f == "1" and dir) or (f=="2" and not dir):
      left=c+left
    else:
      right=right+c

def reverse(s):
  t=""
  for i in range(len(s)-1,-1,-1):
    t+=s[i]
  return t

if dir:
  print(left+ans+right)
else:
  t=reverse(right)+reverse(ans)+reverse(left)
  print(t)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
import itertools
ans = 0
result = []


for i in range(len(a)):
    for j in range(len(a)):
        if i < j:
            ans += a[i] * a[j]
print(ans%(10 ** 9 + 7))

### FIXED CODE ###

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

ans = 0

sum_a = sum(a)


for i in range(n):
    ans += a[i] * (sum_a - a[i])
    sum_a -= a[i]

print(ans%(10 ** 9 + 7))
### BUGGY CODE ###

def main():
	N=int(input())
	S=input()
	count=0
	r=[]
	g=[]
	b=[]
	for i in range(N):
		if S[i]=="R":
			r.append(i+1)
		if S[i]=="G":
			g.append(i+1)
		if S[i]=="B":
			b.append(i+1)
	for x in r:
		for y in g:
			for z in b:
				L=[x,y,z]
				#print(L)
				L=sorted(L)
				if (L[1]-L[0])!=(L[2]-L[1]):
					count+=1
	print(count)


if __name__=='__main__':
	main()

### FIXED CODE ###

N=int(input())
S=input()
count=0
r=S.count("R")
g=S.count("G")
b=S.count("B")

count+=r*g*b
#print(r,g,b)
for i in range(0,N-1):
	for j in range(i+1,N):
		k=2*j-i
		if k>=N:break
		if S[i]!=S[j] and S[j]!=S[k] and S[i]!=S[k]:
			count-=1
print(count)