Harryxun/stf_run huggingface dataset:
from heapq import heappop,heappush

def main():
    N,M,S=map(int,input().split())
    G=[[] for _ in range(N)]
    for i in range(M):
        U,V,A,B=map(int,input().split())
        G[U-1].append([V-1,A,B])
        G[V-1].append([U-1,A,B])
    C=[]
    D=[]
    for _ in range(N):
        c,d=map(int,input().split())
        C.append(c)
        D.append(d)

    MaxMoney=2500

    dp=[[float('inf') for __ in range(MaxMoney+1)] for _ in range(N)]

    cost=0
    money=S
    que=[]
    heappush(que,(cost,0,money)) #cost,node,money
    dp[0][money] = 0

    while len(que)>0:
        cost,node,money=heappop(que)

        stop_money=min(money+C[node],MaxMoney)
        stop_cost=cost+D[node]
        if stop_cost<dp[node][stop_money]:
            dp[node][stop_money]=stop_cost
            heappush(que,(stop_cost,node,stop_money))

        for to_node,to_money,to_cost in G[node]:
            money_=min(money-to_money,MaxMoney)
            if money_<0:
                continue
            cost_=cost+to_cost
            if dp[to_node][money_]<=cost_:
                continue

            dp[to_node][money_]=cost_
            heappush(que,(cost_,to_node,money_))

    for i in range(1,N):
        print(min(dp[i]))




if __name__=="__main__":
    main()

### FIXED CODE ###

from heapq import heappop,heappush

def main():
    N,M,S=map(int,input().split())
    G=[[] for _ in range(N)]
    for i in range(M):
        U,V,A,B=map(int,input().split())
        G[U-1].append([V-1,A,B])
        G[V-1].append([U-1,A,B])
    C=[]
    D=[]
    for _ in range(N):
        c,d=map(int,input().split())
        C.append(c)
        D.append(d)

    MaxMoney=2500

    dp=[[float('inf') for __ in range(MaxMoney+1)] for _ in range(N)]

    cost=0
    money=min(S,MaxMoney)
    que=[]
    heappush(que,(cost,0,money)) #cost,node,money
    dp[0][money] = 0

    while len(que)>0:
        cost,node,money=heappop(que)

        stop_money=min(money+C[node],MaxMoney)
        stop_cost=cost+D[node]
        if stop_cost<dp[node][stop_money]:
            dp[node][stop_money]=stop_cost
            heappush(que,(stop_cost,node,stop_money))

        for to_node,to_money,to_cost in G[node]:
            money_=min(money-to_money,MaxMoney)
            if money_<0:
                continue
            cost_=cost+to_cost
            if dp[to_node][money_]<=cost_:
                continue

            dp[to_node][money_]=cost_
            heappush(que,(cost_,to_node,money_))

    for i in range(1,N):
        print(min(dp[i]))




if __name__=="__main__":
    main()
n = int(input())
a = list(map(int, input().split()))
ma = -100000000
mi = 100000000
for i in range(n):
    if a[i] > ma:
        ma = a[i]
        ma_index = i
    if a[i] < mi:
        mi = a[i]
        mi_index = i
ans = []
if ma >= -mi:
    for i in range(n):
        ans.append((ma_index,i))
    for i in range(n-1):
        ans.append((i,i+1))
else:
    for i in range(n):
        ans.appen((mi_index,i))
    for i in range(n-1):
        ans.append((n-1-i,n-2-i))
print(len(ans))
for x in ans:
    print(x[0]+1,x[1]+1)

### FIXED CODE ###

# coding: utf-8
import sys


def solve(a, begin, end, queue, cnt):
    #print(begin, end)
    if begin >= end:
        return
    maxx = sorted(list(map(abs, a[begin:end + 1])), reverse=True)[0]
    # print(maxx)
    if maxx in a[begin:end + 1]:
        m = a[begin:end + 1].index(maxx) + begin
    else:
        m = a[begin:end + 1].index(-1 * maxx) + begin
        maxx = -1 * maxx
    #print(m, maxx)
    if maxx == 0:
        return []
    if maxx > 0:
        solve(a, begin, m - 1, queue, cnt + 1)
        for i in range(max(0, m - 1), end):
            if a[i + 1] >= a[i]:
                continue
            else:
                a[i + 1] += a[i]
                queue.append((i, i + 1))
                if a[i + 1] < a[i]:
                    a[i + 1] += a[i]
                    queue.append((i, i + 1))
        return queue
    if maxx < 0:
        solve(a, m + 1, end, queue, cnt + 1)
        for i in reversed(range(begin, min(len(a) - 1, m + 1))):
            if a[i] <= a[i + 1]:
                continue
            else:
                a[i] += a[i + 1]
                queue.append((i + 1, i))
                if a[i] > a[i + 1]:
                    a[i] += a[i + 1]
                    queue.append((i + 1, i))
        return queue


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    queue = solve(a, 0, len(a) - 1, [], 0)
    print(len(queue))
    for i in range(len(queue)):
        print(queue[i][0] + 1, queue[i][1] + 1)
package main

import (
	"fmt"
	"math"
	"sort"
)

func main() {
	var X, N int
	fmt.Scanf("%d", &X)
	fmt.Scanf("%d", &N)

	P := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scanf("%d", &P[i])
	}
	sort.Ints(P)
	fmt.Println(P)

	var a int = -1
	if len(P) > 0 {
		for p := 0; p < 102; p++ {
			if math.Abs(float64(X) - float64(p)) < math.Abs(float64(X) - float64(a)) && !Contain(P, p) {
				a = p
			}
		}
	} else {
		a = X
	}
	fmt.Println(a)
}

func Contain(s []int, e int) bool {
	for _, v := range s {
		if e == v {
			return true
		}
	}
	return false
}


### FIXED CODE ###

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

a = -1
if len(P) > 0:
    for p in range(0, 102):
        if abs(X - p) < abs(X - a) and (p not in P):
            a = p
else:
    a = X

print(a)
a,v,b,w,t=int(input().split())
 
if a<b:
  if b+wt<=a+vt:
    print('YES')
  else:
    print('NO')
if a>b:
  if a-vt<=b-wt:
    print('YES')
  else:
    print('NO')

### FIXED CODE ###

a,v=map(int, input().split())
b,w=map(int, input().split())
t=int(input())
 
if a<b:
  if b+w*t<=a+v*t:
    print('YES')
  else:
    print('NO')
if a>b:
  if a-v*t<=b-w*t:
    print('YES')
  else:
    print('NO')
a, b, h, m = map(int, input().split())
import math
vx = 2*math.pi/(12*60)
vy = 2*math.pi/60

x = vx*(60*h+m)
y = vy*m

d = abs(x-y)
z = a**2+b**2-2*a*b*math.cos(d)
z = math.sqrt(z)
print(zf)


### FIXED CODE ###

a, b, h, m = map(int, input().split())
import math
vx = 2*math.pi/(12*60)
vy = 2*math.pi/60

x = vx*(60*h+m)
y = vy*m

d = abs(x-y)
z = a**2+b**2-2*a*b*math.cos(d)
z = math.sqrt(z)
print(z)
N = int(input())
H = list(map(int, input().split()))
max_count = 0
for i in range(N):
  tmp_count = 0
  for j in range(1, N-i):
  	if H[j-1] <= H[j]:
      tmp_count+=1
  if tmp_count > max_count:
    max_count = tmp_count
print(max_count)

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
tmp = 0
s = 0
for i in range(N-1):
  if H[i] >= H[i+1]:
    tmp += 1
    s = max(s, tmp)
  else:
    tmp = 0
    
print(s)
import math
from functools import reduce
k=10**6+1
def judge(n,a):
  c=[0]**k
  for x in a:
    c[x]=+1
  t=any(sum(c[i::i])>1 for i in range(2,k))
  t+=reduce(gcd,a)>1
  return ['pairwise','setwise','not'][t]+' coprime'
n=int(input())
a=list(map(int,input().split()))
print(judge(n,a))

### FIXED CODE ###

from math import gcd
from functools import reduce
NUM_MAX = 10**6 + 1
def solve(n, a):
    c = [0] * NUM_MAX
    for x in a:
        c[x] += 1
    t = any(sum(c[i::i]) > 1 for i in range(2, NUM_MAX))
    t += reduce(gcd, a) > 1
    return ["pairwise", "setwise", "not"][t] + " coprime"

n = int(input())
a = list(map(int, input().split()))
print(solve(n, a))
# -*- coding: utf-8 -*-


class Node():
    def __init__(self, loc=None, left=None, right=None):
        self.loc = loc
        self.l = left
        self.r = right

class Point():
    def __init__(self, id, xy):
        self.id = int(id)
        self.x = int(xy[0])
        self.y = int(xy[1])

if __name__ == '__main__':

    n = int(input())
    P = [Point(i, input().split(" ")) for i in range(n)]
    q = int(input())
    Q = [list(map(int, input().split(" "))) for _ in range(q)]
    T = [None] * n

    def make2DTree(l, r, depth):
        global np
        #if l >= r:
        #    return None

        mid = (l + r) // 2
        t = np
        np += 1
        if depth % 2 == 0:
            P[l:r] = sorted(P[l:r], key=lambda p: p.x)
        else:
            P[l:r] = sorted(P[l:r], key=lambda p: p.y)

        T[t] = Node(loc=mid)
        T[t].l = make2DTree(l, mid, depth + 1)
        T[t].r = make2DTree(mid + 1, r, depth + 1)

        return t

    def find(v, sx, tx, sy, ty, depth, ans):
        x = P[T[v].loc].x
        y = P[T[v].loc].y

        if (sx <= x <= tx) and (sy <= y <= ty):
            ans.append(P[T[v].loc].id)

        if depth % 2 == 0:
            if T[v].l is not None and sx <= x:
                find(T[v].l, sx, tx, sy, ty, depth + 1, ans)
            if T[v].r is not None and x <= tx:
                find(T[v].r, sx, tx, sy, ty, depth + 1, ans)

        else:
            if T[v].l is not None and sy <= y:
                find(T[v].l, sx, tx, sy, ty, depth + 1, ans)
            if T[v].r is not None and y <= ty:
                find(T[v].r, sx, tx, sy, ty, depth + 1, ans)

    np = 0
    root = make2DTree(0, n, 0)

    for sx, tx, sy, ty in Q:
        ans = []
        find(root, sx, tx, sy, ty, 0, ans)
        ans.sort()
        if ans:
            print("\n".join(map(str, ans)))
        print("")



### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right

if __name__ == '__main__':

    P = [tuple(map(int, input().split())) + (i,)
         for i in range(int(input()))]  # (x,y,i)
    P.sort()
    root = int(math.sqrt(len(P)))
    low = [x for x, y, i in P[::root]]
    high = [x for x, y, i in P[root - 1::root]] + [float('inf')]

    # disjoint subsets (ordered by y) of P
    P = [sorted(P[i:i + root], key=itemgetter(1))
         for i in range(0, len(P), root)]
    P = [([y for x, y, i in Pi], Pi)
         for Pi in P]  # ([y in subsets], [subsets])
    q = int(input())
    Q = [list(map(int, input().split(" "))) for _ in range(q)]

    for sx, tx, sy, ty in Q:
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = P[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <= tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str, ret)))
        print()
alf = ['A','B','C','D','E','F']
a,b = map(str,input().split())
if alf.index(a)<alf.index(b):
  print('<')
elif alf.index(a)=alf.index(b):
  print('=')
else:
  print('>')


### FIXED CODE ###

alf = ['A','B','C','D','E','F']
a,b = input().split()
if alf.index(a)<alf.index(b):
  print('<')
elif alf.index(a)==alf.index(b):
  print('=')
else:
  print('>')
# -*- coding:utf-8 -*-

n = int(input())
h = input().split()
count = 0
flag = 0

for i in range(n):
    #print(i)
    for j in range(i):
        if h[i] < h[i-1-j]:
            #print("{} {}".format(h[i-j], h[i]))
            flag = 1
            break
    if flag == 0:
        count += 1
    else:
        flag = 0

print(count)

### FIXED CODE ###

# -*- coding:utf-8 -*-

a, b =  map(int, input().split())
#print("{} {}".format(a, b))
point = 0
for i in range(2):
    if a >= b:
        point += a
        a -= 1
    else:
        point += b
        b -= 1
print(point)
a, b, n = map(int, input().split())
ans = 0
if b > n:
    ans = (a*n)//b
else:
    c = n//b
    max_c = [0]*(c+1)
    for i in range(1, c):
        max_c[i] = (a * (b*(i+1) - 1))//b - i
    max_c[c] = (a*n)//b - c
    print(max(max_c))

### FIXED CODE ###

a, b, n = map(int, input().split())
ans1 = (a*min(n, b-1))//b
ans2 = a*(min(n, b-1)//b)
print(ans1-ans2)
from copy import copy
n = int(input())
a = list(map(int, input().split()))

ok, ng = n, 0
while ok-ng > 1:
	x = (ok+ng)//2
	#d = defaultdict(int)
	d = dict()
	last = 0
	valid = True
	if x == 1:
		for i in range(n-1):
			if a[i] >= a[i+1]:
				valid = False
				break
		if valid:
			ok = x
		else:
			ng = x
		continue

	for i in range(n-1):
		if a[i] < a[i+1]:
			last = a[i+1]
		elif a[i] > a[i+1]:
			dels = []
			for k in d.keys():
				if k > last:
					dels.append(k)
			if a[i+1] > last:
				d[a[i+1]] = 1
			else:
				j = a[i+1]
				while j in d:
					if d[j] != x-1 or j <= 0:
						break
					else:
						dels,append(j)
						j -= 1
				if j in d:
					d[j] += 1
				else:
					d[j] = 1
			last = a[i+1]
		elif a[i] == a[i+1]:
			dels = []
			for k in d.keys():
				if k > last:
					dels.append(k)
			j = a[i+1]
			while j in d:
				if d[j] != x-1 or j <= 0:
					break
				else:
					dels.append(j)
					j -= 1
			if j in d:
				d[j] += 1
			else:
				d[j] = 1
			last = a[i+1]

		for k in dels:
			del d[k]

		if 0 in d:
			valid = False
			break

	if valid:
		ok = x
	else:
		ng = x
print(ok)

### FIXED CODE ###

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

ok, ng = n, 0
while ok-ng > 1:
	x = (ok+ng)//2
	#d = defaultdict(int)
	d = dict()
	last = 0
	valid = True
	if x == 1:
		for i in range(n-1):
			if a[i] >= a[i+1]:
				valid = False
				break
		if valid:
			ok = x
		else:
			ng = x
		continue

	for i in range(n-1):
		dels = []
		if a[i] < a[i+1]:
			last = a[i+1]
			continue

		j = a[i+1]
		for k in d.keys():
			if j < k:
				dels.append(k)

		while j > 0:
			if j in d and d[j] == x-1:
				#d[j] = 0
				dels.append(j)
				j -= 1
			else:
				break

		if j in d:
			d[j] += 1
		else:
			d[j] = 1

		for k in dels:
			del d[k]

		if 0 in d:
			valid = False
			break
		last = j

	if valid:
		ok = x
	else:
		ng = x
print(ok)
"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    import sys
    sys.setrecursionlimit(2000000)
    input = sys.stdin.readline
    N = int(input())
    AB = [{}for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = map(int,input().split())
        AB[a][b] = c
        AB[b][a] = c

    Q,K = map(int,input().split())

    path = {K:""}
    dp = [0]*(N+1)
    def dfs(n,cost):
        path[n]=""
        dp[n]=cost
        for i,c in AB[n].items():
            if i not in path:
                nextcost = (cost+c)%mod
                dfs(i,nextcost)
    dfs(K,0)
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()

### FIXED CODE ###

"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(20000000)
    input = sys.stdin.readline
    N = int(input())
    AB = [[]for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = map(int,input().split())
        AB[a].append((b,c))
        AB[b].append((a,c))

    Q,K = map(int,input().split())

    path = {K:""}
    dp = [0]*(N+1)
    que = deque()
    for n,c in AB[K]:
        que.append((n,c))
    while que:
        now,cost = que.pop()
        path[now]=""
        dp[now]=cost
        for n,c in AB[now]:
            if n not in path:
                que.append((n,cost+c))
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()
a = input().split(" ")
a[0] = int(a[0])
a[1] = int(a[1])
a[2] = int(a[2])
if a[0] > 0 and a[1] > 0:
  print("0 0")
  return
else:
  if a[2] > a[0]:
    a[0] = 0
  a[2] = a[2] - a
  if a[2] > a[1]:
    a[1] = 0
  else: 
    a[1] = a[1] - a[2]
print(str(a[0]) + " " + str(a[1]))

### FIXED CODE ###

a,b,k = map(int, input().split())
x = 0 if k > a else a - k
y = b if (k - a) <= 0 else (0 if (k - a) > b else b - (k - a))
print("{} {}".format(x,y))
# -*- coding: utf-8 -*-


a = [e for e in input().split()]
l = []
i = 0


for x in a:

    if x not in ['+', '-', '*']:
        x = int(x)
        l.append(x)
    else:
        a = l.pop(i)
        b = l.pop(i)

        if x == '+':
            l.append(a + b)
        elif x == '-':
            l.append(a - b)
        elif x == '*':
            l.append(a * b)

        i += 1


print(sum(l))

### FIXED CODE ###

# -*- coding: utf-8 -*-


a = [e for e in input().split()]
# a = ['1', '2', '+', '3', '4','-', '*']
# a = ['1', '2', '+']
l = []


for x in a:

    if x not in ['+', '-', '*']:
        x = int(x)
        l.append(x)
    else:
        a = l.pop()
        b = l.pop()

        if x == '+':
            l.append(b + a)
        elif x == '-':
            l.append(b - a)
        elif x == '*':
            l.append(b * a)


print(sum(l))
x = int(input())
if x == 1:
  print(0)
else if x == 0:
  print(1)

### FIXED CODE ###

x = int(input())
if x == 1:
  print(0)
else:
  print(1)
import numpy as np

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

a = a / sum(a)
a = (a >= 1/(4*m))
if sum(a)>=m:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import numpy as np

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

a = a / sum(a)
a = (a >= 1/(4*m))
if sum(a)>=m:
    print('Yes')
else:
    print('No')
print(B if A >=13 else B//2 if 6 <= A <= 12 else 0)

### FIXED CODE ###

A,B = map(int, input().split())
print(B if A >=13 else B//2 if 6 <= A <= 12 else 0)
n = int(input())
a_list = list(map(int, input().split()))

co = a_list.copy()
co.sort()
if 0 in co or len(co) % 2 == 1:
    co.remove(0)
else:
    print(0)
    quit()


for index in range(len(a_list)[::2]):
    if not a_list[index] == a_list[index + 1]:
        print(0)
        quit()




print(int(pow(2, floor(n / 2))) % (pow(10,9) + 7))

### FIXED CODE ###

from math import factorial, floor
n = int(input())
a_list = list(map(int, input().split()))

co = a_list.copy()
if 0 in co:
    co.remove(0)
co.sort()


if not len(co) % 2 == 0:
    print(0)
    quit()

for index in range(len(a_list))[:-1:2]:
    if not co[index] == co[index + 1]:
        print(0)
        quit()


print(int(pow(2, floor(n / 2))) % (pow(10,9) + 7))
import math
def beautiful:
     a, b, c = input().split()
     d = math.fabs(b-a)
     e = math.fabs(c-b)
      if  d == e:
            print('YES')
      else:
            print('NO')

beautiful()

### FIXED CODE ###

a,b,c=map(int,input().split())
if b-a == c-b:
    print("YES")
else:
    print("NO")
while True:
    i = int(input())
    break if i == 0 else print('Case i: {0}'.format(i))
    

### FIXED CODE ###

i = 0
while True:
    i += 1
    x = int(input())
    if x == 0:
        break
    else:
        print('Case {0}: {1}'.format(i, x))
z = 0

b = [1]
for i in range(1000000):
  j = [a[b[i]-1]]
  b.extend(j)

for i in range(n):
  if b.count(i+1)>=3:
    z = z + 1

if k <= n:
  y = b[k]
else:
  l = (k-n)%z
  y = b[n+l]
print(y)

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
z = 0
b = [1]
c = [0]*n
for i in range(n*3):
  j = [a[b[i]-1]]
  b.extend(j)
  c[a[b[i]-1]-1] = c[a[b[i]-1]-1]+1
  if c[a[b[i]-1]-1] == 2:
    z = z + 1
if k <= n:
  y = b[k]
else:
  l = (k-n)%z
  y = b[n+l]
print(y)
a,b=map(int,input())
if a>8 or b>8:
    print(":(")
else:
    print("Yay!")

### FIXED CODE ###

a,b=map(int,input().split())
if a>8 or b>8:
    print(":(")
else:
    print("Yay!")
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

if N == 1:
    print(max(A[0], BC[0][1]))
    quit()

heapq.heapify(A)
for b, c in BC:
    a = A[0]
    if a >= c:
        continue
    else:
        curPopped = 0
        while curPopped < b:
            a = heapq.heappop(A)
            if a >= c:
                heapq.heappush(A, a)
                break
            curPopped += 1
        for i in range(curPopped):
            heapq.heappush(A, c)

print(sum(A))

### FIXED CODE ###

N, M, K = map(int, input().split())

mod = 10**9 + 7
table = [1]
for i in range(N*M):
    table.append(table[-1] * (i+1) % mod)


def inv(N):
    return pow(N, mod-2, mod)  # Why mod?


def cmb(n, r):
    return table[n] * inv(table[n-r]*table[r]) % mod


print((M ** 2 * (N ** 3 - N) + N ** 2 * (M ** 3 - M)) // 6 * cmb(M * N - 2, K - 2) % mod)
def main():
    N, M = map(int, input().split())
    H_list = [int(_) for _ in input().split()]

    # iso_list = []
    index_list = []
    for m in range(M):
        A, B = map(int, input().split())
        if H_list[A-1] > H_list[B-1]:
            index_list.append(B-1)
        elif H_list[A-1] < H_list[B-1]:
            index_list.append(A-1)
        elif H_list[A-1] < H_list[B-1]:
            index_list.append(A-1)
            index_list.append(B-1)
        # iso_list.append(A)
        # iso_list.append(B)        

    index_list = list(set(index_list))
    for i in index_list:
        del H_list[i]        

    # iso_list = list(set(iso_list))
    # iso_list = len(H_list - iso_list)
    
    # out = iso_list + 
    out = len(H_list)
    print(out)
main()

### FIXED CODE ###

N, M = map(int, input().split())
H = [0] + list(map(int, input().split()))
O = [0] + [1] * N
for _ in range(M):
    A, B = map(int, input().split())
    if H[A] <= H[B]:
        O[A] = 0
    if H[A] >= H[B]:
        O[B] = 0
print(sum(O))
print((H+W)/2)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# B

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

h,w = map(int, input().split())
if h == 1 or w == 1:
    print(1)
elif (h%2==1) and (w%2==1):
    print(int((h * w // 2)+1))
else:
    print(int(h*w/2))
N = int(input())
V = list(map(int, input().split()))
alist = []
tmp = 0

def cook(N, V, alist):
    if N = 1:
        print(V[0])
    
    else:
        V.sort()
        for i in range(0, N - 2, 2):
            if i + 1 > N - 1:
                alist.append(V[i])
                
            else:
                tmp = (V[i] + V[i +1]) / 2
            alist.append(tmp)
            
        N = len(alist)
        V = alist
        alist = []
        cook(N, V, alist)
        
cook(N, V, alist)

### FIXED CODE ###

N = int(input())
v = list(map(float, input().split()))

v.sort()

r = v[0]

for i in v[1::]:
    r = (r + i) / 2

print(r)
X, Y = map(int, input().split(" "))
print("<" if X < Y else "=" if X == Y else ">")


### FIXED CODE ###

X, Y = input().split(" ")
print("<" if X < Y else "=" if X == Y else ">")
n = int(input())
x=[]
y=[]
h=[]
for i in range(0,n):
    a,b,c = map(int,input().split())
    x.append(a)
    y.append(b)
    h.append(c)



for i in range(0,101):
    for j in range(0,101):
        tmph=0
        flag = True
        for k in range(0,n):
            if tmph == 0 and h[k] != 0:
                tmph=abs(x[0]-i)+abs(y[0]-j)+h[0]
            calch = abs(x[k]-i)+abs(y[k]-j)+h[k]
            if tmph != calch:
                flag = False
                break
        if flag == False:
            continue
        else:
            ansx=i
            ansy=j
            ansh=tmph

print(ansx,ansy,ansh)




### FIXED CODE ###

n = int(input())
x=[]
y=[]
h=[]
for i in range(0,n):
    a,b,c = map(int,input().split())
    x.append(a)
    y.append(b)
    h.append(c)
 
 
 
for i in range(0,101):
    for j in range(0,101):
        tmph=0
        flag = True
        for k in range(0,n):
            if tmph == 0 and h[k] != 0:
                tmph=abs(x[k]-i)+abs(y[k]-j)+h[k]
                break
        for k in range(0,n):
            calch = tmph - abs(x[k]-i)-abs(y[k]-j)
            if h[k] != max(calch,0):
                flag = False
                break
        if flag == False:
            continue
        elif tmph == 0:
            flag2 = True
            for c in range(0,101):
                if i == x[c] and j == y[c]:
                    flag2 = False
                    break
            if flag2:
                ansx = i
                ansy = j
                ansh = 1
        else:
            ansx=i
            ansy=j
            ansh=tmph
 
print(ansx,ansy,ansh)
from math import atan,degrees
a,b,x=map(int,input().split())
aab2 = a * a * b /2
if x >= aab2:
  print(90-degrees(atan(a/(b-2 *(x-aab2)/(a*a)))))
else:
  print(90-degrees(atan((2*x/(a*b)/b))))

### FIXED CODE ###

from math import atan,degrees
a,b,x=map(int,input().split())
aab2 = a * a * b /2
if a*a*b==x:
  print(0)
elif x >= aab2:
  print(90-degrees(atan(a/(b-2 *(x-aab2)/(a*a)))))
else:
  print(90-degrees(atan((2*x/(a*b)/b))))