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

import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if ls[ps] < n - 1 and fq[ps]:
                    fq[ps] = False
                    nw = a[ps][ls[ps]]
                    rw = a[nw][ls[nw]]
                    if ps == rw and fq[nw]:
                        if n > ls[ps] + 1:
                            ls[ps] += 1
                            ql.append([d+1, ps])
                        if n > ls[nw] + 1:
                            ls[nw] += 1
                            ql.append([d+1, nw])
                        fq[nw] = False
            else:
                if d > i:
                    ql.appendleft([d, ps])
                    break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ad = [0] * n
    dq = collections.deque([[0, i + 1] for i in range(n)])
    for i in range(10 ** 15):
        fd = {}
        while True:
            if len(dq) != 0:
                d, q = dq.popleft()
                q -= 1
                if d <= i:
                    if ad[q] < n - 1:
                        qq = a[q][ad[q]] - 1
                        tq = a[qq][ad[qq]] - 1
                        if q == tq and qq not in fd and tq not in fd:
                            ad[qq] += 1
                            ad[tq] += 1
                            if ad[qq] < n - 1:
                                dq.append([d + 1, qq + 1])
                            if ad[tq] < n - 1:
                                dq.append([d + 1, tq + 1])
                            fd[qq] = 0
                            fd[tq] = 0
                else:
                    dq.append([d, q + 1])
                    break
            else:
                break
        if len(dq) == 0:
            b = True
            for v in ad:
                if v != n - 1:
                    b = False
                    break
            if b:
                print(i + 1)
                exit()
            else:
                print(-1)
                exit()


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

n = int(input())
arr = list(map(int, input().split()))
ans = 1
for i in arr:
  ans *= i
if ans > 1000000000000000000:
	print(-1)
else:
  print(ans)

### FIXED CODE ###

n = int(input())
arr = list(map(int, input().split()))
ans = 1
f = 0
arr.sort()
for i in arr:
  ans *= i
  if ans > 1e18:
    f = 1
    print(-1)
    break
if f == 0:
  print(ans)
### BUGGY CODE ###

import sys

s = input()
s_no_x = s.replace('x', '')
s_no_x_inv = s_no_x[::-1]

if not s_no_x == s_no_x_inv:
    print(-1)
    sys.exit()

count = 0
for i in range(len(s)):
    if i > len(s):
        break
    if not s[i] == s[len(s) - 1 - i]:
        count += 1
        if s[i] == 'x':
            s = s[:len(s) - i] + 'x' + s[len(s) - i:]
        else:
            s = s[:i] + 'x' + s[i:]
print(count)


### FIXED CODE ###

import sys

s = input()
s_no_x = s.replace('x', '')
s_no_x_inv = s_no_x[::-1]

if not s_no_x == s_no_x_inv:
    print(-1)
    sys.exit()

count = 0
l = 0
r = len(s) - 1
while l < r:
    if l >= r:
        break
    if s[l] == s[r]:
        l += 1
        r -= 1
    if not s[l] == s[r]:
        count += 1
        if s[l] == 'x':
            l += 1
        else:
            r -= 1
print(count)
### BUGGY CODE ###

n,a,b = [int(x) for x in input().split()]
mod = 10**9 + 7
import math
#再起限界突破
import sys
sys.setrecursionlimit(1000000000)
#メモ化再帰
from functools import lru_cache
@lru_cache(maxsize=1000000000)
def action(k):
    if k == 1:
        return 1
    else:
        return k * action(k-1) % mod
ans = pow(2,n,mod)  - action(n)/action(n-a)/action(a) - action(n)/(action(n-b)*action(b)) - 1
print(int(ans%mod))

### FIXED CODE ###

n,a,b = [int(x) for x in input().split()]
mod = 10**9 + 7
def comb(x,y):
    child = 1
    mother = 1
    for i in range(y):
        child = child * (x-i)%mod
        mother = mother * (i+1)%mod
    return child * pow(mother,mod-2,mod) % mod
ans = pow(2,n,mod) - 1
ans -= comb(n,a)
ans %= mod
ans -= comb(n,b)
ans %= mod
print(ans)
### BUGGY CODE ###

n, k = list(map(int, input().split()))
arr = list(map(int, input().split()))
s = []
f = []

z = 0
c = 1
m = 0
for a in range(k-1,k):
    z = 0
    c = 1
    while z < k:
        c = c * arr[a-z]
        z += 1

    s.append(c)
    
lastkm1 = c//arr[m]
p = 1
for i in range(k,n):
    m += 1
    c = lastkm1*arr[i]
    s.append(lastkm1*arr[i])
    lastkm1 = c//arr[m]
    if s[p]>s[p-1]:
        print("Yes")
    else:
        print("No")
    p+=1
    


### FIXED CODE ###

n, k = list(map(int, input().split()))
arr = list(map(int, input().split()))

for i in range(n-k):
    if (arr[i]<arr[i+k]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

#import sys
#input = sys.stdin.readline
from itertools import accumulate
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    for i in range(K):
        B = [0]*(N+1)
        for j in range(N):
            d = A[j]
            x = j-d
            y = j+d
            if x < 0:
                B[0] += 1
            else:
                B[x] += 1
            if N-1 < y:
                B[N] -= 1
            else:
                B[y+1] -= 1
        A = list( accumulate(B))
        check = True
        for j in range(N):
            if A[j] < N:
                check = False
        if check:
            break
    print(" ".join( map(str, A[:-1])))
            
                
        
if __name__ == '__main__':
    main()


### FIXED CODE ###

#import sys
#input = sys.stdin.readline
from itertools import accumulate
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    for i in range(K):
        B = [0]*(N+1)
        for j in range(N):
            d = A[j]
            x = j-d
            y = j+d
            if x < 0:
                B[0] += 1
            else:
                B[x] += 1
            if N-1 < y:
                B[N] -= 1
            else:
                B[y+1] -= 1
        A = list( accumulate(B))
        check = True
        for j in range(N):
            if A[j] < N:
                check = False
        if check:
            break
    print(" ".join( map(str, A[:-1])))
            
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np
def main():
    a = int(input())
    p = list(map(int,input().split()))
    mod = 10**9 + 7
    sum_list =[p[i]*p[t] for i in range(a) for t in range(a) if i<t ]
    num = np.sum(sum_list)
    num = num%mod
    return num
num = main()
print(num)



### FIXED CODE ###

import itertools as itr

a = int(input())
p = list(map(int,input().split()))
mod = 10**9 + 7
ans =0
sum_list = list(itr.accumulate(p))
for i in range(len(p)-1):
    o = p[i+1]
    w =sum_list[i]
    ans = (ans+o*w%mod)%mod
print(ans)
### BUGGY CODE ###

s = input()
ans = 0
def f(n):
    global ans
    while n and (n[0] < '5' or (n[0] == '5' and (len(n) == 1 or n[1] <= '4'))):
        ans += int(n[0])
        n = n[1:]
    if n:
        ans += 1
        f(str(10**len(n)-int(n)))
f(s)
print(ans)

### FIXED CODE ###

n = input()
lenn = len(n)

dp = [0, 10000]
for d in reversed(n):
    d = int(d)
    dp = [min(d + dp[0], d + 1 + dp[1]), min(10 - d + dp[0], 9 - d + dp[1])]

print(min(dp[0], 1 + dp[1]))
### BUGGY CODE ###

def main():
    from collections import deque

    INF = float('inf')

    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    S = [input() for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])

    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                t[h][w] = -1

    while q:
        h, w = q.popleft()
        a = t[h][w]
        if h - 1 >= 0 and t[h - 1][w] > a:
            q.appendleft((h - 1, w))
            t[h - 1][w] = a
        if h + 1 < H and t[h + 1][w] > a:
            q.appendleft((h + 1, w))
            t[h + 1][w] = a
        if w - 1 >= 0 and t[h][w - 1] > a:
            q.appendleft((h, w - 1))
            t[h][w - 1] = a
        if w + 1 < W and t[h][w + 1] > a:
            q.appendleft((h, w + 1))
            t[h][w + 1] = a

        for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
            for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                if t[i][j] <= a + 1:
                    continue
                t[i][j] = a + 1
                q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()


### FIXED CODE ###

from collections import deque

INF = float('inf')

H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(H)]

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])
### BUGGY CODE ###

import numpy as np
n, m = map(int, input().split())
card = np.zeros(n+1, dtype=int)
for i in range(m):
    l, r = map(int, input().split())
    card[l:r+1] += 1

print(list(card).count(m))


### FIXED CODE ###

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

min_id = 1
max_id = n
for i in range(m):
    l, r = map(int, input().split())

    if min_id < l <= max_id:
        min_id = l
    elif max_id < l:
        print(0)
        sys.exit()

    if min_id <= r < max_id:
        max_id = r
    elif r < min_id:
        print(0)
        sys.exit()

print(max_id - min_id + 1)
### BUGGY CODE ###

import numpy as np
H, W = map(int, input().split())
S = []
ij = np.zeros([H,W])    # .の連続数を格納用

for i in range(H):
    S.append(input())
    cnt = 0
    start = 0
    end = 0
    for j in range(W):
        if S[i][j] == '#':
            ij[i, start:end+1] += cnt
            cnt = 0
        elif j > 0 and S[i][j-1] == '#':    # .のstart
            start = j
            end = j
            cnt = 1
        else:
            end = j
            cnt += 1
        if j == W-1:    # 最後に書き込み
            ij[i, start:end+1] += cnt
            cnt = 0

for j in range(W):
    cnt = 0
    start = 0
    end = 0
    for i in range(H):
        if S[i][j] == '#':
            ij[start:end+1, j] += cnt
            cnt = 0
        elif i > 0 and S[i-1][j] == '#':    # .のstart
            start = i
            end = i
            cnt = 1
        else:
            end = i
            cnt += 1
        if i == H-1:    # 最後に書き込み
            ij[start:end+1, j] += cnt
            cnt = 0

ij = ij - 1  # 自分が2回足されるので、1引く
ans = int(ij.max())
print(ans)

### FIXED CODE ###

import numpy as np
H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'
us = np.zeros((H,W), dtype=int)    # .の連続数を格納用
ds = np.zeros((H,W), dtype=int)    # .の連続数を格納用
ls = np.zeros((H,W), dtype=int)    # .の連続数を格納用
rs = np.zeros((H,W), dtype=int)    # .の連続数を格納用

for h in range(1,H):
    us[h, :] = (us[h-1, :] + 1) * S[h-1, :]
for h in range(H-2, -1, -1):
    ds[h, :] = (ds[h+1, :] + 1) * S[h+1, :]
for w in range(1,W):
    ls[:, w] = (ls[:, w-1] + 1) * S[:, w-1]
for w in range(W-2, -1, -1):
    rs[:, w] = (rs[:, w+1] + 1) * S[:, w+1]

ans = ((us + ds + ls + rs)*S).max() + 1
print(ans)
### BUGGY CODE ###

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

import math

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a.sort()
b.sort()
c.sort()

cnum = []

takadaka = math.ceil(k)

for i in range(min(takadaka,x)):
    for j in range(min(takadaka,y)):
        for l in range(min(takadaka,z)):
            cnum.append(a[i] + b[j] + c[l])

cnum.sort()
cnum.reverse()

for i in range(k):
    print(cnum[i])

### FIXED CODE ###

# -*- coding: utf-8 -*-
x,y,z,k = map(int,input().split())
a,b,c = [],[],[]
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

ab = []

for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])

ab.sort()

abc = []

for i in range(min(len(ab),k)):
    for j in range(min(z,k)):
        abc.append(ab[-(i+1)] + c[j])

abc.sort()

for i in range(k):
    print(abc[-(i+1)])
### BUGGY CODE ###

import math
n, a, b = map(int, input().split())

aa = math.factorial(n)/math.factorial(n-a)/math.factorial(a)
bb = math.factorial(n)/math.factorial(n-b)/math.factorial(b)

ans = int(((1 << n) - 1 - aa - bb) % (10**9+7))
print(ans)

### FIXED CODE ###

def modComb(n, r, mod):
    nume = 1
    deno = 1
    for i in range(r):
        nume = nume*(n-i) % mod
        deno = deno*(i+1) % mod
    return nume*pow(deno, mod-2, mod) % mod
 
n, a, b = map(int, input().split())

mod = 10**9+7

ans = (pow(2, n, mod) -1 - modComb(n, a, mod)
       - modComb(n, b, mod)) % mod

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

import sys
sys.setrecursionlimit(10000)
def resolve():
    N = int(input())
    Reds = [list(map(int, input().split(" "))) for i in range(N)]
    Blues = [list(map(int, input().split(" "))) for i in range(N)]
    maxpairs = 0
    BluePerms = permutations(Blues)
    for blues in BluePerms:
        npairs = 0
        for i in range(N):
            if able_to_be_pair(Reds[i], blues[i]):
                npairs += 1
        maxpairs = max(maxpairs, npairs)
    print(maxpairs)

def able_to_be_pair(red, blue):
    return True if (blue[0] - red[0]) > 0 and (blue[1] - red[1]) > 0 else False

import itertools
def permutations(array, choose=None):
    if choose is None:
        choose = len(array)
    return list(itertools.permutations(array, choose))

if '__main__' == __name__:
    resolve()

### FIXED CODE ###

import sys
import itertools
sys.setrecursionlimit(10000)
def resolve():
    N = int(input())
    Reds = sorted([list(map(int, input().split(" "))) for i in range(N)], key=lambda x: x[1], reverse=True)
    Blues = sorted([list(map(int, input().split(" "))) for i in range(N)], key=lambda x: x[0])
    used = []
    for red in Reds:
        for blue in Blues:
            if blue not in used and able_to_be_pair(red, blue):
                used.append(blue)
                break
    print(len(used))

def able_to_be_pair(red, blue):
    return True if (blue[0] - red[0]) > 0 and (blue[1] - red[1]) > 0 else False

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

n=int(input())
a=[int(x) for x in input().split()]
ans =[]
mm=1
for i in range(n):
  tmp = a.index(mm)
  ans.append(tmp+1)
  mm+=1
print(*ans)

### FIXED CODE ###

n=int(input())
a=[int(x) for x in input().split()]
vl =[]
tmp =[]
ans=[0]*n
for i,value in enumerate(a):
  tmp.append(i)
  vl.append(value)
for i in range(n):
  ans[vl[i]-1]=tmp[i]+1
print(*ans)
### BUGGY CODE ###

"""
i - j = A[i] + A[j]
-> i - A[i] = j + A[j]
i > j
"""
N = int(input())
high = list(map(int, input().split()))

cnt = 0
calc = []
for i in range(1, N+1):
  tmp = i - high[i-1]
  calc.append(i + high[i-1])
  if tmp in calc[:-1]:
    cnt += calc[:-1].count(tmp)

print(cnt)

### FIXED CODE ###

"""
i - j = A[i] + A[j]
> i - A[i] = j + A[j]
i > j
"""
N = int(input())
high = list(map(int, input().split()))

ans = 0
calc = {}
for i in range(1, N+1):
  try:
    ans += calc[i - high[i-1]]
  except KeyError:
    pass
  if (i + high[i-1]) in calc.keys():
    calc[i + high[i-1]] += 1
  else:
    calc[i + high[i-1]] = 1

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

n = int(input())
s = input()
ans = 0
slist = ['R','G','B']
sslist = slist[:]
for i in range(n-3):
  for j in range(i+1,n-1):
    if s[i] != s[j]:
      slist.remove(s[i])
      slist.remove(s[j])
      ans += s[j+1:].count(slist[0])
      if 2*j-i <= n-1:
        if s[2*j-i] == slist[0]:
          ans -= 1
      slist = sslist[:]
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
r = s.count('R')
g = s.count('G')
b = s.count('B')
ans = r*g*b
for i in range(n):
  for j in range(i+1,n):
    k = 2*j-i
    if k < n:
      if  s[i] != s[j] and s[j]!= s[k] and s[i] != s[k]:
        ans -= 1
print(ans)
### BUGGY CODE ###

import collections
s = map(int,raw_input())

h = {}
for jj in range(2019+1):
    for d in range(0,10):
        h[jj,d] = (10 * jj + d) % 2019

dp = collections.Counter()
count = 0
for j in range(len(s)):
    ndp = collections.Counter()
    ndp[s[j]] += 1
    for k in dp:
        ndp[h[(k,s[j])]] +=1
        #ndp[(10*k + s[j]) % 2019] += 1
    count += ndp[0]
    dp = ndp

print count




### FIXED CODE ###

import collections
s = map(int,raw_input())

dp = [0] * 2019
count = 0
for j in range(len(s)):
    ndp = [0] * 2019
    ndp[s[j]] += 1
    for k in range(len(dp)):
        ndp[(10*k + s[j]) % 2019] += dp[k]
    count += ndp[0]
    dp = ndp[::]

print count
### BUGGY CODE ###

MOD = 1000000007
S = input()
memo = [[0] * 13 for i in range(len(S)+1)]
memo[0][0] = 1

for idx in range(len(S)):
	ch = S[idx]
	if(ch == '?'):
		for num in range(10):
			for i in range(13):
				if(memo[idx][i] > 0):
					memo[idx+1][(i*10+num)%13] += memo[idx][i] 
	else:
		num = int(ch)
		for i in range(13):
			if(memo[idx][i] > 0):
				memo[idx+1][(i*10+num)%13] += memo[idx][i] 
	
	for i in range(13):
		memo[idx+1][i] %= MOD

print(memo[len(S)][5]%MOD)

### FIXED CODE ###

MOD = 1000000007
S = input()
memo = [[0] * 13 for i in range(len(S)+1)]
memo[0][0] = 1

for idx in range(len(S)):
	ch = S[idx]
	if(ch == '?'):
		for num in range(10):
			for i in range(13):
				if(memo[idx][i] > 0):
					memo[idx+1][(i*10+num)%13] += memo[idx][i] 
	else:
		num = int(ch)
		for i in range(13):
			if(memo[idx][i] > 0):
				memo[idx+1][(i*10+num)%13] += memo[idx][i] 
	
	for i in range(13):
		memo[idx+1][i] %= MOD

print(memo[len(S)][5]%MOD)
### BUGGY CODE ###

N, W = map(int, input().split())
ws = [0]*N
vs = [0]*N
for i in range(N):
  w, v = map(int, input().split()) 
  ws[i] = w
  vs[i] = v

dp = [[0]*(W+1) for i in range(N+1)]
for i in range(1, N+1):
  for sum_w in range(W+1):
    if sum_w - ws[i-1] >= 0:
    	dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w-ws[i-1]]+vs[i-1])
    dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

print(max(dp[-1]))
  

### FIXED CODE ###

import numpy as np

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

dp = np.zeros((N+1, W+1), dtype='uint64')

for i in range(N):
  w, v = map(int, input().split()) 
  dp[i+1][:w] = dp[i][:w]
  dp[i+1][w:] = np.maximum(dp[i][w:], dp[i][:-w]+v)
print(np.max(dp[N]))
### BUGGY CODE ###

#Python

N= input()
#print N
a = map(int, raw_input().split())
#print a


b=[]
for i in range(N):
	b.append(a[i])
	b.reverse()
	#print b

#print b

for j in range(N):
	print b[j],

### FIXED CODE ###

n= input()
a = map(int,raw_input().split())
#print a

l=[ i for i in range(n)]
l_gusu=l[0::2]
l_kisu=l[1::2]

ans=[]
for i in reversed(list(l_gusu)):
	#print i,a[i]
	ans.append(a[i])

for i in l_kisu:
	ans.append(a[i])


ans_str=""
if n%2==0:
	for i in reversed(list(ans)):
		ans_str+=(str(i)+" ")
	print ans_str.strip()
else:
	for i in ans:
		ans_str+=(str(i)+" ")
	print ans_str.strip()
### BUGGY CODE ###

def bitsum(bit,i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i&(-i)
    return s
    
def bitadd(bit,i,x):
    n = len(bit)-1
    while i <= n:
        bit[i] += x
        i += i&(-i)
    return bit

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=lambda x:x[1])
for i in range(N):
    xy[i][1] = i+1
xy.sort()
for i in range(N):
    xy[i][0] = i

# x<xi,y<yi
l1 = [0]*N
# x<xi,y>yi
l2 = [0]*N
# x>xi,y<yi
r1 = [0]*N
# x>xi,y>yi
r2 = [0]*N

bit = [0]*(N+1)
for i in range(N):
    l1[i] = bitsum(bit,xy[i][1])
    l2[i] = i-l1[i]
    r1[i] = xy[i][1]-l1[i]-1
    r2[i] = N-xy[i][1]-l2[i]
    bitadd(bit,xy[i][1],1)

pow2 = [1]*(N+1)
for i in range(N):
    pow2[i+1] = 2*pow2[i]%mod

ans = pow2[N-1]*N%mod
for i in range(N):
    ans += pow2[l1[i]+l2[i]+r1[i]+r2[i]]
    ans -= pow2[l1[i]+r1[i]]
    ans -= pow2[l2[i]+r2[i]]
    ans -= pow2[l1[i]+l2[i]]
    ans -= pow2[r1[i]+r2[i]]
    ans += pow2[l1[i]]
    ans += pow2[l2[i]]
    ans += pow2[r1[i]]
    ans += pow2[r2[i]]
    ans -= 1
    ans %= mod

print(ans)


### FIXED CODE ###

from operator import itemgetter

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=itemgetter(1))
for i in range(N):
    xy[i][1] = i+1
xy.sort(key=itemgetter(0))

pow2 = [1]*(N+1)
for i in range(N):
    pow2[i+1] = 2*pow2[i]%mod

ans = pow2[N-1]*N%mod

bit = BIT(N)
for i in range(N):
    l1 = bit.sum(xy[i][1])
    l2 = i-l1
    r1 = xy[i][1]-l1-1
    r2 = N-xy[i][1]-l2
    bit.add(xy[i][1],1)
    ans += (pow2[l2]-1)*(pow2[r1]-1)*pow2[r2]*pow2[l1]
    ans += (pow2[r2]-1)*(pow2[l1]-1)*(pow2[l2]+pow2[r1]-1)
    ans %= mod

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

#D
from collections import deque
from heapq import heappush, heappop
n,q=map(int,input().split())
data=[[] for i in range(n+1)]
counter=deque([0 for i in range(n+1)])
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    counter[p]+=x
h=[1]
while h:
    a=heappop(h)
    for i in range(len(data[a])):
        counter[data[a][i]]+=counter[a]
        heappush(h,data[a][i])
        data[data[a][i]].remove(a)
counter.popleft()
print(*counter)

### FIXED CODE ###

#D
n,q=map(int,input().split())
data=[[] for i in range(n+1)]
counter=[0]*(n+1)
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    counter[p]+=x
h=[1]
done=[0]*(n+1)
while h:
    a=h.pop()
    for l in data[a]:
        if done[l]==0:
            counter[l]+=counter[a]
            h.append(l)
    done[a]=1
print(*counter[1:])