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

from bisect import *
from heapq import *

def f(n):
    hp = []
    for _ in range(n):
        heappush(hp, list(map(int, input().split())))
    cy = [[0] * 4 for _ in range(n)]
    xy = []
    ys = []
    for i in range(n):
        x, y = heappop(hp)
        s = bisect(ys, y)
        cy[i][3] = pow(2, s, md)
        cy[i][2] = pow(2, i - s, md)
        ys.insert(s, y)
        xy.append([x, y])
    ys = []
    for i in range(n - 1, -1, -1):
        x, y = xy[i]
        s = bisect(ys, y)
        cy[i][0] = pow(2, s, md)
        cy[i][1] = pow(2, n - 1 - i - s, md)
        ys.insert(s, y)
    ans = pow(2, n - 1, md) * n % md
    for i in range(n):
        c0, c1, c2, c3 = cy[i]
        ans = (ans + (c0 - 1) * (c2 - 1) * c1 * c3 + (c1 - 1) * (c3 - 1) * c0 * c2
               - (c0 - 1) * (c1 - 1) * (c2 - 1) * (c3 - 1)) % md
    print(ans)

md = 998244353
n = int(input())
f(n)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class BitSum:
    def __init__(self, n):
        self.n = n + 1
        self.table = [0] * self.n

    def add(self, i, x):
        i += 1
        while i < self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def main():
    md=998244353
    n=II()
    xy=LLI(n)
    yy=set()
    for x,y in xy:yy.add(y)
    ytoj={y:j for j,y in enumerate(sorted(yy))}

    ans=n*(pow(2,n,md)-1)-4*(pow(2,n,md)-1-n)
    ans%=md

    xy.sort()
    bit=BitSum(200005)
    for i,[x,y] in enumerate(xy):
        j=ytoj[y]
        c=bit.sum(j-1)
        ans+=pow(2,c,md)-1
        ans+=pow(2,i-c,md)-1
        ans%=md
        bit.add(j,1)

    bit=BitSum(200005)
    for i,[x,y] in enumerate(xy[::-1]):
        j=ytoj[y]
        c=bit.sum(j-1)
        ans+=pow(2,c,md)-1
        ans+=pow(2,i-c,md)-1
        ans%=md
        bit.add(j,1)

    print(ans)

main()
### BUGGY CODE ###

from collections import*
from time import*
def main():
    start=time()
    (n,),*a=[list(map(int,t.split()))for t in open(0)]
    d={}
    s=0
    es=[]
    for i,b in enumerate(a):
        for j,k in zip(b,b[1:]):
            x,z=sorted((i,j-1))
            x=x*n+z
            y,z=sorted((i,k-1))
            y=y*n+z
            if not x in d:
                d[x]=s
                s+=1
            if not y in d:
                d[y]=s
                s+=1
            es+=(d[x],d[y]),
    e=[[]for _ in range(s)]
    for v1,v2 in es:e[v1]+=v2,
    outs=defaultdict(list)
    ins=defaultdict(int)
    for v1,v2 in es:
        outs[v1].append(v2)
        ins[v2]+=1
    q=deque(v1 for v1 in range(s)if ins[v1]==0)
    res=[]
    while q:
        if time()-start>1.8:
            print(n*(n-1)//2)
            return
        v1=q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2]-=1
            if ins[v2]==0:
                q.append(v2)
    if len(res)<s:
        print(-1)
        return
    data=[1]*s
    for i in res:
        t=data[i]+1
        for j in e[i]:
            if t>data[j]:data[j]=t
    print(max(data))
main()

### FIXED CODE ###

def main():
    from collections import defaultdict,deque
    from itertools import count
    (n,),*a=[list(map(int,t.split()))for t in open(0)]
    d=defaultdict(count().__next__)
    es=[]
    for i,b in enumerate(a,1):
        for j,k in zip(b,b[1:]):
            x,y=i,j
            if y<x:x,y=y,x
            v,w=i,k
            if w<v:v,w=w,v
            es+=(d[x*n+y],d[v*n+w]),
    s=len(d)
    outs=[[]for _ in range(s)]
    ins=[0]*s
    f=set(range(s))
    for i,j in es:
        outs[i]+=j,
        f-={j}
        ins[j]+=1
    q=deque(f)
    r=[]
    data=[0]*s
    m=0
    while q:
        i=q.popleft()
        r+=i,
        t=data[i]+1
        if t>m:m=t
        for j in outs[i]:
            ins[j]-=1
            if ins[j]<1:q+=j,
            if t>data[j]:data[j]=t
    print(-(len(r)<s)or m)
main()
### BUGGY CODE ###

from heapq import heappush, heappop
min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())

AB = [tuple(map(int,input().split())) for _ in range(N)]

AB.sort(key=lambda x: x[1]/x[0])

cost = [(float('inf'),float('inf'))]*(H+1)
last = [0]*(H+1)

q = [((0,0), 0)]

while q:
    cli, t = heappop(q)
    if cost[t] <= cli:
        continue
    cost[t] = cli
    if t == H:
        break

    c,li = cli
    for i,(a,b) in enumerate(AB[li:], start=li):
        d = min2(H,t+a)
        if cost[d] > (c+b,i):
            heappush(q, ((c+b, i), d))

print(cost[H][0])


### FIXED CODE ###

min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())


dp = [float('inf')]*(H+1)
dp[0] = 0

for _ in range(N):
    a,b = map(int,input().split())
    for i,v in enumerate(dp):
        j = min2(H,i+a)
        dp[j] = min2(dp[j],v+b)

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

def main():
    ini_inp=list(map(lambda x:int(x),input().split()))
    N=ini_inp[0]
    M=ini_inp[1]

    L=[]
    R=[]
    for i in range(M):
        sec_inp=list(map(lambda x:int(x),input().split()))
        L.append(sec_inp[0])
        R.append(sec_inp[1])

    counter=0
    for i in range(1,N+1):
        flag=0
        for j in range(M):
            if i<L[j] or i>R[j]:
                flag=1
        if flag==0:
            counter+=1

    print(counter)

if __name__=="__main__":
    main()
        


### FIXED CODE ###

def main():
    ini_inp=list(map(lambda x:int(x),input().split()))
    N=ini_inp[0]
    M=ini_inp[1]

    L=[]
    R=[]
    for i in range(M):
        sec_inp=list(map(lambda x:int(x),input().split()))
        L.append(sec_inp[0])
        R.append(sec_inp[1])

    low=L[0]
    up=R[0]
    flag=0
    for i in range(1,M):
        if L[i]>up:
            flag=1
            break
        elif L[i]>=low:
            low=L[i]
        elif R[i]<=up:
            up=R[i]

    if flag==0:
        print(up-low+1)
    else:
        print(0)

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

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


num_list = []

cnt = 0

while True:
    even_count = 0
    #print(A)

    if not "even" in list(map(lambda x: "even" if x % 2 == 0 else "odd", A)):
        break

    for index, num in enumerate(A):
        if not even_count == 1 and num % 2 == 0:
            num = num//2
            even_count += 1
            A[index] = num

        else:
            num = num * 3
            A[index] = num

    cnt += 1

print(cnt)

### FIXED CODE ###

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



cnt = 0

for num in range(N):
    while A[num] % 2 ==0:
        cnt += 1
        A[num] //= 2
        
print(cnt)
### BUGGY CODE ###

x, k, d = map(int, input().split())

for _ in range(k):
  if x >= 0:
    x -= d
  elif x < 0:
    x += d

if x < 0:
  x = x * -1
print(x)

### FIXED CODE ###

x, k, d = map(int, input().split())

def sgn(x):
  if x > 0:
    return 1
  if x < 0:
    return -1
  return 0

if x > 0:
  x1 = x - k * d
else:
  x1 = x + k * d

if sgn(x) == sgn(x1):
  print(abs(x1))
  exit()
  
xright = x % d
xleft = x % d - d
#0目前
xr = (abs(x - xright) // d) % 2
if k % 2 == xr:
  print(abs(xright))
elif k % 2 != xr:
  print(abs(xleft))
### BUGGY CODE ###

import collections
import math

n = int(input())

m = list(map(str,input().split()))

c = dict(collections.Counter(m))

def ans(a):
    if a<2:
        return 0
    else:
        return math.factorial(a) // (math.factorial(a - 2) * math.factorial(2))

for i in m:
    cnt = 0
    for j,k in c.items():
        if j == i:
            if k - 1 >= 2:
                cnt += ans(k-1)
                
        else:
            cnt += ans(k)
        
    print(cnt)
               

### FIXED CODE ###

import collections
import math

n = int(input())

m = list(map(str,input().split()))

c = dict(collections.Counter(m))
d = {}
hyouji = {}
def ans(a):
    if a<2:
        return 0
    else:
        return math.factorial(a) // (math.factorial(a - 2) * math.factorial(2))

cnt = 0
for i,j in c.items():
    n = ans(j)
    d[i] = n
    cnt += n


for k in m:
    if k in hyouji:
        print(hyouji[k])
    else: 
        if c[k] < 2:
            q = cnt
        elif c[k] == 2:
            q = cnt - 1
        else:
                q = cnt -d[k] + ans(c[k] - 1)

        hyouji[k] = q
        print(hyouji[k])
### BUGGY CODE ###

N, X, Y = map(int, input().split())
X -= 1
Y -= 1
if X > Y:
    X, Y = Y, X

ans = [0] * (N - 1)
for i in range(N - 1):
    minn = 9999999999
    for j in range(i + 1, N):
        ij = abs(i - j)
        ix = abs(i - X)
        iy = abs(i - Y)
        jx = abs(j - X)
        jy = abs(j - Y)

        minn = ij
        minn = min(minn, ix + 1 + jy)
        minn = min(minn, iy + 1 + jx)

        ans[minn - 1] += 1

for i in ans:
    print(i)

### FIXED CODE ###

N, X, Y = map(int, input().split())
X -= 1
Y -= 1
if X > Y:
    X, Y = Y, X

ans = [0] * (N - 1)
for i in range(N - 1):
    for j in range(i + 1, N):
        ij = j - i
        ix = abs(i - X)
        iy = abs(i - Y)
        jx = abs(j - X)
        jy = abs(j - Y)

        minn = ij
        minn = min(minn, ix + 1 + jy)
        minn = min(minn, iy + 1 + jx)

        ans[minn - 1] += 1

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

# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline

## input
N,Q = map(int, readl().rstrip().split())
STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
Dn = [None for _ in range(Q+1)]
for i in range(Q):
  Dn[i] = int(readl().rstrip())
Dn[Q] = 10**10
Rn = []


## solve
for s,t,x in sorted(STX,key=lambda x:x[2]):
  l = r = bisect_left(Dn,s-x)
  t -= x
  while Dn[r] < t:
    Rn.append([Dn[r],x])
    r += 1
  del Dn[l:r]

for d in Dn[:-1]:
  Rn.append([d,-1])
Rn.sort()


## output
for i in range(Q):
  print(Rn[i][1])

### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

N, M, K = list(map(int, input().split(" ")))
A = list(map(int, input().split(" ")))
B = list(map(int, input().split(" ")))
max = 0
for i in range(len(A)+1):
  time_a = 0
  if i > 0:
    time_a = sum(A[:i])
  if time_a > K:
    break
  for j in range(len(B)+1):
    time = time_a
    if j > 0:
    	time += sum(B[:j])
    if time > K:
      break
    elif max < i+j:
      max = i+j
print(max)

### FIXED CODE ###

N, M, K = list(map(int, input().split(" ")))
A = list(map(int, input().split(" ")))
B = list(map(int, input().split(" ")))

sumA = [0] * (N+1)
sumB = [0] * (M+1)
for i in range(N):
  sumA[i+1] = sumA[i] + A[i]
for i in range(M):
  sumB[i+1] = sumB[i] + B[i]

b_i = M
max_count = 0
for i in range(N+1):
  a = sumA[i]
  if a > K:
    continue
  if b_i>0:
    while a + sumB[b_i] > K:
      b_i -= 1
      if b_i==0:
        break
  max_count = max(max_count, i + b_i)
print(max_count)
### BUGGY CODE ###

def f(s):
  r=0
  for i,x in enumerate(s):
    if len(s)==i+1:
      break
    if(x!=s[i+1]):
      del s[i]
      del s[i]
      r+=2
      break
  return r

s=input()
s=list(s)

r=0

while True:
  buf=f(s)
  r+=buf
  if buf==0:
    break

print(r)

### FIXED CODE ###

s=input()

r=0
s0=0
s1=0

for x in s:
  if x=="0":
    if s1!=0:
      s1=s1-1
    else:
      s0=s0+1
  else:
    if s0!=0:
      s0=s0-1
    else:
      s1=s1+1


print(len(s)-s0-s1)
### BUGGY CODE ###

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

A = []
for i in range(M):
  A.append(list(map(int, input().split())))

D1 = [A[i][1] for i in range(M) if A[i][0] == 1]
D2 = [A[i][1] for i in range(M) if A[i][0] in D1]
if N in D2:
  print ("POSSIBLE")
else:
  print ("IMPOSSIBLE")

### FIXED CODE ###

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

A = []
for i in range(M):
  A.append(list(map(int, input().split())))

D1 = set(A[i][1] for i in range(M) if A[i][0] == 1)
D2 = set(A[i][0] for i in range(M) if A[i][1] == N)

if len(D1 & D2) != 0:
  print ("POSSIBLE")
else:
  print ("IMPOSSIBLE")
### BUGGY CODE ###

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

AC_list = []
for i in range(len(S)):
    if S[i:i+2] == "AC":
        AC_list.append(i)
    else:
        pass
    
for i in range(Q):
    l, r = map(int,input().split())
    ans = 0
    for j in AC_list:
        if l-1 <= j <= r-2:
            ans += 1
        elif j > r-2:
            break
    print(ans)

### FIXED CODE ###

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

AC_list = [0]*(N+1)
for i in range(N):
    if S[i:i+2] == "AC":
        AC_list[i+1] = AC_list[i]+1
    else:
        AC_list[i+1] = AC_list[i]

for i in range(Q):
    l, r = map(int,input().split())
    print(AC_list[r-1]-AC_list[l-1])
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def main():
	N, M, L = list(map(int,input().split()))
	P = [list(map(int,input().split())) for i in range(M)]
	Q = int(input())
	st = [list(map(int,input().split())) for i in range(Q)]

	neighbor = [[] for i in range(N)]
	for s,e,d in P:
		if d<=L:
			neighbor[s-1].append((e-1,d))
			neighbor[e-1].append((s-1,d))

	fuellist = [0]*N
	def bfs(start, end):
		fuel = [[10000000,L+1] for i in range(N)]
		fuel[start][0] = 0
		fuel[start][1] = L
		queue = [start]
		while len(queue)>0:
			nq = []						# next target node
			for i in queue:				# target node
				oc, om = fuel[i]
				for j, d in neighbor[i]:	# next node
					if om<d:
						nc = oc+1
						nm = L-d
					else:
						nc = oc
						nm = om-d

					# print(i,j,nc,nm)

					if (nc<fuel[j][0]) or (nc==fuel[j][0] and nm>fuel[j][1]):
						fuel[j][0], fuel[j][1] = nc, nm
						nq.append(j)

			queue = nq					# update target node

		ans = fuel[end][0]
		if fuel[end][0]==10000000: ans = -1

		fuellist[start] = fuel

		print(ans)

	for s, t in st:
		start, end = s-1, t-1
		if fuellist[start]==0:
			bfs(start,end)
		else:
			ans = fuellist[start][end][0]
			if ans==10000000: ans = -1
			print(ans)


if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys


def main():
	input = sys.stdin.readline
	N, M, L = list(map(int,input().split()))
	P = [list(map(int,input().split())) for i in range(M)]
	Q = int(input())
	st = [list(map(int,input().split())) for i in range(Q)]

	neighbor = [[] for i in range(N)]
	for s,e,d in P:
		if d<=L:
			neighbor[s-1].append((e-1,d))
			neighbor[e-1].append((s-1,d))
		# if d<=L:
		# 	neighbor[s-1][e-1] = neighbor[e-1][s-1] = d

	# print(neighbor)
	# start, end = 2,1

	fuellist = [0]*N
	def bfs(start, end):
		# fuel = [[10000000,L+1] for i in range(N)]
		fuelc, fuelm = [10000000]*N, [L+1]*N
		# fuel[start][0] = 0
		# fuel[start][1] = L
		fuelc[start], fuelm[start] = 0, L
		queue = [start]
		while len(queue)>0:
			nq = []						# next target node
			nq_append = nq.append
			for i in queue:				# target node
				oc, om = fuelc[i], fuelm[i]
				for j, d in neighbor[i]:
				# for j, d in enumerate(neighbor[i]):	# next node
					# if d==10**10: continue
					if om<d:
						nc = oc+1
						nm = L-d
					else:
						nc = oc
						nm = om-d

					# print(i,j,nc,nm)

					if nc<fuelc[j]:
						fuelc[j], fuelm[j] = nc, nm
						nq_append(j)
					elif nc==fuelc[j] and nm>fuelm[j]:
						fuelm[j] = nm
						nq_append(j)

			queue = nq					# update target node

		# ans = fuel[end][0]
		ans = fuelc[end]
		if ans==10000000: ans = -1

		fuellist[start] = fuelc

		print(ans)

	for s, t in st:
		start, end = s-1, t-1

		if fuellist[start]!=0:
			ans = fuellist[start][end]
			if ans==10000000: ans = -1
			print(ans)
		elif fuellist[end]!=0:
			ans = fuellist[end][start]
			if ans==10000000: ans = -1
			print(ans)
		else:
			bfs(start,end)


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

import fractions

N = int(input())
nums = list(map(int, input().split()))

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

num = nums[0]
for i in range(N - 1):
    num = lcm(num, nums[i + 1])
print(sum([num // i for i in nums]) % (10 ** 9 + 7))

### FIXED CODE ###

import fractions

N = int(input())
nums = list(map(int, input().split()))

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

num = nums[0]
for i in range(N - 1):
    num = lcm(num, nums[i + 1])
print(sum([num // i for i in nums]) % (10 ** 9 + 7))
### BUGGY CODE ###


h,n = list(map(int,input().split()))
inf = 100000000000000000000
dp = [inf]*(2*100000)
for i in range(-1,-100000,-1):
    dp[i] = 0
ls = [0]*n
for i in range(n):
    ls[i] = list(map(int,input().split()))
dp[0] = 0
for i in range(h):
    for j in range(n):
        dp[i+1] = min(dp[i+1],dp[i+1-ls[j][0]]+ls[j][1])
print(dp[h])

### FIXED CODE ###


h,n = list(map(int,input().split()))
inf = 100000000000000000000
dp = [inf]*(2*100000)
for i in range(-1,-100000,-1):
    dp[i] = 0
ls = [0]*n
for i in range(n):
    ls[i] = list(map(int,input().split()))
dp[0] = 0
for i in range(h):
    for j in range(n):
        dp[i+1] = min(dp[i+1],dp[i+1-ls[j][0]]+ls[j][1])
print(dp[h])
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

ans = []
s = ns()
n = len(s) + 1
now = 0
min_now = 0
for i in range(n):
    left = 0
    right = 0
    offset = 0
    while i - offset - 1 >= 0:
        if s[i - offset - 1] != '<':
            break
        left += 1
        offset += 1
    offset = 0
    while i + offset < n - 1:
        if s[i + offset] != '>':
            break
        right += 1
        offset += 1
    ans.append(max(left, right))

print(sum(ans))

### FIXED CODE ###

import sys
from collections import deque

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

ans = []
s = ns()
n = len(s) + 1
now = 0
min_now = 0

ri = deque()
le = deque()

now = 0
for i in range(n-1):
    if s[i] == '<':
        now += 1
    else:
        now = 0
    le.append(now)
now = 0
for i in range(n-1):
    if s[(n-2)-i] == '>':
        now += 1
    else:
        now = 0
    ri.appendleft(now)
le.appendleft(0)
ri.append(0)

for i in range(n):
    ans.append(max(le.popleft(), ri.popleft()))

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

n = int(input())
s = input()
"""
rcount=0
gcount=0
bcount=0
for i in range(n):
    if s[i]=="R":
        rcount+=1
    elif s[i]=="G":
        gcount+=1
    else:
        bcount+=1
"""
al=s.count("R")*s.count("G")*s.count("B")

for i in range(n-2):
    for k in range(i+1,n):
        dis=k-i
        l=k+dis
        if k+dis>=n:
            continue
        if s[i]!=s[k] and s[i]!=s[l] and s[k]!=s[l]:
            al-=1

print(al)


### FIXED CODE ###

n = int(input())
s = input()

al=s.count("R")*s.count("G")*s.count("B")

for i in range(n-2):
    for k in range(i+1,n-1):
        l=k+(k-i)
        if l>=n:
            continue
        if s[i]!=s[k] and s[i]!=s[l] and s[k]!=s[l]:
            al-=1

print(al)
### BUGGY CODE ###

def PF(n):
    fs = []
    q = int(n ** 0.5) 
    for i in range(2, q + 1):
        if n % i == 0:
            r = 0
            while n % i == 0:
                n //= i
                r += 1
            fs.append([i, r])
    if n != 1:
        fs.append([n, 1])
    return fs

n=int(input())
cnt=0;N=n
j=1;x=n
while j<n:
  num=1
  x=x-j
  V=PF(x)
  for w in range(len(V)):
    num=num*(V[w][1]+1)

  cnt=cnt+num
  
  j=j+1
  x=n
print(cnt)

### FIXED CODE ###

N=int(input())
x=0
for i in range(1,N):
  x=x+(N-1)//i
print(x)
### BUGGY CODE ###

n=int(input())
p = list(map(int,input().split()))
# print(p)
ans=0

for i in range(n):
    if i == 0:
        ans+=1
        continue

    for j in range(i):
        # print(p[i],p[j],i,j)
        if p[i] > p[j]:
            break
        elif j == i-1:
            ans+=1

print(ans)


### FIXED CODE ###

n=int(input())
p = list(map(int,input().split()))
# print(p)
min=p[0]
ans=0

for i in range(n):
    if i == 0:
        ans+=1
        continue
    if p[i] > min:
        continue
    if p[i] < min:
        min=p[i]
        ans+=1

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

n1 = int(input())
s1 = input()

r1 = 0
for i1 in range (n1):
    for i2 in range((n1 - i1) // 2):
        if s1[i1:((n1 - i1) // 2) + i1 - i2] in s1[((n1 - i1) // 2) + i1 - i2:]:
            if ((n1 - i1) // 2) - i2 > r1:
                r1 = ((n1 - i1) // 2) - i2
            break

print(r1)

### FIXED CODE ###

n1 = int(input())
s1 = input()

r1 = 0
r2 = 0
for i1 in range (n1):
    if n1 - (r1 * 2) - i1 < 0:
        break
    for i2 in range(n1 - r1):
        t2 = r1 + i2 + 1
        if s1[i1:i1 + t2] in s1[i1 + t2:] and s1[i1:i1 + t2] != "":
            continue
        else:
            r1 = max(r1, r1 + i2)
            break


print(r1)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

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

for i in range(n):
    lst[i]=sorted(lst[i])

for i in range(m):
    left=str(print_lst[i][0]+1)
    right=str(lst[print_lst[i][0]].index(print_lst[i][1])+1)
    prnt=["0"*(6-len(left)),left,"0"*(6-len(right)),right]
    print("".join(prnt))

### FIXED CODE ###

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
lst=[]
for i in range(n):
    lst.append([])

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

for i in range(n):
    lst[i]=sorted(lst[i],key=lambda x:x[2])

for i in range(n):
    for j in range(len(lst[i])):
        lst[i][j].append(j+1)

lst=[i for j in lst for i in j]
lst=sorted(lst,key=lambda x:x[0])

for i in range(m):
    left=str(lst[i][1])
    right=str(lst[i][3])
    prnt=["0"*(6-len(left)),left,"0"*(6-len(right)),right]
    print("".join(prnt))
### BUGGY CODE ###

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

for i in range(0, m):
    p, y = list(map(int, input().split()))
    tmps[p-1].append(y)
    pys.append([p, y])

for tmp in tmps:
    tmp.sort()

for py in pys:
    p, y = py
    yindex = tmps[p-1].index(y)+1
    print('{:06}'.format(p) + '{:06}'.format(yindex))

### FIXED CODE ###

n, m = list(map(int, input().split()))
tmps = [[] for _ in range(n)]
pyxs = []

for i in range(m):
    p, y = list(map(int, input().split()))
    pyxs.append([p, y, i])

pyxs.sort(key = lambda x: x[1])

num = [0] * (n+1)
ans = [None]*m

for p, y, x in pyxs:
    ans[x] = '{:06}'.format(p) + '{:06}'.format(num[p]+1)
    num[p] += 1

for s in ans:
    print(s)