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

##解答を見た O(HW)+O(HW)+O(Q) ~ O(Q)

H,W,D = map(int,input().split())
A = []
for i in range(H):
    tmp = list(map(int,input().split()))
    A.append(tmp)

pos = []
for k in range(1,H*W+1):##O(HW)
    for i in range(H):
        for j in range(W):
            if A[i][j] == k:
                pos.append([i+1,j+1])
                break
dist = []
for i in range(1,H*W+1):##O(HW)
    if i<=D:
        dist.append(0)
    else:
        dist.append(dist[i-D-1]+abs(pos[i-1][0]-pos[i-D-1][0])+abs(pos[i-1][1]-pos[i-D-1][1]))
def exam(L,R):##O(1)
    """
    ans = 0
    while R != L:
        ##print("L",L,"R",R)
        ans += abs(dist[L+D-1][0]-dist[L-1][0])+abs(dist[L+D-1][1]-dist[L-1][1])
        L += D
    """
    return dist[R-1] - dist[L-1]  

LR = []
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    LR.append([L,R])

for i in range(Q):##O(Q)
    print(exam(LR[i][0],LR[i][1]))

### FIXED CODE ###

##解答を見た 手前でO(H^2W^2) ~O(10^9)くらいのことをしていた
H,W,D = map(int,input().split())
A = []
for i in range(H):
    A.append(list(map(int,input().split())))

pos = [[0 for i in range(2)] for j in range(H*W+1)]

for i in range(H):
    for j in range(W):
        pos[A[i][j]][0] = i+1
        pos[A[i][j]][1] = j+1

dist = []
for i in range(1,H*W+1):##O(HW)
    if i<=D:
        dist.append(0)
    else:
        dist.append(dist[i-D-1]+abs(pos[i][0]-pos[i-D][0])+abs(pos[i][1]-pos[i-D][1]))

LR = []
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    LR.append([L,R])

for i in range(Q):
    print(dist[LR[i][1]-1]-dist[LR[i][0]-1])
### BUGGY CODE ###

def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    d=tuple([-I]+list(map(int,t[n:]))+[I])
    N0=2**(q+1).bit_length()
    data=array('i',[I]*2*N0)
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
A=sorted(A)

table=[0]*(10**6+1)
for i in range(n):
    table[A[i]]+=1

for i in range(n):
    if A[i]>0:
        j=2
        while A[i]*j<10**6+1:
            if table[A[i]*j]>0:
                table[A[i]*j]=-1
            j+=1

cnt=0
for x in table:
    if x==1:
        cnt+=1
print(cnt)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
A=sorted(A)
up=max(A)
table=[0]*(up+1)
for i in range(n):
    table[A[i]]+=1
aset=set(A)

for i in range(len(aset)):
    if table[A[i]]>0:
        j=2
        while A[i]*j<up+1:
            if table[A[i]*j]>0:
                table[A[i]*j]=-1
            j+=1

cnt=0
for x in table:
    if x==1:
        cnt+=1
print(cnt)
### BUGGY CODE ###

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

for i in range(min(K, 100)):
    B = [0] * N
    for j in range(N):
        cnt = 0
        for k in range(N):
            if k - A[k] - 0.5 <= j <= k + A[k] + 0.5:
                cnt += 1
        B[j] = cnt
    A = B[:]
print(*A)



### FIXED CODE ###

import numpy as np
from numba import njit


@njit
def solve(N, K, A):
    for _ in range(K):
        B = np.zeros(N + 1, dtype=np.int64)
        for i in range(N):
            a = A[i]
            B[max(0, i - a)] += 1
            B[min(N, i + a + 1)] -= 1
        A = np.cumsum(B)[:-1]
        if np.all(A == N):
            return A
    return A


N, K = map(int, input().split())
A = np.array(input().split(), dtype=int)
print(' '.join(map(str, solve(N, K, A))))
### BUGGY CODE ###

import heapq
def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = []
    C = []
    for i in range(M):
        b, c = map(int, input().split())
        B.append(b)
        C.append(c)
        
    heapq.heapify(A)
    for i in range(M):
        for j in range(B[i]):
            if C[i] < A[0]:
                break
            heapq.heapreplace(A, C[i])
    
    print(sum(A))


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    N, M = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    operate = []
    for _ in range(M):
        b, c = map(int,input().split())
        operate.append([b,c])
    operate.sort(reverse=True, key=lambda x:x[1])    

    rewrite = [0] * N
    idx = 0
    for b,c in operate:
        for i in range(b):
            rewrite[idx] = c
            idx += 1
            if idx == N:
                break
        if idx == N:
            break
    
    ans = 0
    for i in range(N):
        ans += max(A[i],rewrite[i])
    
    print(ans)

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

from collections import deque

INF = 10**6

H,W = map(int,input().split())
C1,C2 =map(lambda x : int(x) - 1,input().split())
D1,D2 = map(lambda x : int(x) - 1,input().split())

S = [input() for _ in range (H)]
t = [[INF]*W for _ in range (H)]


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


q = deque([(C1,C2)])
a = 0
t[C1][C2] = a

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

    if t[D1][D2]!= INF:
        break

    a+=1

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


if t[D1][D2] == INF:
    print(-1)
else:
    print(t[D1][D2])


### FIXED CODE ###

from collections import deque


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

    from builtins import max, min, range

    INF = 10 ** 6

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

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

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

        if t[Dh][Dw] != INF:
            break

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

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


main()
### BUGGY CODE ###

from collections import Counter
n = int(input())
dic = Counter(list(map(int,input().split())))
rslt = 1
a = 10**9 + 7
if n % 2 == 0:
    if dic != Counter(sum([[i,i] for i in range(1, n, 2)], [])):
        rslt = 0
    else:
        rslt = 2**(n//2) % a

else:
    if dic != Counter(abs(i) for i in range(-n+1, n, 2)):
        rslt = 0
    else:
        rslt = 2**(n//2) % a
            
print(rslt)

### FIXED CODE ###

from collections import Counter
n = int(input())
ns = list(map(int, input().split()))
rslt = 0
a = 10 ** 9 + 7
cnt = Counter(ns)
if n % 2 == 0:
    for i in range(1, n, 2):
        if cnt[i] != 2:
            print(0)
            exit()
    rslt = pow(2, n // 2, a)
else:
    for i in range(2, n, 2):
        if cnt[i] != 2:
            print(0)
            exit()
    if cnt[0] == 1:
        rslt = pow(2, n // 2, a)
print(rslt)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
                L1 = L[i]
                L2 = L[j]
                L3 = L[k]
                if L1<L2+L3 and L2<L1+L3 and L3<L1+L2:
                    ans += 1
print(ans)

### FIXED CODE ###

from bisect import bisect_left # 左から何番目に入るかを二分探索（O(logN)）で返す
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N):
    L1 = L[i]
    for j in range(i+1, N):
        L2 = L[j]
        sumL = L1 + L2
        k = bisect_left(L, sumL)
        ans += max(0, k-j-1) # (k-1)-(j+1)+1

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

n,m,q = map(int,input().split())
c=[[0 for i in range(n+1)] for j in range(n+1)]
x=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(m):
    l,r = map(int,input().split())
    x[l][r] += 1
for i in range(1,n+1):
    for j in range(1,n+1):
        c[i][j] = c[i][j-1] + x[i][j]
for i in range(q):
    p,q = map(int,input().split())
    sum = 0
    for j in range(p,q+1):
         sum+= c[j][q] - c[j][p-1]
    print(sum)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,m,q = map(int,input().split())
c=[[0 for i in range(n+1)] for j in range(n+1)]
x=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(m):
    l,r = map(int,input().split())
    x[l][r] += 1
for i in range(1,n+1):
    for j in range(1,n+1):
        c[i][j] = c[i][j-1] + x[i][j]
for i in range(q):
    p,q = map(int,input().split())
    sum = 0
    for j in range(p,q+1):
         sum+= c[j][q] - c[j][p-1]
    print(sum)
### BUGGY CODE ###

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

MOD = 10**9+7

ans=0
for i in range(60):
    one_cnt = 0
    for a in a_list:
        one_cnt += (a & 2**i)
    one_cnt //= 2**i
    zero_cnt = n - one_cnt
    ans = (ans + (2**i * one_cnt * zero_cnt) % MOD) % MOD
print(ans)

### FIXED CODE ###

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

MOD = 10**9+7

ans=0
for i in range(60):
    one_cnt = 0
    for a in a_list:
        one_cnt += (a & 2**i)
    one_cnt //= 2**i
    zero_cnt = n - one_cnt
    ans = (ans + (2**i * one_cnt * zero_cnt) % MOD) % MOD
print(ans)
### BUGGY CODE ###

n = int(input())
A = [int(input()) for i in range(n)]
max = A[1]-A[0]
min = A[0]

for i in range(n-1):
    if(max < A[i+1]-A[0]):
        max = A[i+1]-A[0]

for i in range(1,n-1):
    if(min > A[i]):
        for j in range(i,n-1):
            if(max < A[j+1]-A[i]):
                max = A[j+1]-A[i]
print(max)


### FIXED CODE ###

n = int(input())
A = [int(input()) for i in range(n)]
max = A[1]-A[0]
min = A[0]

for i in range(1,n):
    if(max < A[i]-min):
        max = A[i]-min
    if(min > A[i]):
        min = A[i]

print(max)
### BUGGY CODE ###

from collections import deque
d = deque()
d.extend(input())
q = int(input())
for i in range(q):
  qu = input().split()
  if qu[0] == "1":
    d.reverse()
  else:
    if qu[1] == "1":
      d.extendleft(qu[2])
    else:
      d.extend(qu[2])

print(''.join(list(d)))


### FIXED CODE ###

from collections import deque
d = deque()
d.extend(input())
q = int(input())
r = False
for i in range(q):
  qu = input().split()
  if qu[0] == "1":
    r = not r
  else:
    if (qu[1] == "1" and not r) or (qu[1] == "2" and r):
      d.extendleft(qu[2])
    else:
      d.extend(qu[2])

if r:
  d.reverse()

print(''.join(list(d)))
### BUGGY CODE ###

from queue import Queue
import sys
input = sys.stdin.readline

B = int(1E8)

def main():

    H, W = map(int, input().split())
    
    l = 0
    q = Queue()
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.put(B*h+w)
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append(B*(h-1) + w)
            if h != H-1:
                Next[h][w].append(B*(h+1) + w)
            if w != 0:
                Next[h][w].append(B*h + w-1)
            if w != W-1:
                Next[h][w].append(B*h + w+1)

    c = -1
    for _ in range(H+W+2):
        if l == 0:
            break
        nl = 0
        for _ in range(l):
            hw = q.get()
            h, w = hw//B, hw%B
            for nhw in Next[h][w]:
                nh, nw = nhw//B, nhw%B
                if not checked[nh][nw]:
                    q.put(B*nh + nw)
                    checked[nh][nw] = True
                    nl += 1
        l = nl
        c += 1

    print(c)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

B = int(1E8)

def main():

    H, W = map(int, input().split())
    
    l = 0
    q = []
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.append(B*h+w)
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append(B*(h-1) + w)
            if h != H-1:
                Next[h][w].append(B*(h+1) + w)
            if w != 0:
                Next[h][w].append(B*h + w-1)
            if w != W-1:
                Next[h][w].append(B*h + w+1)

    c = -1
    for _ in range(H+W+2):
        qq = []
        if len(q) == 0:
            break
        for hw in q:
            h, w = hw//B, hw%B
            for nhw in Next[h][w]:
                nh, nw = nhw//B, nhw%B
                if not checked[nh][nw]:
                    qq.append(B*nh + nw)
                    checked[nh][nw] = True
        q = qq
        c += 1

    print(c)


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

import itertools

N = int(input())
A_list = list(map(int, input().split()))
A_list.insert(0, 0)
product_dict = {}
for i, j in itertools.combinations(range(len(A_list)), 2):
    product_dict[str(i) + "&" + str(j)] = A_list[i] * A_list[j]

sum = 0
for i in range(1, N):
    for j in range(i + 1, N + 1):
        sum += product_dict[str(i) + "&" + str(j)]
        sum = sum % 1000000007
print(sum)


### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
A_list.insert(0, 0)

cum_sum = 0
cum_sum_list = []
for i in range(N + 1):
    cum_sum += A_list[i]
    cum_sum_list.append(cum_sum)

ans = 0
for i in range(1, N+1):
    ans += A_list[i] * (cum_sum_list[N] - cum_sum_list[i])
    ans = ans % 1000000007
print(ans)
### BUGGY CODE ###

import math
from functools import reduce
k=int(input())
def gcd(*numbers):
    return reduce(math.gcd, numbers)
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      ans+=gcd(i,j,l)
print(ans)

### FIXED CODE ###

import math
from functools import reduce
k=int(input())
def gcd(*numbers):
    return reduce(math.gcd, numbers)
ans=0
for i in range(1,k+1):
  for j in range(i,k+1):
    for l in range(j,k+1):
      if l==i:
        ans+=gcd(i,j,l)
      elif i==j or j==l:
        ans+=3*gcd(i,j,l)
      else:
        ans+=6*gcd(i,j,l)
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
h=[0]*N
s=[0]*K
d=[0]*(N-K+1)

for i in range(N):
  h[i]=int(input())
h=sorted(h)

for i in range(N-K+1):
  for j in range(K):
    s[j]=h[i+j]
  d[i]=s[K-1]-s[0]
  if d[i] == 0:
    print(0)
    exit()

print(min(d))

### FIXED CODE ###

N,K=map(int,input().split())
H=[int(input()) for i in range(N)]
H.sort()

ans=float('inf')
for i in range(N-K+1):
  ans=min(ans,H[i+K-1]-H[i])
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
a,b = list(),list()
for i in range(n):
  temp = list(map(int,input().split()))
  a.append(temp[0])
  b.append(temp[1])
for i in range(n):
  for j in range(n-1, i, -1):
    if a[j] < a[j-1]:
      temp = a[j]
      a[j] = a[j-1]
      a[j-1] = temp
      temp = b[j]
      b[j] = b[j-1]
      b[j-1] = temp
sum = 0
for i in range(n):
  sum += b[i]
  if sum >= k:
    print(a[i])
    exit()

### FIXED CODE ###

n,k = map(int,input().split())
num = [0] * 100000
for i in range(n):
  c,d = map(int,input().split())
  num[c-1] += d
sum = 0
for i in range(100000):
  sum += num[i]
  if sum >= k:
    print(i + 1)
    exit()
### BUGGY CODE ###

import copy
N = int(input())
numbers = [int(i) for i in input().split()]

mid = (N - 1) // 2
for i in range(N):
    copy_num = copy.deepcopy(numbers)
    index_num = copy_num.pop(i)
    copy_num = sorted(copy_num)
    print(copy_num[mid])
    

### FIXED CODE ###

import copy
N = int(input())
numbers = [int(i) for i in input().split()]
copy_num = sorted(copy.deepcopy(numbers))

mid = N // 2
mid_num = copy_num[mid]

for i in range(N):
    if numbers[i] >= mid_num:
        print(copy_num[mid-1])
    else :
        print(mid_num)
### BUGGY CODE ###

import sys
S=raw_input()
judge=["dream","dreamer","erase","eraser"]

S_pointer=0

V=set()
V.add(0)

cnt=0
while cnt<len(S)/5+1:
	tmp=set()
	for i in V:
		for j in judge:
			if S[i:i+7].find(j)==0:
				if i+len(j)==len(S):
					tmp.add(i+len(j))
					print "YES"
					sys.exit()
				else:
					tmp.add(i+len(j))

	V=V|tmp
	cnt+=1

#print V

print "YES" if max(V)==len(S) else "NO"

### FIXED CODE ###

import sys
S=raw_input()
judge=["dream","dreamer","erase","eraser"]

V=set()
V.add(0)

cnt=0
while cnt<len(S):
	tmp=set()
	for i in V:
		for j in judge:
			if S[i:i+7].find(j)==0:
				tmp.add(i+len(j))
				if i+len(j)==len(S):
					print "YES"
					sys.exit()
	V=tmp
	cnt+=1
else:
	print "NO"
### BUGGY CODE ###

n,m=map(int,input().split())
ans=int(1)
for i in range(1,n+1):
    ans*=i
    
for i in range(1,m+1):
    ans*=i

if n==m:
    ans*=2

if abs(n-m)>1:
    ans=0

print(ans%1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
if abs(n-m)>1:
    print(0)

else:
    ans=int(1)
    for i in range(1,n+1):
        ans*=i
        ans%=1000000007
    
    for i in range(1,m+1):
        ans*=i
        ans%=1000000007

    if n==m:
        ans*=2
        ans%=1000000007
    
    print(ans)
### BUGGY CODE ###

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=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

bitl = BIT(N)
for i in range(N):
    l1[i] = bitl.sum(xy[i][1])
    l2[i] = i-l1[i]
    bitl.add(xy[i][1],1)

bitr = BIT(N)
for i in range(N):
    r1[N-i-1] = bitr.sum(xy[N-i-1][1])
    r2[N-i-1] = i-r1[N-i-1]
    bitr.add(xy[N-i-1][1],1)

ans = pow(2,N-1,mod)*N%mod
for i in range(N):
    L1 = pow(2,l1[i],mod)
    L2 = pow(2,l2[i],mod)
    R1 = pow(2,r1[i],mod)
    R2 = pow(2,r2[i],mod)
    ans += L1*L2%mod*R1%mod*R2%mod
    ans -= L1*R1%mod
    ans -= L2*R2%mod
    ans -= L1*L2%mod
    ans -= R1*R2%mod
    ans += L1+L2+R1+R2-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 ###

r,g,b,n = map(int,input().split())
lis=[r,g,b]
lis.sort()
cnt=0
for i in range(n//lis[2] + 1):
  for l in range(n//lis[1]+1):
    for m in range(n//lis[0]+1):
      if i*lis[2]+l*lis[1]+m*lis[0] == n:
        cnt+=1
print(cnt)


### FIXED CODE ###

b,r,g,n=map(int,input().split())
ans=0
for i in range(3000//r+1):
    for j in range(3000//g+1):
        if n-j*g-i*r>=0 and (n-j*g-i*r)%b==0:
            ans+=1
print(ans)
### BUGGY CODE ###

N, K = [int(n) for n in input().split()]
dice = [int(n) for n in input().split()]

def ev(p):
    return (1 + p)/2

maxev = 0
for i in range(len(dice) - K + 1):
    current_ev = 0
    for j in range(K):
        current_ev += ev(dice[i + j])
    maxev = max(maxev, current_ev)

print(maxev)

### FIXED CODE ###

N, K = [int(n) for n in input().split()]
#dice = [int(n) for n in input().split()]
evs = [(1 + int(n))/2 for n in input().split()]
cumsum = [0]

for i in range(1,N+1):
    cumsum.append(cumsum[i-1] + evs[i-1])

k_cum = [cumsum[i+K] - cumsum[i] for i in range(N-K+1)]

print(max(k_cum))