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

from operator import itemgetter
import array

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

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

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

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

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

def compute_mst_kruskal(max_v, edges):
    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(max_v)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    return weight

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))
    print(compute_mst_kruskal(N,edges))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import array
import sys
input = sys.stdin.readline

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

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

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

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

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

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

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

N = int(input())

ans = 0
L = []
for i in range(N):
    L.append(int(input()))

l = set(L)

for j in l:
    if L.count(j)%2 == 1:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())

ans = 0
L = []
ans_L = {}

for i in range(N):
    L.append(int(input()))

for j in L:
    if not j in ans_L.keys():
        ans_L[j] = 0
    
    if ans_L[j]==0:
        ans_L[j] += 1
    elif ans_L[j]== 1:
        ans_L[j] -= 1

print(sum(ans_L.values()))
### BUGGY CODE ###

S = list(input())
Q = int(input())
reverse=0
for i in range(Q):
    q=input().split()
    if int(q[0])==1:
        reverse=(reverse+1)%2
    else :      
        if (reverse+(int(q[1])-1))%2:
            S.append(q[2])
        else:
            S.insert(0,q[2])
            
if reverse:
    S.reverse()
print("".join(S))
        
    



### FIXED CODE ###

S = list(input())
Q = int(input())
reverse=0
head=[]
tail=[]
for i in range(Q):
    q=input().split()
    if int(q[0])==1:
        reverse=(reverse+1)%2
    else :      
        if (reverse+(int(q[1])-1))%2:
            tail.append(q[2])
        else:
            head.append(q[2])

            
head.reverse()
if reverse:
    tmp=head
    head=tail
    tail=tmp
    S.reverse()
    head.reverse()
    tail.reverse()
    
    
print("".join(head+S+tail))
### BUGGY CODE ###

N, K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*(N)

for i in range(1,N):
    now = h[i]
    dp[i] = min([abs(now-h[j])+dp[j] for j in range(max(i-K,0),i)])

print(dp[N-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*(N)

for i in range(1,N):
    now = h[i]
    dp[i] = min([abs(now-h[j])+dp[j] for j in range(max(i-K,0),i)])

print(dp[N-1])
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import defaultdict

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

R = []
G = []
B = []

for i in range(N):
    if S[i] == 'R':
        R.append(i)
    if S[i] == 'G':
        G.append(i)
    if S[i] == 'B':
        B.append(i)

base = len(R)*len(G)*len(B)

cnt = 0
for r in R:
    for g in G:
        for b in B:
            if abs(b-g) == abs(g-r) or abs(b-r) == abs(r-g) or abs(g-b) == abs(b-r) or abs(g-r) == abs(r-b) or abs(r-b) == abs(b-g) or abs(r-g) == abs(g-b):
                cnt += 1
print(base-cnt)

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

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

R = []
G = []
B = []

for i in range(N):
    if S[i] == 'R':
        R.append(i)
    if S[i] == 'G':
        G.append(i)
    if S[i] == 'B':
        B.append(i)

base = len(R)*len(G)*len(B)

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        k = 2*j - i
        if k >= N or S[i] == S[j] or S[j] == S[k] or S[k] == S[i]:
            continue
        cnt += 1

print(base-cnt)
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n, m = LI()
    py = LIR(m)
    city = [[] for i in range(n)]
    for p, y in py:
        city[p-1].append(y)
        city[p-1].sort()
    for p, y in py:
        a = "00000" + str(p)
        a = a[-6:]
        b = "00000" + str(city[p-1].index(y) + 1)
        b = b[-6:]
        print(a+b)    
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n, m = LI()
    py = LIR(m)
    pya = py[::1]
    py.sort(key=lambda x: x[1])
    city = [1 for i in range(n)]
    dicity = {}
    for p, y in py:
        dicity[(p,y)] = city[p-1]
        city[p-1] += 1    
    for p, y in pya:
        a = "00000" + str(p)
        a = a[-6:]
        b = "00000" + str(dicity[(p, y)])
        b = b[-6:]
        print(a+b)

    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()
### BUGGY CODE ###

""" E
    https://atcoder.jp/contests/abc173/tasks/abc173_e
"""
import sys
import math
from functools import reduce

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(N, X, M):
    A = X
    l = [A]
    i = -1
    for _ in range(1, M):
        A = (A * A) % M if M > 0 else 0
        if A in l:
            i = l.index(A)
            break
        else:
            l.append(A)

    if i == -1:
        return sum(l)
    else:
        s1 = sum(l[:i])
        len_repeat = len(l) - i
        s2 = sum(l[i:])

        return s1 + int((N-i)/len_repeat) * s2 + sum(l[i:(N-i)%len_repeat+i])

if __name__ == "__main__":
    _N, _X, _M = readIntegerSet(3)

    print(main(_N, _X, _M))

### FIXED CODE ###

""" E
    https://atcoder.jp/contests/abc173/tasks/abc173_e
"""
import sys
import math
from functools import reduce

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(N, X, M):
    A = X
    m = {A: A}
    i = -1
    for j in range(1, M):
        A = (A * A) % M if M > 0 else 0
        if A in m:
            i = list(m.keys()).index(A)
            break
        else:
            m[A] = A

    if i == -1:
        return sum(m.values())
    else:
        l = list(m.values())
        s1 = sum(l[:i])
        len_repeat = len(l) - i
        s2 = sum(l[i:])

        return s1 + int((N-i)/len_repeat) * s2 + sum(l[i:(N-i)%len_repeat+i])

if __name__ == "__main__":
    _N, _X, _M = readIntegerSet(3)

    print(main(_N, _X, _M))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = 10**9

# 個数制限なしナップザック問題
h,n = map(int, input().split())

# 二次元配列で
a,b = [],[]
for i in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

dp = [[INF] * (h + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(h + 1):
        if j <= a[i]:
            dp[i + 1][j] = min(dp[i][j], b[i])
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - a[i]] + b[i])
print(dp[n][h])

# 一次元配列で
# dp = [INF]*(h+1)
# dp[0] = 0
# for i in range(n):
#     a,b = map(int, input().split())
#     for j in range(h):
#         nj = min(a+j, h)
#         dp[nj] = min(dp[nj], dp[j]+b)
# print(dp[-1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = 10**9

# 個数制限なしナップザック問題
h,n = map(int, input().split())
dp = [INF]*(h+1)
dp[0] = 0
for i in range(n):
    a,b = map(int, input().split())
    for j in range(h):
        nj = min(a+j, h)
        dp[nj] = min(dp[nj], dp[j]+b)

print(dp[-1])
### BUGGY CODE ###

s = int(input())
result = []
ans = []
for i in range(1000000):
    if i == 0:
        result.append(s)
    elif result[i-1] % 2 == 0:
        aim = result[i - 1] // 2
        result.append(aim)
    else:
        aim = result[i - 1] * 3 + 1
        result.append(aim)
for j in range(len(result)):
    for k in range(len(result)):
        if result[j] == result[k] and j > k:
            ans.append(j)
            
print(ans[0] + 1)
            

### FIXED CODE ###

s = int(input())
a = []
while s not in a:
    a.append(s)
    if s%2 == 0:
        s = s/2
    else:
        s = 3*s+1
print(len(a)+1)
### BUGGY CODE ###

N,P=map(int,input().split())
if N==1:
  print(P)
  exit(0)
res=[]
while True:
  if P==1:
    break
  for i in range(2,P+1):
    if P%i==0:
      res.append(i)
      P//=i
      break
  else:
    break

import collections
counter=collections.Counter(res)
ans=1
for c in counter.items():
  key=c[0]
  val=c[1]
  ans*=(key**(val//N))
  
print(ans)

### FIXED CODE ###

N,P=map(int,input().split())
if N==1:
  print(P)
  exit(0)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

res=factorization(P)
  
ans=1
for c in res:
  key=c[0]
  val=c[1]
  ans*=(key**(val//N))
  
print(ans)
### BUGGY CODE ###

n = int(input())
li = [int(input()) for _ in range(n)]

idx_li = []

count = 1
bu = li[0]
idx_li.append(bu)
if bu == 2:
  print(count)
  exit()
  
while True:
  bu = li[bu - 1]
  count += 1
  
  if bu == 2:
    print(count)
    exit()
  
  if bu in idx_li:
    print(-1)
    exit()
  else:
    idx_li.append(bu)
    
  

### FIXED CODE ###

n = int(input())
li = [int(input()) for _ in range(n)]

light = 1
count = 0

for i in range(n):
  light = li[light - 1]
  count+=1
  if light == 2:
    print(count)
    exit()
print(-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

# R: 0, G: 1, B: 2

# 後ろにいくつ自分と同じ文字があるかの表を作る
DP = []
for i in range(3):
    DP.append([0] * N)

# 末尾だけループの前に代入
if S[-1] == 'R':
    DP[0][-1] = 1
elif S[-1] == 'G':
    DP[1][-1] = 1
elif S[-1] == 'B':
    DP[2][-1] = 1

for i in reversed(range(0, N - 1)):
    if S[i] == 'R':
        DP[0][i] = DP[0][i + 1] + 1
        DP[1][i] = DP[1][i + 1]
        DP[2][i] = DP[2][i + 1]
    elif S[i] == 'G':
        DP[0][i] = DP[0][i + 1]
        DP[1][i] = DP[1][i + 1] + 1
        DP[2][i] = DP[2][i + 1]
    elif S[i] == 'B':
        DP[0][i] = DP[0][i + 1]
        DP[1][i] = DP[1][i + 1]
        DP[2][i] = DP[2][i + 1] + 1

#print(DP)

ans = 0
for i in range(0, N - 2):
    for j in range(i + 1, N - 1):
        # i と j が一緒か確認
        if S[i] == S[j]:
            # 一緒であればこの2文字目はスキップ
            continue
        else:
            #print('i: {}, j: {}'.format(i, j))
            # 一緒じゃなければ3文字目(s3)を探す
            ij = (S[i], S[j])
            s3 = 'B'
            int_s3 = 2
            if 'R' not in ij:
                s3 = 'R'
                int_s3 = 0
            elif 'G' not in ij:
                s3 = 'G'
                int_s3 = 1

            # 3文字目の後ろの文字数を取得
            s3_back = DP[int_s3][j + 1]
            #print('s3: {}, s3_back = {}'.format(s3, s3_back))

            # 0ならスキップ
            if s3_back == 0:
                continue

            # j + (j - i)の場所に3文字目があれば文字数を1引く
            if j + (j - i) < N:
                if S[j + (j - i)] == s3:
                    s3_back -= 1
                    #print('kita')

            ans += s3_back

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

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

# R, G, Bの数をカウント
R_count = 0
G_count = 0
B_count = 0
for s in list(S):
    if s == 'R':
        R_count += 1
    elif s == 'G':
        G_count += 1
    elif s == 'B':
        B_count += 1

# R, G, Bの全組み合わせ数を求める
ans = R_count * G_count * B_count

# 3文字が等間隔に存在する組み合わせがあれば引いていく
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = j + (j - i)
        if k >= N:
            break
        if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            ans -= 1

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

import bisect

n=int(input())
a=list(int(input()) for i in range(n))
b=[]
b.append(-1)


for i in range(n):
    if a[i]>b[0]:
        x=bisect.bisect_right(b,a[i]-1)
        b[x-1]=a[i]
    else:
        b.insert(0,a[i])
print(len(b))

### FIXED CODE ###

import collections
from collections import deque
import bisect

n=int(input())
a=list(int(input()) for i in range(n))
b=deque()
b.append(-1)


for i in range(n):
    if a[i]>b[0]:
        x=bisect.bisect_right(b,a[i]-1)
        b[x-1]=a[i]
    else:
        b.appendleft(a[i])
print(len(b))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-

x = input()
s = x.find('ST')
cnt = 0
while s != -1:
    x = x[:s] + x[s+2:]
    cnt += 1
    s = x.find('ST')
#     print(x)
# print(cnt)
print(len(x))


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-

x = input()
n = len(x)

s, t = 0, 0
cnt = 0
for i in range(n):
    if x[i] == 'T':
        if s > 0:
            s -= 1
            cnt += 2
    elif x[i] == 'S':
        s += 1

# i = 0
# s = 0
# t = 0
# cnt = 0
# while i < n:
#     while i < n and x[i] == 'T':
#         i += 1
#         t += 1
#     tmp = min(t, s)
#     cnt += tmp * 2
#     if t - tmp == 0:
#         s -= tmp
#     else:
#         s = 0
#         t = 0

#     while i < n and x[i] == 'S':
#         i += 1
#         s += 1
print(n - cnt)
### BUGGY CODE ###

# coding: utf-8
# 133C
"""
L<=i<=j<=R
(i×j)mod 2019
0≤L<R≤2×10^9
"""

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

min2019 = 2019
for i in range(L, R):
    for j in range(R, i, -1):
        if (i * j) % 2019 < min2019:
            min2019 = (i * j) % 2019
print(min2019)

### FIXED CODE ###

# coding: utf-8
# 133C
"""
L<=i<=j<=R
(i×j)mod 2019
0≤L<R≤2×10^9
"""

def solve(L, R):
    if R - L > 2019:
        return 0
    
    tmp = 2019
    for i in range(L, R):
        for j in range(R, i, -1):
            if (i * j) % 2019 < tmp:
                tmp = (i * j) % 2019
    return tmp
 
L, R = map(int, input().split())
print(solve(L, R))
### BUGGY CODE ###

# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
#import math
import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    N=int(input())
    X=list(map(int,input().split()))
    Y=sorted(X)
    Z=[(Y[:i]+Y[i+1:])[N//2-1] for i in range(N)]

    for i in range(N):
        print(Z[Y.index(X[i])])




resolve()

### FIXED CODE ###

def resolve():
    N=int(input())
    X=list(map(int,input().split()))
    Y=sorted(X)
    l=Y[N // 2-1]
    r=Y[N//2]


    for i in X:
        if i<r:
            print(r)
        else:
            print(l)






resolve()
### BUGGY CODE ###

import numpy as np

N, M, Q = map(int, input().split())
d = np.zeros([N+1, N+1], np.int32)

for _ in range(M):
	tl,tr = map(int, input().split())
	d[tl,tr] += 1

d = np.add.accumulate(d, axis = 1)
d = np.flipud(d)

d = np.add.accumulate(d)

d = np.flipud(d)

ans = []
for _ in range(Q):
	tp,tq = map(int, input().split())

	ans.append(d[tp,tq])

for a in ans:
	print(a)

### FIXED CODE ###

import numpy as np
import sys

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

I = sys.stdin.read().split()

L,R = np.array(I[:2*M], np.int32).reshape([2,-1], order='F')
p,q = np.array(I[2*M:], np.int32).reshape(2,-1, order='F')
d = np.zeros([N+1, N+1], np.int32)

d = np.zeros([1+N, 1+N], np.int32)
np.add.at(d, (N-L,R), 1)

d = np.add.accumulate(d, axis = 1)
d = np.add.accumulate(d)

ans = d[N-p,q]

for a in ans:
	print(a)
### BUGGY CODE ###

n=int(input())

pdat=[]
mdat=[]

for i in range(n):
    s=input()
    
    mini=0
    now=0
    for q in range(len(s)):
        if s[q]=="(":
            now+=1
        else:
            now-=1
            mini=(min(mini,now))
    if now>=0:
        pdat.append((now,mini,mini-now))
    else:
        mdat.append((now,mini,mini-now))

pdat.sort(key=lambda x:-x[1])
mdat.sort(key=lambda x:x[2])
pdat.extend(mdat)

now=0
for d in pdat:
    if now+d[1]<0:
        print("No")
        break
    now+=d[0]
else:
    if now==0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n=int(input())

pdat=[]
mdat=[]

for i in range(n):
    s=input()
    
    mini=0
    now=0
    for q in range(len(s)):
        if s[q]=="(":
            now+=1
        else:
            now-=1
            mini=(min(mini,now))
    if now>=0:
        pdat.append((now,mini,mini-now))
    else:
        mdat.append((now,mini,mini-now))

pdat.sort(key=lambda x:-x[1])
mdat.sort(key=lambda x:x[2])

now=0
for d in pdat+mdat:
    if now+d[1]<0:
        print("No")
        break
    now+=d[0]
else:
    if now==0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

inpl = lambda: list(map(int,input().split()))
N = int(input())
rate = []
rate.append(inpl())
rate.append(inpl())
AB = []
BA = []
for i in range(3):
    rA, rB = rate[0][i], rate[1][i]
    if rB > rA:
        AB.append((rA, rB))
    elif rA > rB:
        BA.append((rB, rA))

dpAB = [0]
for i in range(1,N+1):
    q = [0]
    for cost, ret in AB:
        if i >= cost:
            q.append(dpAB[i-cost] + ret)
    dpAB.append(max(dpAB[i-1]+1, max(q)))

M = dpAB[N]
dpBA = [0]
for i in range(1,M+1):
    q = [0]
    for cost, ret in BA:
        if i >= cost:
            q.append(dpBA[i-cost] + ret)
    dpBA.append(max(dpBA[i-1]+1, max(q)))

print(dpBA[M])

### FIXED CODE ###

from fractions import gcd
from functools import reduce
inpl = lambda: list(map(int,input().split()))
def lcm(a,b):
    return a*b//gcd(a,b)
def lcm_list(numbers):
    return reduce(lcm, numbers)

N = int(input())
rate = []
rate.append(inpl())
rate.append(inpl())
AB = []
BA = []
for i in range(3):
    rA, rB = rate[0][i], rate[1][i]
    if rB > rA:
        AB.append((rA, rB))
    elif rA > rB:
        BA.append((rB, rA))
for l in [AB, BA]:
    l.sort(key=lambda x: -x[1]/x[0])

def buy_and_sell(N, cost_ret):
    if len(cost_ret) == 0:
        return N
    else:
        Nunit = lcm_list([ x[0] for x in cost_ret ])
        b0, s0 = cost_ret[0]
        q = N // b0
        n = max(0, q - 2*Nunit//b0 + 1)
        Ndp = N - n*b0
        dp = [0]*(Ndp+1)
        w = [0]*(len(cost_ret)+1)
        for i in range(1,Ndp+1):
            k = 1
            for cost, ret in cost_ret:
                if i >= cost:
                    w[k] = dp[i-cost] + ret
                    k += 1
            dp[i] = max(dp[i-1]+1, max(w))
        return s0*n + dp[-1]

M = buy_and_sell(N, AB)
L = buy_and_sell(M, BA)
print(L)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
const = 1000000007
ans = 0
a = 0
for i in range(N):
    for j in range(i + 1, N):
        a += A[j]
    ans += A[i] * a
    a = 0
print(ans%const)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
const = 1000000007
ans = 0
total = sum(A)
for i in range(N):
    total -= A[i]
    ans += A[i] * total
print(ans%const)