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

H,W = map(int,input().split())
maze = []
for i in range(H):
    s = input()
    m = []
    for j in range(W):
        m.append(s[j])
    maze.append(m)
d = [[10**9 for i in range(W*H)] for i in range(W*H)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
for i in range(W*H):
    h = i//W
    w = i%W
    if maze[h][w] == '#':
        continue
    for j in range(4):
        x = w + dx[j]
        y = h + dy[j]
        k = x + y*W
        if 0<=x<=W-1:
            if 0<=y<=H-1:
                if maze[y][x] == '.':
                    d[i][k] = 1
                    d[k][i] = 1
for i in range(W*H):
    d[i][i] = 0
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(W*H):
        for i in range(W*H):
            for j in range(W*H):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
warshall_floyd(d)
ans = 0
for i in range(W*H):
    for j in range(W*H):
        if d[i][j] < 10**9:
            ans = max(ans,d[i][j])
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
maze = []
for i in range(H):
    s = input()
    m = []
    for j in range(W):
        m.append(s[j])
    maze.append(m)
d = [[10**9 for i in range(W*H)] for i in range(W*H)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
for i in range(W*H):
    h = i//W
    w = i%W
    if maze[h][w] == '#':
        continue
    for j in range(4):
        x = w + dx[j]
        y = h + dy[j]
        k = x + y*W
        if 0<=x<=W-1:
            if 0<=y<=H-1:
                if maze[y][x] == '.':
                    d[i][k] = 1
                    d[k][i] = 1
for i in range(W*H):
    d[i][i] = 0
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(W*H):
        for i in range(W*H):
            for j in range(W*H):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
warshall_floyd(d)
ans = 0
for i in range(W*H):
    for j in range(W*H):
        if d[i][j] < 10**9:
            ans = max(ans,d[i][j])
print(ans)
### BUGGY CODE ###

import heapq
import numpy as np

N, Q = map(int, input().split())
ans = np.zeros((N+1), dtype=np.int)
graph = {i:[None, []] for i in range(1, N+1)}
nums = {i for i in range(1, N+1)}
visited = [False] * (N+1)

for i in range(N-1):
    a, b = map(int, input().split())
    graph[b][0] = a
    graph[a][1].append(b)
    if a in nums:
        nums.remove(a)

q = [(0, n) for n in nums]

while q:
    x, n = heapq.heappop(q)
    
    if not visited[n]:
        visited[n] = True
        par, child = graph[n]
        
        if not par is None:
            graph[par][1].extend(child)
        
            heapq.heappush(q, (x+1, par))
for i in range(Q):
    p, x = map(int, input().split())
    ans[p] += x
    ans[graph[p][1]] += x
    
for n in ans[1:]:
    print(n, '', end='')


### FIXED CODE ###

from collections import deque

def main():
  N, Q = map(int, input().split())
  visited = [False] * (N+1)
  graph = {i:deque() for i in range(N+1)}

  for i in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

  visited[1] = True

  c = [0] * (N+1)
  for i in range(Q):
    p, x = map(int, input().split())
    c[p] += x
    
  q = [1]
  while q:
    per = q.pop()
    for child in graph[per]:
      if not visited[child]:
        visited[child] = True
        c[child] += c[per]
        q.append(child)

  for i in range(1, N+1):
    print(c[i], '', end='')

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


def main():

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

    ans = 0
    for i in range(1000):
        d1 = (i // 100) % 10
        d2 = (i // 10) % 10
        d3 = i % 10
        d1_flag = True
        d2_flag = True

        for j in S:

            now = int(j)
            if d1_flag:
                if d1 == now:
                    d1_flag = False
                continue

            if d2_flag:
                if d2 == now:
                    d2_flag = False
                continue

            if d3 == now:
                ans += 1
                break

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

ans = 0


for i in range(10):
    for j in range(10):
        for k in range(10):
            flag1 = 0
            flag2 = 0
            
            for l in range(n):
                if flag1 == 0 and s[l] == str(i):
                    flag1 = 1
                    continue
                
                if flag1 == 1 and flag2 == 0 and s[l] == str(j):
                    flag2 = 1
                    continue
                
                if flag1 == 1 and flag2 == 1 and s[l] == str(k):
                    ans += 1
                    break
                
print(ans)
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    import collections

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    fp = [[10**6 for _ in range(W)] for _ in range(H)]

    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0
    next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]
    w_goto = []
    for i in range(5):
        for j in range(5):
            if [i, j] in next_y_x:
                pass
            else:
                w_goto.append([-2 + i, -2 + j])
    w_goto.remove([0,0])

    while que:
        temp = que.popleft()
        w_num = temp[2]

        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                    que.appendleft([ny, nx, temp[2]])
                    fp[ny][nx] = w_num
        
        for dy, dx in w_goto:
            nwy = temp[0] + dy
            nwx = temp[1] + dx
            nw = w_num +1

            if 0 <= nwy <= H-1 and 0 <= nwx <= W-1:
                if grid[nwy][nwx] == '.' and fp[nwy][nwx] >= w_num:
                    que.append([nwy, nwx, nw])
                    fp[nwy][nwx] = nw


    if fp[Dh][Dw] != 10**6:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    from collections import deque

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num] * W for _ in range(H)]

    que = deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

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

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

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if a[i] % a[j] == 0:
            ans -= 1
            break

print(ans)

### FIXED CODE ###

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

dp = [0]*(10**6 + 1)
ans = 0

for i in a:
    if dp[i] == 0:
        for j in range(1,10**6+1):
            if i * j > 10**6:
                break
            dp[i*j] += 1
    elif dp[i] == 1:
        dp[i] += 1

for i in a:
    if dp[i] == 1:
        ans += 1


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

n, k = map(int, input().split())
hlst = list(map(int, input().split()))
inf = 10 ** 10
dp = [inf for _ in range(n)]
dp[0] = 0
for i in range(1, n):
    for j in range(1, k + 1):
        if i - j < 0:
            break
        dp[i] = min(dp[i - j] + abs(hlst[i] - hlst[i - j]), dp[i])
print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
hlst = list(map(int, input().split()))
inf = 10 ** 10
dp = [inf for _ in range(n)]
dp[0] = 0
for i in range(1, n):
    for j in range(1, k + 1):
        if i - j < 0:
            break
        dp[i] = min(dp[i - j] + abs(hlst[i] - hlst[i - j]), dp[i])
print(dp[-1])
### BUGGY CODE ###

N=int(input())
data = list(map(int, input().split()))
ans=0
for i in range(0,N):
    a=[]
    a=data[0:i+1]
    if a[i]==min(a):
        ans+=1

print(ans)

### FIXED CODE ###

N=int(input())
data = list(map(int, input().split()))
ans=1
minmin=data[0]
if N==1:
    ans=1
elif N>1:
    minmin=data[0]
    for i in range(1,N):

        if data[i]<=minmin:
            minmin=data[i]
            #if minmin<=data[i]:
            ans+=1
                #continue
        #if minmin<=data[i]:
            #ans+=1

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

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

h, n = na()
inf = 10**9+7
dp = [inf for i in range(h+1)]
dp[0] = 0
for i in range(n):
    a, b = na()
    for j in range(h):
        dp[min(j + a, h)] = min(dp[min(j + a, h)], dp[j] + b)
print(dp[h])


### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

h, n = na()
inf = 10**9+7
dp = [inf for i in range(h+1)]
dp[0] = 0
for i in range(n):
    a, b = na()
    for j in range(h):
        dp[min(j + a, h)] = min(dp[min(j + a, h)], dp[j] + b)
print(dp[h])
### BUGGY CODE ###

def main():
    n, k = [int(x) for x in input().split()]
    scores = [int(x) for x in input().split()]
    former = 0
    rank = 1
    for score in scores[:k]:
        rank *= score

    for shift in range(n - k):
        former = rank
        rank //= scores[shift]
        rank *= scores[shift + k]
        if former < rank:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, k = [int(x) for x in input().split()]
    scores = [int(x) for x in input().split()]

    for remover, new_commer in zip(scores, scores[k:]):
        if remover < new_commer:
            print('Yes')
        else:
            print('No')


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

def main():
    s = list(reversed(input()))
    mod = 10**9+7
    memo = [0 for _ in [0]*13]
    m13 = [(10**i) % 13 for i in range(12)]
    memo[0] = 1
    for i in range(len(s)):
        memo2 = [0 for _ in [0]*13]
        a = m13[i % 12]
        if s[i] == "?":
            list_ = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        else:
            list_ = [int(s[i])]
        list_ = [(a*j) % 13 for j in list_]
        for l in list_:
            for j in range(13):
                memo2[(l+j) % 13] += memo[j]
        memo = [j % mod for j in memo2]
    print(memo[5])


main()

### FIXED CODE ###

s=list(reversed(input()))
mod=10**9+7
memo=[0 for _ in [0]*13]
m13=[(10**i)%13 for i in range(12)]
memo[0]=1
for i in range(len(s)):
    memo2=[0 for _ in [0]*13]
    a=m13[i%12]
    if s[i]=="?":
        list_=[0,1,2,3,4,5,6,7,8,9]
    else:
        list_=[int(s[i])]
    list_=[(a*j)%13 for j in list_]
    for l in list_:
        for j in range(13):
            memo2[(l+j)%13]+=memo[j]
    memo=[j%mod for j in memo2]
print(memo[5])
### BUGGY CODE ###

from collections import Counter
a = int(input())
b = list(map(int, input().split()))
for i in range(1, a+1):
    d = Counter(b)
    if d.most_common(1)[0][1] == 1:
        print(a // i)
    else:
        r = 0
        while d:
            t = d.most_common(i)
            if len(t) < i:
                break
            d.subtract(Counter([k[0] for k in t]))
            if d.most_common()[-1][1] < 0:
                break
            r += 1
        print(r)


### FIXED CODE ###

from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    m = max(list(Counter(A).values()))
    d = Counter(Counter(A).values())
    l = []
    t = 0
    for i in range(m, 0, -1):
        t += d[i]
        l.append(t)
    l.reverse()
    t = 0
    r = []
    for i in range(N):
        if m > i:
            t += l[i]
        r.append(t//(i+1))
    p = -1
    a = []
    for i, v in enumerate(reversed(r)):
        if p != v:
            a.append((v, N-i))
        p = v
    a.append((N, 0))
    t = 0
    aa = []
    for i in range(1, N+1):
        if a[t][0] < i:
            t += 1
        aa.append(a[t][1])
    for i in aa:
        print(i)
main()
### BUGGY CODE ###

H, N = map(int, input().split())
magiclist = [0]*N
dp = [0] * (N+1)
for s in range(N+1):
    dp[s] = [10**9] * (H + 1)
    dp[s][0] = 0
for i in range(N):
    magiclist[i] = [0]*2
    damage, mp = map(int, input().split())
    magiclist[i][0], magiclist[i][1] = damage, mp
    for j in range(H + 1):
        if j - damage < 0:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], (mp + dp[i + 1][j - damage]))
kouho = dp[N][H]
for h in range(N):
    kouho = min(kouho, min(dp[N][H-magiclist[h][0]:H])+magiclist[h][1])
print(kouho)


### FIXED CODE ###

H, N = map(int, input().split())
magiclist = [0]*N
dp = [0] * (N+1)
for s in range(N+1):
    dp[s] = [10**9] * (H + 1)
    dp[s][0] = 0
for i in range(N):
    magiclist[i] = [0]*2
    damage, mp = map(int, input().split())
    magiclist[i][0], magiclist[i][1] = damage, mp
    for j in range(H + 1):
        if j - damage < 0:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], (mp + dp[i + 1][j - damage]))
kouho = dp[N][H]
for h in range(N):
    kouho = min(kouho, min(dp[N][H-magiclist[h][0]:H])+magiclist[h][1])
print(kouho)
### BUGGY CODE ###

n = int(input())
List = list(map(int, input().split()))
count = 0

for i in range(n):
  for j in range(i+1):
    if List[i] > List[j]:
      break
    if i == j:
      count += 1
print(count)

### FIXED CODE ###

n = int(input())
List = list(map(int, input().split()))
count = 1
min = List[0]

for i in range(n):
  if min > List[i]:
    min =List[i]
    count += 1
print(count)
### BUGGY CODE ###

import math
import bisect

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

ans = 0
while(len(A)>1):
  a = A[-1]
  A = A[:-1]
  b = (1<<(int(math.log(a,2))+1))-a
  #print(a,b)
  r = bisect.bisect_left(A, b)
  if r < len(A) and A[r] == b:
    ans += 1
    if r == 0:
      A = A[1:]
    elif r == len(A)-1:
      A = A[:r]
    else:
      A = A[:r]+A[r+1:]
print(ans)

### FIXED CODE ###

import math
import bisect
import collections

N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)
A = sorted(list(C.keys()))
#print(C)
#print(A)

ans = 0
for i in range(len(A)-1,-1,-1):
  a = A[i]
  b = (1<<(int(math.log(a,2))+1))-a
  if a == b:
    ans += C[a]//2
    C[a] -= C[a]//2*2
  else:
    r = bisect.bisect_left(A, b)
    if r < i and A[r] == b:
      mn = min(C[a],C[A[r]])
      ans += mn
      C[a] -=  mn
      C[A[r]] -= mn
print(ans)
### BUGGY CODE ###

def solve(ls) -> int:
  n = len(ls)
  assert(3 <= n <= 2 * 10**3)

  def n_possible_cs(a: int, b: int, first_ic: int) -> int:
    def bin_search_le_rightmost(s: int, e: int, target: int):
      if s == e:
        if ls[s] > target:
          return None
        else:
          return s

      mid = s + (e - s) // 2

      if ls[mid] <= target and (mid + 1 < n and ls[mid + 1] > target):
        return mid
      elif ls[mid] <= target:
        return bin_search_le_rightmost(mid + 1, e, target)
      else:
        return bin_search_le_rightmost(s, mid, target)

    idx = bin_search_le_rightmost(first_ic, n - 1, a + b - 1)
    return 0 if idx is None else idx - first_ic + 1

  ret = 0
  for ia in range(0, n - 2):
    for ib in range(ia + 1, n - 1):
      a, b = (ls[ia], ls[ib])
      x = n_possible_cs(a, b, ib + 1)
      ret += x
  return ret


n = int(input().strip())
ls = [int(l) for l in input().split()]

print(solve(sorted(ls)))


### FIXED CODE ###

import bisect


def solve(ls) -> int:
  n = len(ls)
  assert(3 <= n <= 2 * 10**3)

  def n_possible_cs(a: int, b: int, first_ic: int) -> int:
    # def bin_search_le_rightmost(s: int, e: int, target: int):
    #   if s == e:
    #     if ls[s] > target:
    #       return None
    #     else:
    #       return s
    #
    #   mid = s + (e - s) // 2
    #
    #   if ls[mid] <= target and (mid + 1 < n and ls[mid + 1] > target):
    #     return mid
    #   elif ls[mid] <= target:
    #     return bin_search_le_rightmost(mid + 1, e, target)
    #   else:
    #     return bin_search_le_rightmost(s, mid, target)

    idx = bisect.bisect_left(ls, a + b, first_ic)
    return 0 if idx == first_ic else idx - first_ic

  ret = 0
  for ia in range(0, n - 2):
    for ib in range(ia + 1, n - 1):
      a, b = (ls[ia], ls[ib])
      x = n_possible_cs(a, b, ib + 1)
      ret += x
  return ret


n = int(input().strip())
ls = [int(l) for l in input().split()]

print(solve(sorted(ls)))
### BUGGY CODE ###

def main():
    
    s = input()[::-1]
    mod = 10**9+7
    dp = [[0 for j in range(13)] for i in range(len(s)+1)]
    dp[0][0] = 1
    ten = 1


    for i in range(len(s)):
        if s[i] == "?":
            for k in range(10):
                x = k*ten%13
                for j in range(13):
                    dp[i+1][(j+x)%13] = (dp[i][j]+dp[i+1][(j+x)%13])%mod
        
        else:
            x = int(s[i])*ten%13
            for j in range(13):
                dp[i+1][(j+x)%13] += dp[i][j]%mod

        ten *= 10%mod

    print(dp[-1][5]%mod)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    
    s = input()[::-1]
    mod = 10**9+7
    dp = [[0 for j in range(13)] for i in range(len(s)+1)]
    dp[0][0] = 1
    ten = 1


    for i in range(len(s)):
        if s[i] == "?":
            for k in range(10):
                x = k*ten%13
                for j in range(13):
                    dp[i+1][(j+x)%13] = (dp[i][j]+dp[i+1][(j+x)%13])%mod
        
        else:
            x = int(s[i])*ten%13
            for j in range(13):
                dp[i+1][(j+x)%13] = (dp[i][j]+dp[i+1][(j+x)%13])%mod

        ten = (ten*10)%13

    print(dp[-1][5]%mod)

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

N=int(input())
A=[]
Q={}
for i in range(N):
    B=input()
    A.append(B)
    Q[B]=0
    
    
for i in A:
    Q[i]+=1
    
max_Q = [kv[0] for kv in Q.items() if kv[1] == max(Q.values())] ##辞書式でvalueが最大のもののkeyの並び替え
QQ=sorted(max_Q)
for i in range(len(QQ)):
    print(QQ[i])

### FIXED CODE ###

N=int(input())
A=[]
Q={}
for i in range(N):
    B=input()
    A.append(B)
    Q[B]=0
    
for i in A:
    Q[i]+=1
    
a=max(Q.values())
ans=[]
for i in Q:
    if Q[i]==a:
        ans.append(i)
ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

import sys
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
input = sys.stdin.readline
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
xy = [list(map(int,input().split())) for i in range(n)]
xls,yls = list(zip(*xy))
xi = [(xls[i],i) for i in range(n)]
yi = [(yls[i],i) for i in range(n)]
xi.sort()
yi.sort()
xd = [0 for i in range(n)]
yd = [0 for i in range(n)]
for i in range(n):
  x,ix = xi[i]
  y,iy = yi[i]
  xd[ix] = i
  yd[iy] = i
ans = 0
bit = Bit(n+1)
xyd = list(zip(xd,yd))
xyd.sort()
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)



### FIXED CODE ###

import sys
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
input = sys.stdin.readline
from collections import defaultdict
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
dcy = defaultdict(int)
xy = [list(map(int,input().split())) for i in range(n)]
xy.sort()
yls = list(zip(*xy))[1]
yls = list(yls)
for i in range(n):
  dcy[yls[i]] = i
yls.sort()
yind = [0 for i in range(n)]
for i in range(n):
  ind = dcy[yls[i]]
  yind[ind] = i
xyd = []
for i in range(n):
  xyd.append((i,yind[i]))
ans = 0
bit = Bit(n+1)
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)
### BUGGY CODE ###

import itertools

N = int(input())
V = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

cand = [int(i) for i in range(N)]
ans = []
for i in range(N):
    hoge = list(itertools.combinations(tuple(cand), i))
    for t in hoge:
        tl = list(t)
        tmp = 0
        for j in tl:
            tmp += (V[j] - C[j])
        ans.append(tmp)
print(max(ans))     

### FIXED CODE ###

N = int(input())
V = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
gap = []
for i in range(N):
    tmp = V[i]-C[i]
    if tmp > 0:
        gap.append(tmp)

ans = 0
for i in gap:
    ans += i

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

s = input()
q = int(input())
p = 1
start = ""
end = ""
query =[]
for i in range(q):
    a = list(map(str,input().split()))
    query.append(a)

for i in range(q):
    if int(query[i][0]) == 1:
        p = p * (-1)
    else:
        if int(query[i][1]) == 1:
            if p ==1:
                start = query[i][2] + start
            else:
                end = query[i][2] + end
        else:
            if p == 1:
                end = query[i][2] + end
            else:
                start = query[i][2] + start
if p == 1:
    ans = start + s + end[::-1]
else:
    ans = end + s[::-1] + start[::-1]
print(ans)

### FIXED CODE ###

s = input()
q = int(input())
p = 1
start = ""
end = ""
query =[]
for i in range(q):
    a = list(map(str,input().split()))
    query.append(a)

for i in range(q):
    if int(query[i][0]) == 1:
        p = p * (-1)
    else:
        if int(query[i][1]) == 1:
            if p ==1:
                start = query[i][2] + start
            else:
                end = query[i][2] + end
        else:
            if p == 1:
                end = query[i][2] + end
            else:
                start = query[i][2] + start
if p == 1:
    ans = start + s + end[::-1]
else:
    ans = end + s[::-1] + start[::-1]
print(ans)