Harryxun/stf_run huggingface dataset:
def dfs(g, seen, n, ans):
    all_seen = True

    for si in seen:
        if si == False:
            all_seen = False

    if all_seen:
        ans += 1
        return ans

    for m in g[n]:
        if seen[m]:
            continue

        seen[m] = True
        ans = dfs(g, seen, m, ans)
        seen[m] = False

    return ans


def main():
    n, m = map(int, stdin.readline().split())
    ab = [map(int, stdin.readline().split()) for _ in range(n)]
    g = [[] for _ in range(n)]
    for abi in ab:
        a, b = abi
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)
    seen = [False for _ in range(n)]
    seen[0] = True

    ans = 0

    ans = dfs(g, seen, 0, ans)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin


def dfs(g, seen, n):
    all_seen = True

    for si in seen:
        if si == False:
            all_seen = False

    if all_seen:
        return 1

    ans = 0

    for m in g[n]:
        if seen[m]:
            continue

        seen[m] = True
        ans += dfs(g, seen, m)
        seen[m] = False

    return ans


def main():
    n, m = map(int, stdin.readline().split())
    ab = [map(int, stdin.readline().split()) for _ in range(m)]
    g = [[] for _ in range(n)]
    for abi in ab:
        a, b = abi
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)
    seen = [False for _ in range(n)]
    seen[0] = True

    ans = dfs(g, seen, 0)

    print(ans)


if __name__ == "__main__":
    main()
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
INF = 10**9+7
s = A[0]
A = set(A)

ans = [0]*(N+1)
ans[0] = 1
if s == 1:
    ans[1] = 0
else:
    ans[1] = 1


for i in range(2,N+1):
    if i in A:
        ans[i] = 0
    else:
        ans[i] = ans[i-1] + ans[i-2]
        ans[i] %= INF
        
print(ans[-1])

### FIXED CODE ###

N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
INF = 10**9+7
ans = [0]*(N+1)
ans[1] = 1
if M != 0:
    s = A[0]
    if s == 1:
        ans[1] = 0
A = set(A)
ans[0] = 1

for i in range(2,N+1):
    if i in A:
        ans[i] = 0
    else:
        ans[i] = ans[i-1] + ans[i-2]
        ans[i] %= INF
        
print(ans[-1])
N = int(input())

*H, = map(int, input().split())

max = 0
count = 0
def dfs(node):
    global max
    global count

    if (node+1)==N:
        if max<count:
            max = count
        return 
    if H[node]<H[node+1]:
        if max<count:
            max = count
        return 
    count = count + 1
    dfs(node+1)

for node in range(N):
    dfs(node)
    count = 0
print(max)

### FIXED CODE ###

N = int(input())
*H, = map(int, input().split())


count_max = 0
count_temp = 0
flg = 0
#全探索
for i in range(0, len(H)-1, 1):

    if H[i] < H[i+1]:
        if count_max < count_temp:
            count_max = count_temp
        count_temp = 0
        flg = 1
        continue

    count_temp = count_temp + 1

    if H[i+1]==H[len(H)-1]:
        if count_max < count_temp:
            count_max = count_temp
        flg = 1

if flg == 1:
    print(count_max)
else:
    print(0)
alpha = "abcdefghijklmnopqrstuvwxyz"
counts = {key:0 for key in alpha} 
while True:
    t = input()
    if t == "":
        break
    for s in t:
        c = s.lower()
        if c in alpha :
            counts[c] += 1

for key in sorted(counts):
    print(key+" : "+str(counts[key]))

### FIXED CODE ###

import sys
alpha = "abcdefghijklmnopqrstuvwxyz"
dic = {c:0 for c in alpha}

t = sys.stdin.read()
for s in t:
    s = s.lower()
    if s in alpha :
        dic[s] += 1

for key in sorted(dic):
    print("{} : {}".format(key,dic[key]))
def judge_color(n):
  if 1 <= n <= 399:
    return "gray"
  elif 400 <= n <= 799:
    return "brown"
  elif 800 <= n <= 1199:
    return "green"
  elif 1200 <= n <= 1599:
    return "sky"
  elif 1600 <= n <= 1999:
    return "blue"
  elif 2000 <= n <= 2399:
    return "yellow"
  elif 2400 <= n <= 2799:
    return "orange"
  elif 2800 <= n <= 3199:
    return "red"
  else:
    return "free"

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

d = {}
for each in a:
  color = judge_color(each)
  d[color] = d.get(color, 0) + 1
  
c = d.get("free",0)
l = len(d)
if c == 0:
  print(l, l)
else:
  print(max(l-1,1) l-1+c)

### FIXED CODE ###

def judge_color(n):
  if 1 <= n <= 399:
    return "gray"
  elif 400 <= n <= 799:
    return "brown"
  elif 800 <= n <= 1199:
    return "green"
  elif 1200 <= n <= 1599:
    return "sky"
  elif 1600 <= n <= 1999:
    return "blue"
  elif 2000 <= n <= 2399:
    return "yellow"
  elif 2400 <= n <= 2799:
    return "orange"
  elif 2800 <= n <= 3199:
    return "red"
  else:
    return "free"

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

d = {}
for each in a:
  color = judge_color(each)
  d[color] = d.get(color, 0) + 1
  
c = d.get("free",0)
l = len(d)
if c == 0:
  print(l, l)
else:
  print(max(l-1,1), l-1+c)
a = int(input())
kazu = [int(input()) for _ in range(2)]
if a == 1:
  print("Hello World")
else:
  print(sum(kazu))

### FIXED CODE ###

a = int(input())
if a == 1:
  print("Hello World")
else:
  b = int(input())
  c = int(input())
  print(b + c)
a=[int(input())for _ in[0]*int(input())]
m=a[-1]+1
b=[1]*-~m
x=1
while 2*x*-~x<m:
 y=x
 while 2*x*y+x+y<m:
  b[2*x*y+x+y]=0
  y+=1
 x+=1
print(sum(b[e]for e in a))


### FIXED CODE ###

b=[1]*500000
for i in range(3,999,2):
 if b[i//2]:b[i*i//2::i]=[0]*len(b[i*i//2::i])
def p(x):
 if x<5*1e5:return b[x]
 x=2*x+1
 for i in range(3,int(x**.5+1),2):
  if x%i==0:return 0
 return 1
print(sum(p(int(input()))for _ in[0]*int(input())))
def comb(n, r):
	from math import factorial
	return factorial(n) // (factorial(n - r) * factorial(r))

def main():
	import sys
	input = sys.stdin.readline
	N, K = map(int, input().split())
	num = 10 ** 9 + 7
	a = N - K + 1
	print(a)
	if K > 1:
		for j in range(2, K+1):
			b1 = comb(a, j) % num
			b2 = comb(K-1, j-1) % num
			ans = b1 * b2 % num
			print(ans)
			if ans == 0:
				sys.exit()

if __name__ == '__main__':
    main()

### FIXED CODE ###

def comb(n, r):
	from math import factorial
	return factorial(n) // (factorial(n - r) * factorial(r))

def main():
	import sys
	input = sys.stdin.readline
	N, K = map(int, input().split())
	num = 10 ** 9 + 7
	a = N - K + 1
	print(a)
	if K > 1:
		if 2 * K <= N + 1:
			for j in range(2, K+1):
				b1 = comb(a, j) % num
				b2 = comb(K-1, j-1) % num
				ans = (b1 * b2) % num
				print(ans)
		else:
			for j in range(2, N-K+2):
				b1 = comb(a, j) % num
				b2 = comb(K-1, j-1) % num
				ans = (b1 * b2) % num
				print(ans)
			for j in range(N-K+2, K+1):
				print(0)


if __name__ == '__main__':
    main()
n = int(input())
s = input()

s = list(s)

l1 = 'abcdefghijklmnopqrstuvwxyz'
l1 = list(l1)

l2 = 'abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz'
l2 = list(l2)

s1 = [0]*len(s)
s2 = [0]*len(s)

for i in range(len(s)):
	s1[i] = l1.index(s[i])

for i in range(len(s)):
	s2[i] = l2[s1[i]+n] 

#リスト１つずつくっつけて文字列にする
ans = ''.join(s2)
	
print(ans)


### FIXED CODE ###

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

s = list(s)

l1 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
l1 = list(l1)

l2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'
l2 = list(l2)

s1 = [0]*len(s)
s2 = [0]*len(s)

for i in range(len(s)):
	s1[i] = l1.index(s[i])

for i in range(len(s)):
	s2[i] = l2[s1[i]+n] 

#リスト１つずつくっつけて文字列にする
ans = ''
for i in range(len(s2)):
	ans = ans + s2[i]

print(ans)
A = int(input())
B = int(input())
C = int(input())
D = int(input())

areaAB = A*B
areaCD = C*D

if areaAB == areaCD:
  print (areaAB)
  
if areaAB > areaCD:
  print (areaAB)

if areaCD > areaAB:
  print (areaCD)

### FIXED CODE ###

a,b,c,d = map(int, input().split())

ab = a * b
cd = c * d

if ab == cd:
    print(int(ab))
elif ab > cd:
    print(int(ab))
else:
    print(int(cd))
S = input()

# s = S[0]
temp_T = 100000
for i in range(len(S)-1):
    if(S[i+1] != s[i]):
        judge = max(i+1,len(S)-(i+1))
        temp_T = min(judge, temp_T)
        s = S[i]

print(temp_T)


### FIXED CODE ###

S = input()

# s = S[0]
temp_T = len(S)
for i in range(len(S)-1):
    if(S[i] != S[i+1]):
        judge = max(i+1,len(S)-(i+1))
        temp_T = min(judge, temp_T)

print(temp_T)
import array

def merge_sort(A):
    if len(A) <= 1:
        return A, 0
    mid = len(A) // 2
    left, lcount = merge_sort(A[:mid])
    right, rcount = merge_sort(A[mid:])
    merged, count = merge(left, right)
    return merged, lcount + rcount + count

def merge(left, right):
    lpos = 0
    rpos = 0
    rcount = 0
    merged = array.array('B', [])  # List is too slow, so use array instead
    len_left = len(left)
    len_right = len(right)
    while lpos < len_left and rpos < len_right:
        if left[lpos] < right[rpos]:
            merged.append(left[lpos])
            lpos += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            rcount += len(left[lpos:])
    
    if left[lpos:]:
        merged.extend(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
    
    return merged, rcount
    
if __name__ == '__main__':
    n = int(raw_input())
    A = array.array('B', map(int, raw_input().split()))
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count

### FIXED CODE ###

from array import array

def merge_sort(A):
    if len(A) <= 1:
        return A, 0
    mid = len(A) // 2
    left, lcount = merge_sort(A[:mid])
    right, rcount = merge_sort(A[mid:])
    merged, count = merge(left, right)
    return merged, lcount + rcount + count

def merge(left, right):
    lpos = 0
    rpos = 0
    rcount = 0
    merged = array('I', [])  # List is too slow. Use an array instead.
    len_left = len(left)
    len_right = len(right)
    while lpos < len_left and rpos < len_right:
        if left[lpos] < right[rpos]:
            merged.append(left[lpos])
            lpos += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            #rcount += len(left[lpos:])
            rcount += len_left - lpos
    
    if left[lpos:]:
        merged.extend(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
    
    return merged, rcount
    
if __name__ == '__main__':
    n = int(raw_input())
    A = array('I', map(int, raw_input().split()))
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count
import sys
# import pdb
input = sys.stdin.readline

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

dp_list = [-1 for _ in range(N)]
dp_list[0] = 0
dp_list[1] = abs(hs[1] - hs[0])

def dp_memo(p):
  if dp_list[p] != -1:
    return dp_list[p]

  result = min(dp_memo(p-1) + abs(hs[p] - hs[p-1]), dp_memo(p-2) + abs(hs[p] - hs[p-2]))
  dp_list[p] = result
  return result


def dp_recur():
  cost1 = 0
  cost2 = abs(hs[1] - hs[0])

  if N == 2:
    print(cost2)
    exit()
  # pdb.set_trace()
  for i in range(2, N):
    cost3 = min(cost2 + abs(hs[i] - hs[i-1]), cost1 + abs(hs[i] - hs[i-2]))
    cost1 = cost2
    cost2 = cost3
  return cost3

# print(dp_recur())
print(dp_memo(N-1))


### FIXED CODE ###

import sys
# import pdb
input = sys.stdin.readline

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

cost1 = 0
cost2 = abs(hs[1] - hs[0])

if N == 2:
  print(cost2)
  exit()
# pdb.set_trace()
for i in range(2, N):
  cost3 = min(cost2 + abs(hs[i] - hs[i-1]), cost1 + abs(hs[i] - hs[i-2]))
  cost1 = cost2
  cost2 = cost3

print(cost3)
from collections import deque
d = deque()

for _ in range(int(input())):
    s = input()
    try:
        com, val = s.split()
        val = int(val)
    except ValueError:
        com = s
    
    if com == 'insert':
        d.appendleft(val)
    elif com == 'delete':
        d.remove(val)
    elif com == 'deleteFirst':
        d.popleft()
    elif com == 'deleteLast':
        d.pop()

print(*d)



### FIXED CODE ###

import collections
a=collections.deque()
for _ in range(int(input())):
    b=input()
    if b[0]=='i':a.appendleft(b[7:])
    elif b[6]==' ':
        try:a.remove(b[7:])
        except:pass
    elif len(b)>10:a.popleft()
    elif len(b)>6:a.pop()
print(*a)
# セル3(変数のリセット)
input_count = 0

def func(i, d, marks):
    rooms = numpy.nonzero(d[i])[0]
    new_room = []
    if rooms.size == 0:
        return marks
    for j in rooms:
        room_idx = j
        if room_idx in marks:
            continue
        marks[room_idx] = i
        new_room.append(room_idx)
    for j in new_room:
        marks = func(j, d, marks)
    return marks

def get_input():
    N, M =  list(map(int, input().split()))
    d = numpy.zeros((N,N))
    for i in range(M):
        a, b =  list(map(int, input().split()))
        d[a-1, b-1] = 1
        d[b-1, a-1] = 1
    return N, M, d

def write_result(marks, N):
    flag = True
    output_str = ''
    for i in range(1, N):
        if i not in marks:
            flag = False
            break
        output_str += f'{marks[i]+1}\n'
    if flag:
        print('Yes')    
        print(output_str)
    else:
        print('No')

import numpy


N, M, d = get_input()

marks = {0:0}
try:
    marks = func(0, d, {0: 0})
    write_result(marks, N)
except:
    pass



### FIXED CODE ###


def get_input():
    N, M =  list(map(int, input().split()))
    routes = {}
    for i in range(M):
        a, b =  list(map(int, input().split()))
        a_idx = a - 1
        b_idx = b - 1
        if a_idx in routes:
            routes[a_idx].append(b_idx)
        else:
            routes[a_idx] = [b_idx]
        
        if b_idx in routes:
            routes[b_idx].append(a_idx)
        else:
            routes[b_idx] = [a_idx]

    return N, M, routes

def write_result(marks, N):
    flag = True
    output_str = ''
    for i in range(1, N):
        if i not in marks:
            flag = False
            break
        output_str += f'{marks[i]+1}\n'
    if flag:
        print('Yes')    
        print(output_str)
    else:
        print('No')

import numpy


marks = {0:0}

N, M, routes = get_input()
mark = {0:0}
start_nodes = [0]
while start_nodes:
    next_nodes = []
    for i in start_nodes:
        for n in routes[i]:
            if n in marks:
                continue
            marks[n] = i
            next_nodes.append(n)
    start_nodes = next_nodes   
write_result(marks, N)
s = input()
s.replace(','. ' ')
print(s)

### FIXED CODE ###

s = input()
print(s.replace(',', ' '))
n = int(input())
aa = sorted(list(map(int,input().split())))
a_max = max(aa)

half = a_max/2
p = bisect_left(aa, half)
if abs(half - aa[p]) >= abs(half - aa[p-1]):
  print(a_max,aa[p-1])  
else:
  print(a_max,aa[p])  

### FIXED CODE ###

from bisect import bisect_left

n = int(input())
aa = sorted(list(map(int,input().split())))
a_max = max(aa)

half = a_max/2
p = bisect_left(aa, half)
if abs(half - aa[p]) >= abs(half - aa[p-1]):
  print(a_max,aa[p-1])  
else:
  print(a_max,aa[p])
# ########## ------ Import ------- ##########

import sys
import math
from collections import Counter
from collections import deque as deq
from functools import lru_cache

# ########## ------ Define -------- #########

INT_MAX = float("inf")
INT_MIN = float("-inf")

# ########## ------ Input Functions ---- #########

input = sys.stdin.readline


def inp():
    return(int(input()))


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


def insr():
    s = input()
    return(list(s[:len(s) - 1]))


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


# ########## ------ Code ------- ##########
def go(i):
    if i == 0:
        dp[i] = 0
        return dp[i]
    if i == 1:
        dp[i] = abs(a[0] - a[i])
        return dp[i]

    if dp[i] != -1:
        return dp[i]

    dp[i] = min(abs(a[i] - a[i - 1]) + go(i - 1),
                abs(a[i] - a[i - 2]) + go(i - 2))
    return dp[i]


t = inp()
a = inlt()
dp = [-1] * (t)

print(go(t - 1))



### FIXED CODE ###

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

dp = [0] * n
dp[1] = abs(arr[1] - arr[0])

for i in range(1, n - 1):
    dp[i + 1] = min(dp[i - 1] + abs(arr[i + 1] - arr[i - 1]), dp[i] + abs(arr[i + 1] - arr[i]))

print(dp[-1])
lis = [str(input()) for i in range(5)]

m = 10
ss = 0
for i in range(5):
      if 0 != int(lis[i][-1]) < m:
            idx = i
            m =  int(lis[i][-1])
            ss = lis[i]

for i in range(5):
      if int(lis[i][-1]) != 0:
            lis[i] = (int(lis[i])//10)*10 + 10
      else:
            lis[i] = int(lis[i])

lis[idx] = int(ss)

print(sum(lis))


### FIXED CODE ###

import math
ans = 0
min_mod = 10
for i in range(5):
      a = int(input())
      ans += math.ceil(a/10)*10
      if a % 10 != 0:
            min_mod = min(min_mod,a%10)
print(ans + min_mod - 10)
length = input()
list = list(map(int, input().split()))

for i in range(length):
  if i == (length - 1):
    print('Yes')
    break
  elif (list[i+1] - list[i]) >1 :
    list[i+1] += 1 
  elif list[i+1] >= 1 :
    continue
  elif list[i+1] < list[i]:
    print("No")
    break

### FIXED CODE ###

length = input()
a_list = list(map(int, input().split()))
 
for i in range(len(a_list)-1):
  if a_list[i] < a_list[i+1]:
    a_list[i+1] -= 1
  elif a_list[i] > a_list[i+1]:
    print("No")
    exit()
    
print('Yes')
MAX_N = 10000000+1

def make_sosu_tbl():
    for i in range(2, MAX_N):
        if sos[i]:
            for j in range(i+i, MAX_N+1, i):
                sos[j] = 0
        if i**2 >= MAX_N:break

sos = [1] * (MAX_N+1)
make_sosu_tbl()
while 1:
    n = int(input())
    if not n: break
    for i in reversed(range(13, n+1)):
        if sos[i] and sos[i-2] and sos[i-6] and sos[i-8]:
            print(i)
            break

### FIXED CODE ###

# from datetime import datetime

# measure_start = datetime.now()
move = [[[10, 10], [4, 4]], [[8, 2],[4, 2]]]

MAX_N = 10000000+1
sos = [1] * (MAX_N+1)
sos[0] = sos[1] = 0
for i in range(2, int(MAX_N**0.5)+1):
    if sos[i]:
        for j in range(i+i, MAX_N+1, i):
            sos[j] = 0

while 1:
    try:
        n = int(input())

        if not n: break
        n -= (n%2 == 0)
        while n >= 13:
            if sos[n] and sos[n-2] and sos[n-6] and sos[n-8]:
                print(n)
                break
            else:
                n -= move[sos[n-8]][sos[n-6]][sos[n-2]]
    # measure_stop = datetime.now()
    # print(measure_stop - measure_start)
    except:
        pass
s = input()
v = ["SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"]
i = 7
for w in v:
  if s != v[i]:
    i -= 1
  else:
    print(i)
    break

### FIXED CODE ###

s = input()
v = ["SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"]
i = 7
for w in v:
  if s != w:
    i -= 1
  else:
    print(i)
    break
N = int(input())
A = list(map(int, input().split()))

A.sort()
L = []
pre_val = A[0]
count = 0
for a in A:
    if pre_val == a:
        count += 1
    else:
        temp = [pre_val, count]
        L.append(temp)
        count = 1
        pre_val = a
L.append([pre_val, count])

res = 0
for i in range(len(L)):
    flag = False
    if A[i][1] != 1:
        continue
    Ai = L[i][0]
    for j in range(i):
        Aj = L[j][0]
        if Ai % Aj == 0:
            flag = True
            break
    if flag is False:
        res += 1
print(res)
N = int(input())
A = list(map(int, input().split()))

A.sort()
L = []
pre_val = A[0]
count = 0
for a in A:
    if pre_val == a:
        count += 1
    else:
        temp = [pre_val, count]
        L.append(temp)
        count = 1
        pre_val = a
L.append([pre_val, count])

res = 0
for i in range(len(L)):
    flag = False
    if A[i][1] != 1:
        continue
    Ai = L[i][0]
    for j in range(i):
        Aj = L[j][0]
        if Ai % Aj == 0:
            flag = True
            break
    if flag is False:
        res += 1
print(res)


### FIXED CODE ###

X, N = map(int, input().split())
P = list(map(int, input().split()))

min_val = -1
for i in range(-1000, 1000):
    if i in P:
        continue
    if abs(min_val - X) > abs(X - i):
        min_val = i
if len(P) == 0:
    print(X)
else:
    print(min_val)
import math

a,b = map(int,input().split())

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

print(lcm(a, b))

### FIXED CODE ###

import fractions

a,b = map(int,input().split())

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

print(lcm(a, b))
n=int(input())
for i in range(n+1):
	if int(i*1.08)==n:
  	print(i)
    exit()
print(':(')

### FIXED CODE ###

n=int(input())
for i in range(n+1):
    if int(i*1.08)==n:
        print(i)
        exit()
print(':(')
import numpy as np

h,w,k=map(int,input().split())
a=[input() for _ in range(h)]
b=[]
for i in a:
    b+=[[1 if j=="#" else 0 for j in i]]
c=np.array(b)
print(c)
ans=0
for i in range(2**(h*w)):
    for j in range(h*w):
        d=c.copy()
        if ((i>>j)&1):
            if j<=h:
                d[j]=0
            else:
                d[:,j-h]=0
        if np.sum(d)==k:
            ans+=1
print(ans)

### FIXED CODE ###

h,w,k=map(int,input().split())
a=[input() for _ in range(h)]
ans=0
for H in range(2**h):
    for W in range(2**w):
        c=0
        for i in range(h):
            for j in range(w):
                if H>>i&1 and W>>j&1 and a[i][j]=="#":
                    c+=1
        if c==k:
            ans+=1
print(ans)
W, H, N = [int(i) for i in input().split(" ")]

a1 = [0,0]
a2 = [W,0]
a3 = [0,0]
a4 = [0,H]

for i in range(0,N):
  lst = [int(i) for i in input().split(" ")]
  if lst[2] == 1:
    a1[0] = max(a1[0],lst[0])
  elif lst[2] == 2:
    a2[0] = max(a2[0],lst[0])
  elif lst[2] == 3:
    a3[1] = max(a3[1],lst[1])
  elif lst[2] == 4:
    a4[1] = max(a4[1],lst[1])

print(max(0,a2[0]-a1[0])*max(0,(a4[1]-a3[1]))


### FIXED CODE ###

W, H, N = [int(i) for i in input().split(" ")]

a1 = [0,0]
a2 = [W,0]
a3 = [0,0]
a4 = [0,H]

for i in range(0,N):
  lst = [int(i) for i in input().split(" ")]
  if lst[2] == 1 and lst[0] > a1[0]:
    a1[0] = lst[0]
  elif lst[2] == 2 and lst[0] < a2[0]:
    a2[0] = lst[0]
  elif lst[2] == 3 and lst[1] > a3[1]:
    a3[1] = lst[1]
  elif lst[2] == 4 and lst[1] < a4[1]:
    a4[1] = lst[1]

if (a2[0]-a1[0])<0 or (a4[1]-a3[1])<0:
    print(0)
else:
    print((a2[0]-a1[0])*(a4[1]-a3[1]))
def output(S,T,i,j):
  op = ""
  for k in S[:j-i]:
    if k == "?":
      op += "a"
    else:
      op += k
  op += T
  if j-i+len(T) < len(S):
    for k in S[j-i+len(T):]:
      if k == "?":
        op += "a"
      else:
        op += i
  return op


S = input()
T = input()
SS = len(S)
TT = len(T)
cand = []
if TT > SS:
  print("UNRESTORABLE")
else:
  for i,t in enumerate(T):
    for j,s in enumerate(S):
      c = 0
      if ((t == s) or (s == "?")) and (i <= j) and (TT - i <= SS - j):
        for ss, tt in zip(S[j-i:], T):
          if ss != tt and ss != "?":
            break
          else:
            c += 1
        if c == TT:
          cand.append(output(S,T,i,j))
  cand.sort()
  cand.append("UNRESTORABLE")
  print(cand[0])

### FIXED CODE ###

def output(S,T,i,j):
  op = ""
  for k in S[:j-i]:
    if k == "?":
      op += "a"
    else:
      op += k
  op += T
  if j-i+len(T) < len(S):
    for k in S[j-i+len(T):]:
      if k == "?":
        op += "a"
      else:
        op += k
  return op


S = input()
T = input()
SS = len(S)
TT = len(T)
cand = []
if TT > SS:
  print("UNRESTORABLE")
else:
  for i,t in enumerate(T):
    for j,s in enumerate(S):
      c = 0
      if ((t == s) or (s == "?")) and (i <= j) and (TT - i <= SS - j):
        for ss, tt in zip(S[j-i:], T):
          if ss != tt and ss != "?":
            break
          else:
            c += 1
        if c == TT:
          cand.append(output(S,T,i,j))
  cand.sort()
  cand.append("UNRESTORABLE")
  print(cand[0])
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    ab[a].append(b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,-1*v)
    if len(h)!=0:
        s+=-1*heapq.heappop(h)
print(s)


### FIXED CODE ###

import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    if a<=m:
        ab[a].append(b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,-1*v)
    if len(h)>0:
        s+=-1*heapq.heappop(h)
print(s)