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

from sys import stdin
n = int(stdin.readline().rstrip())
V = [int(x) for x in stdin.readline().rstrip().split()]
V_odd = [V[2 * k] for k in range(int(n / 2))]
V_even = [V[2 * k + 1] for k in range(int(n / 2))]
V_odd_major = [0]
V_even_major = [0]
X = 0
Y = 0
for l in range(len(V_odd)):
    V_odd_sub = [x for x in V_odd if x == V_odd[l]]
    V_even_sub = [x for x in V_even if x == V_even[l]]
    if len(V_odd_sub) > V_odd_major[len(V_odd_major) - 1]:
        V_odd_major.append(len(V_odd_sub))
        X = V_odd[l]
    if len(V_even_sub) > V_even_major[len(V_even_major) - 1]:
        V_even_major.append(len(V_even_sub))
        Y = V_even[l]
V_odd_major.sort(reverse=True)
V_even_major.sort(reverse=True)
if X != Y:
    print(n - V_odd_major[0] - V_even_major[0])
else:
    print(n - (max(V_odd_major[1] + V_even_major[0], V_odd_major[0] + V_even_major[1])))

### FIXED CODE ###

from sys import stdin
import collections
n = int(stdin.readline().rstrip())
V = [int(x) for x in stdin.readline().rstrip().split()]
V_odd = [V[2 * k] for k in range(int(n / 2))]
V_even = [V[2 * k + 1] for k in range(int(n / 2))]
co = collections.Counter(V_odd)
ce = collections.Counter(V_even)
if co.most_common()[0][0] != ce.most_common()[0][0]:
    print(n - co.most_common()[0][1] - ce.most_common()[0][1])
elif len(co.most_common()) == 1 and len(ce.most_common()) == 1:
    print(co.most_common()[0][1])
else:
    print(n - (max(co.most_common()[1][1] + ce.most_common()[0][1], co.most_common()[0][1] + ce.most_common()[1][1])))
### BUGGY CODE ###

import sys
import fractions
#import time

def in_ctrl():
    _input = [_.rstrip() for _ in sys.stdin.readlines()]
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    K = int(_input[0])
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    return K


def out_ctrl(s):
    print(s)


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


if __name__ == "__main__":
    #t1 = time.time()
    K = in_ctrl()
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    #cnt = 0
    ## 全部同じ数字(a=b=c)
    #for a in range(1,K+1):
    #    cnt += a
    ## 1つ同じ数字(a<b=c)
    #for a in range(1,K+1):
    #    for b in range(a+1,K+1):
    #        ans = fractions.gcd(a,b)
    #        cnt += 6*ans
    ## 全部違う数字(a<b<c)
    #for a in range(1,K+1):
    #    for b in range(a+1,K+1):
    #        for c in range(b+1,K+1):
    #            if a !=b and b!=c:
    #                ans = fractions.gcd(a,b)
    #                cnt += 6*fractions.gcd(ans, c)
    #            else:
    #                pass
    cnt = 0
    for a in range(1,K+1):
        cnt += a
        for b in range(a+1,K+1):
            ans = fractions.gcd(a,b)
            cnt += 6*ans
            for c in range(b+1,K+1):
                if a !=b and b!=c:
                    cnt += 6*fractions.gcd(ans, c)
                else:
                    pass
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    out_ctrl(cnt)
    #print(time.time()-t1)

### FIXED CODE ###

import sys
import fractions

def in_ctrl():
    _input = [_.rstrip() for _ in sys.stdin.readlines()]
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    K = int(_input[0])
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    return K


def out_ctrl(s):
    print(s)


if __name__ == "__main__":
    K = in_ctrl()
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    dict_ = {}
    for a in range(1,K+1):
        cnt += a
        for b in range(a+1,K+1):
            if '{}_{}'.format(a,b) in dict_:
                ans = dict_['{}_{}'.format(a,b)]
            else:
                ans = fractions.gcd(a,b)
                dict_['{}_{}'.format(a,b)] = ans
            cnt += 6*ans
            for c in range(b+1,K+1):
                if '{}_{}'.format(ans,c) in dict_:
                    _ans = dict_['{}_{}'.format(ans,c)]
                else:
                    _ans = fractions.gcd(ans, c)
                    dict_['{}_{}'.format(ans,c)] = _ans
                cnt += 6*_ans
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    out_ctrl(cnt)
### BUGGY CODE ###

import sys

temp = []
largest = 1

for line in sys.stdin:
    a,b = [int(x) for x in line.split()]
    if a > b:
        x,y = a,b
    else:
        x,y = b,a
    i = x
    while i > 1:
        if (x % i) == 0 and (y % i) == 0:
            x = x / i
            y = y / i
            largest *= i
        i -= 1
    smallest = largest * (a/largest) * (b/largest)
    print('%d %d' % (largest, smallest))
    largest = 1

### FIXED CODE ###

import sys

temp = []
largest = 1

for line in sys.stdin:
    a,b = [int(x) for x in line.split()]
    if a > b:
        x,y = a,b
    else:
        x,y = b,a
    while y:
        x,y = y,x%y
    smallest = x * (a/x) * (b/x)
    print('%d %d' % (x, smallest))
### BUGGY CODE ###

S = input()

# S = 'dreamerer'

words = ['dream', 'dreamer', 'erase', 'eraser']

flag = False
while True:
    for word in words:
        # word=words[0]
        length = len(word)
        if S[-length:] == word:
            S = S[:len(S) - length]
            flag = True
            break
    if flag:
        if S == '':
            print('YES')
            break
        else:
            continue
    else:
        print('NO')
        break


### FIXED CODE ###

S = input()

# S = 'dreameraser'

words = ['dream', 'dreamer', 'erase', 'eraser']

while True:
    flag = False

    for word in words:
        # word=words[3]
        length = len(word)
        if S[-length:] == word:
            S = S[:len(S) - length]
            flag = True
            break

    if flag:
        if S == '':
            print('YES')
            break
        else:
            continue
    else:
        print('NO')
        break
### BUGGY CODE ###

s = list(input())[::-1]

mod = 10**9 + 7

rest = []
for i in range(6):
    res = []
    for j in range(10):
        res.append(((10**i)*j) % 13)
    rest.append(res)

nowtable = [0] * 13
nowtable[0] = 1

for i in range(len(s)):
    degree = i % 6
    nextable = [0] * 13
    if s[i] == '?':
        for j in range(10):
            for k in range(13):
                index = (k + rest[degree][j]) % 13
                nextable[index] = (nextable[index] + nowtable[k]) % mod
    else:
        num = int(s[i])
        for k in range(13):
            index = (k + rest[degree][num]) % 13
            nextable[index] = (nextable[index] + nowtable[k]) % mod
    nowtable = nextable

print(nowtable[5])


### FIXED CODE ###

s = list(input())[::-1]

mod = 10**9 + 7

rest = []
for i in range(6):
    res = []
    for j in range(10):
        res.append(((10**i)*j) % 13)
    rest.append(res)

nowtable = [0] * 13
nowtable[0] = 1

for i in range(len(s)):
    degree = i % 6
    nextable = [0] * 13
    if s[i] == '?':
        for j in range(10):
            for k in range(13):
                index = (k + rest[degree][j]) % 13
                nextable[index] = (nextable[index] + nowtable[k]) % mod
    else:
        num = int(s[i])
        for k in range(13):
            index = (k + rest[degree][num]) % 13
            nextable[index] = (nextable[index] + nowtable[k]) % mod
    nowtable = nextable

print(nowtable[5])
### BUGGY CODE ###

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


for i in range(N):
    SUM=0
    for j in range(i,N):

        if SUM&A[j]==0:
            count+=1
            SUM=SUM+A[j]
            
        else:
            break


print(count)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
count=0
F=0
B=0
SUM=0



while F<N:
    while True:
        SUMtest=SUM+A[B]
        XORtest=SUM^A[B]

        if SUMtest==XORtest:
            if B==N-1:
                for i in range(F,N):
                    count=count+(N-i)
                F=N
                break
                
            else:
                B+=1
                SUM=SUMtest

        else:
            count=count+(B-F)
            SUM=SUM-A[F]
            F+=1
            break


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

#!/usr/bin/env python3

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    N = II()
    S = input()

    ans = []
    for i in range(2**N, 2**(N+1)):
        if bin(i)[3:].count('1') == N - 3:
            t = ''
            for s, b in zip(S, bin(i)[3:]):
                if b != '1':
                    t += s
            ans.append(t)
        
    print(len(set(ans)))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    # N = II()
    # S = input()

    # ans = []
    # for i in range(2**N, 2**(N+1)):
    #     if bin(i)[3:].count('1') == N - 3:
    #         t = ''
    #         for s, b in zip(S, bin(i)[3:]):
    #             if b != '1':
    #                 t += s
    #         ans.append(t)
        
    # print(len(set(ans)))

    N = II()
    S = input()

    ans = 0
    for i in range(10):
        a = S.find(str(i))
        if a != -1:
            for j in range(10):
                b = S.find(str(j), a+1)
                if b != -1:
                    for k in range(10):
                        c = S.find(str(k), b+1)
                        if c != -1:
                            ans += 1

    print(ans)

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

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

newn = abs(n-k)

while n > newn:
  n = newn
  newn = abs(n-k)
else:
  print(n)

### FIXED CODE ###

n,k = map(int,input().split())
a = n % k
b = k - a
print(min(a,b))
### BUGGY CODE ###

# B

N = int(input())
AN = list(map(int, input().split()))
ans = 1
for A in AN:
    ans *= A

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

### FIXED CODE ###

# B
 
N = int(input())
AN = list(map(int, input().split()))
if 0 in AN:
    print(0)
    exit()
ans = 1
for A in AN:
    ans *= A
    if ans > 10 ** 18:
        print(-1)
        exit()
 
print(ans)
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(k):
  if a>0:
    a-=1
  elif b>0:
    b-=1
  else:
    pass
print(str(a)+' '+str(b))

### FIXED CODE ###

a,b,k=map(int,input().split())
if a>k:
  a-=k
elif a+b>k:
  a,b=0,b-k+a
else:
  a=0
  b=0
print(str(a)+' '+str(b))
### BUGGY CODE ###

import math


def combinations_with_replacement_count(n, r):
    return math.factorial(n + r - 1) // (math.factorial(n - 1) * math.factorial(r))


nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
fact = {}
i = 2
while m != 1 :
    while m % i == 0:
        m = m // i
        if i in fact:
            fact[i] += 1
        else:
            fact[i] = 1
    i += 1
j = 2
ans = 1
for k in fact:
    ans = ans * combinations_with_replacement_count(n, fact[k])
print(ans % (10 ** 9 + 7))

### FIXED CODE ###

import math


def combinations_with_replacement_count(n, r):
    return math.factorial(n + r - 1) // (math.factorial(n - 1) * math.factorial(r))


nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
fact = {}
i = 2
while i * i <= m:
    while m % i == 0:
        m = m // i
        if i in fact:
            fact[i] += 1
        else:
            fact[i] = 1
    i += 1
if m > 1:
    fact[m] = 1
j = 2
ans = 1
for k in fact:
    ans = ans * combinations_with_replacement_count(n, fact[k])
print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

S=input()
s0=''
s1=''
n=len(S)
for i in range(n):
  if i%2==0:
    s0+='0'
    s1+='1'
  else:
    s0+='1'
    s1+='0'
is0=bin(int(s0,2)^int(S,2))[2:]
is1=bin(int(s1,2)^int(S,2))[2:]
lis0=[]
lis1=[]
for i in range(len(is0)):
  lis0.append(is0[i])
for i in range(len(is1)):
  lis1.append(is1[i])
while '0' in lis0:
  lis0.remove('0')
while '0' in lis1:
  lis1.remove('0')
print(min(len(lis0),len(lis1)))

### FIXED CODE ###

S=input()
c0=0
c1=0
for i in range(len(S)):
  if i%2==0:
    if S[i]=='0':
      c0+=1
  else:
    if S[i]=='1':
      c0+=1
for i in range(len(S)):
  if i%2==0:
    if S[i]=='1':
      c1+=1
  else:
    if S[i]=='0':
      c1+=1
print(min(c0,c1))
### BUGGY CODE ###

n = int(input())
dA = {}
A = []
for a in input().split():
    A.append(a)
    if a in dA:
        dA[a] += 1
    else:
        dA[a] = 1

cA = {}
for a in dA:
    cA[a] = dA[a] * (dA[a] - 1) // 2

for a in A:
    print(sum(cA.values()) - dA[a] + 1)


### FIXED CODE ###

n = int(input())
dA = {}
A = []
for a in input().split():
    A.append(a)
    if a in dA:
        dA[a] += 1
    else:
        dA[a] = 1

cA = {}
for a in dA:
    cA[a] = dA[a] * (dA[a] - 1) // 2

s = sum(cA.values())
for a in A:
    print(s - dA[a] + 1)
### BUGGY CODE ###

import math
from functools import lru_cache

@lru_cache(maxsize=100000)
def gcd_list(a, b, c):
    return gcd(gcd(a, b), c)

@lru_cache(maxsize=100000)
def gcd(x, y):
    return math.gcd(x, y)

k = int(input())
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd_list(a,b,c)
print(ans)


### FIXED CODE ###

# import math
# from functools import lru_cache

# @lru_cache(maxsize=100000)
# def gcd_list(a, b, c):
#     return gcd(gcd(a, b), c)

# @lru_cache(maxsize=100000)
# def gcd(x, y):
#     return math.gcd(x, y)


# for k in range (1, 201):
#     ans = 0
#     for a in range(1, k+1):
#         for b in range(1, k+1):
#             for c in range(1, k+1):
#                 ans += gcd_list(a,b,c)
#     print("%d:%d," % (k, ans))


a = {
1:1,
2:9,
3:30,
4:76,
5:141,
6:267,
7:400,
8:624,
9:885,
10:1249,
11:1590,
12:2208,
13:2689,
14:3411,
15:4248,
16:5248,
17:6081,
18:7485,
19:8530,
20:10248,
21:11889,
22:13687,
23:15228,
24:17988,
25:20053,
26:22569,
27:25242,
28:28588,
29:31053,
30:35463,
31:38284,
32:42540,
33:46581,
34:50893,
35:55362,
36:61824,
37:65857,
38:71247,
39:76884,
40:84388,
41:89349,
42:97881,
43:103342,
44:111528,
45:120141,
46:128047,
47:134580,
48:146316,
49:154177,
50:164817,
51:174438,
52:185836,
53:194157,
54:207927,
55:218812,
56:233268,
57:245277,
58:257857,
59:268182,
60:288216,
61:299257,
62:313635,
63:330204,
64:347836,
65:362973,
66:383709,
67:397042,
68:416448,
69:434025,
70:456967,
71:471948,
72:499740,
73:515581,
74:536073,
75:559758,
76:583960,
77:604833,
78:633651,
79:652216,
80:683712,
81:709065,
82:734233,
83:754734,
84:793188,
85:818917,
86:846603,
87:874512,
88:909496,
89:933081,
90:977145,
91:1006126,
92:1041504,
93:1073385,
94:1106467,
95:1138536,
96:1187112,
97:1215145,
98:1255101,
99:1295142,
100:1342852,
101:1373253,
102:1422195,
103:1453816,
104:1502376,
105:1553361,
106:1595437,
107:1629570,
108:1691292,
109:1726717,
110:1782111,
111:1827492,
112:1887772,
113:1925853,
114:1986837,
115:2033674,
116:2089776,
117:2145333,
118:2197483,
119:2246640,
120:2332104,
121:2379085,
122:2434833,
123:2490534,
124:2554600,
125:2609625,
126:2693919,
127:2742052,
128:2813988,
129:2875245,
130:2952085,
131:3003306,
132:3096024,
133:3157249,
134:3224511,
135:3306240,
136:3388576,
137:3444609,
138:3533637,
139:3591322,
140:3693924,
141:3767085,
142:3842623,
143:3912324,
144:4027884,
145:4102093,
146:4181949,
147:4270422,
148:4361548,
149:4427853,
150:4548003,
151:4616104,
152:4718640,
153:4812789,
154:4918561,
155:5003286,
156:5131848,
157:5205481,
158:5299011,
159:5392008,
160:5521384,
161:5610705,
162:5739009,
163:5818390,
164:5930196,
165:6052893,
166:6156139,
167:6239472,
168:6402720,
169:6493681,
170:6623853,
171:6741078,
172:6864016,
173:6953457,
174:7094451,
175:7215016,
176:7359936,
177:7475145,
178:7593865,
179:7689630,
180:7886244,
181:7984165,
182:8130747,
183:8253888,
184:8403448,
185:8523897,
186:8684853,
187:8802826,
188:8949612,
189:9105537,
190:9267595,
191:9376656,
192:9574704,
193:9686065,
194:9827097,
195:9997134,
196:10174780,
197:10290813,
198:10493367,
199:10611772,
200:10813692
}

k = int(input())
print(a[k])
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
for i in range(m):
  a[a.index(max(a))]//=2
print(sum(a))

### FIXED CODE ###

from heapq import *
n,m = map(int,input().split())
a = list(map(lambda x:-int(x),input().split()))
heapify(a)
for i in range(m):
  heappush(a,-(-heappop(a)//2))
print(-sum(a))
### BUGGY CODE ###

import numpy as np

def main():
  H, W = map(int, input().split())
  G = [list(input()) for _ in range(H)]
  direction = [[0,1],[0,-1],[1,0],[-1,0]]
  black = np.zeros((H,W))
  que = []
  for i in range(H):
    for j in range(W):
      if G[i][j] == '#':
        que.append([i,j])
        black[i][j] = 0
  while que:
    nh, nw = que.pop(0)
    for dh, dw in direction:
      if nh+dh<0 or nh+dh>H-1 or nw+dw<0 or nw+dw>W-1:
        continue
      if black[nh+dh][nw+dw] > 0:
        continue
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
  print(int(np.max(black)))

if __name__ == "__main__":
  main()

### FIXED CODE ###

import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  G = [['#' == x for x in input()] for _ in range(H)]
 
  black = deque([(i, j) for i in range(H) for j in range(W) if G[i][j]])
 
  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi > 0 and not G[bi - 1][bj]:
        G[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj > 0 and not G[bi][bj - 1]:
        G[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi < H - 1 and not G[bi + 1][bj]:
        G[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj < W - 1 and not G[bi][bj + 1]:
        G[bi][bj + 1] = True
        next_black.append((bi, bj + 1))
    if next_black:
       black = copy.copy(next_black)
    else:
       break
  print(ans - 1)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
f.sort()
a.sort(reverse=True)
x = 0
l = []
for i in range(n):
    l.append(a[i]*f[i])
m = max(l)
nibu = [0,m]
while nibu[0]+1 < nibu[1]:
    p = (nibu[0]+nibu[1])//2
    count = 0
    for i in range(n):
        if p < l[i]:
            count += (l[i]-p)//f[i]
            if (l[i]-p)%f[i] > 0:
                count += 1
    if count > k:
        nibu[0] = p
    else:
        nibu[1] = p
count = 0
p = nibu[0]
#print(a,f)
for i in range(n):
    if p < l[i]:
        count += (l[i]-p)//f[i]
        if (l[i]-p)%f[i] > 0:
            count += 1
    #print(count)
if count > k:
    print(nibu[1])
else:
    print(nibu[0])

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
f.sort()
a.sort(reverse=True)
x = 0
l = []
for i in range(n):
    l.append(a[i]*f[i])
m = max(l)
nibu = [0,m]
while nibu[0]+1 < nibu[1]:
    p = (nibu[0]+nibu[1])//2
    count = 0
    for i in range(n):
        if p < l[i]:
            count += (l[i]-p)//f[i]
            if (l[i]-p)%f[i] > 0:
                count += 1
    if count > k:
        nibu[0] = p
    else:
        nibu[1] = p
count = 0
p = nibu[0]
#print(a,f)
for i in range(n):
    if p < l[i]:
        count += (l[i]-p)//f[i]
        if (l[i]-p)%f[i] > 0:
            count += 1
    #print(count)
if count > k:
    print(nibu[1])
else:
    print(nibu[0])
### BUGGY CODE ###

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

ans = int(0.5*n*(n-1))
AA=[ans]
G = [i for i in range(n+1)]
H = [1 for i in range(n+1)]
for i in range(m) :
    x = A[m-1-i][0]
    y = A[m-1-i][1]
    #print("{} {}".format(x,y))
    if G[x] != G[y] :
        xx=G[x]
        for j in range(n+1) :
            if G[j] == xx :
                G[j] = G[y]
        ans -= H[xx] * H[G[y]]
        nn = H[xx] + H[G[y]]
        H[xx]=0
        H[G[y]]=nn
    #print(G)
    #print(H)
    #print(ans)
    AA.append(ans)

for i in range(len(AA)-1):
    print(AA[len(AA)-2-i])


### FIXED 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

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

for i in range(m):
    for j in range(2):
        A[i][j] -= 1

U = UnionFind(n)
ans = n * (n-1) // 2
ANS = []
for i in range(m-1, -1, -1):
    ANS.append(ans)
    a = A[i][0]
    b = A[i][1]
    ua = U.find(a)
    ub = U.find(b)
    if ua != ub:
        ans -= U.parents[ua] * U.parents[ub]
        U.union(ua, ub)

for i in range(len(ANS)-1, -1, -1):
    print(ANS[i])
### BUGGY CODE ###

from collections import defaultdict, deque
import sys
import heapq
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M, P = [int(a) for a in input().split()]
    ABC = [
        [int(a) for a in input().split()]
        for _ in range(M)
    ]

    FORWARD = defaultdict(lambda: [])
    BACK = defaultdict(lambda: [])
    for a, b, c in ABC:
        t = FORWARD[a]
        t.append((b, c))
        FORWARD[a] = t

        t = BACK[b]
        t.append((a, c))
        BACK[b] = t

    mem = {N}
    q = [N]
    while len(q) != 0:
        t = q.pop()
        for t2, _ in BACK[t]:
            if t2 in mem:
                continue
            q.append(t2)
            mem.add(t2)

    ABC = [(a, b, P - c) for a, b, c in ABC if a in mem and b in mem]

    table = [MAX] * (N + 1)
    history_table = [set() for _ in range(N + 1)]
    table[1] = 0
    history_table[1] = {1}
    # table2 = [-1] * N
    for _ in range(len(mem)):
        for a, b, c in ABC:
            if table[a] == MAX:
                continue
            if table[a] + c < table[b]:
                if b in history_table[a]:
                    print(-1)
                    return
                table[b] = table[a] + c
                h2 = set(history_table[a])
                h2.add(b)
                history_table[b] = h2
    print(max(0, -table[N]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, deque
import sys
import heapq
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M, P = [int(a) for a in input().split()]
    ABC = [
        [int(a) for a in input().split()]
        for _ in range(M)
    ]

    FORWARD = defaultdict(lambda: [])
    BACK = defaultdict(lambda: [])
    for a, b, c in ABC:
        t = FORWARD[a]
        t.append((b, c))
        FORWARD[a] = t

        t = BACK[b]
        t.append((a, c))
        BACK[b] = t

    mem = {N}
    q = [N]
    while len(q) != 0:
        t = q.pop()
        for t2, _ in BACK[t]:
            if t2 in mem:
                continue
            q.append(t2)
            mem.add(t2)

    ABC = [(a, b, P - c) for a, b, c in ABC if a in mem and b in mem]

    table = [MAX] * (N + 1)
    history_table = [set() for _ in range(N + 1)]
    table[1] = 0
    # history_table[1] = {1}
    # table2 = [-1] * N
    for _ in range(len(mem)):
        for a, b, c in ABC:
            if table[a] == MAX:
                continue
            if table[a] + c < table[b]:
                # if b in history_table[a]:
                #     print(-1)
                #     return
                table[b] = table[a] + c
                # h2 = set(history_table[a])
                # h2.add(b)
                # history_table[b] = h2
    for a, b, c in ABC:
        if table[a] == MAX:
            continue
        if table[a] + c < table[b]:
            print(-1)
            return
    print(max(0, -table[N]))


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

def f(): return map(int,raw_input().split())
n,q=f()
A=[0]*(n+1)
a0,b0=0,0
for _ in range(q):
  a,b=f()
  A[a]+=b
  if A[a]>b0: a0,b0=a,A[a]
  else:
    b0=max(A)
    a0=A.index(b0)
  print a0,b0

### FIXED CODE ###

def f(): return map(int,raw_input().split())
n,q=f()
a0,v0=0,0
A=[0]*(n+1)
for _ in range(q):
  a,v=f()
  A[a]+=v
  if a==a0 and v<0:
    v0=max(A)
    a0=A.index(v0)
  elif A[a]>v0: a0,v0=a,A[a]
  elif A[a]==v0 and a<a0: a0=a
  print a0,v0