Harryxun/stf_run huggingface dataset:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


show_flg = False
# show_flg = True


def main():
    N, M = MI()

    if N <= 2 or M <= 2:
        graph = [[1] * (M+2) for i in range(N+2)]
        for i in range(1, N+1):
            for j in range(1, M+1):
                for v in product([0, -1, 1], repeat=2):
                    graph[v[0] + i][v[1] + j] = 1 - graph[v[0] + i][v[1] + j]

        ans = 0
        for i in range(1, N+1):
            for j in range(1, M+1):
                if graph[i][j] == 0:
                    ans += 1

        print(ans)
    else:
        print((M - 2) * (N - 2))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


show_flg = False
# show_flg = True


def main():
    N, M = MI()

    # graph = [[1] * (M+2) for i in range(N+2)]
    # for i in range(1, N+1):
    #     for j in range(1, M+1):
    #         for v in product([0, -1, 1], repeat=2):
    #             graph[v[0] + i][v[1] + j] = 1 - graph[v[0] + i][v[1] + j]

    # ans = 0
    # for i in range(1, N+1):
    #     for j in range(1, M+1):
    #         if graph[i][j] == 0:
    #             ans += 1

    # print(ans)

    if N == 1 and M == 1:
        print(1)
    elif M == 1 or N == 1:
        print(max(N, M) - 2)
    else:
        print((M - 2) * (N - 2))


if __name__ == '__main__':
    main()
input()
li = list(map(int, input().split()))
li.sort(reverse=True)
alice = [i for index,i in enumerate(li) if index % 2 == 0]
ans = alice * 2 - sum(li)
print(alice)

### FIXED CODE ###

input()
li = list(map(int, input().split()))
li.sort(reverse=True)
alice = sum([i for index,i in enumerate(li) if index % 2 == 0])
ans = alice * 2 - sum(li)
print(ans)
#二部グラフになっている時の色の塗り分けを聞いている
n=int(input())
es=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=list(map(int,input().split()))
  es[u-1].append([v,w])
  es[v-1].append([u,w])

colors=[0 for i in range(n)]
#深さ優先探索　頂点vをcolorで塗ることを考える
def dfs(v,color):
  colors[v-1]=color
  for i in es[v-1]:
    if i[1]%2==0 and colors[i[0]-1]==0:
      dfs(i[0],color)
    elif i[1]%2==1 and colors[i[0]-1]==0:
      dfs(i[0],(-1)*color)
  return colors

    
a=dfs(1,-1)
for i in a:
  if i==-1:
    print(0)
  else:
    print(1)
  


### FIXED CODE ###

# 再帰の深さが1000を超えそうなときはこれをやっておく
import sys
sys.setrecursionlimit(10**7)
#二部グラフになっている時の色の塗り分けを聞いている
n=int(input())
es=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=list(map(int,input().split()))
  es[u-1].append([v,w])
  es[v-1].append([u,w])

colors=[0 for i in range(n)]
#深さ優先探索　頂点vをcolorで塗ることを考える
def dfs(v,color):
  colors[v-1]=color
  for i in es[v-1]:
    if i[1]%2==0 and colors[i[0]-1]==0:
      dfs(i[0],color)
    elif i[1]%2==1 and colors[i[0]-1]==0:
      dfs(i[0],(-1)*color)
  return colors

    
a=dfs(1,-1)
for i in a:
  if i==-1:
    print(0)
  else:
    print(1)
import sys
from heapq import *
H,O=[],''
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=f'{-heappop(H)}\n')
print(O[-1])


### FIXED CODE ###

import sys
from heapq import*
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))
def resolve():
    inp = input().split()
    a = int(inp[0])
    b = int(inp[1])
    k = int(inp[2])

    if (a - k) <= 0 :
        k = k - a
        a = 0
    else:
        a = a - k
        k = 0

    if (b - k) <= 0:
        k = k - b
        b = 0
    else:
        b = b - k
        k = 0

    print(str(a) + ' ' + str(b))

    
if __name__ == "__main__":
    reslove()

### FIXED CODE ###

import sys
from io import StringIO
import unittest

def resolve():
    inp = input().split()
    a = int(inp[0])
    b = int(inp[1])
    k = int(inp[2])

    if (a - k) <= 0 :
        k = k - a
        a = 0
    else:
        a = a - k
        k = 0

    if (b - k) <= 0:
        k = k - b
        b = 0
    else:
        b = b - k
        k = 0

    print(str(a) + ' ' + str(b))

if __name__ == "__main__":
    resolve()
N = int(input())
c = list(input())

r = c.count("R")
rs = c[:r]
rsw = rs.count("W")
a = rsw

w = list(reversed(c)).index("R")
w = (N - 1) - w
ws = c[:w]
b = ws.count("W")

print(min(a,b))




### FIXED CODE ###

import sys

N = int(input())
c = list(input())

r = c.count("R")
if r == 0 :
    print(0)
    sys.exit()   
rs = c[:r]
rsw = rs.count("W")
a = rsw

w = list(reversed(c)).index("R")
w = (N - 1) - w
ws = c[:w]
b = ws.count("W")
print(min(a,b))
a, b = map(int, input().split())
for n in range(1, 4):
  if a*b*c % 2 == 1:
    return 'Yes'
return 'No'

### FIXED CODE ###

a, b = map(int, input().split())
for c in range(1, 4):
  if a*b*c % 2 == 1:
    print('Yes')
    break
  else:
    if c == 3:
      print('No')
## C
n, m = map(int,input().split())
a = [0] * n
b = [0] * n
for i in range(0,n):
    a[i], b[i] = map(int,input().split())

dict = {}
for i in range(0,n):
    dict[a[i]] = b[i]

l = sorted(a)

for j in range(0,n-1):
    if l[j] == l[j-1]:
        dic[l[j]] = dic[l[j]]+dic[l[j-1]]
        l[j-1] = -j
        dic[l[j-1]] = 0

#print(l)
#print(dict)

ex = 0
num = 0

for i in range(0,n):
    #print(l[i])
    if num + dict[l[i]] <= m:
        ex = ex + l[i] * dict[l[i]]
        num = num + dict[l[i]]
    else:
        ex = ex + l[i] * (m - num)
        num = m
    #print([ex,num])
    if num == m:
        break

print(ex)






### FIXED CODE ###

##### C 再チャレンジ

##以下、二次元配列を、各リストの最初の要素でソートするアルゴリズム

def two_dim_merge_sort(arr):#＃arrは二次元配列
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = two_dim_merge_sort(left)
    right = two_dim_merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return two_dim_merge(left, right)


def two_dim_merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i][0] <= right[r_i][0]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

##ここまで

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

l = [0]*n

for i in range(0,n):
    l[i] = list(map(int,input().split()))

s = two_dim_merge_sort(l)

num = 0
ex = 0

for i in range(0,n):
    if num + s[i][1] <= m:
        ex = ex + s[i][0] * s[i][1]
        num = num + s[i][1]
    else:
        ex = ex + s[i][0] * (m-num)
        num = m
    if num == m:
        break
        
print(ex)
for i in input():
    i.sprit()
    a = int(i[i][0])
    b = int(i[i][1])
    temp = a+b
    x = 0
    while temp // (10**x) > 0:
        x += 1
    print(x)

### FIXED CODE ###

import sys

for s in sys.stdin:
  a,b = map(int,s.split())
  print(len(str(a+b)))
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)


def calc(x, isTrans):
    if isTrans:
        y = np.copy(x.T)
    else:
        y = np.copy(x)

    for i in range(len(y)):
        xxx = np.copy(y[i])
        tmp_l = np.arange(len(xxx))
        tmp_l[xxx > 0] = 0
        np.maximum.accumulate(tmp_l, out=tmp_l)
        left = tmp_l

        xxx_reverse = xxx[::-1]
        tmp_r = np.arange(len(xxx_reverse))
        tmp_r[xxx_reverse > 0] = 0
        np.maximum.accumulate(tmp_r, out=tmp_r)
        right = len(xxx)-tmp_r[::-1]-1

        y[i] = right-left-1
        y[i][xxx == 0] = 0

    if isTrans:
        return np.transpose(y)
    else:
        return y


if __name__ == "__main__":
    h, w = map(int, readline().split())
    room = np.zeros((h+2, w+2), dtype=np.int)
    for i in range(1, h+1):
        room[i][1:-1] = [0 if i == "#" else 1 for i in input()]

    a = calc(room, True)
    b = calc(room, False)
    ans = (a + b).max() - 1
    print(ans)


### FIXED CODE ###

import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def calc(x, isTrans):
    if isTrans:
        y = np.copy(x.T)
    else:
        y = np.copy(x)

    for i in range(len(y)):
        xxx = np.copy(y[i])
        tmp_l = np.arange(len(xxx))
        tmp_l[xxx > 0] = 0
        np.maximum.accumulate(tmp_l, out=tmp_l)
        left = tmp_l

        xxx_reverse = xxx[::-1]
        tmp_r = np.arange(len(xxx_reverse))
        tmp_r[xxx_reverse > 0] = 0
        np.maximum.accumulate(tmp_r, out=tmp_r)
        right = len(xxx)-tmp_r[::-1]-1

        y[i] = right-left-1
        y[i][xxx == 0] = 0

    if isTrans:
        return np.transpose(y)
    else:
        return y


if __name__ == "__main__":
    h, w = map(int, readline().split())
    room = np.zeros((h+2, w+2), dtype=np.int)
    for i in range(1, h+1):
        room[i][1:-1] = [0 if i == "#" else 1 for i in input()]

    a = calc(room, True)
    b = calc(room, False)
    ans = (a + b).max() - 1
    print(ans)
b = input()

if b == A:
  print("T")
if b == T:
  print("A")
if b == C:
  print("G")
if b == G:
  print("C")

### FIXED CODE ###

b = input()
 
if b == "A":
  print("T")
if b == "T":
  print("A")
if b == "C":
  print("G")
if b == "G":
  print("C")
n = int(input())
ln = list(str(n))
from collections import Counter
nc = dict(Counter(ln))
s = 0
if n != 0:
    for i in range(1, 10):
        s += i * nc[str(i)]
if s % 9 == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = int(input())
ln = list(str(n))
from collections import Counter
nc = dict(Counter(ln))
s = 0
if n != 0:
    for i in range(1, 10):
        if str(i) in nc:
            s += i * nc[str(i)]
if s % 9 == 0:
    print('Yes')
else:
    print('No')
n, y = map(int, input().split())

ans = "-1, -1, -1"

for n10000 in range(n+1):
    for n5000 in range(n - n10000 + 1):
        n1000 = n - n5000 - n10000
        money_total = n10000 * 10000 + n5000 * 5000 + n1000 * 1000
        if money_total == y:
            ans = f"{n10000} {n5000} {n1000}"

print(ans)


### FIXED CODE ###

n, y = map(int, input().split())

for n10000 in range(n+1):
    for n5000 in range(n - n10000 + 1):
        n1000 = n - n5000 - n10000
        money_total = n10000 * 10000 + n5000 * 5000 + n1000 * 1000
        if money_total == y:
            print(n10000, n5000, n1000)
            exit()

print(-1, -1, -1)
n=int(input())
h=list(map(int,input().split()))
a,b=0,[]
for i in range(1000000):
    if h[i]<h[i+1]:
        b.append(i-a)
        a=i+1
    if i+2==len(h):
        b.append(i-a+1)
        break
print(b)

### FIXED CODE ###

import sys
n=int(input())
h=list(map(int,input().split()))
a,b=0,[]
if len(h)==1:
    print('0')
    sys.exit()
for i in range(1000000):
    if h[i]<h[i+1]:
        b.append(i-a)
        a=i+1
    if i+2==len(h):
        b.append(i-a+1)
        break
print(max(b))
s=list(input())

for i in range(len(s)):
  s.pop(2*i-1)
  
ss=''.join(map(str,s))

print(ss)

### FIXED CODE ###

s=list(input())

for i in range(len(s)):
  if i%2==1:
    s[i]=''
  
ss=''.join(map(str,s))

print(ss)
def main(A, dp, n):
    if n == -1:
        return dp[0]

    if (n in A) == False: 
        dp[n] = (dp[n + 1] + dp[n + 2]) % mod
    return main(A, dp, n-1)
 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (10**5)
A = [int(input()) for _ in range(M)] 
if (N-1 in A) == False:
    dp[N], dp[N-1] = 1, 1
else:
    dp[N] = 1
ans = main(A, dp, N-2)
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (N+2)
A = set([int(input()) for _ in range(M)]) 
dp[-2] = 1

for i in range(N-1, -1, -1):
    if (i in A) == False:
        dp[i] = (dp[i + 1] + dp[i + 2]) % mod 

print(dp[0])
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
a, b = map(int, input().split())
c = a * b
if c % 2 = 0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
a, b = map(int, input().split())
c = a * b
if c % 2 == 0:
  print("Even")
else:
  print("Odd")
N, Q = map(int, input().split())
data = input()
result = [0] * N
for i in range(N-1):
  if data[i] == "A" and data[i+1]:
    result[i+1] = result[i] + 1
  else:
    result[i+1] = result[i

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


### FIXED CODE ###

b = input()

if b == "A":
  print("T")
elif b == "T":
  print("A")
elif b == "C":
  print("G")
elif b == "G":
  print("C")
A, B, C, K = [int(i) for i in input().split(" ")]
N = [A, B, C]
# print("N:", N)
for i in N:
    K -= i
    if K == 0:
        # print("i:", i)
        # print("K:", K)
        if i == 0:
            N[i+1] = 0
            N[i+2] = 0
        elif i == 1:
            N[i+1] = 0
        break
    elif K < 0:
        # print("i:", i)
        # print("K:", K)
        if i == 0:
            N[i+1] = 0
            N[i+2] = 0
        elif i == 1:
            N[i+1] = 0
        N[i-1] += K
        break
# print("N:", N)
print(1 * N[0] -1 * N[2])

### FIXED CODE ###

A, B, C, K = [int(i) for i in input().split(" ")]
N = [A, B, C]
for i in range(len(N)):
    K -= N[i]
    if K == 0:
        if i == 0:
            N[i+1] = 0
            N[i+2] = 0
        elif i == 1:
            N[i+1] = 0
        break
    elif K < 0:
        if i == 0:
            N[i+1] = 0
            N[i+2] = 0
        elif i == 1:
            N[i+1] = 0
        N[i] += K
        break
print(1 * N[0] -1 * N[2])
def is_float_str(num_str, default=0):
    try:
        return {"is_float": True, "val": float(num_str)}
    except ValueError:
        return {"is_float": False, "val": default}


def compute(operand, val1, val2):
    if operand == "+":
        return val1 + val2
    elif operand == "-":
        return val1 - val2
    elif operand == "*":
        return val1 * val2
    elif operand == "/":
        return val1 / val2


def get_input():
    while True:
        try:
            yield input()
        except EOFError:
            break


# split with ' '
formulas = list(get_input())
for (i, formula) in enumerate(formulas, 0):
    formulas[i] = formula.split(' ')
stack = []

for formula in formulas:
    for elm in formula:
        if is_float_str(elm)["is_float"]:
            stack.append(is_float_str(elm)["val"])
        elif elm in ['+', '-', '*', '/']:
            stack.append(compute(elm, stack.pop(), stack.pop()))

if len(stack) == 1:
    print(str(stack[0]) + '\n')


### FIXED CODE ###

def is_float_str(num_str, default=0):
    try:
        return {"is_float": True, "val": float(num_str)}
    except ValueError:
        return {"is_float": False, "val": default}


def compute(operand, val1, val2):
    if operand == "+":
        return val2 + val1
    elif operand == "-":
        return val2 - val1
    elif operand == "*":
        return val2 * val1
    elif operand == "/":
        return val2 / val1


def get_input():
    while True:
        try:
            yield input()
        except EOFError:
            break


if __name__ == '__main__':
    # split with ' '
    formulas = list(get_input())
    for (i, formula) in enumerate(formulas, 0):
        formulas[i] = formula.split(' ')
    stack = []

    for formula in formulas:
        stack = []
        for elm in formula:
            if is_float_str(elm)["is_float"]:
                stack.append(is_float_str(elm)["val"])
            elif elm in ['+', '-', '*', '/']:
                stack.append(compute(elm, stack.pop(), stack.pop()))
        if len(stack) == 1:
            print(format(stack[0], '.6f'))
import math
from sympy import *
a,b,X = map(float,input().split())
T = math.atan(a/b)
if X <= a**2*b/2.0:
    c = 2*X/(a*b**2)
    t = Symbol('t', real=True)
    x = solve(t**3-c*t**2+t-c)[0]
    theta = 90.0 -math.atan(x)*180/math.pi
else:
    Y = a**2*b-X
    theta = math.atan(2*Y/a**3)*180/math.pi
print(theta)

### FIXED CODE ###

import math
a,b,X = map(float,input().split())
T = math.atan(a/b)
if X <= a**2*b/2.0:
    c = 2*X/(a*b**2)
    theta = 90.0 -math.atan(c)*180/math.pi
else:
    Y = a**2*b-X
    theta = math.atan(2*Y/a**3)*180/math.pi
print(theta)
N,L=map(int,input().split())
S=[input() for n in range(N)]
for num in range(L):
    ans1=S[num]
    for num2 in range(L):

        ans2=S[num2]
        for i in range(L):
            if ans1[i]>ans2[i]:
                break
            elif ans1[i]==ans2[i]:
                continue
            else :
                S[num],S[num2]=S[num2],S[num]
print("".join(S))

### FIXED CODE ###

N,L=map(int,input().split())
S=[input() for n in range(N)]
S=sorted(S)
"""for num in range(L):
    ans1=S[num]
    for num2 in range(L):

        ans2=S[num2]
        for i in range(L):
            if ans1[i]>ans2[i]:
                break
            elif ans1[i]==ans2[i]:
                continue
            else :
                S[num],S[num2]=S[num2],S[num]
                break
"""
print("".join(S))
#tempt
s=input()
t=input()
lt=len(t)
ls=len(s)
cnt=0
flag=True

for i in range(lt):
    for j in range(ls):
        if t[i]==s[j]:
            bs=j
            bt=i
            af=j
            at=j
            check=True
            while bs>0 and bt>0: #before
                if s[bs]=="?" or s[bs]==t[bt]:
                    continue
                else:
                    check=False
                bs-=1
                bt-=1
            if bt>0:
                check=False
            while af < ls and at < lt:  # before
                if s[af] == "?" or s[af] == t[at]:
                    continue
                else:
                    check = False
                af += 1
                at += 1
            if at != lt-1:
                check = False
        if not check:
            flag=False
        else:
            flag=True
    if flag:
        continue
    else:
        print("UNRESTORABLE")
        exit()




### FIXED CODE ###

S=input()
T=input()
tmp=[]
for i in range(len(S)):
    flag=True
    for j in range(min(len(T),len(S)-i)):
        if S[i+j]==T[j] or S[i+j]=="?" or T[j]=="?":
            continue
        else:
            flag=False
    if flag:
        rec=S[:i]+T+S[i+len(T):]
        if len(rec)==len(S):
            rec=rec.replace("?","a")
            tmp.append(rec)
if tmp==[]:
    print("UNRESTORABLE")
    exit()
tmp.sort()
print(tmp[0])
N = int(input())
h = list(map(int,input().split()))
dp = [999999] * N

dp[0] = 0
dp[1] = abs(h[0]-h[1])
for i in range(N-2):
    dp[i + 2] = min((dp[i] + abs(h[i] - h[i+2])), (dp[i+1] + abs(h[i+1] - h[i+2])))
    print(dp)
print(dp[N-1])


### FIXED CODE ###

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

dp[0] = 0
dp[1] = abs(h[0]-h[1])
for i in range(N-2):
    dp[i + 2] = min((dp[i] + abs(h[i] - h[i+2])), (dp[i+1] + abs(h[i+1] - h[i+2])))
   
print(dp[N-1])
A,B,C,D=map(int,input().split())
print([Balanced,Left,Right][(C+D<A+B)-(C+D>A+B)])


### FIXED CODE ###

A, B, C, D = map( int, input().split())
L = A + B
R = C + D

if( L < R):
  print('Right')
  
elif(L == R):
  print('Balanced')
  
else:
  print('Left')
inr = lambda: list(map(int, input().split()))

N, Y = inr()

lmn = [[-1, -1, -1]]

for x in range(N+1):
    for y in range(N+1):
        z = N - x - y
        oto_sum = 10000 * x + 5000 * y + 1000 * z
        if Y == oto_sum:
            lmn.append([x, y, z])
print(lmn[1][0],lmn[1][1],lmn[1][2])

### FIXED CODE ###

inr = lambda: list(map(int, input().split()))

N, Y = inr()

lmn = [-1, -1, -1]

for x in range(N+1):
    for y in range(N-x+1):
        z = N - x - y
        oto_sum = 10000 * x + 5000 * y + 1000 * z
        if z >= 0 and oto_sum == Y:
            print(x, y, z)
            exit()

print(-1, -1, -1)
def s(x):
    print('',x,end='')
def p(u):
    if u+1:s(u);p(R[u]);p(L(u))
def i(u):
    if u+1:i(R(u));s(u);p(L(u))
def o(u):
    if u+1:o(R(u));o(L(u));s(u)
        
n = int(input())
R, L = [0]*n, [0]*n
for _ in range(n):
    a, b, c = map(int, input().split())
    R[a] = b
    L[a] = c
root = (set(range(n))-set(R)-set(L)).pop()
print(f'Preorder{p(r)}')
print(f'Inorder{i(r)}')
print(f'Postorder{o(r)}')


### FIXED CODE ###

def s(x):
    print('',x,end='')
def p(u):
    if u+1:s(u);p(R[u]);p(L[u])
def i(u):
    if u+1:i(R[u]);s(u);i(L[u])
def o(u):
    if u+1:o(R[u]);o(L[u]);s(u)
        
n = int(input())
R, L = [0]*n, [0]*n
for _ in range(n):
    a, b, c = map(int, input().split())
    R[a] = b
    L[a] = c

root = (set(range(n))-set(R)-set(L)).pop()
print('Preorder');p(root)
print('\nInorder');i(root)
print('\nPostorder');o(root)
print()
N = input()
T,A = input().split()
H = list(map(lambda x: abs(T - int(x) * 0.006 - A),input().split()))
print(H.index(min(H))+1)

### FIXED CODE ###

N = input()
T,A = map(int,input().split())
H = list(map(lambda x: abs(T - int(x) * 0.006 - A),input().split()))
print(H.index(min(H))+1)
# コンビネーション
mod = 10**9+7
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 10**6+6 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

r1, c1, r2, c2 = map(int, input().split())

ans = 0
for c in range(c1, c2+1):
    ans += cmb(c+r2+1, r2) - cmb(c+r1, r1-1)
    ans %= mod
print(ans)

### FIXED CODE ###

# コンビネーション
mod = 10**9+7
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 3*10**6+6 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

r1, c1, r2, c2 = map(int, input().split())

ans = 0
for c in range(c1, c2+1):
    ans += cmb(c+r2+1, r2) - cmb(c+r1, r1-1)
    ans %= mod
print(ans)