Harryxun/stf_run huggingface dataset:
import sys
sys.stdin = open("./sample_data.txt")
input = sys.stdin.readline

######################################

from collections import deque

SA = input()
SB = input()
SC = input()

count_a = len(SA)-1
count_b = len(SB)-1
count_c = len(SC)-1

da = deque()
db = deque()
dc = deque()

for i in range(len(SA)-1):
    da.append(SA[i])
for j in range(len(SB)-1):
    db.append(SB[j])
for k in range(len(SC)-1):
    dc.append(SC[k])

turn = 0
times = count_a+count_b+count_c
for i in range(times):
    if turn == 0:
        if count_a== 0:
            print("A")
            exit()
        a = da.popleft()
        count_a -= 1
        if a == "a":
            continue
        else:
            turn = 1
            continue
    elif turn == 1:
        if count_b == 0:
            print("B")
            exit()
        b = db.popleft()
        count_b -= 1
        if b == "b":
            continue
        else:
            turn = 2
            continue
    elif turn == 2:
        if count_c == 0:
            print("C")
            exit()
        c = dc.popleft()
        count_c -=1
        if c == "c":
            continue
        else:
            turn = 0


### FIXED CODE ###

from collections import deque

SA = input()
SB = input()
SC = input()

count_a = len(SA)
count_b = len(SB)
count_c = len(SC)

da = deque()
db = deque()
dc = deque()

for i in range(len(SA)):
    da.append(SA[i])
for j in range(len(SB)):
    db.append(SB[j])
for k in range(len(SC)):
    dc.append(SC[k])

turn = 0
times = count_a+count_b+count_c
for i in range(times):
    if turn == 0:
        if count_a== 0:
            print("A")
            exit()
        a = da.popleft()
        count_a -= 1
        if a == "a":
            continue
        elif a =="b":
            turn = 1
            continue
        else:
            turn = 2
            continue
    elif turn == 1:
        if count_b == 0:
            print("B")
            exit()
        b = db.popleft()
        count_b -= 1
        if b == "b":
            continue
        elif b =="a":
            turn = 0
            continue
        else:
            turn = 2
            continue
    elif turn == 2:
        if count_c == 0:
            print("C")
            exit()
        c = dc.popleft()
        count_c -=1
        if c == "c":
            continue
        elif c == "a":
            turn = 0
            continue
        else:
            turn = 1
            continue
k = int(input())

if k % 2 == 0:
	answer = (k/2) * (K/2)
else:
	answer = (k//2) * ((k//2) + 1) 
print(int(answer))

### FIXED CODE ###

K = int(input())

if K % 2 == 0:
	answer = (K/2) * (K/2)
else:
	answer = (K//2) * ((K//2) + 1) 
print(int(answer))
a, b = input().split(' ')
c = int(a) + int(b)
if (a%3==0 and a > 3) or (b%3==0 and b>3) or (c%3==0 and c>3):
  print("Possible")
else:
  print("Impossible")

### FIXED CODE ###

a, b = map(int, input().split(" "))
if a % 3 == 0 or b % 3 == 0 or (a + b) % 3 == 0:
  print("Possible")
else:
  print("Impossible")
n = int(input())
p = list(map(int, input().split()))

j = p[0]
count = 1
for i in range(n):
  '''
    if j == 1:
        break
        '''
    if p[i] <= j:
        count += 1
        j = p[i]
print(count)

### FIXED CODE ###

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

j = p[0]
count = 0
for i in range(n):
    if j >= p[i]:
        count += 1
        j = p[i]
print(count)
num = list(map(int, input().split()))
if max(num) == sum(num.remove(max(num))): print('Yes')
else: print('No')

### FIXED CODE ###

print('Yes' if (lambda x: sum(x[:2]) == x[2])(sorted(map(int, input().split()))) else 'No')
N,A=map(int,input().split())
if A >= (N%500):
  print('Yes')
else:
  print('no')

### FIXED CODE ###

N=int(input())
A=int(input())
if A >= (N%500):
  print('Yes')
else:
  print('No')
import math
from functools import reduce

n = int(input())
a = [int(i) for i in input().split()]

def gcd(nums):
    return reduce(math.gcd, nums)

ans_l = []
for i in range(len(a)):
    aa = a[:i] + a[(i+1):]
    ans_l.append(gcd(aa))
ans = max(ans_l)
print(ans)

### FIXED CODE ###

import sys
from functools import reduce

input = sys.stdin.readline

def gcd(a,b):
    if b>a:
        a, b = b, a
    while b:
        a, b = b, a%b
    return a

n = int(input())
a = [int(i) for i in input().split()]


ans = 0
l = [0]*(n+1)
r = [0]*(n+1)
for i in range(n):
    l[i+1] = gcd(l[i], a[i])
    r[n-i-1] = gcd(r[n-i], a[n-i-1])
for i in range(n):
    ans = max(ans, gcd(l[i], r[i+1]))
print(ans)
N = int(input())
x = []
result = "No"
for i in range(1, 10):
    for j in range(i, 10):
        x.append(i*j)
print(x)
if N in x:
    result = "Yes"
print(result)

### FIXED CODE ###

a, b = map(int, input().split())
result = -1
if a in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
    if b in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
        result = a*b
print(result)
from functools import lru_cache

n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))
  
@lru_cache(maxsize=100000)
def comb(n):
  if n in a:
    return 0
  elif n in (0, 1):
    return 1
  else:
    return (comb(n-1) + comb(n-2))

print(comb(n)%(10**9 + 7))

### FIXED CODE ###

n, m = list(map(int,input().split()))
a = []
for i in range(m):
  a.append(int(input()))
c = [0] * (n+2) #combination
for i in a:
  c[i] = -1
c[0] = 1

for i in range(n):
    if c[i] < 0:
      continue
    if c[i+1] >= 0:
        c[i+1] = c[i] + c[i+1]
    if c[i+2] >= 0:
        c[i+2] = c[i] + c[i+2]
    c[i] = c[i] % 10**9+7
print(c[n]%(10**9+7))
D,T,S = input().split()
out = 'Yes' if D < T * S else 'No'
print(out)

### FIXED CODE ###

D,T,S = [int(i) for i in input().split()]
out = 'Yes' if D <= T * S else 'No'
print(out)
s = input()
ans = []
for i in range(4):
    ans.append(s[i])

ans.sort()
print('Yes' if ans[0] == ans[1] and ans[2] == ans[3] ans ans[0] != ans[2] else 'No')

### FIXED CODE ###

s = input()
ans = []
for i in range(4):
    ans.append(s[i])

ans.sort()
print('Yes' if ans[0] == ans[1] and ans[2] == ans[3] and ans[0] != ans[2] else 'No')
A,B = map(int,input().split())
S = input()

sliceA = S[0:A]
sliceB = S[A+1:A+B+1]

if sliceA.isdigit() and sliceB.isdigit() and S.find("-") == A and len(sliceA) == A and len(sliceB) == B:
    print("yes")
else:
    print("no")

### FIXED CODE ###

M = int(input())
twoDays = 48
print(twoDays - M)
s = input()
t = input()
a = int(input())
b = int(input())
u = input()

if s==u:
  print(s-1,t)
else:
  print(s,t-1)  

### FIXED CODE ###

s, t = input().split(" ")
a, b = (int(x) for x in input().split(" "))
u = input()
 
if s==u:
  print(a-1, b)
else:
  print(a, b-1)
S = input()
if S[-1] = "s"
	print( S, "es" )
else print( S, "s" )

### FIXED CODE ###

S = input()
if S[-1] == "s":
  print( S + "es" )
else: 
  print( S + "s" )
K,X=map(int,input().split())
print ('Yes' if 500 * K =< X else 'No')

### FIXED CODE ###

a = input().split()
K = int(a[0])
X = int(a[1])
if 500 * K >= X:
    print('Yes')
else:
    print('No')
N = int(input())
Alist = list(map(int, input().split()))
memo = [{} for i in range(N)]

def ddp(cur_N, ai):
    if ai in memo[cur_N]:
        return memo[cur_N][ai]
    if cur_N >=N-1:
        return ai
    aj = Alist[cur_N+1]
    ret = max((ai + ddp(cur_N+1, aj)), (-1*ai + ddp(cur_N+1, -1*aj)))
    memo[cur_N][ai] = ret
    return ret
print(ddp(0, Alist[0]))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
N = int(input())
Alist = list(map(int, input().split()))
memo = [{} for i in range(N)]

def ddp(cur_N, ai):
    if ai in memo[cur_N]:
        return memo[cur_N][ai]
    if cur_N >=N-1:
        return ai
    aj = Alist[cur_N+1]
    ret = max(ai + ddp(cur_N+1, aj), -1*ai + ddp(cur_N+1, -1*aj))
    memo[cur_N][ai] = ret
    return ret
print(ddp(0, Alist[0]))
a,b,k=map(int,input().split())

aa =[]
bb=[]
cc=[]

for i in range(1,a):
    if a % i == 0:
        aa.append(i)

for i in range(1,b):
    if a % i == 0:
        bb.append(i)

if a==1:
    aa.append(1)

if b==1:
    bb.append(1)

cc=sorted(list(set(aa) & set(bb)),reverse=True)
print(cc[k-1])

### FIXED CODE ###

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

c=[]

for i in range(1,max(a,b)+1):
    if a % i == 0 and b % i == 0:
        c.append(i)
c.sort(reverse=True)

print(c[k-1])
a, b = map(int, input().split())

# get GCD(Gratest Common Divisor: 最大公約数)
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# get divisors(公約数)
def divisors(n):
    nums = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            nums.append(i)
            if i != n // i:
                nums.append(n//i)
    return nums.sort()

# is prime(Prime Number: 素数)
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0: return False
    return True

x = divisors(gcd(a, b))

ans = 1
for _x in x:
    ans += is_prime(_x)

print(ans)


### FIXED CODE ###

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

agcd = gcd(a,b)

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)

    divisors.sort()
    return divisors

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False

    return True

x = make_divisors(agcd)
ans = 1
for _x in x:
    ans += is_prime(_x)

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

if n == k:
   for i in a:
       ans *= i
       if abs(ans) >10**9+7:
           ans = ans%(10**9+7)

elif all(i <= 0 for i in a) and k%2 ==1:
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        if abs(ans) > 10 ** 9 + 7:
            ans = ans % (10 ** 9 + 7)

else:
    am =[]
    ap =[]

    a.sort(key = abs,reverse = True)
    amax = a[:k]
    amin = a[k:]
    c=1
    if 0 in amax:
        ans = 0
    else:
        for i in amax:
            if i<0:
                am.append(i)
                c *=-1
            elif i>0:
                ap.append(i)
        if c ==1:
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)
        else:

            if min(amin)/min(ap) > max(amin)/max(am):
                amax.remove(max(am))
                amax.append(max(amin))
            else:
                amax.remove(min(ap))
                amax.append(min(amin))
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)

print(ans% (10 ** 9 + 7))

### FIXED CODE ###

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

if n == k:
   for i in a:
       ans *= i
       if abs(ans) >10**9+7:
           ans = ans%(10**9+7)

elif all(i <= 0 for i in a) and k%2 ==1:
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        if abs(ans) > 10 ** 9 + 7:
            ans = ans % (10 ** 9 + 7)

else:
    am =[]
    ap =[]

    a.sort(key = abs,reverse = True)
    amax = a[:k]
    amin = a[k:]
    c=1
    if 0 in amax:
        ans = 0
    else:
        for i in amax:
            if i<0:
                am.append(i)
                c *=-1
            elif i>0:
                ap.append(i)
        if c ==1:
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)
        else:
            if ap == []:
                amax.remove(max(am))
                amax.append(max(amin))

            elif max(am)*min(amin) < min(ap)*max(amin):
                amax.remove(max(am))
                amax.append(max(amin))
            else:
                amax.remove(min(ap))
                amax.append(min(amin))
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)

print(ans % (10 ** 9 + 7))
a,b=map(int,input().split())
res = a*b
res = int(res)
print(res)

### FIXED CODE ###

import decimal
a,b=map(str,input().split())
RES = decimal.Decimal(a)*decimal.Decimal(b)
res = int(RES)
print(res)
N, K = map(int, input().split())
if N % K == :
  print(0)
else:
  print(1)

### FIXED CODE ###

N, K = map(int, input().split())
if N % K == 0:
  print(0)
else:
  print(1)
W, H, x, y = map(int, input().split())

ans = [min(x, W - x) * H, min(y, H - y) * W]

if (x == 0 and y == 0) or (x == W and y == 0) or (x == 0 and y == H) or (x == W and y == H):
    print(W * H / 2, 0)
elif y / x == H / W:
    if x == W / 2 and y == H / 2:
        print(W * H / 2, 1)
    else:
        print(W * H / 2, 0)
else:
    print(max(ans), int(ans[0] == ans[1]))


### FIXED CODE ###

W, H, x, y = map(int, input().split())

print(W * H / 2, 1 if W / 2 == x and H / 2 == y else 0)
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  c = [[0 for i in range(a+1)] for j in range(b+1)]
  maxl = 0
  for i in range(a):
    for j in range(b):
      if X[i] == Y[j]:
        c[i][j+1] = c[i][j] + 1
      elif c[i][j+1] < c[i][j+1]:
        c[i][j+1] = c[i][j+1]
      maxl = max(maxl, c[i][j+1])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

### FIXED CODE ###

def lcs_size():
  X = raw_input()
  Y = raw_input()
  a = len(X)
  b = len(Y)
  z2 = [0 for i in range(b+1)]

  for i in range(a):
    ch = X[i]
    z1 = z2 + []
    for j in range(b):
      if ch == Y[j]:
        z2[j+1] = z1[j] + 1
      elif z2[j+1] < z2[j]:
        z2[j+1] = z2[j]

  return z2[-1]

q = input()
for k in range(q):
  print lcs_size()
W,H,x,y,z = map(int, input().split())
if (x-r >= 0 and x + r <= W) and (y-r >= 0 and y + r <= H):
                                                            print("Yes")
else:
                                                            print("No")

### FIXED CODE ###

W,H,x,y,r = map(int, input().split())
if (x-r >= 0 and x + r <= W) and (y - r >= 0 and y + r <= H):
                                                            print("Yes")
else:
                                                            print("No")
class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, idx, x):
        idx += self.n
        self.tree[idx] = x
        while idx:
            idx >>= 1
            self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        vl = vr = self.ie
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.tree[lt])
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.tree[rt], vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

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

st = SegmentTree(A, gcd, 0)
res = 1

for i in range(N):
    res = max(res, gcd(st.query(0, i), st.query(i + 1, N + 1)))

print(res)

### FIXED CODE ###

def gcd(x,y):
  if y == 0:
    return x
  else:
    return gcd(y,x%y)

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

accum_gcd = []
gcd_A = A[0]
for j in range(n):
    gcd_A = gcd(gcd_A,A[j])
    accum_gcd.append(gcd(gcd_A,A[j]))

accum_gcd_i = []
A_i = A[::-1]
gcd_A_i = A_i[0]
for j in range(n):
    gcd_A_i = gcd(gcd_A_i,A_i[j])
    accum_gcd_i.append(gcd(gcd_A_i,A_i[j]))

accum_gcd_pop = []

for j in range(n):
    if j == 0:
        accum_gcd_pop.append(accum_gcd_i[n-2])
    elif j == n-1:
        accum_gcd_pop.append(accum_gcd[n-2])
    else:
        accum_gcd_pop.append(gcd(accum_gcd[j-1],accum_gcd_i[n-j-2]))
print(max(accum_gcd_pop))
from collections import Counter
n = int(input())
v = tuple(map(int, input().split()))
c1 = Counter(v[::2])
c2 = Counter(v[1::2])
if len(set(v)) == 1:
    print(n // 2)
else:
    c1m = c1.most_common(1)
    c2m = c2.most_common(1)
    if c1m[0][0] == c2m[0][0]:
        print(min(n - c1m[0][1] - c2m[1][1], n - c1m[1][1] - c2m[0][1]))
    else:
        print(n - c1m[0][1] - c2m[0][1])


### FIXED CODE ###

from collections import Counter
n = int(input())
v = tuple(map(int, input().split()))
c1 = Counter(v[::2])
c2 = Counter(v[1::2])
if len(set(v)) == 1:
    print(n // 2)
else:
    c1m = c1.most_common(2)
    c2m = c2.most_common(2)
    if c1m[0][0] == c2m[0][0]:
        print(min(n - c1m[0][1] - c2m[1][1], n - c1m[1][1] - c2m[0][1]))
    else:
        print(n - c1m[0][1] - c2m[0][1])
a,b,c,d=list(map(int,input().split()))
print(min(a,b)+min(c,d))

### FIXED CODE ###

a,b,c,d=int(input()),int(input()),int(input()),int(input())
print(min(a,b)+min(c,d))
n=int(input())
l=int(input())
arr = ["" for x in range(n)]
for i in range(n):
    arr[i]=input()
arr.sort()
for i in range(n):
    print(arr[i],end="")

### FIXED CODE ###

N, L = map(int, input().split())
ans = ""
s = []
for i in range(N):
    s.append(input())

s.sort()
for i in range(N):
    ans += s[i]
print(ans)
n = input()
for i in range(0, n-1):
   R[i] = input()
minv = R[0]
maxv = R[1] - R[0]
for j in range(1, n-1):
   maxv = max(maxv, R[j] - minv) 
   minv = min(minv, R[j])
print maxv - minv

### FIXED CODE ###

n = input()
R = []
for i in range(0, n):
   R.append(int(raw_input()))

maxv = R[1] - R[0]
minv = R[0]

for v in range(1, n):
   if minv > R[v]:
      minv = R[v]
   elif maxv < R[v] - minv:
      maxv = R[v] - minv
print maxv
def make_divisors(n: int) -> list:
    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


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

ans = []
for i in reversed(range(N)):
    if A[i] == 1:
        ans.append(i + 1)
        divisors = make_divisors(i + 1)
        for j in divisors:
            A[j + 1] = (A[j + 1] + 1) % 2

if A.count(1) != 0:
    print(len(ans))
    for i in reversed(range(len(ans))):
        print(ans[i])
else:
    print(-1)


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
A.insert(0, 0)

ans = []
for i in reversed(range(1, N + 1)):
    if sum(A[i::i]) % 2 != A[i]:
        A[i] = (A[i] + 1) % 2
    if A[i] == 1:
        ans.append(i)

print(len(ans))
if len(ans) > 0:
    print(*ans)
import sys
from scipy.special import comb
x,y=map(int,input().split())
MOD=10**9 + 7
t=(x+y)//3
if((x+y)%3!=0 or x<t or y<t or 2*t<x or 2*t<y):
    print(0)
    sys.exit()

n=t+1
k=x-t+1
#print(n)
#print(k)
print( comb(n-1,k-1,exact=True) % MOD)


### FIXED CODE ###

import sys
MOD=(10**9) + 7
x,y=map(int,input().split())

if((x+y)%3!=0):
    print(0)
    sys.exit()

n=((x+y)//3) + 1
k=y-(n-2)

fac=[0 for _ in range(n)]   #n!
finv=[0 for _ in range(n)]  #1/n!
inv=[0 for _ in range(n)]   #

fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1

for i in range(2,n):
    fac[i]=fac[i-1]*i%MOD
    inv[i]=MOD - inv[MOD%i] * (MOD//i)%MOD
    finv[i]=finv[i-1]*inv[i]%MOD

def ncr(n,k):
    if(n < k):
        return 0
    elif(n < 0 or k < 0):
        return 0
    else:
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


print(ncr(n-1,k-1))
def main():
    H, W, M = map(int, input().split())
    bombs = [list(map(int, input().split())) for i in range(M)]
    
    if M == 1:
        return 1
    
    hw = [[0] * W for i in range(H)]
    
    for i in range(len(bombs)):
        [h, w] = bombs[i]
        hw[h - 1][w - 1] = 1
    
    wh = [list(x) for x in zip(*hw)]
    hw_tuple_list = []
    for i in range(len(hw)):
        hw_tuple_list.append((sum(hw[i]), i+1))
    
    wh_tuple_list = []
    for i in range(len(wh)):
        wh_tuple_list.append((sum(wh[i]), i+1))

    h_list = sorted(hw_tuple_list, reverse = True)
    w_list = sorted(wh_tuple_list, reverse = True)

    h_max = h_list[0][0]
    h_idx_list = []
    for i in range(len(h_list)):
        if h_max > h_list[i][0]:
            break
        h_idx_list.append(h_list[i][1])

    w_max = w_list[0][0]
    w_idx_list = []
    for i in range(len(w_list)):
        if w_max > w_list[i][0]:
            break
        w_idx_list.append(w_list[i][1])
    
    cnt = 1
    for i in range(len(h_idx_list)):
        for j in range(len(w_idx_list)):
            if hw[h_idx_list[i] - 1][w_idx_list[j] - 1] != 1:
                cnt = 0
                break
    return w_max + h_max - cnt

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

def main():
    H, W, M = map(int, input().split())
    bombs = [list(map(int, input().split())) for i in range(M)]
    
    if M == 1:
        return 1
    
    hw = [0] * H
    wh = [0] * W
    
    for i in range(len(bombs)):
        [h, w] = bombs[i]
        hw[h-1] += 1
        wh[w-1] += 1
    
    hw_tuple_list = []
    for i in range(len(hw)):
        hw_tuple_list.append((hw[i], i+1))
    
    wh_tuple_list = []
    for i in range(len(wh)):
        wh_tuple_list.append((wh[i], i+1))

    h_list = sorted(hw_tuple_list, reverse = True)
    w_list = sorted(wh_tuple_list, reverse = True)

    h_max = h_list[0][0]
    h_idx_list = []
    check_h = [0] * H
    for i in range(len(h_list)):
        if h_max > h_list[i][0]:
            break
        h_idx_list.append(h_list[i][1])
        check_h[h_list[i][1]-1] = 1

    w_max = w_list[0][0]
    w_idx_list = []
    check_w = [0] * W
    for i in range(len(w_list)):
        if w_max > w_list[i][0]:
            break
        w_idx_list.append(w_list[i][1])
        check_w[w_list[i][1]-1] = 1
    
    cnt = 0
    for [h, w] in bombs:
        if check_h[h-1] == 1 and check_w[w-1] == 1:
            cnt += 1
    return h_max + w_max if cnt != len(h_idx_list) * len(w_idx_list) else h_max + w_max - 1

if __name__ == '__main__':
    print(main())
input()
S=input()
K=int(input())
for s in S:
  if s=!S[k-1]:
    s
  else:
    '*'
print(S)

### FIXED CODE ###

input()
S=input()
k=int(input())
for s in S:
  print(s if s==S[k-1] else "*",end="")
from scipy.special import perm, comb
N, K = map(int, input().split())
mod = 10**9 + 7

Atable = [0] * (K + 1)
for i in range(1, K + 1):
    Atable[i] = comb(K - 1, i - 1)
Btable = [0] * (K + 1)
for i in range(1, K + 1):
    Btable[i] = comb(N - K + 1, i)

for i in range(1, K + 1):
    print(int(((Atable[i] % mod) * (Btable[i] % mod)) % mod))

### FIXED CODE ###

N, K = map(int, input().split())
mod = 10**9 + 7

factorial = [1]
inverse = [1]

for i in range(1, N + 2):
    factorial.append(factorial[i - 1] * i % mod)
    inverse.append(pow(factorial[i], mod - 2, mod))


def C(n, r):
    if n < r:
        return 0
    return (factorial[n] * inverse[r] * inverse[n - r]) % mod


Atable = [0] * (K + 1)
for i in range(1, K + 1):
    Atable[i] = C(K - 1, i - 1)
Btable = [0] * (K + 1)
for i in range(1, K + 1):
    Btable[i] = C(N - K + 1, i)

for i in range(1, K + 1):
    print(int(((Atable[i] % mod) * (Btable[i] % mod)) % mod))
x, y = map(int,input().split())

if x % 3 == 0 :
  print (0)
elif y % 3 == 0 :
  print (0)
else :
  if y > x :
    z = y
    y = x
    x = z

  a = int(x / 3) + 1
  if y % 2 == 0 :
    a = a - 1
    s = a * y
    #print (s)

    t = int((x - a) * y / 2)
    #print (t)
    if t > s :
      print (t - s)
    else
      print (s - t)
  else :
    s = a * y
    #print (s)

    x = x - a
  
    if y > x :
      z = y
      y = x
      x = z
  
    b = int(x / 2)
    t = b * y
    #print (t)

    print (s - t)

### FIXED CODE ###


def abc_3() :
	H, W = map(int, input().split())
	print (min(div_3(H, W), div_3(W, H), div_s(H, W), div_s(W, H)))

def div_3(H, W) :
	w = W //3
	if w == 0 :
		return 10000000000
	if W % 3 == 0 :
		return 0
	else :
		return H

def div_s(H, W) :
	min_diff = 10000000000
	for w in range(1, W) :
		s1 = w * H
		s2 = (W - w) * (H // 2)
		s3 = W * H - s2 - s1
		diff = max(s1, s2, s3) - min(s1, s2, s3)
		if diff < min_diff :
			min_diff = diff
	return min_diff

#for i in range(5) :
#	abc_3()
#	print ('input:', end = '')
#	if input() == 'q' :
#		break

abc_3()