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

import itertools
n, y = map(int, input().split())
a = [i for i in range(y // 10000 + 1)]
b = [i for i in range(y // 5000 + 1)]
m = list(itertools.product(a, b))
m = m[::-1]
ans = 0
for i in range(len(m)):
  if n - m[i][0] - m[i][1] >= 0 and m[i][0] * 10000 + m[i][1] * 5000 + (n - m[i][0] - m[i][1]) * 1000 == y:
    print(m[i][0], m[i][1], n - m[i][0] - m[i][1])
    ans = 1
    break
if ans == 0:
  print('-1 -1 -1')

### FIXED CODE ###

import itertools
n, y = map(int, input().split())
k = [i for i in range(n + 1)]
ans = 0
for a, b in itertools.product(k, k):
  if n >= a + b and a * 10000 + b * 5000 + (n - a - b) * 1000 == y:
    print(a, b, n - a - b)
    ans = 1
    break
if ans == 0:
  print('-1 -1 -1')
### BUGGY CODE ###

mod = int(1e9 + 7)
N = int(input())
A = list(map(int, input().split()))
S = 0
j = 1
Z = [0 for i in range(N)]
while A != Z:
  m = 0
  n = 0
  for i in range(N):
    if A[i] % 2 == 1:
      m += 1
    else:
      n += 1
    A[i] //= 2
  S += ((m * n) * j) % mod
  j *= 2
  j %= mod
  S %= mod
S %= mod
print(S)

### FIXED CODE ###

mod = int(1e9 + 7)
N = int(input())
A = [format(i, '060b') for i in map(int, input().split())]
S = 0
for k in range(60):
  s = [b[59-k] for b in A]
  v = s.count('0')*s.count('1')
  S += (v<<k)
S %= mod
print(S)
### BUGGY CODE ###

n,k=map(int,input().split())
l=[]
for j in range(0,n):
    l.append(input().split())
ans=0
for a in range(0,k):
     for b in range(0,k):
         i=0
         total=0
         while i<n:
           m=((int(l[i][0])-a)//k)%2
           h=((int(l[i][1])-b)//k)%2
           if ((m+h)%2==0 and str(l[i][2])=="W") or ((m+h)%2==1 and str(l[i][2])=="B"):
               total=total+1
               i=i+1
           else:
               i=i+1

         else:
              ans=max(ans,total,n-total)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
imos = [[0 for i in range(k)] for j in range(k)]
white = 0
for i in range(n):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == "W":
        c = 1
    else:
        c = 0
    x %= 2*k
    y %= 2*k

    if x > k-1:
        x -= k
        c += 1
    if y > k-1:
        y -=k
        c += 1
    c %= 2

    if c == 1:
        white += 1
        imos[x][y] -= 1
    else:
        imos[x][y] += 1

for i in range(k):
    for j in range(k-1):
        imos[i][j+1] += imos[i][j]

for j in range(k):
    for i in range(k-1):
        imos[i+1][j] += imos[i][j]

ans = 0
for i in range(k):
    for j in range(k):
        exp = imos[k-1][k-1] - imos[k-1][j] - imos[i][k-1] + 2 * imos[i][j] + white
        ans = max(ans, max(exp, n - exp))

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

h,n=map(int,input().split())
L=[]
for i in range(n):
    a,b=map(int,input().split())
    L.append((b/a,a,b))

L.sort()

dp=[100000000 for i in range(h+1)]
dp[0]=0
for i in range(h):
    for q in range(n):
        power=L[q][1]
        magic=L[q][2]
        dp[min(h,i+power)]=min(dp[min(h,i+power)],dp[i]+magic)

print(dp[h])    
    


### FIXED CODE ###

h,n=map(int,input().split())
L=[]
for i in range(n):
    a,b=map(int,input().split())
    L.append((b/a,a,b))

dp=[100000000 for i in range(h+1)]
dp[0]=0
for i in range(h):
    for q in range(n):
        power=L[q][1]
        magic=L[q][2]
        dp[min(h,i+power)]=min(dp[min(h,i+power)],dp[i]+magic)

print(dp[h])
### BUGGY CODE ###

from collections import Counter
ans = 0
s = []
N = int(input())
for i in range(N):
	tmp = []
	string = input()
	for st in string:
		tmp.append(st)
	s.append(tmp)
 
for m in range(len(s)):
	for n in range(len(s)):
		if Counter(s[n])==Counter(s[m]) and s[m] != s[n]:
			ans+=1
print(int(ans/2))

### FIXED CODE ###

ans = 0
s = {}
N = int(input())
for i in range(N):
	tmp = []
	string = input()
	for st in string:
		tmp.append(st)
	tmp.sort()
	stmp = ''.join(tmp)
	if stmp in s and s[stmp] > 0:
		ans += s[stmp]
		s[stmp] = s[stmp]+1
	else:
		s[stmp] = 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

class Factorization:	
	def __init__(self):
		# privateなインスタンス変数を作成
		self.__factors = dict()
		self.__n = 0
	
	
	def get_factors(self, n):
		# [summary] 素因数分解した結果を、辞書([素因数, 指数]...)で返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			# 2より小さい数の場合、素因数分解できない
			return { n:1 }
		else:
			self.__factorization()
			
			return self.__factors
	
	
	def get_divisors(self, n):
		# [summary] 約数をリストに列挙
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return [1]
		else:
			self.__factorization()
			divisors = [1]
			
			for k, v in self.__factors.items():
				import copy
				copy_ = copy.deepcopy(divisors)
								
				for i in range(1, v + 1):
					for c in copy_:
						divisors.append(c * (k ** i))
			
			return divisors

				
	def count_divisors(self, n):
		# [summary] 約数の個数を返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return 1
		else:
			self.__factorization()
			count = 1
			
			for v in self.__factors.values():
				count *= v + 1
			
			return count
	

	def	__factorization(self):
		# [summary]素因数分解した結果を、インスタンス変数に格納
		
		# 2,3,5で、割れなくなるまで割り続ける
		# (末尾に2,3,5のつく数は素数でないことが明白なので
		# 後続の処理で素数のリストに入れないように、先に処理する)
		self.__divide_with(2)
		self.__divide_with(3)
		self.__divide_with(5)
			
		# 平方根以下の素数で総当たりで試し割りする
		# (実際は、素数らしき数)
		import math
		sqrt_ = math.floor(math.sqrt(self.__n))
			
		primes = [7, 11, 13, 17, 19, 23, 29, 31]
		i = 0
		is_break = False
			
		while self.__n > 1:
			for p in primes:
				if p + i <= sqrt_:
					self.__divide_with(p + i)
				else:
					# 試し割りする数が平方根を超えたら、ループを抜ける
					is_break = True
						
					# 1が素因数に追加されることを防止
					if self.__n > 1:
						self.__factors.setdefault(self.__n, 1)
				
			if is_break:
				break
			else:
				i += 30
	
	
	def __divide_with(self, d):
		count = 0
		
		while self.__n % d == 0:
			self.__n //= d
			count += 1
		
		if count > 0:
			self.__factors.setdefault(d, count)


# D - Not Divisible
n = int(input())
a = list(map(int, input().split()))
dic = dict()
 
for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

if 1 in dic.keys():
	if dic[1] == 1:
		print(1)
	else:
		print(0)
else:
	ans = 0
	appeared = set()
	lib = Factorization()
 
	for k, v in sorted(dic.items(),key=lambda x:x[0]):
		is_exist = False
 
		if v == 1:
			divisors = lib.get_divisors(k)
		
			for d in divisors:
				if d in appeared:
					is_exist = True
					break
 
			if is_exist == False:
				ans += 1
 
		if is_exist == False:
			appeared.add(k)
 
	print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

# D - Not Divisible
n = int(input())
a = list(map(int, input().split()))
dic = dict()

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

multiples = set()
upper = 10 ** 6

for k in dic.keys():
  i = 2
  
  while True:
    if k * i <= upper:
      multiples.add(k * i)
      i += 1
    else:
      break

ans = 0

for k, v in dic.items():
  if v == 1:
    if not k in multiples:
      ans += 1

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

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

n_total = 0

S_jk = []
for j in range(1,N-1):
  tmp = []
  for k in range(j+1,N):
    if S[j] != S[k]:
      tmp.append(k)
  S_jk.append(tmp)
for i in range(0,N-2):
  for j in range(i+1,N-1):
    if S[i] != S[j]:
      for k in range(len(S_jk[j-1])):
        if S[i] != S[S_jk[j-1][k]] and (j-i) != (S_jk[j-1][k]-j):
          n_total+=1
print(n_total)

"""
for i in range(0,N-2):
  for j in range(i+1,N-1):
    if S[i] != S[j]:
      for k in range(j+1,N):
        if S[i] != S[k] and S[j] != S[k] and (j-i) != (k-j): 
          n_total+=1
print(n_total)
"""

### FIXED CODE ###

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

n_R, n_G, n_B, n_total = 0, 0, 0, 0
for i in range(N):
  if S[i] == 'R':
    n_R+=1
  elif S[i] == 'G':
    n_G+=1
  else:
    n_B+=1
n_total += (n_R*n_G*n_B)
for j in range(1,N-1):
  i = j-1
  k = j+1
  while 1:
    if 0 <= i and k < N:
      if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
        #print(i,j,k, S[i], S[j], S[k])
        n_total-=1
    else:
      break
    i -= 1
    k += 1
print(n_total)
### BUGGY CODE ###

N = int(input())

ans = 0    
for i in range(1, N+1):
    for j in range(i, N+1, i):
        ans += j

print(ans)

### FIXED CODE ###

n = int(input())

table = [0] * (n + 1)
    
for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        table[j] += j


print(sum(table))
### BUGGY CODE ###

N, M = map(int, input().split())
A = []
for i in range(M):
    A.append(list(map(int,input().split())))
A = A[::-1]


P = [[x+1] for x in range(N)]
n = [x+1 for x in range(N)]
an = [N*(N-1)/2]


for i in range(M-1):
    Aind = A[i][0]-1
    Bind = A[i][1]-1
    PAind = P[n[Aind]-1]
    PBind = P[n[Bind]-1]
    if n[Aind] != n[Bind]:
        an.append(an[i]-len(PAind) * len(PBind))
        P[n[Aind]-1].extend(PBind)
        for j in PBind:
            n[j-1] = n[Aind]
    else:
        an.append(an[i])
        
        
an = an[::-1]
for k in range(M):
    print(int(an[k]))

### FIXED CODE ###

N, M = map(int, input().split())
A = []
for i in range(M):
    A.append(list(map(int,input().split())))
A = A[::-1]


P = [[x+1] for x in range(N)]
n = [x+1 for x in range(N)]
an = [N*(N-1)/2]


for i in range(M-1):
    if an[i] == 0:
        an.append(0)
    else:        
        Aind = A[i][0]-1
        Bind = A[i][1]-1
        PAind = P[n[Aind]-1]
        PBind = P[n[Bind]-1]
        if n[Aind] != n[Bind]:
            if len(PAind) >= len(PBind):
                an.append(an[i]-len(PAind) * len(PBind))
                P[n[Aind]-1].extend(PBind)
                for j in PBind:
                    n[j-1] = n[Aind]
            else:
                an.append(an[i]-len(PAind) * len(PBind))
                P[n[Bind]-1].extend(PAind)
                for j in PAind:
                    n[j-1] = n[Bind]
        else:
            an.append(an[i])
            
        
an = an[::-1]
for k in range(M):
    print(int(an[k]))
### BUGGY CODE ###

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

h = list(sorted([int(input()) for i in range(N)]))
ans = float('inf')

for i in range(N-K+1):
    tmp = h[i:i+K]
    ans = min(ans, tmp[-1] - tmp[0])

print(ans)


### FIXED CODE ###

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

h = list(sorted([int(input()) for i in range(N)]))
h_dif = [h[i+K-1] - h[i] for i in range(N-K+1)]
print(min(h_dif))
### BUGGY CODE ###

import math
import collections

def main():
    n = int(input())
    num_list = list(map(int, input().split()))  
    for i in range(len(num_list)):
        ansdic = {}
        pop = num_list.pop(i)
        dic = collections.Counter(num_list)
        for k, j in dic.items():
            if j < 2:
              pass
            else:
              ansdic[k] = int(j * (j-1)/2)
        print(sum(ansdic.values()))
        ansdic = {}
        num_list.insert(i, pop)
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import math
    n = int(input())
    inlis = list(map(int, input().split()))
    indic = dict()
    total = 0

    for num in inlis:
        if num in indic:
            indic[num] += 1
        else:
            indic[num] = 1
    
    for k, v in indic.items():
        total += int(v * (v-1) / 2)
    
    for num in inlis:
        print(total - indic[num] + 1)





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

import bisect

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

a.sort()
pullout = 0
#print(a)

for i in range(1,max(a)+1):
    numi = bisect.bisect_right(a,i) - bisect.bisect_left(a,i)
    #print(i,numi)
    if numi == 0 or numi == i:
        continue
    elif numi > i:
        pullout += numi - i
    elif numi < i:
        pullout += numi

print(pullout)

### FIXED CODE ###

import bisect

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

a.sort()
pullout = 0
#print(a)

for i in list(set(a)):
    numi = bisect.bisect_right(a,i) - bisect.bisect_left(a,i)
    #print(i,numi)
    if numi == 0 or numi == i:
        continue
    elif numi > i:
        pullout += numi - i
    elif numi < i:
        pullout += numi

print(pullout)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def add_link(a, b):
    la = links[a]
    i, j = [(0, 1), (1, 0)][s[b] == 'B']
    if not la[i] and la[j]:
        able[a] = True
    la[i].add(b)
 
n, m = map(int, input().split())
s = input()
links = [[set(), set()] for _ in range(n)]
able = [None] * n
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    add_link(a, b)
    add_link(b, a)

used = [None]*n
def erase(v):
  if s[v] == "A":
    l = 0
  else:
    l = 1
  for q in links[v][0]:
    if not able[q]:
      continue
    links[q][l].remove(v)
    if links[q][l] == set():
      able[q] = False
      used[q] = True
      erase(q)
  for q in links[v][1]:
    if not able[q]:
      continue
    links[q][l].remove(v)
    if links[q][l] == set():
      able[q] = False
      used[q] = True
      erase(q)

for i in range(n):
  if not able[i]:
    if not used[i]:
      erase(i)
if any(able):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n, m = map(int, input().split())
s = input()
links = [[] for _ in range(2*n)]
visit = [0] * n *2
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    if s[a] == s[b]:
      links[a].append(b+n)
      links[b].append(a+n)
    else:
      links[a+n].append(b)
      links[b+n].append(a)
def dfs(v):
  visit[v] = 1
  for i in links[v]:
    if visit[i] == 1:
      print("Yes")
      exit()
    elif visit[i] == 0:
      dfs(i)
  visit[v] = -1
  
for i in range(n):
  if visit[i] == 0:
    dfs(i)
print("No")
### BUGGY CODE ###

n, q = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
ans = (n - 2)**2
t1 = [n] * (n + 1)
t2 = [n] * (n + 1)
h, w = n, n
for t, x in queries:
    if t == 1:
        tmp = t1[x]
        ans -= tmp - 2
        w = min(w, x)
        for i in range(h + 1):
            t2[i] = w
    else:
        tmp = t2[x]
        ans -= tmp - 2
        h = min(h, x)
        for i in range(w + 1):
            t1[i] = h
print(ans)


### FIXED CODE ###

n, q = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
ans = (n - 2)**2
t1 = [n] * (n + 1)
t2 = [n] * (n + 1)
h, w = n, n
for t, x in queries:
    if t == 1:
        if x < w:
            tmp = h
            for i in range(x, w+1):
                t1[i] = h
            w = x
        else:
            tmp = t1[x]
        ans -= tmp - 2
    else:
        if x < h:
            tmp = w
            for i in range(x, h+1):
                t2[i] = w
            h = x
        else:
            tmp = t2[x]
        ans -= tmp - 2
print(ans)
### BUGGY CODE ###

N = int(input())

A = []
for _ in range(N):
    a = int(input())
    if a in A:
        A.remove(a)
    else:
        A.append(a)

print(len(A))

### FIXED CODE ###

'''
全量のリストを用いると検索対象が大きくなってしまうため、ディクショナリで都度追加/削除する
'''

N = int(input())

A = {}

for _ in range(N):
    tmp = int(input())
    if tmp in A:
        del A[tmp]
    else:
        A[tmp] = 1

print(len(A))
### BUGGY CODE ###

import collections
n,k = map(int,input().split())
ls = list(map(int,input().split()))
a = list(set(ls))
c = collections.Counter(ls)
p = 0
if len(a) > k:
    for i in range(len(a)-1):
        if len(a) - k - i > 0:
            p += c.most_common()[-1-i][1]
        elif len(a) - k - i == 0:
            print(p)
else:
    print(0)

### FIXED CODE ###

import sys
n,k = map(int,input().split())
ls = list(map(int,input().split()))
p = len(list(set(ls)))
if p <= k:
    print(0)
    sys.exit()
di=[float("inf")]*n
for i in range(n):
    if di[ls[i]-1] == float("inf"):
        di[ls[i]-1] = 1
    else:
        di[ls[i]-1] += 1
di.sort(reverse=True)
q = 0 
while True:
    s = di.pop()
    p -= 1
    q += s
    if p <= k:
        print(q)
        sys.exit()
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = 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[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M=[int(i) for i in input().split(" ")]
uf = UnionFind(N)
for i in range(M):
    A,B=[int(i) for i in input().split(" ")]
    uf.union(A-1,B-1)

print(max([len(i) for i in uf.all_group_members().values()]))


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for i in range(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[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M=[int(i) for i in input().split(" ")]
uf = UnionFind(N)
for i in range(M):
    A,B=[int(i) for i in input().split(" ")]
    uf.union(A-1,B-1)

d={}
for i in range(N):
    root = uf.find(i)
    d[root]=d.get(root,0)+1

print(max(d.values()))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
for i in a:
    if a.count(i)-1:
        print('NO')
        exit()
print('YES')

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if n == len(set(a)):
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

N = input()
N = int(N)

A = input().split()
for i in range(len(A)):
    print(A.index(str(i+1))+1, end=" ")


### FIXED CODE ###

N = input()
N = int(N)
ans = [0]*N
A = input().split()

for i in range(N):
    ans[int(A[i])-1] = i+1

for i in ans:
    print(i, end=" ")
### BUGGY CODE ###

n,m=[int(i) for i in input().split()]
P=[[int(i) for i in input().split()] for j in range(m)]

def prefecturesort(i):
    return i[0]

def yearsort(i):
    return i[1]

W=[]
Z=[]

for i in range(m):
    P[i].append(i)
    W.append(P[i][0])

P.sort(key=prefecturesort)
P_c=[]
sum=0
for i in range(n):
    c=W.count(i+1)
    if c==0:
        P_c.append([])
    else:
        P_c.append(P[sum:c+sum])
    sum+=c
    P_c[i].sort(key=yearsort)
for x in P_c:
    for j in range(len(x)):
        X=str("{0:06d}".format(x[j][0]))
        Y=str("{0:06d}".format(j+1))
        Z.append([X+Y,x[j][2]])
Z.sort(key=yearsort)
for i in range(m):
    print(Z[i][0])

    

### FIXED CODE ###

n,m=[int(i) for i in input().split()]
P=[[int(i) for i in input().split()] for j in range(m)]

def prefecturesort(i):
    return i[0]

def yearsort(i):
    return i[1]

W=[0 for i in range(n)]
Z=[]

for i in range(m):
    P[i].append(i)
    W[P[i][0]-1]+=1

P.sort(key=prefecturesort)
P_c=[]
sum=0
for i in range(n):
    c=W[i]
    if c==0:
        P_c.append([])
    else:
        P_c.append(P[sum:c+sum])
    sum+=c
    P_c[i].sort(key=yearsort)
for x in P_c:
    for j in range(len(x)):
        X=str("{0:06d}".format(x[j][0]))
        Y=str("{0:06d}".format(j+1))
        Z.append([X+Y,x[j][2]])
Z.sort(key=yearsort)
for i in range(m):
    print(Z[i][0])
### BUGGY CODE ###

L, R = map(int, input().split())

if L - R + 1 >= 2019:
     print(0)
else:
    ans = float('Inf')
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            ans = min(ans, (i * j) % 2019)
    print(ans)


### FIXED CODE ###

L, R = map(int, input().split())

if R - L + 1 >= 2019:
    print(0)
else:
    res = 2018
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            res = min(res, (i * j) % 2019)
    print(res)
### BUGGY CODE ###

S,Q=input(),int(input())
reverse=0
for i in range(Q):
    T=input().split()
    if T[0]=='1':reverse=0 if reverse else 1
    else:
        if T[1]=='1':
            if reverse:S=S+T[2]
            else:S=T[2]+S
        else:
            if reverse:S=T[2]+S
            else:S=S+T[2]
s=list(S);s.reverse()
print(''.join(s) if reverse else S)

### FIXED CODE ###

S,Q=input(),int(input())
l,r='',''
reverse=0
for i in range(Q):
    T=input().split()
    if T[0]=='1':reverse=0 if reverse else 1
    else:
        if T[1]=='1':
            if reverse:r=r+T[2]
            else:l=T[2]+l
        else:
            if reverse:l=T[2]+l
            else:r=r+T[2]
if reverse:
    s=list(l+S+r);s.reverse()
    print(''.join(s))
else:
    print(l+S+r)
### BUGGY CODE ###

import sys
sys.setrecursionlimit((10 ** 6))
N, M, P = map(int, input().split())
INF = float('inf')
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c - P
    G[a].append((b, -c))

check = [False] * N


def dfs(u, used):
    if used[u]:
        return
    used[u] = True
    for w, c in G[u]:
        dfs(w, used)


def dfs2(u, dest):
    used = [False] * N
    dfs(u, used)
    check[u] = used[dest]


dist = [INF] * N
for i in range(N):
    dfs2(i, N - 1)

dist[0] = 0
for i in range(N):
    update = False
    for e in range(N):
        for w, c in G[e]:
            if not check[e] or not check[w] or dist[e] == INF:
                continue
            if dist[w] > dist[e] + c:
                dist[w] = dist[e] + c
                update = True

    if not update:
        break
    if i == N - 1:
        print(-1)
        exit()

print(max(0, -dist[N - 1]))







### FIXED CODE ###

import sys
sys.setrecursionlimit((10 ** 6))
input = sys.stdin.readline
N, M, P = map(int, input().split())
INF = float('inf')
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c - P
    G[a].append((b, -c))
dist = [INF] * N
dist[0] = 0
for i in range(N):
    for e in range(N):
        for w, c in G[e]:
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c

ans = -dist[N - 1]
is_negative = [False] * N
for i in range(N):
    for e in range(N):
        for w, c in G[e]:
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c
                is_negative[w] = True

            if is_negative[e]:
                is_negative[w] = True

if is_negative[N - 1]:
    print(-1)
else:
    print(max(ans, 0))