Harryxun/stf_run huggingface dataset:
import bisect

N = int(input())
a = list(map(int, input().split()))
to = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    to[u].append(v)
    to[v].append(u)
del u, v

ans = [-1] * N


def dfs(v, prev_dp):
    dp = [*prev_dp]
    if len(dp) == 0 or a[v] > dp[-1]:
        dp.append(a[v])
    else:
        pos = bisect.bisect_left(dp, a[v])
        dp[pos] = a[v]
    ans[v] = len(dp)

    for u in to[v]:
        if ans[u] == -1:
            dfs(u, dp)


dfs(0, [])


for an in ans:
    print(an)


### FIXED CODE ###

import bisect
import sys


N = int(input())
a = list(map(int, input().split()))
to = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    to[u].append(v)
    to[v].append(u)
del u, v

ans = [-1] * N


def dfs(v, dp):
    # dp は参照渡し
    if len(dp) == 0 or a[v] > dp[-1]:
        dp.append(a[v])
        back = -1
    else:
        pos = bisect.bisect_left(dp, a[v])
        back = dp[pos]
        dp[pos] = a[v]
    ans[v] = len(dp)

    for u in to[v]:
        if ans[u] == -1:
            dfs(u, dp)
    if back == -1:
        dp.pop()
    else:
        dp[pos] = back


sys.setrecursionlimit(10 ** 6)
dfs(0, [])


for an in ans:
    print(an)
n=int(input())
arr=set(map(int,input().split())
print("YES" if n==len(arr) else "NO")

### FIXED CODE ###

n=int(input())
arr=set(map(int,input().split()))
print("YES" if n==len(arr) else "NO")
import sys
from collections import Counter
m = Counter(sys.stdin.readlines().lower())
for i in 'abcdefghijklmnopqrstuvwxyz':
    print(i, ":", m[i])



### FIXED CODE ###

import sys
from collections import Counter
m = Counter(sys.stdin.read().lower())
for i in 'abcdefghijklmnopqrstuvwxyz':
    print(i, ":", m[i])
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def main():
    n, x, y = map(int, input().split())
    tree = [[0] * n for i in range(n)]

    for i in range(1, n):
        for j in range(i+1, n+1):
            # if i <= x and j >= y:
            #     tree[i - 1][j - 1] = j-i-(y - x - 1)
            # elif i <= x and j < y:
            #     tree[i - 1][j - 1] = x - i + min(y - j + 1, j - x)
            # elif i > x and j >= y:
            #     tree[i - 1][j - 1] = j - y + min(i-x+1, y-i)
            # else:
            #     tree[i - 1][j - 1] = j-i
            tree[i - 1][j - 1] = min(j-i, abs(x-i) +
                                     1+abs(j-y), abs(y-i)+1+abs(j-x))

    for k in range(1, n):
        ans = 0
        for i in range(n):
            ans += tree[i].count(k)
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    n, x, y = LI()
    d = [0]*n
    for i in range(1, n):
        for j in range(i + 1, n + 1):
            d[min(j - i, abs(x - i) + 1 + abs(j - y),
                  abs(y - i) + 1 + abs(j - x)) - 1] += 1
    for k in range(n-1):
        print(d[k])


if __name__ == "__main__":
    main()
N, W = map(int, input().split())
import numpy as np
dp = np.zeros(W + 1, dtype=int)
for i in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
print(dp.max())

### FIXED CODE ###

N, W = map(int, input().split())
import numpy as np
dp = np.zeros(W+1, dtype=int)
for i in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
print(dp.max())
children = int(input())
total = 0

for i in range(chldren):
  total += i+1
print(total)

### FIXED CODE ###

children = int(input())
total = 0
for i in range(children):
  i += 1
  total += i
print(total)
dbflag="aaa.txt"

def debug(*args):
	if ""!=dbflag: print(*args)

if ""!=dbflag: _INDATA=open(dbflag)

def readline():
	if ""!=dbflag:return _INDATA.readline()
	else: return input()


result = -1

c = readline().rstrip()

BOIN = {'a','i','u','e','o'}


if c in BOIN:
	result = "vowel"
else:
	result = "consonant"

print(result)


### FIXED CODE ###

dbflag=""

def debug(*args):
	if ""!=dbflag: print(*args)

if ""!=dbflag: _INDATA=open(dbflag)

def readline():
	if ""!=dbflag:return _INDATA.readline()
	else: return input()


result = -1

c = readline().rstrip()

BOIN = {'a','i','u','e','o'}


if c in BOIN:
	result = "vowel"
else:
	result = "consonant"

print(result)
def two_power(num: int) -> int:
    count = 0

    while num % 2 == 0:
        try:
            num = num / 2
            count += 1
        except ValueError:
            pass
    return count


n = int(input())
li = (input().split(' '))

l = []
for i in range(0, n):
    l.append(int(li[i]))

ans_list = []
for i in range(0, n):
    ans_list.append(two_power(l[i]))

print(max(ans_list))

### FIXED CODE ###

n = input()

n0 = int(n[0])
n1 = int(n[1])
n2 = int(n[2])

s = n0 + n1 + n2
print(s)
nums = input(3).split(5)
a = int(nums[0])
b = int(nums[1])
print(a * b,(a + b) * 2)

### FIXED CODE ###

nums = input().split()
a = int(nums[0])
b = int(nums[1])
print(a * b,(a + b) * 2)
x = int(input())


def func(p):
    q = 1
    while q <= x:
        q *= p
    return q / p


z = []
a = 2

if x = 1:
    print("1")
    exit()

else:
    while a <= x ** 0.5:
        z.append(func(a))
        a += 1

print(max(z))


### FIXED CODE ###

x = int(input())

if x == 1:
    print("1")
    exit()


def func(p):
    q = p
    while q < x:
        q *= p
        if q == x:
            return q
    if q / p == p:
        return 1
    else:
        return q // p


z = []
a = 2

while a <= x:
    z.append(func(a))
    a += 1

print(max(z))
r = int(input())
pi = 3.141592653589
print("{0:0.6f} {1:0.6f}".format((r**2)*pi,r*2*pi))

### FIXED CODE ###

import math
r = float(input())
print("{0:.6f} {1:.6f}".format(r**2*math.pi,r*2*math.pi))
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)

    if n > 10**4:
        raise 't'

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        t = list(d[s] - set([m]))[-1]
        if len(d[t]) > 2:
            if h:
                if f[t]:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    tt = True
    gf = collections.defaultdict(bool)
    while tt:
        if rf:
            gf = collections.defaultdict(bool)
            f = collections.defaultdict(bool)
            rf = False
        tt = False
        for k,v in list(d.items()):
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True, -1)
                if res:
                    return 'First'
                tt = True
    return 'Second'


print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    kk = None
    for _ in range(n-1):
        a,b = LI()
        kk = [a,b]
        d[a].add(b)
        d[b].add(a)

    tt = True
    gf = collections.defaultdict(bool)
    while tt:
        tt = False
        for k,v in list(d.items()):
            if len(v) == 1:
                vt = list(v)[0]
                if len(d[vt]) == 1:
                    continue
                for vv in d[vt]:
                    if vv == k:
                        continue
                    if vt in d[vv]:
                        d[vv].remove(vt)
                d[vt] = set([k])
                tt = True
            elif len(v) == 0:
                return 'First'
    return 'Second'


print(main())
for vertical in range(h + 1):
    for horizontal in range(vertical):
        if horizontal == 0 or horizontal == vertical - 1\
                or vertical == h:
            print('*', end='')
        else:
            print('+', end='')

### FIXED CODE ###

while True:
    H, W = [int(i) for i in input().split()]
    if H == W == 0:
        break
      
    for h in range(H):
        for w in range(W):
            if h == 0 or h == H-1 or w == 0 or w == W - 1:
                print('#', end='')
            else:
                print('.', end='')
        print()
      
    print()
import bisect
n = int(input())
 
l = list(map(int, input().split()))
l.sort()
a = 0
 
for i in range(n-2):
    for j in range(i+1,n-1):
        s = bisect.bisect_left(l[i]+l[j])
        a += n-s-1 


print(a)

### FIXED CODE ###

import bisect
n = int(input())
 
l = list(map(int, input().split()))
l.sort()
a = 0
#print(l)
for i in range(n-2):
    for j in range(i+1,n-1):
        s = bisect.bisect_left(l,l[i]+l[j])-j-1
        a+=s


print(a)
n,m = map(int,input().split()
if (n*m)%2 ==0:
          print("Even")
else:
          print(Odd)

### FIXED CODE ###

n,m = map(int,input().split())
if (n*m)%2 ==0:
          print("Even")
else:
          print("Odd")
N,M==map(int,input().split())
if N==M:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

N,M=map(int,input().split())
if N==M:
  print('Yes')
else:
  print('No')
S = input()
list = []
j = -1
for i in range(0, len(S)):
    if not(S[i]=="A" or S[i]=="C" or S[i]=="G" or S[i]=="T"):
        list.append(i-j-1)
        j = i
print("{}".format(max(list)))


### FIXED CODE ###

S = input()
S = S+"0"
max = 0
j = -1
for i in range(0, len(S)):
    if not(S[i]=="A" or S[i]=="C" or S[i]=="G" or S[i]=="T"):
        if max<i-j-1:
            max = i-j-1
        j = i
print("{}".format(max))
import math
from functools import reduce

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

print(reduce((lambda x, y: math.gcd(x, y)), a))

### FIXED CODE ###

import fractions
from functools import reduce

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

#print(reduce((lambda x, y: math.gcd(x, y)), a))
print(reduce((lambda x, y: fractions.gcd(x, y)), a))
n = int(input())
ans = 0
for i in range(int(n**0.5)-1,n):
    if n%i==n//i:
        ans +=1

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
div = make_divisors(n)
for i in div[1:]:
    if n//(i-1)==n%(i-1):
        ans += i-1

print(ans)
n = int(input())
a = [int(input()) - 1 for _ in range(n)]
print(sum(a))

### FIXED CODE ###

_ = input()
a = list(map(int,input().split()))
print(sum(a) - len(a))
s = input()
ans = ''
for i in range(len(s)):
  s_i = s[i]
  if s_i = '?':
    if i < len(s):
      if s[i + 1] == 'D':
        ans += 'P'
        continue
    else:
      ans += 'D'
      continue
  ans += s_i
print(ans)
      

### FIXED CODE ###

s = input()
ans = ''
for i in range(len(s)):
  s_i = s[i]
  if s_i == '?':
      ans += 'D'
      continue
  ans += s_i
print(ans)
S=int(input())
W=int(input())

if S<=W:
    print('unsafe')
    
else:
    print('safe')

### FIXED CODE ###

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

if S<=W:
    print('unsafe')
    
else:
    print('safe')
n=int(input())
a = list(map(int,split(input())))
a.sort()
print(abs(a[0]-a[-1]))

### FIXED CODE ###

n=int(input())
a = list(map(int,input().split()))
a.sort()
print(abs(a[0]-a[-1]))
N = int(input())
A = list(map(int, input().split()))
Adict = []
for i in A:
  if i in Adict:
    Adict[i]=Adict[i]+1
  else:
    Adict.update({i:1})
B = [0, 0]
for i in Adict.keys():
    if Adict[i] >= 2:
        B.append(i)
    if Adict[i] >= 4:
        B.append(i)
B.sort()
print(B[-1]*B[-2])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Adict = {}
for i in A:
    if i in Adict:
        Adict[i]=Adict[i]+1
    else:
        Adict.update({i:1})
B = [0, 0]
for i in Adict.keys():
    if Adict[i] >= 2:
        B.append(i)
    if Adict[i] >= 4:
        B.append(i)
B.sort()
print(B[-1]*B[-2])
x=int(input())
k=int(input())
s=0
for i in range(0,20):
    b=int(str(x)[i:i+1])
    if b==1:
        s=s+1
    elif(b>1):
        s=s+1
        c=b
        break;
if (k<s):
    print("1")
else:
    print(c)

### FIXED CODE ###

S=input()
K=int(input())
a=0
b=0
N=len(S)
for i in range(N):
    if S[i]=="1":
        a=i+1
    else:
        b=S[i]
        break
if K<=a:
    print(1)
else:
    print(b)
n,m=map(int,input().split())
v=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  v[a-1].append(b-1)

memo=[-1]*n
def dp(x):
  if memo[x]!=-1:return memo[x]
  r=0
  for i in v[x]:
    r=max(r,dp(i)+1)
  memo[x]=r
  return r
print(max(dp(i) for i in range(n)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(2000000000)
n,m=map(int,input().split())
v=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  v[a-1].append(b-1)

memo=[-1]*n
def dp(x):
  if memo[x]!=-1:return memo[x]
  r=0
  for i in v[x]:
    r=max(r,dp(i)+1)
  memo[x]=r
  return r
print(max(dp(i) for i in range(n)))
a = input().split()
print(int(a[0]+a[1]/2))

### FIXED CODE ###

def main():
  a, b = (int(_) for _ in input().split())
  print(int(a+b/2))
main()
h,w= map(int, input().split())
if h%2!=0 & w%2!=0 :
    print(h*((w+1)//2))
else 
    print(h*w/2)

### FIXED CODE ###

H,W = map(int, input().split())
print(1 if H*W in [H,W] else W*(H//2)+(W//2+W%2)*(H%2))
n,m=map(int,input().split())
for i in range(m):
    print(m-i+,m+i+1)


### FIXED CODE ###

n,m=map(int,input().split())
g=m//2
k=m-g
for i in range(m):
    if i%2==1:
        a=n-g-((i+1)//2)
        b=a+i+1
        print(a,b)
    else:
        a=k-(i//2)
        b=a+i+1
        print(a,b)
w = input()

s = {}
for c  in w:
    s[c] += 1

b = True
for k,v in s.items():
    b = b and v % 2 == 0

if b:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

w = input()

s = {}
for c in w:
    if c in s:
        s[c] += 1
    else:
        s[c] = 1
b = True
for k,v in s.items():
    b = b and v % 2 == 0

if b:
    print("Yes")
else:
    print("No")
ans=-10**18
if a<=0<=b or c<=0<=d:
  ans=0
ans=max(ans,a*c,a*d,b*c,b*d)
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

import sys
input=sys.stdin.readline

a,b,c,d=map(int,input().split())
ans=-10**18
#x=0 or y=0
if a<=0<=b or c<=0<=d:
    ans=max(ans,0)
#x<0 and y>0
ans=max(ans,b*c)
#x>0 and y>0
ans=max(ans,b*d)
#x<0 and y<0
ans=max(ans,a*c)
#x>0 and y<0
ans=max(ans,a*d)
print(ans)
N = int(input())
S = list(map(int, input().split()))

ans = 0
for c in range(N):
    a = 0
    if (N-1) % c:
        for i in range(1, (N-1)//c):
            a += S[i*c] + S[N-1-i*c]
            ans = max(ans, a)
    else:
        for i in range(1, (N-1)//(2*c)):
            a += S[i*c] + S[N-1-i*c]
            ans = max(ans, a)
print(ans)

### FIXED CODE ###

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

ans = 0
for c in range(1, N):
    a = 0
    if (N-1) % c:
        for i in range(1, (N-1)//c):
            a += S[i*c] + S[N-1-i*c]
            ans = max(ans, a)
    else:
        se = set(list(range(N)))
        for i in range(1, (N-1)//c):
            if i*c not in se or N-1-i*c not in se or i*c == N-1-i*c:
                break
            se.remove(i*c)
            se.remove(N-1-i*c)
            a += S[i*c] + S[N-1-i*c]
            ans = max(ans, a)
print(ans)
def main():
    N = input_int()
    S = input()

    print(len(rec(S)))
    print(rec(S))


def rec(s):
    if len(s) <= 1:
        return s

    i = 0

    while i + 1 in range(len(s)) and s[i] == s[i+1]:
        i += 1

    return s[0] + rec(s[i+1:])


def input_int():
    return int(input())


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


def input_int_list():
    return list(map(int, input().split()))


main()


### FIXED CODE ###

def main():
    N = input_int()
    S = input()

    validitylist = [False] * N
    validitylist[0] = True

    for i in range(1, N):
        if S[i-1] != S[i]:
            validitylist[i] = True
    
    print(len([i for i in validitylist if i is True]))



def input_int():
    return int(input())


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


def input_int_list():
    return list(map(int, input().split()))


main()
W, H, N = map(int,input().split())
Map = np.ones((H, W),dtype = int)
for i in range(N):
    x,y,a = map(int,input().split())
    if a == 1:
        Map[:,:x] = 0
    elif a == 2:
        Map[:,x:] = 0
    elif a == 3:
        Map[:y,:] = 0
    else:
        Map[y:,:] = 0
print(Map.sum())    

### FIXED CODE ###

import numpy as np
W, H, N = map(int,input().split())
Map = np.ones((H, W),dtype = int)
for i in range(N):
    x,y,a = map(int,input().split())
    if a == 1:
        Map[:,:x] = 0
    elif a == 2:
        Map[:,x:] = 0
    elif a == 3:
        Map[:y,:] = 0
    else:
        Map[y:,:] = 0
print(Map.sum())
a = list(map(int, input().split()))
[print(*i) for i in a.sort()]


### FIXED CODE ###

a = list(map(int, input().split()))
a.sort()
print(" ".join(map(str, a)))
import sys
input = sys.stdin.readline

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

g = [[] for _ in range(n)]
c = [0] * n
visited = [False] * n

#根に近い順に累積和
def dfs(i):
    visited[i] = True
    for j in g[i]:
        if visited[j] == True:
            continue
        c[j]+=c[i]
        dfs(j)

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

for i in range(q):
    p,x = map(int,input().split())
    c[p - 1]+=x

dfs(0)
print(*c)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n,q = map(int,input().split())

g = [[] for _ in range(n)]
c = [0] * n
visited = [False] * n

#根に近い順に累積和
def dfs(i):
    visited[i] = True
    for j in g[i]:
        if visited[j] == True:
            continue
        c[j]+=c[i]
        dfs(j)

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

for i in range(q):
    p,x = map(int,input().split())
    c[p - 1]+=x

dfs(0)
print(*c)
Q = 10**9+7
from collections import deque
from itertools import accumulate
#import sys
#input = sys.stdin.readline
def main():
    N, K = map( int, input().split())
    ans = 0
    d = deque()
    e = deque()
    M = int(N**(1/2))*2
    for i in range(1, int(N**(1/2))+1):
        if i**2 == N:
            d.append(i)
            M -= 1
            continue
        d.append(i)
        e.appendleft(N//i)
    T = list(d+e)
    CT = [1]*M
    for i in range(1,M):
        CT[i] = T[i] - T[i-1]
    accT = list( map(lambda x:x%Q, accumulate(CT) ))
    dp = [[0]*M for _ in range(K)]
    for i in range(M):
        dp[1][i] = accT[-i-1]*CT[i]%Q
    for k in range(1, K-1):
        accT[0] = dp[k][0]
        for i in range(M-1):
            accT[i+1] = (accT[i]+dp[k][i+1])%Q
        for i in range(M):
            dp[k+1][i] = accT[-i-1]*CT[i]%Q
    print(sum(dp[K-1])%Q)
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

Q = 10**9+7
from collections import deque
from itertools import accumulate
#import sys
#input = sys.stdin.readline
def main():
    N, K = map( int, input().split())
    ans = 0
    d = deque()
    e = deque()
    M = int(N**(1/2))*2
    for i in range(1, int(N**(1/2))+1):
        if i**2 == N:
            d.append(i)
            M -= 1
            continue
        d.append(i)
        e.appendleft(N//i)
    T = list(d)+list(e)
    CT = [1]*M
    for i in range(1,M):
        CT[i] = T[i] - T[i-1]
    accT = list( map(lambda x:x%Q, accumulate(CT) ))
    dp = [[0]*M for _ in range(K)]
    for i in range(M):
        dp[1][i] = accT[-i-1]*CT[i]%Q
    for k in range(1, K-1):
        accT[0] = dp[k][0]
        for i in range(M-1):
            accT[i+1] = (accT[i]+dp[k][i+1])%Q
        for i in range(M):
            dp[k+1][i] = accT[-i-1]*CT[i]%Q
    print(sum(dp[K-1])%Q)
    
if __name__ == '__main__':
    main()
a,b,c=map(int, input().split())
print(max((a!=b)+(b!=c)+(c!=a),1)

### FIXED CODE ###

a,b,c=map(int, input().split())
print(max((a!=b)+(b!=c)+(c!=a),1))
while 1:
   H, W = map(int, raw_input().split())
            
   if H == 0 and W == 0:
      break
   for i in range(0, H):
      if i%2 == 0:
         if W%2 == 0:
            print "#."*(W/2)
         else:
            print "#."*(w/2)+"#"
      else:
         if W%2 == 0:
            print ".#"*(W/2)
         else:
            print ".#"*(w/2)+"."
   print ""

### FIXED CODE ###

while 1:
   H, W = map(int, raw_input().split())
           
   if H == 0 and W == 0:
      break
   for i in range(H):
      if i%2 == 0:
         if W%2 == 0:
            print "#."*(W/2)
         elif W%2 == 1:
            print "#."*(W/2)+"#"
      elif i%2 == 1:
         if W%2 == 0:
            print ".#"*(W/2)
         elif W%2 == 1:
            print ".#"*(W/2)+"."
   print ""
n,m=map(int,input().split())
a=set(map(int,input().split()))
b=set(map(int,input().split()))
c=1;N=0;M=0
for k in range(n*m,0,-1):
  if k in A and k in B:
    N+=1;M+=1
  elif k in A:
    c*=M;N+=1
  elif k in B:
    c*=N;M+=1
  else:
    c*=N*M-n*m+k
  c%=(10**9+7)
print(c)

### FIXED CODE ###

import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
x=10**9+7
if len(set(a))!=len(a) or len(set(b))!=len(b):
  print(0)
else:
  a.sort()
  b.sort()
  L=[]
  for i in range(n):
    l=[]
    for j in range(m):
      l.append(0)
    L.append(l)
  if m*n in a and m*n in b:
    L[a.index(m*n)][b.index(m*n)]=m*n
    ct=1
    ctn=1
    ctm=1
    A=set(a)
    B=set(b)
    for k in range(m*n-1,0,-1):
      if k in A and k in B:
        L[bisect.bisect_left(a,k)][bisect.bisect_left(b,k)]=k
        ct*=1
        ctn+=1
        ctm+=1
      elif k in A:
          ct*=ctm
          ctn+=1
      elif k in B:
          ct*=ctn
          ctm+=1
      else:
        ct*=(ctm*ctn-m*n+k)
      if ct==0:
        break
      ct=ct%x
    print(ct)
  else:
    print(0)