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


def myAnswer(N:int,K:int,P:list) ->  int:
   ans =[]
   for p in P:
      tmp =(p+1)/2
      ans.append(tmp)
   accum = []
   for i in range(0,N-K+1,1):
      accum.append(sum(ans[i:i+K]))
   # print(accum)
   return max(accum)

def modelAnswer():
   return
def main():
   N,K = map(int,input().split())
   P = list(map(int,input().split()))
   print(myAnswer(N,K,P[:]))
if __name__ == '__main__':
   main()

### FIXED CODE ###

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

ruisekiwa=[0]

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

max_value=0
for i in range(N-K+1):
    tmp=ruisekiwa[i+K]- ruisekiwa[i]
    if(max_value < tmp):
        max_value=tmp
print(max_value)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,q = map(int,input().split())
tree = {i : [] for i in range(n)}
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  tree[a].append(b)
  tree[b].append(a)
score = [0 for _ in range(n)]
for i in range(q):
  p,x = map(int,input().split())
  score[p-1] += x
  
def dfs(parent,node,s):
  for n in tree[node]:
    if n == parent:
      continue
    score[n] += score[node]
    dfs(node,n,s)

dfs(-1,0,0)
  
print(*score)
 


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,q = map(int,input().split())
tree = {i : [] for i in range(n)}
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  tree[a].append(b)
  tree[b].append(a)
score = [0 for _ in range(n)]
for i in range(q):
  p,x = map(int,input().split())
  score[p-1] += x
  
def dfs(parent,node,s):
  for n in tree[node]:
    if n == parent:
      continue
    score[n] += score[node]
    dfs(node,n,s)

dfs(-1,0,0)
  
print(*score)
### BUGGY CODE ###

from math import log2,ceil
from collections import defaultdict
import sys
input=sys.stdin.readline
n=int(input())
a=tuple(map(int,input().split()))
mod=10**9+7
cnt=defaultdict(lambda :0)

for temp in a:
    if temp==0:continue
    digit=len(bin(temp))-2
    for j in range(ceil(digit)+1):
        if (temp>>j)&1:
            cnt[j]=cnt[j]+1

#print(cnt)
ans=0
for digit,count in cnt.items():
    ans=(ans+pow(2,digit)*count*(n-count))%mod
print(ans%mod)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=tuple(map(int,input().split()))
mod=10**9+7
cnt=[0]*60

for temp in a:
    if temp==0:continue
    digit=len(bin(temp))-2
    for j in range(digit):
        if (temp>>j)&1:
            cnt[j]=cnt[j]+1

#print(cnt)
ans=0
for i in range(60):
    if cnt[i]==0:continue
    ans=(ans+pow(2,i)*cnt[i]*(n-cnt[i]))%mod
print(ans%mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect

def main():
    N, Q = LI()
    XST = []
    ts = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
        ts.append(s)
        ts.append(t)
    ts.sort()
    ts.append(INF)
    D = []
    for _ in range(Q):
        D.append(II())
    xs = [INF] * (N * 2 + 1)
    XST.sort(reverse=True)
    for x, s, t in XST:
        s0 = bisect(ts, s)
        t0 = bisect(ts, t)
        for i in range(s0, t0):
            xs[i] = x
    for d in D:
        y = bisect(ts, d)
        y = xs[y]
        if y == INF:
            y = -1
        print(y)
    return

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
    D = []
    for _ in range(Q):
        D.append(II())
    ans = [-1] * Q
    nexts = [-1] * Q
    XST.sort()
    for x, s, t in XST:
        i = bisect_left(D, s)
        end = bisect_left(D, t)
        while i < end:
            if nexts[i] == -1:
                ans[i] = x
                nexts[i] = end
                i += 1
            else:
                i = nexts[i]
    for y in ans:
        print(y)
    return

main()
### BUGGY CODE ###

N, K = map(int, input().split())
dK = 2*K

MeetDemand =[[0 for c in range(dK+1)] for r in range(dK)]
for i in range(N):
    x, y, c =input().split()
    x = int(x) % dK
    y = int(y) 
    if c == "W":
        y += K
    y %= dK
    if 0 <= x < K and 0 <= y < K:
        MeetDemand[0][0] += 1
        MeetDemand[x+1][y+1] += 2
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][0] -= 1
        MeetDemand[0][y+K+1] += 1
        MeetDemand[x+1][y+K+1] -= 2
    elif 0 <= x < K:
        MeetDemand[0][y-K+1] += 1
        MeetDemand[x+1][y-K+1] -= 2
        MeetDemand[x+1][0] += 1
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][y+1] += 2
    elif 0 <= y < K:
        MeetDemand[x-K+1][0] += 1
        MeetDemand[x-K+1][y+1] -= 2
        MeetDemand[0][y+1] += 1
        MeetDemand[0][y+K+1] -= 1
        MeetDemand[x-K+1][y+K+1] += 2
    else:
        MeetDemand[0][0] += 1
        MeetDemand[0][y-K+1] -= 1
        MeetDemand[x-K+1][0] -= 1
        MeetDemand[x-K+1][y-K+1] += 2
        MeetDemand[0][y+1] += 1
        MeetDemand[x-K+1][y+1] -= 2

for x in range(K):
    for y in range(1, dK+1):
        MeetDemand[x][y] += MeetDemand[x][y-1]
Ans = max(MeetDemand[0][:dK+1])
for y in range(dK+1):
    for x in range(1, K):
        MeetDemand[x][y] += MeetDemand[x-1][y]
        Ans = max(Ans, MeetDemand[x][y])
print(Ans)

### FIXED CODE ###

N, K = map(int, input().split())
dK = 2*K

MeetDemand =[[0 for y in range(dK+1)] for x in range(K+1)]
for i in range(N):
    x, y, c =input().split()
    x = int(x) % dK
    y = (int(y)+K if c=="W" else int(y)) % dK
    if K <= x:
        if 0 <= y < K:
            x -= K
            y += K
        else:
            x %= K
            y %= K
    if 0 <= y < K:
        MeetDemand[0][0] += 1
        MeetDemand[x+1][y+1] += 2
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][0] -= 1
        MeetDemand[0][y+K+1] += 1
        MeetDemand[x+1][y+K+1] -= 2
    else:
        MeetDemand[0][y-K+1] += 1
        MeetDemand[x+1][y-K+1] -= 2
        MeetDemand[x+1][0] += 1
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][y+1] += 2

for x in range(K):
    for y in range(1, dK):
        MeetDemand[x][y] += MeetDemand[x][y-1]
for y in range(dK):
    for x in range(1, K):
        MeetDemand[x][y] += MeetDemand[x-1][y]

Ans = max(MeetDemand[0][:dK])
for i in range(1, K):
    Ans = max(Ans, max(MeetDemand[i][:dK]))
print(Ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[i+1 for i in range(0, N)]
for i in range(0, N):
    print(A.index(B[i])+1,end=" ")

### FIXED CODE ###

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

import sys
import math
input = sys.stdin.readline
ceil = math.ceil

def main():
    def isok(z,val):##適宜変更
        return (z-val<=2*d)
    def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1
        ok = -1
        ng = len(ls)
        idx = (ok+ng)//2
        while ng-ok>1:
            num = ls[idx]
            if isok(num,val):
                ok = idx
            else:
                ng = idx
            idx = (ok+ng)//2
        return ok ##一番右のTrueのindex  Trueの個数はok+1こ

    n,d,a = map(int,input().split())
    mon = []
    for i in range(n):
        x,h = map(int,input().split())
        mon.append((x,h))
    mon.sort()
    keys = [ls[0] for ls in mon] #bisect用の配列

    damage = [0]*(n+1)
    ans = 0
    for i in range(n):
        x,h = mon[i]
        res = h-damage[i]
        if res>0:##体力が残ってたら
            c = ceil(res/a)
            ans+=c
            idx = bisect(keys[i:],x) ##爆風が届くぎりぎりの位置
            if idx==-1:continue
            damage[i] +=a*c
            damage[i+idx+1] -=a*c
        damage[i+1] += damage[i]
    print(ans)
if __name__=="__main__":
    main()


### FIXED CODE ###

import sys
import math
input = sys.stdin.readline
ceil = math.ceil

def main():
    def isok(z,val):##適宜変更
        return (z-val<=2*d)
    def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1
        ok = -1
        ng = len(ls)
        idx = (ok+ng)//2
        while ng-ok>1:
            num = ls[idx]
            if isok(num,val):
                ok = idx
            else:
                ng = idx
            idx = (ok+ng)//2
        return ok ##一番右のTrueのindex  Trueの個数はok+1こ

    n,d,a = map(int,input().split())
    mon = []
    for i in range(n):
        x,h = map(int,input().split())
        mon.append((x,h))
    mon.sort()
    keys = [ls[0] for ls in mon] #bisect用の配列

    damage = [0]*(n+1)
    ans = 0
    for i in range(n):
        x,h = mon[i]
        res = h-damage[i]
        if res>0:##体力が残ってたら
            c = ceil(res/a)
            ans+=c
            idx = bisect(keys,x) ##爆風が届くぎりぎりの位置
            if idx==-1:continue
            damage[i] +=a*c
            damage[idx+1] -=a*c
        damage[i+1] += damage[i]
    print(ans)
if __name__=="__main__":
    main()
### BUGGY CODE ###

n,q=map(int,input().split())
ab=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*(n-1)]
pq=[list(map(int,input().split())) for _ in [0]*q]
for i in range(q):
    pq[i][0]-=1

graph=[[] for _ in [0]*n]
[graph[a].append(b) for a,b in ab if a<b]
[graph[b].append(a) for a,b in ab if a>b]

plus=[0 for _ in [0]*n]
for i,j in pq:
    plus[i]+=j

pos=[]
ans=[0 for _ in [0]*n]
temp=0
q=[0]
memo=[False for _ in [0]*n]
#memo[0]=True
while q:
    i=q.pop(-1)
    if memo[i]==False:
        pos.append(i)
        temp+=plus[i]
        ans[i]=temp
    memo[i]=True

    g=graph[i]
    for j in g:
        if memo[j]==False:
            q.append(j)
            break
    else:
        temp-=plus[pos[-1]]
        pos.pop(-1)
        if pos!=[]:
            q.append(pos[-1])
print(*ans)

### FIXED CODE ###

n,q=map(int,input().split())
ab=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*(n-1)]
pq=[list(map(int,input().split())) for _ in [0]*q]
for i in range(q):
    pq[i][0]-=1

graph=[[] for _ in [0]*n]
[graph[a].append(b) for a,b in ab if a<b]
[graph[b].append(a) for a,b in ab if a>b]

plus=[0 for _ in [0]*n]
for i,j in pq:
    plus[i]+=j

pos=[]
ans=[0 for _ in [0]*n]
temp=0
q=[0]
memo=[False for _ in [0]*n]

while q:
    i=q.pop(-1)
    if memo[i]==False:
        pos.append(i)
        temp+=plus[i]
        ans[i]=temp
    memo[i]=True

    while graph[i]:
        j=graph[i].pop(-1)
        if memo[j]==False:
            q.append(j)
            break
    else:
        temp-=plus[pos[-1]]
        pos.pop(-1)
        if pos!=[]:
            q.append(pos[-1])
print(*ans)
### BUGGY CODE ###

def main():
    K,S = map(int,input().split())

    count = 0
    for x in range(K + 1):
        for y in range(K + 1):
            for z in range(K + 1):
                if x + y + z == S:
                    count += 1
    print(count)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    K,S = map(int,input().split())

    count = 0
    for x in range(max(0,S - 2*K), K + 1):
        for y in range(max(0,S - x - K), K + 1):
            if 0 <= S - x - y <= K:
                count += 1
    print(count)

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

import re

s =  input()

ret = 0
t = re.subn('ABC', 'BCA', s)

while t[1] :
    ret += t[1]
    t = re.subn('ABC', 'BCA', t[0])

print(ret)

### FIXED CODE ###

s =  list(input())

ret = 0
i = 0
a = 0
bc = 0

while True :
    while i < len(s) and s[i] == 'A' :
        a += 1
        i += 1

    while i < len(s) - 1 and s[i:i+2] == ['B', 'C']  :
        bc += 1
        i += 2

    ret += a * bc

    bc = 0

    if i < len(s) and s[i] != 'A' :
        a = 0
        
    while i < len(s) and s[i] != 'A' :
        i += 1

    if i >= len(s) - 1 :
        break
    

print(ret)
### BUGGY CODE ###

n = int(input())
suuretu = list(map(int,input().split()))
nn = frg = 0

while nn <= n-2:
    mm = nn+1
    while mm <= n-1:
        if suuretu[nn] == suuretu[mm]:
            frg = 1
            break
        else:
            mm +=1
    nn += 1
if frg == 1:
    print('NO')
else:
    print('YES')

### FIXED CODE ###

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

if len(li) == len(set(li)):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

n, k, q = map(int, input().split())
point = {}
tmp = 0

for i in range(q):
    tmp = int(input())
    if tmp in point:
        point[tmp] += 1

    else:
        point[tmp] = 1

for b in range(1, n + 1):
    tmp = 0
    for c in point:
        if c == b:
            continue

        else:
            tmp += point[c]

    if tmp >= k:
        print("No")

    else:
        print("Yes")


### FIXED CODE ###

n, k, q = map(int, input().split())
point = {}
tmp = 0

for i in range(q):
    tmp = int(input())
    if tmp in point:
        point[tmp] += 1

    else:
        point[tmp] = 1

total = sum(point.values())

for b in range(1, n + 1):
    if b in point:
        if total - point[b] >= k:
            print("No")
        else:
            print("Yes")

    else:
        if total >= k:
            print("No")

        else:
            print("Yes")
### BUGGY CODE ###

def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista 

def ciasteczka(): 
    N, K = wczytaj_liste()
    max_cukierkow = wczytaj_liste()
    przed = [1]
    for dziecko in max_cukierkow:
        po = [0]* max(len(przed)+ dziecko, K+1)
        for i in range(len(po)):
            for b in range(dziecko+1):
                j = i - b
                if  0 <= j < len(przed):
                    po[i] += przed[j]
                    if po[i] >= 10**9+7:
                        po[i] -= 10**9+7
        przed = po
    print(przed[K])
    
ciasteczka() 

### FIXED CODE ###

def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista 

def ciasteczka(): 
    N, K = wczytaj_liste()
    max_cukierkow = wczytaj_liste()
    przed = [1]
    for dziecko in max_cukierkow:
        po = [None]* min(len(przed)+ dziecko, K+1)
        suma_kroczaca = 0
        for i in range(len(po)):
            if len(przed) > i: #trzeba dodać
                suma_kroczaca += przed[i]
            if i-dziecko-1 > -1:
                suma_kroczaca -= przed[i-dziecko-1]
            suma_kroczaca %= 10**9+7
            po[i] = suma_kroczaca
        przed = po
    if K < len(przed):
        print(przed[K])
    else:
        print(0)
    
ciasteczka()
### BUGGY CODE ###

tmp = [int(i) for i in input().split()]
N,Q = tmp[0],tmp[1]
S = [str(i) for i in input().split()][0]

for i in range(Q):
  L = [int(i) for i in input().split()]
  s = S[L[0]-1:L[1]]

  cnt = 0
  for i in range(0,len(s)):
    if s[i]=='A':
      if i+1!=len(s) and s[i+1]=='C':
        cnt+=1
  print(cnt)


### FIXED CODE ###

tmp = [int(i) for i in input().split()]
N,Q = tmp[0],tmp[1]
S = [str(i) for i in input().split()][0]

cnt=0
num=[0]
for i in range(len(S)):
  if S[i-1]=='A':
    if S[i]=='C':
      cnt+=1
  num.append(cnt)

for i in range(Q):
  L = [int(i) for i in input().split()]
  print(num[L[1]]-num[L[0]])
### BUGGY CODE ###

#
# abc067 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """6
1 2 3 4 5 6"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2
10 -10"""
        output = """20"""
        self.assertIO(input, output)


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

    ans = float("inf")
    S = sum(A)
    if N == 2:
        ans = abs(A[0]-A[1])
    else:
        for i in range(1, N-1):
            t = sum(A[:i])
            ans = min(ans, abs(S-2*t))
    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()


### FIXED CODE ###

#
# abc067 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """6
1 2 3 4 5 6"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2
10 -10"""
        output = """20"""
        self.assertIO(input, output)


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

    ans = float("inf")
    S = sum(A)
    T = []
    T.append(A[0])
    for i in range(1, N):
        T.append(T[i-1]+A[i])

    if N == 2:
        ans = abs(A[0]-A[1])
    else:
        for i in range(1, N-1):
            ans = min(ans, abs(S-2*T[i]))
    print(ans)


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

N,K = map(int,input().split())
A = list(map(int,input().split()))
A = [0] + A
stack = [A[1]]
while True:
    last = A[stack[-1]]
    if last in stack:
        ind = stack.index(last)
        if ind == stack[-1]:
            break
    stack.append(last)
    if len(stack) == K:
        print(stack[-1])
        exit(0)
mod = len(stack[ind:])
idx = ind + (K-ind-1)%mod
print(stack[idx])

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    A = list(map(lambda x: int(x)-1, input().split()))
    now = 0
    dict_ = {}
    stack = []
    for i in range(N):
        if now not in dict_:
            dict_[now] = A[now]
            stack.append(now)
            now = A[now]
        else:
            idx = stack.index(now)
            mod = i - idx
            break
    idx = idx + (K-idx) % mod
    idx = min(K, idx)
    print(stack[idx]+1)


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

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

gates = []
for _ in range(m):
    gates.append(tuple(map(int, input().split())))

gates.sort(key=lambda x: (x[0], x[1]), reverse=True)

count = 0
for i in range(1, n+1):
    for gate in gates:
        if i < gate[0] or gate[1] < i :
            break
    else:
        count += 1
print(count)


### FIXED CODE ###

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

gates = []
start, end = 1, n
for _ in range(m):
    L, R = map(int, input().split())
    if L > start:
        start = L
    if R < end:
        end = R

print(len(range(start, end+1)))
### BUGGY CODE ###

N, A, B = map(int, input().split())
X = list(map(int, input().split()))
dif = [X[i+1] - X[i] for i in range(N-1)]
dif = sorted(dif)
ans = 10**100
for k in range(N):
    ans = min(ans, B*k + A*sum(dif[:N-1-k]))
print(ans)

### FIXED CODE ###

N, A, B = map(int, input().split())
X = list(map(int, input().split()))
ans = 0
for i in range(N-1):
    ans += min((X[i+1] - X[i]) * A, B) 
print(ans)
### BUGGY CODE ###

D = input()
D = int(D)
while True:
    pass

if D == 25:
    print('Christmas')
elif D == 24:
    print('Christmas Eve')
elif D == 23:
    print('Christmas Eve Eve')
elif D == 22:
    print('Christmas Eve Eve Eve')


### FIXED CODE ###

D = input()
D = int(D)
if D == 25:
    print('Christmas')
elif D == 24:
    print('Christmas Eve')
elif D == 23:
    print('Christmas Eve Eve')
elif D == 22:
    print('Christmas Eve Eve Eve')
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline
n = int(input())
l = sorted([int(i) for i in input().split()])
ans = 0
for i in range(1,n-1):
    for j in range(i+1,n):
        if l[j] - l[i] >= l[i-1]:
            break
        elif i - bisect.bisect_right(l[:i-1],(l[j]-l[i])) > 0:
            ans += i - bisect.bisect_right(l[:i-1],(l[j]-l[i]))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
l = sorted([int(i) for i in input().split()])
ans = 0
for i in range(1,n-1):
    tmp=0
    for j in range(i+1,n):
        if l[j] - l[i] >= l[i-1]:
            break
        else:
            for k in range(tmp,i):
                if l[tmp] > l[j]-l[i]:
                    ans += i-tmp
                    break
                elif l[k] > l[j]-l[i]:
                    tmp = k
                    ans += i-tmp
                    break
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

a, b, n = map(int, input().split())
ans = 0
e = min(n+1,b)
s = max(int(b/a),e-1000)
for i in range(s, e):
  x = (int(a*i/b)-a*int(i/b))
  if ans < x:
    ans = x
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = [int(input()) for _ in range(M)]
s = 1
s_ = 0
for n in range(1, N+1):
  if n in A:
    s, s_ = 0, s
    continue
  s, s_ = (s + s_) % (10 ** 9 + 7), s
print(s)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = set([int(input()) for _ in range(M)])
s = [0 for _ in range(N + 1)]
s[0] = 1
if 1 not in A:
  s[1] = 1

for n in range(2, N+1):
  if n in A:
    continue
  else:
    s[n] = s[n-1] + s[n-2]
print(s[-1] % (10 ** 9 + 7))
### BUGGY CODE ###

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

l1 = [[] for i in range(n)]
l2 = []

for i in range(m):
    p,y = map(int,input().split())
    l1[p-1].append(y)
    l2.append((p,y))

for p in range(n):
    l1[p].sort()

for i in range(m):
    p = l2[i][0]
    k = l1[p-1].index(l2[i][1])+1
    p = str(p)
    k = str(k)
    ans = "0"*(6-len(p))+p+"0"*(6-len(k))+k
    print(ans)


### FIXED CODE ###

s=input().split()
n=int(s[0])
m=int(s[1])
l=[[] for i in range(100000)]
d=[{} for i in range(100000)]
inp=[]
for i in range(m):
    s=input().split()
    p=int(s[0])
    y=int(s[1])
    inp.append((p,y))
    l[p-1].append(y)
for i in range(100000):
    l[i].sort()
for i in range(100000):
    cnt=1
    for j in l[i]:
        d[i][j]=cnt
        cnt+=1
for pa in inp:
    L=pa[0]
    R=d[L-1][pa[1]]
    L=str(L)
    R=str(R)
    for i in range(6-len(L)):
        print("0",end="")
    print(L,end="")
    for i in range(6-len(R)):
        print("0",end="")
    print(R)