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

import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline

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

P=[i for i in range(N+1)]
size=[1 for i in range(N+1)]

def find(a):
    if a==P[a]:
        return a
    else:
        return find(P[a])
        
def union(b,c):
    B=find(b)
    C=find(c)
    if size[C]>size[B]:
        P[B]=P[C]
    else:
        P[C]=P[B]
G=[0 for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    G[a]+=1
    G[b]+=1
    union(a,b)
#print(P)
PP=[]
for i in range(N+1):
    PP.append(find(P[i]))
#print(PP)
PPP=[0 for i in range(N+1)]
for i in range(1,N+1):
    PPP[PP[i]]+=1
#print(PPP)

B=[[]for i in range(N+1)]
for i in range(K):
    c,d=map(int,input().split())
    B[c].append(d)
    B[d].append(c)
#print(G)
#print(B)
ans=[]
for i in range(1,N+1):
    ANS=PPP[PP[i]]-1-G[i]
    for j in B[i]:
        if PP[j]==PP[i]:
            ANS-=1
    ans.append(ANS)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline

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

P=[i for i in range(N+1)]
size=[1 for i in range(N+1)]

def find(a):
    if a==P[a]:
        return a
    else:
        return find(P[a])
        
def union(b,c):
    B=find(b)
    C=find(c)
    if size[C]>size[B]:
        P[B]=P[C]
        size[C]+=size[B]
    else:
        P[C]=P[B]
        size[B]+=size[C]
G=[0 for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    G[a]+=1
    G[b]+=1
    union(a,b)
#print(P)
PP=[]
for i in range(N+1):
    PP.append(find(P[i]))
#print(PP)
PPP=[0 for i in range(N+1)]
for i in range(1,N+1):
    PPP[PP[i]]+=1
#print(PPP)

B=[[]for i in range(N+1)]
for i in range(K):
    c,d=map(int,input().split())
    B[c].append(d)
    B[d].append(c)
#print(G)
#print(B)
ans=[]
for i in range(1,N+1):
    ANS=PPP[PP[i]]-1-G[i]
    for j in B[i]:
        if PP[j]==PP[i]:
            ANS-=1
    ans.append(ANS)
print(*ans)
### BUGGY CODE ###

N, K = map(int, input().split())
sushi = []
for i in range(N):
    s = list(map(int, input().split()))
    sushi.append(s)


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

def find_next(start, curr, point, tlist, tcount):
    if start == N:
        return [point, curr]
    max_c = curr
    max_p = point
    for s in sushi[start:]:
        if tlist[s[0]] > 0:
            continue
        for ri in range(len(curr) - 1, -1, -1):
            r = curr[ri]
            if tlist[r[0]] >= 2:
                c2 = [c for c in curr]
                t2 = [t for t in tlist]
                del c2[ri]
                c2.append(s)
                t2[r[0]] -= 1
                t2[s[0]] = 1
                p2 = point - r[1] + s[1] + (tcount + 1) * (tcount + 1) - tcount * tcount
                np, pc = find_next(start + 1, c2, p2, t2, tcount + 1)

                if np > max_p:
                    max_p = np
                    max_c = pc
                break
    return [max_p, max_c]

result = sushi[0: K]
type_count = [0] * (N + 1)

for r in result:
    type_count[r[0]] += 1
type_num = 0
for t in type_count:
    if t > 0:
        type_num += 1
point = type_num * type_num
for r in result:
    point += r[1]
ans_p, ans_c = find_next(K, result, point, type_count, type_num)

print(ans_p)

### FIXED CODE ###

N, K = map(int, input().split())
sushi = []
for i in range(N):
    s = list(map(int, input().split()))
    sushi.append(s)


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

# pick from first
point = 0
neta_set = set()
removable_idx = list()
for i in range(K):
    s = sushi[i]
    point += s[1]
    if s[0] not in neta_set:
        neta_set.add(s[0])
    else:
        removable_idx.append(i)
point += len(neta_set) **2
max_point = point

# pick latest
for s in sushi[K:]:
    if len(removable_idx) == 0:
        break
    if s[0] in neta_set:
        continue
    idx = removable_idx[-1]
    count = len(neta_set)
    point += s[1] - sushi[idx][1]
    point += (count + 1) ** 2 - count ** 2
    neta_set.add(s[0])
    removable_idx = removable_idx[:-1]

    if point > max_point:
        max_point = point
print(max_point)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())
m = int(n)
a = list(map(int,input().split()))
cnt = 0
s = 0

def ers(n,m,a,cnt,s):
    if len(a) == 0:
        cnt = -1
        return cnt
    for i in range(s,n):
        if i+1 != a[i]:
            a.pop(i)
            cnt+=1
            n -= 1
            if cnt > m-1:
                cnt = -1
                return cnt
            return ers(n,m,a,cnt,s)
        else:
            s += 1
    return cnt

res = ers(n,m,a,cnt,s)

print(str(res))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(N):
    if A[i] != i+1-cnt:
        cnt += 1
if cnt == N:
    print(-1)
else:
    print(cnt)
### BUGGY CODE ###

import collections
n = int(input())
a_list = list(map(int, input().split()))
come_list = [0] * (n+1)
come_num = 1
for a in a_list:
  come_list[a] = come_num
  come_num += 1

ret_str = ""
for index in range(1, len(a_list)+1):
  ret_str += str(come_list[index])
  ret_str += " "
print(ret_str)

### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
come_list = [0] * n
come_num = 0
for a in a_list:
  come_list[a-1] = come_num+1
  come_num += 1

print(*come_list)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
  ans=a.index(i)+1
  if(i!=n):
     print(ans,end=" ")
  else:
    print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
for i , j in enumerate(a):
  ans[j-1]=i+1
print(*ans)
### BUGGY CODE ###

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

A.sort()
B.sort()
C.sort()
ans = 0
for i in A:
    for j in B:
        for k in C:
            if (i<j)&(j<k):
                ans += 1
print(ans)

### FIXED CODE ###

import bisect
n= int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()
ans = 0
for i in range(n):
    x = bisect.bisect_left(a,b[i])
    y = bisect.bisect_right(c,b[i])
    ans += x*(n-y)
print(ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from collections import deque
    from collections import defaultdict

    N = int(input())
    # 1-indexed
    A = [deque() for _ in range(N+1)]
    # O(N^2)
    for i in range(1,N+1):
        for j in input().split():
            A[i].append(int(j))

    # O(N)
    def is_not_empty():
        for x in A:
            if x:
                return True
        return False

    answer = 0
    while is_not_empty():
        played = defaultdict(int)
        for i in range(1,N+1):
            if i in played:
                continue
            if not A[i]:
                continue
            enemy = A[i].popleft()
            ME = A[enemy].popleft()
            if ME == i and played[enemy] == 0:
                played[enemy] += 1
                played[ME] += 1
            else:
                A[i].appendleft(enemy)
                A[enemy].appendleft(ME)
        if not played:
            print(-1)
            exit()
        answer += 1

    print(answer)

if __name__ == '__main__':
    main()

### FIXED CODE ###

# O(N)
def is_not_empty(A):
    for x in A:
        if x:
            return True
    return False

def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    N = int(input())
    # 1-indexed
    A = [deque() for _ in range(N+1)]
    # O(N^2)
    for i in range(1,N+1):
        for j in input().split():
            A[i].append(int(j))

    # 当日の参加者
    today = set()
    # 初日
    for i in range(1,N+1):
        # 既に参加した人はダメ
        if i in today:
            continue
        enemy = A[i].popleft()
        ME = A[enemy].popleft()
        if ME == i and not(enemy in today):
            today.add(ME)
            today.add(enemy)
        else:
            A[i].appendleft(enemy)
            A[enemy].appendleft(ME)
    # 初日に誰も試合できなかったとき
    if not today:
        print(-1)
        exit()

    # 前日の参加者
    yesterday = today
    # 日数
    answer = 1
    while is_not_empty(A):
        today = set()
        # 前日に試合した人は必ず次の日に試合する
        for i in yesterday:
            if not A[i]:
                continue
            if i in today:
                continue
            enemy = A[i].popleft()
            ME = A[enemy].popleft()
            if ME == i and not(enemy in today):
                today.add(ME)
                today.add(enemy)
            else:
                A[i].appendleft(enemy)
                A[enemy].appendleft(ME)
        if not today:
            print(-1)
            exit()
        answer += 1
        yesterday = today

    print(answer)

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

n,k = map(int, input().split())
list_x = list((map(int, input().split())))
ans = 10**9
for i in range(0,n-k+1):
    prob_list = list_x[i:i+k]
    dist = min(abs(list_x[i]),abs(list_x[i+k-1])) + (list_x[i+k-1] - list_x[i])
    if ans > dist:
        ans = dist
print(ans)


### FIXED CODE ###

def binarySearch(list_a, key):
    left = 0
    right = len(list_a)
    while left < right:
        mid = (left + right) // 2
        if list_a[mid] == key:
            return mid
            break
        elif key < list_a[mid]:
            right = mid
        else:
            left = mid+1
    else:
        return mid

n,k = map(int, input().split())
list_x = list((map(int, input().split())))
ans = 10**9
key_point = binarySearch(list_x,0)
for i in range(key_point-k,key_point+1):
    if i < 0:
        continue
    try:
        dist = min(abs(list_x[i]),abs(list_x[i+k-1])) + (list_x[i+k-1] - list_x[i])
        if ans > dist:
            ans = dist
    except:
        pass
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from heapq import heappushpop

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

# B_x = max {A_y | y\subset x}
# と思ったが、2元ずつ持つ必要がある。
# (値、何番から来たか)
B = []
for n,a in enumerate(A):
    arr = [(0,0),(a,n)]
    m = n
    while m:
        bit = m & (-m)
        (x,i),(y,j) = B[n-bit]
        if (x,i) != arr[-1]:
            heappushpop(arr,(x,i))
        if (y,j) != arr[-1]:
            heappushpop(arr,(y,j))
        m -= bit
    B.append(arr)

answer = [0]
for (x,i),(y,j) in B[1:]:
    z = answer[-1]
    if z < x + y:
        z = x + y
    answer.append(z)
print('\n'.join(map(str,answer[1:])))



### FIXED CODE ###

import sys
input = sys.stdin.readline
from heapq import heappushpop

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

# B_x = max {A_y | y\subset x}
# と思ったが、2元ずつ持つ必要がある。
# (値、何番から来たか)
B = []
for n,a in enumerate(A):
    arr = [(0,0),(a,n)]
    m = n
    while m:
        bit = m & (-m)
        (x,i),(y,j) = B[n-bit]
        if (x,i) != arr[-1]:
            heappushpop(arr,(x,i))
        if (y,j) != arr[-1]:
            heappushpop(arr,(y,j))
        m -= bit
    B.append(arr)

answer = [0]
for (x,i),(y,j) in B[1:]:
    z = answer[-1]
    if z < x + y:
        z = x + y
    answer.append(z)
print('\n'.join(map(str,answer[1:])))
### BUGGY CODE ###

from queue import deque
def main():
    R, W = "R", "W"
    N = int(input())
    _C = input()
    C = deque(_C)

    count = 0
    while True:
        i = len(C) -1
        while C[i] != R:
            i -= 1
            if i < 0:
                break
        j = 0
        while C[j] != W:
            j +=1
            if j >= len(C):
                break
        if  i < j:
            break
        C[i], C[j] = C[j], C[i]
        count += 1
    
    print(count)
if __name__ == '__main__':
    main()


### FIXED CODE ###

from queue import deque
def main():
    R, W = "R", "W"
    N = int(input())
    C = input()

    counter = dict()
    for c in C:
        counter[c] = counter.get(c, 0) + 1
    r = counter.get(R, 0)

    _counter = dict()
    for c in C[r:]:
        _counter[c] = _counter.get(c, 0) + 1
    _r = _counter.get(R, 0)

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

H, W = map(int, input().split())
A = [None]*H
for i in range(H):
    A[i] = list(map(int, input().split()))
B = [None]*H
for i in range(H):
    B[i] = list(map(int, input().split()))

# C: A-Bの絶対値を持つ
C = [[None]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])

K = 80*(H+W-1)
dp = [[[0]*(K+1) for _ in range(W)] for _ in range(H)]
dp[0][0][C[0][0]] = 1

for i in range(H):
    for j in range(W):
        for k in range(K+1):
            if i and dp[i-1][j][k]:
                dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1
            if j and dp[i][j-1][k]:
                dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1

for k in range(K+1):
    res = dp[H-1][W-1][k]
    if res:
        print(k)
        exit()

### FIXED CODE ###

H, W = map(int, input().split())
A = [None]*H
for i in range(H):
    A[i] = list(map(int, input().split()))
B = [None]*H
for i in range(H):
    B[i] = list(map(int, input().split()))

# C: A-Bの絶対値を持つ
C = [[None]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])

K = 80*(H+W-1)//2 + 1# 80*(H+W-1)の半分を超えるのは無駄
dp = [[[0]*(K+1) for _ in range(W)] for _ in range(H)]# 答えから80*(H+W-1)を引く
dp[0][0][C[0][0]] = 1

for i in range(H):
    for j in range(W):
        for k in range(K+1):
            if i and dp[i-1][j][k]:
                if k+C[i][j] < K:
                    dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1
            if j and dp[i][j-1][k]:
                if k+C[i][j] < K:
                    dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1

for k in range(K+1):
    res = dp[H-1][W-1][k]
    if res:
        print(k)
        break
### BUGGY CODE ###

while True:
	n=int(input())
	if n==0:
		break
	A=[]
	for i in range(n):
		A.append(int(input()))
	MAX=[0]*(len(A))
	end=len(A)
	for i in range(end):
		for j in range(i+1,end+1):
			s=sum(A[i:j])
			if MAX[i]<s:
				MAX[i]=s
	print(max(MAX))

### FIXED CODE ###

while True:
	n=int(input())
	if n==0:
		break
	A=[]
	for i in range(n):
		x=int(input())
		A.append(x)

	B=[int()]*n
	B[0]=A[0]
	for i in range(1,n):
		if A[i]>=A[i]+B[i-1]:
			B[i]=A[i]
		else:
			B[i]=A[i]+B[i-1]
	print(max(B))
### BUGGY CODE ###

n = int(input())

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


s = 0
for i in range(n):
  if a.count(a[i]) is not 1:
    s+=1
if s == 0:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

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

import sys

sys.setrecursionlimit(10 ** 5)


class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0 for _ in range(n + 1)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y

        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N, K, L = map(int, input().split())
r_union_find = UnionFind(N)
t_union_find = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    r_union_find.union(p, q)

for i in range(L):
    r, s = map(int, input().split())
    t_union_find.union(r, s)

answers = []

for i in range(1, N + 1):
    count = 0
    r_p = r_union_find.find(i)
    t_p = t_union_find.find(i)
    for j in range(1, N + 1):
        if r_p == r_union_find.find(j) and t_p == t_union_find.find(j):
            count += 1
    answers.append(count)
answers = map(str, answers)
print(" ".join(answers))


### FIXED CODE ###

import sys
from collections import Counter

sys.setrecursionlimit(10 ** 5)


class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0 for _ in range(n + 1)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y

        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N, K, L = map(int, input().split())
r_union_find = UnionFind(N)
t_union_find = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    r_union_find.union(p, q)

for i in range(L):
    r, s = map(int, input().split())
    t_union_find.union(r, s)

pair = []

for i in range(1, N + 1):
    count = 0
    r_p = r_union_find.find(i)
    t_p = t_union_find.find(i)
    pair.append((r_p, t_p))

counter = Counter(pair)

answers = []
for p in pair:
    answers.append(counter[p])

answers = map(str, answers)
print(" ".join(answers))
### BUGGY CODE ###

def f(x, y, z, n):
    if (x+y+z)**2 - x*y - y*z - z*x == n:
        return True
    return False


N = int(input())
for i in range(1, N+1):
    ans = 0
    for x in range(1, int(i**0.5)+2):
        for y in range(x, int(i**0.5)+2):
            for z in range(y, int(i**0.5)+2):
                if f(x, y, z, i):
                    if x == y == z:
                        ans += 1
                    elif x == y or y == z or z == x:
                        ans += 3
                    else:
                        ans += 6
    print(ans)


### FIXED CODE ###

def f(x, y, z):
    return (x+y+z)**2 - x*y - y*z - z*x


N = int(input())
for i in range(1, N+1):
    ans = 0
    for x in range(1, int(i**0.5)+2):
        for y in range(x, int(i**0.5)+2):
            if f(x, y, y-1) >= i:
                break
            l = y - 1
            r = int(i**0.5) + 1
            while r >= l:
                z = (r+l) // 2
                if f(x, y, z) == i:
                    if x < y:
                        if x == z or y == z:
                            ans += 3
                        else:
                            ans += 6
                    else:
                        if z == y:
                            ans += 1
                        else:
                            ans += 3
                if f(x, y, z) > i:
                    r = z - 1
                else:
                    l = z + 1

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

n = int(input())
a = 0
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return len(lower_divisors + upper_divisors[::-1])
for j in range(1,n+1):
    a += j * make_divisors(j)
print(a)


### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
  ans+=(i+i*(n//i))*(n//i)//2
print(ans)
### BUGGY CODE ###

import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
from fractions import gcd

mod = 10**9+7

n = ni()
a = na()
b,c = 1,0

def lcm(m,n):
    return (m*n)//gcd(m,n)

for i in a:
    b=lcm(b,i)

for i in a:
    c+=b//i

print(c%mod)

### FIXED CODE ###

import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
from fractions import gcd

mod = 10**9+7

n = ni()
a = na()
b,c = 1,0

def lcm(m,n):
    return (m*n)//gcd(m,n)

for i in a:
    b=lcm(b,i)

for i in a:
    c+=b//i

print(c%mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
N = int(input())

match = [[-1] * (N) for _ in range(N)]
c = 0
for i in range(N):
    for j in range(i+1, N):
        match[i][j] = c
        c += 1


def get_id(i, j):
    if i > j:
        i, j = j, i
    return match[i][j]


G = {k: [] for k in range(c)}
for i in range(N):
    L = map(int, input().split())
    pid = -1
    for l in L:
        id = get_id(i, l-1)
        if pid != -1:
            G[id].append(pid)
        pid = id

visited = [False]*c
calculated = [False]*c
dp = [-1]*c


def dfs(v):
    if dp[v] >= 0:
        return dp[v]
    visited[v] = True
    dp[v] = 1
    for nxt in G[v]:
        if visited[nxt] is True and calculated[nxt] is False:
            print(-1)
            exit()
        d = dfs(nxt)
        if d >= dp[v]:
            dp[v] = d+1
    calculated[v] = True
    return dp[v]


ans = 0
for i in range(c):
    res = dfs(i)
    ans = max(ans, res)
print(ans)


### FIXED CODE ###

from collections import deque

N = int(input())
L = [deque([int(i)-1 for i in input().split()]) for i in range(N)]

q = deque(range(N))
d = [0 for i in range(N)]
pairs = [-1 for i in range(N)]
while q:
    a = q.popleft()  # qの左端の選手のindexをpopleft
    if len(L[a]) == 0:
        continue
    b = L[a].popleft()

    if pairs[b] == a:  # bのリクエストがaなら
        d[a] = d[b] = max(d[a], d[b]) + 1
        q.append(a)
        q.append(b)
    else:
        pairs[a] = b
print(max(d) if not any(L) else -1)
### BUGGY CODE ###

from bisect import bisect_left

n,m = list(map(int,input().split()))
a = [[0] for i in range(n)]
b = [None]*m
for i in range(m):
    p,s = list(map(int,input().split()))
    p-=1
    a[p].append(s)
    b[i] = [p,s]
for i in range(len(a)):
    a[i].sort()
for i in range(len(b)):
    ken = b[i][0]
    si = a[ken].index(b[i][1])
    si = bisect_left(a[ken], b[i][1])
    ken = str(ken+1).zfill(6)
    si = str(si).zfill(6)
    print("".join([ken,si]))

### FIXED CODE ###

from bisect import bisect_left


n,m = list(map(int,input().split()))
a = [[0] for i in range(n)]
b = [None]*m
for i in range(m):
    p,s = list(map(int,input().split()))
    p-=1
    a[p].append(s)
    b[i] = [p,s]
for i in range(len(a)):
    a[i].sort()
for i in range(len(b)):
    ken = b[i][0]
    si = bisect_left(a[ken], b[i][1])
    ken = str(ken+1).zfill(6)
    si = str(si).zfill(6)
    print("".join([ken,si]))
### BUGGY CODE ###

N,A,B = map(int,input().split())
h = [0]*N
for i in range(N):
    h[i] = int(input())

# x回で全モンスター倒せるかどうかをにぶちゃん(にぱー)

import math

def check(x):
    count = 0
    for i in range(N):
        count += math.ceil(max(h[i] - B * x, 0) / (A - B))
           
    if count <= x:
        return True
    else:
        return False
    
def solve():
    
    left = -1
    right = 10**9+1
    
    while abs(right-left) > 1:
    
        center = (right+left)//2
    
        if check(center) == True:
            right = center
        elif check(center) == False:
            left = center
        
    return right
    
print(solve())

### FIXED CODE ###

N,A,B = map(int,input().split())
h = [0]*N
for i in range(N):
    h[i] = int(input())

# x回で全モンスター倒せるかどうかをにぶちゃん(にぱー)

import math

def check(x):
    count = 0
    for i in range(N):
        count += math.ceil(max(h[i] - B * x, 0) / (A - B))
           
    if count <= x:
        return True
    else:
        return False
    
def solve():
    
    left = -1
    right = 10**9+1
    
    while abs(right-left) > 1:
    
        center = (right+left)//2
    
        if check(center) == True:
            right = center
        elif check(center) == False:
            left = center
        
    return right
    
print(solve())
### BUGGY CODE ###

N, M = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(M)]


ans = set(range(l[0][0], l[0][1] + 1))
for i in range(1, M):
    ans = ans.intersection(set(range(l[i][0], l[i][1] + 1)))
print(len(ans))

### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())

l = [list(map(int, input().split())) for _ in range(M)]
l = np.array(l)
ans = list(range(l[:, 0].max(), l[:, 1].min() + 1))
print(len(ans))