CodeEff/ECCO huggingface dataset:
# Original solution
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    s = str(readline().rstrip().decode('utf-8'))
    mt = 0
    for i in range(0, n):
        zs = s[i:]
        zln = len(zs)
        zl = [0] * zln
        zi = 1
        zj = 0
        while zi < zln:
            while zi + zj < zln and zs[zj] == zs[zi+zj]:
                zj += 1
            zl[zi] = zj
            if zj == 0:
                zi += 1
                continue
            zk = 1
            while zi + zk < zln and zk + zl[zk] < zj:
                zl[zi+zk] = zl[zk]
                zk += 1
            zi += zk
            zj -= zk
        for j in range(len(zl)):
            if zl[j] <= j:
                mt = max(mt, zl[j])
    print(mt)


if __name__ == '__main__':
    solve()


# Optimized solution
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    s = str(readline().rstrip().decode('utf-8'))
    mt = 0
    for i in range(n):
        zs = s[i:]
        zln = len(zs)
        zl = [0] * zln
        zi = 1
        zj = 0
        while zi < zln:
            while zi + zj < zln and zs[zj] == zs[zi+zj]:
                zj += 1
            zl[zi] = zj
            if zj == 0:
                zi += 1
                continue
            zk = 1
            while zi + zk < zln and zk + zl[zk] < zj:
                zl[zi+zk] = zl[zk]
                zk += 1
            zi += zk
            zj -= zk
        for j in range(len(zl)):
            if zl[j] <= j:
                mt = max(mt, zl[j])
    print(mt)


if __name__ == '__main__':
    solve()
# Original solution
#!/usr/bin/env python3
import sys


def z_algo(N, S):
    end = 1
    start = 0
    max_length = 0

    while start < N:
        while end-start > N-end:
            break
        subword = S[start:end]
        if subword in S[end:]:
            max_length = max(max_length, len(subword))
            end += 1
        else:
            start += 1
            if start == end:
                end += 1
    return max_length


def solve(N: int, S: str):
    print((z_algo(N, S)))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)


if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys


def two_pointers(N, S):
    end = 1
    start = 0
    max_length = 0

    while start < N:
        if end-start > N-end:
            break
        subword = S[start:end]
        if subword in S[end:]:
            max_length = max(max_length, len(subword))
            end += 1
        else:
            start += 1
            if start == end:
                end += 1
    return max_length


def solve(N: int, S: str):
    print((two_pointers(N, S)))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)


if __name__ == '__main__':
    main()
# Original solution
import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(eval(input()))
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

dic = dict()

def zalg(s):
    n = len(s)
    ret = [0] * n
    ret[0] = n
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        ret[i] = j

        if j == 0:
            i += 1
            continue

        k = 1
        while k < j and k + ret[k] < j:
            ret[i + k] = ret[k]
            k += 1

        i += k
        j -= k

    return ret

def solve(n=None, s1=None, s2=None):
    n = getN()
    s = getS()
    ans = 0
    for i in range(n):
        ps = s[i:]
        z = zalg(ps)
        for i, zz in enumerate(z):
            if i >= zz:
                ans = max(ans, zz)
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
    return


if __name__ == "__main__":
    # main()
    solve()



# Optimized solution
import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(eval(input()))
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

dic = dict()

def zalg(s):
    n = len(s)
    ret = [0] * n
    ret[0] = n
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        ret[i] = j

        if j == 0:
            i += 1
            continue

        k = 1
        while k < j and k + ret[k] < j:
            ret[i + k] = ret[k]
            k += 1

        i += k
        j -= k

    return ret

def solve(n=None, s1=None, s2=None):
    n = getN()
    s = list(getS())
    ans = 0
    for i in range(n):
        ps = s[i:]
        z = zalg(ps)
        for i, zz in enumerate(z):
            if i >= zz:
                ans = max(ans, zz)
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
    return


if __name__ == "__main__":
    # main()
    solve()
# Original solution
import collections


class RollingHashSingle:
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod

        self.hash = [0]
        self.power = [1]
        for c in s:
            self.hash.append((self.hash[-1] * base + ord(c)) % mod)
            self.power.append(self.power[-1] * base % mod)

    def get(self, left, right):
        h = self.hash[right] - self.hash[left] * self.power[right - left]
        return (h + self.mod) % self.mod


class RollingHash:
    def __init__(self,
                 s,
                 base=(10**4 + 7, 10**4 + 9),
                 mod=(10**9 + 7, 10**9 + 9)):
        if isinstance(base, int):
            assert isinstance(mod, int)
            self.base = (base, )
            self.mod = (mod, )
        elif isinstance(base, tuple):
            assert isinstance(mod, tuple)
            assert len(base) == len(mod)
            self.base = base
            self.mod = mod
        else:
            raise ValueError()

        self._rh = [
            RollingHashSingle(s, base, mod)
            for base, mod in zip(self.base, self.mod)
        ]

    def get(self, left, right):
        return tuple(rh.get(left, right) for rh in self._rh)


n = int(eval(input()))
s = input().rstrip()
rh = RollingHash(s)


def check(diff):
    d = collections.defaultdict(list)
    for i in range(n - diff + 1):
        h = rh.get(i, i + diff)
        d[h].append(i)
    for l in list(d.values()):
        if max(l) - min(l) >= diff:
            return True
    return False


lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
print(lo)

# Optimized solution
n = int(eval(input()))
s = input().rstrip()


def check(length):
    d = set()
    for i in range(n - 2 * length + 1):
        d.add(s[i:i + length])
        if s[i + length:i + 2 * length] in d:
            return True
    return False


lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
print(lo)
# Original solution
import random
from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(eval(input()))
s = input().rstrip()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
	power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
	hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
	return ((hvalue[r]-hvalue[l])*power[n-r])%mod
ans = 0
for i in range(1,n//2+1):
	dc = defaultdict(int)
	for j in range(n-i+1):
		x = rollinghash(j,i+j)
		if dc[x]:
			rg = dc[x]
			if rg<=j:
				ans = max(ans,i)
				break
		else:
			dc[x] = i+j
print(ans)

# Optimized solution
import random
from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(eval(input()))
s = input().rstrip()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
  power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
  hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
  return ((hvalue[r]-hvalue[l])*power[n-r])%mod
def pun(i):
  dc = defaultdict(int)
  if i>n//2:
    return False
  for j in range(n-i+1):
    x = rollinghash(j,i+j)
    if dc[x]:
      rg =dc[x]
      if rg<=j:
        return True
    else:
      dc[x] = i+j
  return False
l=0
r=n//2+1
while l+1<r:
  mi=(l+r)//2
  if pun(mi):
    l=mi
  else:
    r=mi
print(l)
# Original solution
import sys
import collections


def main():
    n = int(sys.stdin.readline().strip())
    s = sys.stdin.readline().strip()
    # s = 'strangeorange'

    index_sets = [set() for _ in range(26)]
    pointers = []

    longest = 0
    for i in range(len(s)):
        c = s[i]
        order = ord(c) - ord('a')
        index_set = index_sets[order]
        next_pointers = []
        for _ in range(len(pointers)):
            cur, length, origin = pointers.pop()
            if s[cur+1] == c and cur+1 != origin:
                next_pointers.append([cur+1, length+1, origin])
                longest = max(longest, length+1)
        pointers = next_pointers

        for index in index_set:
            longest = max(longest, 1)
            pointers.append([index, 1, i])
        index_sets[order].add(i)

    print(longest)


main()


# Optimized solution

import sys
import collections


def main():
    n = int(sys.stdin.readline().strip())
    s = sys.stdin.readline().strip()
    # s = 'strangeorange'
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

    res = 0
    for i in range(n-1, -1, -1):
        for j in range(n-1, i, -1):
            if s[i] == s[j]:
                if j == n-1:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i+1][j+1]+1
                res = max(res, min(dp[i][j], j-i))
    print(res)


main()
# Original solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        for j in range(N - 1, i, -1):
            if S[i] == S[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            if ans < min(dp[i][j], j - i):
                ans = min(dp[i][j], j - i)

    print(ans)
    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    ans = 0

    for i in range(N - 1, -1, -1):
        for j in range(N - 1, i, -1):
            if S[i] == S[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
            if ans < min(dp[i][j], j - i):
                ans = min(dp[i][j], j - i)

    print(ans)
    return


if __name__ == '__main__':
    main()
# Original solution
import heapq
a, b = list(map(int, input().split()))
print((sum(heapq.nlargest(2, [a, a-1, b, b-1]))))


# Optimized solution
a, b = list(map(int, input().split()))
print((max([a+b, 2*a-1, 2*b-1])))
# Original solution
a,b = list(map(int, input().split()))
ans = 0
for i in range(2):
  if a >= b:
    ans += a
    a -= 1
  else:
    ans += b
    b -= 1
print(ans)

  

# Optimized solution
a,b = list(map(int, input().split()))
if abs(a-b) > 0:
  print((max(a,b) * 2 - 1))
else:
  print((a+b))
# Original solution
a, b = list(map(int, input().split()))
val1 = a + (a-1)
val2 = b + (b-1)
val3 = a + b
print((max([val1, val2, val3])))

# Optimized solution
A, B = list(map(int, input().split()))
large = max(A, B)
if A == B:
    print((large + large))
else:
    print((large + (large-1)))
# Original solution
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

a,b = LI()
ans = max(a+a-1,a+b,b+b-1)
print(ans)

# Optimized solution
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

a, b = LI()
if a != b:
    print((max(a, b)*2-1))
else:
    print((a+b))
# Original solution
A, B = list(map(int, input().split()))

if A - B > 1:
  x = 2 * A - 1
elif B - A > 1:
  x = 2 * B - 1
else:
  x = A + B

print(x)

# Optimized solution
A, B = list(map(int, input().split()))

if A - B >= 2:
  print((2 * A - 1))
elif B - A >= 2:
  print((2 * B - 1))
else:
  print((A + B))
# Original solution
A,B=list(map(int,input().split()))
if A>B:
    print((A+max(A-1,B)))    
else:
    print((B+max(A,B-1)))

# Optimized solution
A,B=list(map(int,input().split()))
print((max(A+B,2*A-1,2*B-1)))
# Original solution
# -*- coding: utf-8 -*-

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

if A == B:
    print((A * 2))
else:
    print((max(A, B) * 2 - 1))


# Optimized solution
# -*- coding: utf-8 -*-

A, B = list(map(int, input().split()))
print((A * 2 if A == B else max(A, B) * 2 - 1))
# Original solution
from sys import stdin
input = lambda: stdin.readline().rstrip()
a, b = list(map(int, input().split()))
if a > b:
    ans = a + a - 1
elif a < b:
    ans = b + b - 1
else:
    ans = a + b
print(ans)


# Optimized solution
a, b = list(map(int, input().split()))
if a > b:
    ans = a + a - 1
elif a < b:
    ans = b + b - 1
else:
    ans = a + b
print(ans)
# Original solution
a, b = list(map(int, input().split()))
ans=0
for i in range(2):
    ans += max(a,b)
    if a>b:
        a -=1
    else:
        b -=1
print(ans)

# Optimized solution
a, b = list(map(int, input().split()))
preans = max(a*2-1,b*2-1)
ans=max(preans,a+b)
print(ans)
# Original solution
a,b = list(map(int,input().split()))
#押すのはa-a,b-b,a-bのうちのいずれか
print((max(2*a-1,2*b-1,a+b)))

# Optimized solution
a,b = list(map(int,input().split()))
print((max(2*a-1,2*b-1,a+b)))
# Original solution
a,b=list(map(int,input().split()))
print((2*max(a,b)-1 if abs(a-b)>1 else a+b))

# Optimized solution
a,b=list(map(int,input().split()))
print((max(2*a-1,2*b-1,a+b)))
# Original solution
a,b=list(map(int,input().split()))
print((max(2*a-1,2*b-1,a+b)))

# Optimized solution
A, B = list(map(int, input().split()))
print((max(2*A-1, 2*B-1, A+B)))
# Original solution
k = input().split()
a = int(k[0])
b = int(k[1])
s = 0
if(a>=b):
    s+=a
    a-=1
else:
    s+=b
    b-=1
print((s+max(a,b)))

# Optimized solution
k = input().split()
a = int(k[0])
b = int(k[1])
print((max(2*a-1,2*b-1,a+b)))
# Original solution
a,b=list(map(int,input().split()))
print((max(a,b)*2-1+int(a==b)))

# Optimized solution
a,b=list(map(int,input().split()))
print((max(2*a-1,2*b-1,a+b)))
# Original solution
def recur(ba,bb):
    if(ba <= 0 and bb <= 0):
        return 0
    if(ba <= 0):
        #only b twice
        return (bb*2)-1
    elif(bb<=0):
        return (ba*2)-1
    else:
        tb = max(bb+bb-1,recur(ba,bb-2))
        ta = max(ba+ba-1,recur(ba-2,bb))
        bt = max(ba+bb,recur(ba-1,bb-2))
        return max(max(tb,ta),bt)

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

print((recur(a,b)))


# Optimized solution
def recur(ba,bb):
    tb = (2*bb)-1
    ta = (2*ba)-1
    bt = ba+bb
    return max(max(tb,ta),bt)

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

print((recur(a,b)))
# Original solution
A,B = list(map(int,input().split()))

count = 0

for _ in range(2):
  if A > B:
    count += A
    A -= 1
  else:
    count += B
    B -= 1
print(count)

# Optimized solution
a,b = list(map(int,input().split()))
print((a+max(a-1,b) if a>b else b+max(a,b-1)))
# Original solution
N, M = [int(i) for i in input().split(' ')]
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)

s = input().strip()
d = {}
starts = set()
for s1 in 'AB':
    d[s1] = {}
    for s2 in 'AB':
        d[s1][s2] = defaultdict(set)
for ll in sys.stdin:
    i, j = ll.strip().split(' ')
    i, j = int(i)-1, int(j)-1
    d[s[i]][s[j]][i].add(j)
    d[s[j]][s[i]][j].add(i)
    if s[i] == 'A' and s[j] == 'A':
        starts.add(i)


checked = set()
def walk(i, depth, path):
    if depth == 0:
        dd = d['A']['A']
    elif depth == 1:
        dd = d['A']['B']
    elif depth == 2:
        dd = d['B']['B']
    else:
        dd = d['B']['A']
    checked.add(((depth)%4, i))
    if len(dd[i]) == 0:
        return False
    r = False
    for item in dd[i]:
        if ((depth+1)%4, item) in path:
            return True
        if ((depth+1)%4, item) not in checked:
#            r = r or walk(item, (depth+1) % 4, path + [((depth+1)%4 ,item)])
            r = r or walk(item, (depth+1) % 4, path | {((depth+1)%4 ,item)})
    return r

result = False
for item in starts:
    if item not in checked:
        result = result or walk(item, 0, {(0, item)})
#        result = result or walk(item, 0, [(0, item)])
if result:
    print('Yes')
else:
    print('No')


# Optimized solution
N, M = [int(i) for i in input().split(' ')]
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)

s = input().strip()
d = {}
starts = set()
for s1 in 'AB':
    d[s1] = {}
    for s2 in 'AB':
        d[s1][s2] = defaultdict(set)
for ll in sys.stdin:
    i, j = ll.strip().split(' ')
    i, j = int(i)-1, int(j)-1
    d[s[i]][s[j]][i].add(j)
    d[s[j]][s[i]][j].add(i)
    if s[i] == 'A' and s[j] == 'A':
        starts.add(i)


checked = set()
def walk(i, depth, path):
    if depth == 0:
        dd = d['A']['A']
    elif depth == 1:
        dd = d['A']['B']
    elif depth == 2:
        dd = d['B']['B']
    else:
        dd = d['B']['A']
    checked.add(((depth)%4, i))
    if len(dd[i]) == 0:
        return False
    r = False
    for item in dd[i]:
        if ((depth+1)%4, item) in path:
            return True
        if ((depth+1)%4, item) not in checked:
#            r = r or walk(item, (depth+1) % 4, path + [((depth+1)%4 ,item)])
            path.add(((depth+1)%4, item))
            r = r or walk(item, (depth+1) % 4, path)
            path.remove(((depth+1)%4, item))
    return r

result = False
for item in starts:
    if item not in checked:
        result = result or walk(item, 0, {(0, item)})
#        result = result or walk(item, 0, [(0, item)])
if result:
    print('Yes')
else:
    print('No')
# Original solution
import sys

def solve1(s, cache={}):
    n = len(s)
    if n == 1:
        return 1
    r = n
    while 1:
        i = 1
        while i < n:
            if s[i] != s[0]:
                for k in range(i):
                    s[k] = s[i]
                break
            if s[-i-1] != s[-1]:
                for k in range(i):
                    s[-k-1] = s[-i-1]
                break
            i += 1
        if n == i:
            break
        r = min(r, n - i)
    return r


line = sys.stdin.readline().strip()
print((solve1(list(line))))


# Optimized solution
import sys

def solve1(s):
    n = len(s)
    i = 0
    while i <= n // 2:
        if s[n // 2] != s[n // 2 - i]:
            break
        if s[(n - 1) // 2] != s[(n - 1) // 2 + i]:
            break
        i += 1
    return (n - 1) // 2 + i


line = sys.stdin.readline().strip()
print((solve1(list(line))))
# Original solution
n,q=list(map(int,input().split()))
ans=[0]*n
for i in range(q):
    a,v=list(map(int,input().split()))
    ans[a-1]+=v
    t=ans.index(max(ans))
    print(t+1,ans[t])
exit()

# Optimized solution
n,q=list(map(int,input().split()))
ans=[0]*n
t=-1
for i in range(q):
    a,v=list(map(int,input().split()))
    ans[a-1]+=v
    if v<0:
        t=-1
    if t==-1:
        t=ans.index(max(ans))
    elif ans[t]<ans[a-1] or (ans[t]==ans[a-1] and t>a-1):
        t=a-1
    print(t+1,ans[t])
exit()
# Original solution
n,q=list(map(int,input().split()))
ans={}
t=-1
for i in range(q):
    a,v=list(map(int,input().split()))
    if a in ans:
        ans[a]+=v
    else:
        ans[a]=v
    if t==-1:
        t=a
    elif ans[a]>ans[t] or (ans[a]==ans[t] and a<t):
        t=a

    if v<0:
        t=-1
    if t==-1:
        for i in ans:
            if t==-1:
                t=i
            elif ans[t]<ans[i]:
                t=i
            elif ans[t]==ans[i] and t>i:
                t=i
    print(t,ans[t])
exit()

# Optimized solution
n,q=list(map(int,input().split()))
ans=[0]*n
key=value=0
for i in range(q):
    a,v=list(map(int,input().split()))
    a-=1
    ans[a]+=v
    if a==key and v<0:
        value=max(ans)
        key=ans.index(value)
    elif ans[a]>value:
        key=a
        value=ans[a]
    elif ans[a]==value and a<key:
        key=a
    print(key+1,value)
# Original solution
from heapq import heappush, heappop
inputs = lambda: list(map(int, input().split()))
n, q = inputs()
n += 1
que = [(0, 1, -1)]
data = [0] * n
T = [-1] * n
for t in range(q):
    a, v = inputs()
    data[a] += v
    T[a] = t

    heappush(que, (-data[a], a, t))
    while 1:
        v, k, p = heappop(que)
        if T[k] == p:
            print(k, -v)
            heappush(que, (v, k, p))
            break

# Optimized solution
from heapq import heappush, heappop
inputs = lambda: list(map(int, input().split()))
n, q = inputs()
n += 1
que = [(0, 1, -1)]
data = [0] * n
T = [-1] * n
for t in range(q):
    a, v = inputs()
    data[a] += v
    T[a] = t

    heappush(que, (-data[a], a, t))
    v, k, p = que[0]
    while T[k]!=p:
        heappop(que)
        v, k, p = que[0]
    print(k, -v)
# Original solution
n, q = list(map(int, input().split()))
s = [0]*n
for i in range(q):
	a,v = list(map(int, input().split()))
	s[a-1] += v
	ss = sorted(s,reverse=True)
	print(s.index(ss[0])+1,ss[0])

# Optimized solution
n, q = list(map(int, input().split()))
s = [0]*n
mx,mxa = 0, 0
for i in range(q):
	a,v = list(map(int, input().split()))
	s[a-1] += v
	if v > 0:
		if s[a-1] > mx:
			mx = s[a-1]
			mxa = a-1
		elif s[a-1] == mx:
			if a-1 < mxa:
				mxa = a-1
	elif v < 0:
		if a-1 == mxa:
			mx = max(s)
			mxa = s.index(mx)
	print(mxa+1,mx)