Harryxun/stf_run huggingface dataset:
import sys
import itertools

dataset_num = int(input())

class Overflow(Exception):
    pass

for _ in range(dataset_num):
    try:
        k1 = input()
        k2 = input()
        k1_val = [0] * 80
        k2_val = [0] * 80

        if len(k1) > 80 or len(k2) > 80:
            raise Overflow()
        
        for i, x in enumerate(reversed(k1)):
            k1_val[i] = int(x)

        for i, x in enumerate(reversed(k2)):
            k2_val[i] = int(x)
        
        res = [0] * 80
        for i in range(0, 80):
            res[i] += k1_val[i] + k2_val[i]
            if res[i] >= 10:
                res[i+1] += 1
                res[i] -= 10
        sumstr = "".join([str(x) for x in itertools.dropwhile(lambda x: x == 0, reversed(res))])
        if len(sumstr) > 80:
            raise Overflow()

        print(sumstr)
    except Overflow:
        print("overflow")

### FIXED CODE ###

import sys
import itertools

dataset_num = int(input())

class Overflow(Exception):
    pass

for _ in range(dataset_num):
    try:
        k1 = input()
        k2 = input()
        k1_val = [0] * 100
        k2_val = [0] * 100

        if len(k1) > 80 or len(k2) > 80:
            raise Overflow()
        
        for i, x in enumerate(reversed(k1)):
            k1_val[i] = int(x)

        for i, x in enumerate(reversed(k2)):
            k2_val[i] = int(x)
        
        res = [0] * 100 
        for i in range(0, 100):
            res[i] += k1_val[i] + k2_val[i]
            if res[i] >= 10:
                res[i+1] += 1
                res[i] -= 10
        sumstr = "".join([str(x) for x in itertools.dropwhile(lambda x: x == 0, reversed(res))])
        if len(sumstr) > 80:
            raise Overflow()
        if len(sumstr) == 0:
            sumstr = "0"

        print(sumstr)
    except Overflow:
        print("overflow")
import numpy as np

def prod(p, q, r):
    return A[p] + B[q] + C[r]

x, y, z, k = [int(a) for a in input().split()]
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
C = [int(a) for a in input().split()]

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

progress = [(0, 0, 0, prod(0,0,0))]


def expand(p, q, r):
    result = []
    if p + 1 < x:
        result.append((p+1, q, r, prod(p+1, q, r)))
    if q + 1 < y:
        result.append((p, q+1, r, prod(p, q+1, r)))
    if r + 1 < z:
        result.append((p, q, r+1, prod(p, q, r+1)))
    return result

for i in range(k):
    prods = [tup[-1] for tup in progress]

    max_val = max(prods)
    max_idx = prods.index(max_val)
    p, q, r, _ = progress[max_idx]

    print(max_val)
    progress.pop(max_idx)
    progress.extend(expand(p, q, r))
    progress = list(set(progress))


### FIXED CODE ###

a = int(input())
b = input()
c = input()
d = input()
e = int(input())
k = int(input())

if e - a > k:
  print(':(')
else:
  print('Yay!')
I = lambda s:map(int, s)

p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(I(s), 1) if x % p == 0)
else:
  d = [1] + [0] * 9
  t, y = 0, 1
  for i, x in enumerate(I(reversed(s)), 1):
    t = (t + x * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)


### FIXED CODE ###

from itertools import accumulate
from collections import Counter

p = int(input().split()[1])
a = list(map(int, input()))
if 10 % p == 0:
  r = sum(i for i, x in enumerate(a, 1) if x % p == 0)
else:
  a = accumulate(x * pow(10, i, p) for i, x in enumerate(reversed(a), 1))
  c = Counter(x % p for x in a) 
  c[0] += 1
  r = sum(i * (i - 1) // 2 for i in c.values())
print(r)
s=input()
k=int(input())
n=0
for i in s:
    if int(i)==1:
        n+=1
    else:
        break
if n < k:
    pritn(s[n])
else:
    print(1)

### FIXED CODE ###

s=input()
k=int(input())
n=0
for i in s:
    if int(i)==1:
        n+=1
    else:
        break
if n < k:
    print(s[n])
else:
    print(1)
n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(n):
    if i+1==p[i]:
        p[i],p[i+1]=p[i+1],p[i]
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(n):
    if i+1==p[i]:
        if i+1==n:
            p[i],p[i-1]=p[i-1],p[i]
        else:
            p[i],p[i+1]=p[i+1],p[i]
        ans+=1
print(ans)
N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
B = [[int(i) for i in input().split()] for Q in range(Q)]

p = [0]*100000
for i in range(N):
    p[A[i]] += 1

for i in range(Q):
    p[B[i][1]] += p[B[i][0]]
    p[B[i][0]] = 0

    cnt = 0
    for j in range(100000):
        cnt += p[j]*j
    print(cnt)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
B = [[int(i) for i in input().split()] for Q in range(Q)]

p = [0]*100001
for i in range(N):
    p[A[i]] += 1

cnt = 0
for j in range(100001):
    cnt += p[j]*j

for i in range(Q):
    cnt = cnt + (B[i][1]- B[i][0]) * p[B[i][0]]

    p[B[i][1]] += p[B[i][0]]
    p[B[i][0]] = 0

    print(cnt)
N,M=map(int, input().split())
A=[list(map(int, input().split())) for i in range(M)]
G=[[]for i in range(N)]
for a,b in A:
  G[a-1].append(b-1)
def chmax(a,b):
  if a>=b:
    return a
  else:
    return b
dp=[-1]*N
def rec(v):
  if dp[v]!=-1:
    return dp[v]
  ans=0
  for i in G[v]:
    ans=chmax(ans,rec(i)+1)
  dp[v]=ans
  return dp[v]
    
ans=0
for i in range(N):
  ans=chmax(ans,rec(i))
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5+10)
input=sys.stdin.readline

N,M=map(int, input().split())
A=[list(map(int, input().split())) for i in range(M)]
G=[[]for i in range(N)]
for a,b in A:
  G[a-1].append(b-1)
def chmax(a,b):
  if a>=b:
    return a
  else:
    return b
dp=[-1]*N
def rec(v):
  if dp[v]!=-1:
    return dp[v]
  ans=0
  for i in G[v]:
    ans=chmax(ans,rec(i)+1)
  dp[v]=ans
  return dp[v]
    
ans=0
for i in range(N):
  ans=chmax(ans,rec(i))
print(ans)
a = int(input())
b = input()

print(b.count('ABC'))

### FIXED CODE ###

k,x = map(int,input().split())

if 500*k >= x:
    print('Yes')
else:
    print('No')
n = int(input())
ans = 0

l = [sorted(input()) for _ in range(n)]
dellist = lambda items, indices: [item for idx, item in enumerate(items) if idx not in indices]

while True:
    a = l.pop(0)
    li = []
    for i in range(len(l)):
        if l[i] == a:
            li.append(i)

    dellist(l, li)

    ans += sum(range(li + 1))

print(ans)

### FIXED CODE ###

from collections import Counter

def p_c():
    n = int(input())
    ans = 0

    l = ["".join(sorted(input())) for _ in range(n)]

    a = Counter(l).values()

    for i in a:
        ans += sum(range(i))

    print(ans)
    
    
if __name__ == '__main__':
    p_c()
n=int(input())
array=[]
for i in range(n):
  k=int(input())
  array.append(k)
array.sort()
sum=0
for i in range(n-1):
  sum+=array[i]
if array[n-1]<sum:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n=int(input())
array=list(map(int,input().split()))
array.sort()
sum=0
for i in range(n-1):
  sum+=array[i]
if array[n-1]<sum:
  print('Yes')
else:
  print('No')
import itertools
L,R = map(int,input().split())

ans_list=[]
for v in itertools.combinations(range(L,R+1),2):
  buf1 = v[0]%2019
  buf2 = v[1]%2019
  ans_list.append((buf1*buf2)%2019)
print(min(ans_list))

### FIXED CODE ###

import itertools
L,R = map(int,input().split())
if (L+2019) < R:
  R = L+2019

ans_list=[]
for v in itertools.combinations(range(L,R+1),2):
  buf1 = v[0]%2019
  buf2 = v[1]%2019
  ans_list.append((buf1*buf2)%2019)
print(min(ans_list))
def a(t,i):
    if i==l and eval(t)==7:
        print(t+'=7')
        exit()
    a(t+'+'+s[i+1],i+1)
    a(t+'-'+s[i+1],i+1)

s = input()
l = len(s)-1
a(s[0],0)

### FIXED CODE ###

def dfs(i, Str, res):
    if i==3:
        if res==7:
            print(Str+"=7")
            exit()
        return
    
    dfs(i+1,Str+"+"+s[i+1],res+int(s[i+1]))
    dfs(i+1,Str+"-"+s[i+1],res-int(s[i+1]))

s=input()
dfs(0,s[0],int(s[0]))
# 計算量O(N2M)

N = int(input())

d = list(map(int,input().split()))
d_cnt = [0]*max(d)

for v in d:
    d_cnt[v-1] += 1

M = int(input())

t = list(map(int,input().split()))
t_cnt = [0]*max(t)

for v in t:
    t_cnt[v-1] += 1

if N < M:
    print('NO')
    exit()

for dn,tn in zip(d_cnt,t_cnt):
    if tn != 0:
        if dn < tn:
            print('NO')
            exit()

print('YES')


### FIXED CODE ###

# 計算量O(N2M)
import collections
N = int(input())

d = collections.Counter(list(map(int,input().split())))

M = int(input())
t = list(map(int,input().split()))
t_num = t.copy()
t_num = set(list(t_num))
t = collections.Counter(t)

if N < M:
    print('NO')
    exit()

for key in t_num:
    if d[key] < t[key]:
        print('NO')
        exit()
print('YES')
A, B, H, M = map(float, input().split())

m_theta = (M/60.0)*2*pi
h_theta = 1/12.0*(H + M/60.0) * 2* pi
mh_theta = abs(m_theta - h_theta)

x = A**2 + B**2 - 2*A*B*cos(mh_theta)
x = sqrt(x)
print(x)


### FIXED CODE ###

import math
from math import cos,pi,sqrt,radians

A, B, H, M = map(float, input().split())

m_theta = (M/60.0)*2*pi
h_theta = 1/12.0*(H + M/60.0) * 2* pi
mh_theta = abs(m_theta - h_theta)

x = A**2 + B**2 - 2*A*B*cos(mh_theta)
x = sqrt(x)
print(x)
a ,b = map(int(input().split()))
print a*b + ' ' + 2(*(a+b)

### FIXED CODE ###

a, b = map(int, input().split())
print(a*b, a*2 + b*2)
import math
a=list(map(int,input().split()))
ans=0
if max(a)-min(a)>=2:
    print(0)
else:
    if a[0]==a[1]:
        ans=math.factorial(max(a))
        ans=(ans%1000000007)*(ans%1000000007)*2
    else:
        ans=math.factorial(max(a))
        ans=(ans%1000000007)*((ans/max(a))%1000000007)
    print(int(ans%1000000007 ))

### FIXED CODE ###

import math
a=list(map(int,input().split()))
ans=0
if max(a)-min(a)>=2:
    print(0)
else:
    if a[0]==a[1]:
        ans=math.factorial(max(a))
        ans=(ans%1000000007)*(ans%1000000007)*2
    else:
        ans=math.factorial(max(a))
        ans1 = math.factorial(min(a))
        ans=(ans%1000000007)*((ans1)%1000000007)
    print(int(ans%1000000007 ))
A,B=list(map(int, input().split()))
if A<=8 and B<=8:
  print('Yay!')
else:
  peint(':(')

### FIXED CODE ###

A,B=list(map(int, input().split()))
if A<=8 and B<=8:
  print('Yay!')
else:
  print(':(')
import math
from functools import reduce
from math import gcd
K = int(input())
A=[]
B=[]
for a in range(1,K+1):
    for b in range(1,K+1):
        A.append(gcd(a,b))
for x in range(len(A)):
    for c in range(1,K+1):
        B.append(gcd(A[x],c))
for i in range(len(B)):
    sum +=B[i]
print(sum)


### FIXED CODE ###

import math
 
 
N = int(input())
 
s = 0
 
for i in range(N):
    for j in range(N):
        ss = math.gcd(i+1,j+1)
        for k in range(N):
            s +=math.gcd(ss,k+1)
 
print(s)
n=int(input())
a = list(map(int, input().split()))

t=[[0]*n for k in range(n)]
tt=[[0]*n for k in range(n)]

def search(i,j):
   if i==j or j==n or i==n-1:
      return
   if tt[i][j]==1:
      return
   if j-i==a[i]+a[j]:
      t[i][j]=1

   tt[i][j]=1

   search(i+1,j)
   search(i,j+1)
search(0,1)
result=0
for row in t:
    result += sum(row)

print(result)

### FIXED CODE ###

import collections
n=int(input())
a = list(map(int, input().split()))
an=0
ii=[]
jj=[]
for i in range(n):
    ii.append(i+a[i])
    jj.append(i-a[i])
jjj=collections.Counter(jj)
for i in range(n):
    an+=jjj[ii[i]]
print(an)
t = [0]
x = [0]
y = [0]
N = int(input())
for i in range(1,N+1):
  ti,xi,yi = map(int,input(),split())
  t.append(ti)
  x.append(xi)
  y.append(yi)
  
flg = True
 
for i in range(1,N-1):
  if t[i]-t[i-1] <　x[i]-x[i-1] + y[i]-y[i-1]:
    flg = False
  else (t[i]-t[i-1])%2 != (x[i]-x[i-1]+y[i]-y[i-1])%2:
    flg = False
if(flg):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b = map(int, input().split())
if a*b % 2 == 0:
  print("Even")
else:
  print("Odd")
n, m, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
x.append(X)
y.append(y)

for i in range(len(x)):
	for j in range(i, len(x)):
		if (x[i] == y[j]) or (y[i] == x[j]):
			print('War')
			exit()

if max(x) >= min(y):
	print('War')
	exit()

print('No War')

### FIXED CODE ###


n, m, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
x.append(X)
y.append(Y)

for i in range(len(x)):
	for j in range(len(y)):
		if (x[i] == y[j]):
			print('War')
			exit()

if max(x) >= min(y):
	print('War')
	exit()

print('No War')
N, K = map(int, input().split())
A = input()

A[K-1::] = A[k-1::].lower()
print(A)

### FIXED CODE ###

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

if K < len(A):
    ans = A[:K-1] + A[K-1].lower() + A[K:]
else:
    ans = A[:K-1] + A[K-1].lower()
print(ans)
N, M = map(int, input().split())
li = list(map(int,input().split()))

li.sort()
tmp = 0

for i in range(M):
    B, C = map(int, input().split())
    for j in range(B):
        if li[j] < C:
            li[j] = C
        else:
            break
    li.sort()

print(sum(li))

### FIXED CODE ###

A, B = map(int, input().split())

if A >= 13:
    print(B)
elif A >= 6 and A <= 12:
    print("{:.0f}".format(B/2))
elif A <= 5:
    print(0)
a = ai()
x = lma()
print(sum(x)-a)

### FIXED CODE ###

def a():return input()#s
def ai():return int(input())#a,n or k
def ma():return map(int, input().split())#a,b,c,d or n,k
def ms():return map(str, input().split())#,a,b,c,d
def lma():return list(map(int, input().split()))#x or y
def lms():return list(map(str, input().split()))#x or y
a = ai()
x = lma()
print(sum(x)-a)
n = int(input());
list = map(int, input());
ans = 1
for i in range(n):
    ans *= list[i]
    if ans>10**18 :
        ans = -1
        break
print(ans)


### FIXED CODE ###

n = int(input());
list = list(map(int,input().split()))
zero = False
for i in list:
    if i==0:
        zero = True
        break
if zero:
    print(0)
else:
    ans = 1
    for i in list:
        ans *= i
        if ans>10**18:
            ans = -1
            break
    print(ans)
a,b = map(int,input().split())
print(max[a+b,a-b,a*b])


### FIXED CODE ###

a,b = map(int,input().split())
print(max([a+b,a-b,a*b]))
s = input()
if s=='AAA' or s==s'BBB:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

s = input()
if s=='AAA' or s=='BBB':
    print('No')
else:
    print('Yes')
s = input().split('')
n = 0
for si in s:
    if si == '+':
        n = n + 1
    else:
        n = n - 1
print(n)


### FIXED CODE ###

s = input()
n = 0
for i in range(len(s)):
    if s[i] == '+':
        n = n + 1
    else:
        n = n - 1
print(n)
n=input().split()
a=n[0]
b=n[1]
S=a*b
L=(2*a)+(2*b)
print(S' 'L)


### FIXED CODE ###

#cording; UTF-8
a,b=[int(x) for x in input().split()]

S = a*b
L = 2*(a+b)
print(S,L)
A,B,AB,X,Y= int(input.split())
ans = (X * A) + (Y * B)
max_ab_cnt = max(X,Y)
for ab_cnt in (max_ab_cnt+1):
    a_cnt = max(X - ab_cnt, 0)
    b_cnt = max(Y - ab_cnt,0)
    tmp = (a_cnt *A) + (ab_cnt * 2 * AB) + (b_cnt * B)
    ans = min(ans, tmp)
print(ans)

### FIXED CODE ###

A,B,AB,X,Y= list(map(int, input().split()))
ans = (X * A) + (Y * B)
max_ab_cnt = max(X,Y)
for ab_cnt in range(max_ab_cnt+1):
    a_cnt = max(X - ab_cnt, 0)
    b_cnt = max(Y - ab_cnt,0)
    tmp = (a_cnt *A) + (ab_cnt * 2 * AB) + (b_cnt * B)
    ans = min(ans, tmp)
print(ans)
import numpy as np
n = int(input())
a_list = list(map(int,input().split()))
import math
result = 0
check = True
for a in a_list:
  if a == 0:
    check = False
    break
  else:
    result += math.log10(a)
if check == False:
  print(0)
elif 10**result > 18:
  print(-1)
else:
  print(int(10**result))
  
  

### FIXED CODE ###

n = int(input())
a_list = list(map(int,input().split()))
result = 1
if 0 in a_list:
  print(0)
else:
  for a in a_list:
    result = result *a
    if len(str(result)) >= 19:
      if result == 10**18:
        continue
      else:
        result = -1
        break
        
  print(result)
S = input()
S.replace("hi",":")
if len(set(s)) == 1:
  print("Yes")
else:
  print("No)

### FIXED CODE ###

S = input()
if S.count("hi") == len(S)/2:
    print("Yes")
else:
    print("No")
s = input()
t = input()
cnt = 0
for i, p in enumerate(range(s)):
  if p != t[i]:
    cnt += 1
    
print(cnt)

### FIXED CODE ###

s = input()
t = input()
cnt = 0
for i, p in enumerate(s):
  if p != t[i]:
    cnt += 1
    
print(cnt)
n = int(input())
list = [int(i) for i in input().split()]

ans = 1
flag = True
for i in range(n):
    if i%2==0:
        right *= list[i]
    else:
        left *= list[i]

ans = left*right
if ans>10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

ans = 1
flag = True
for i in range(n):
    ans *= list[i]
    if ans>10**18:
        flag = False
        ans = ans%(10**18)
    if list[i]==0:
        flag = True
        break

if flag:
    print(ans)
else:
    print(-1)
N = int(input())
str(n)
listN = sorted(N)
if listN.count("7") >= 1:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

N = int(input())
listN = sorted(str(N))
if listN.count("7") >= 1:
    print("Yes")
else:
    print("No")
num = list(map(int, input().split()))
if(num[1]-num[0] = num[2]-num[1]):
    print('Yes')
else
    print('No')



### FIXED CODE ###

num = list(map(int, input().split()))
if num[1]-num[0] == num[2]-num[1]:
	print('YES')
else:
	print('NO')
import sys
from collections import deque
A = deque(input())
B = int(input())
for i in range(B):
    C = sys.stdin.readline().split()
    if C[0] == "1":
        A.reverse()
    else:
		X = C[2]
        if C[1] == "1":
            A.appendleft(X)
        else:
            A.append(X)
print("".join(A))

### FIXED CODE ###

A = input()
B = int(input())
C = ""
for i in range(B):
    D = input().split()
    if D[0] == "1":
        C,A = A,C
    else:
        if D[1] == "1":
            C += D[2]
        else:
            A += D[2]
C = C[::-1]
print(C+A)
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
s=list(input())
mod=10**9+7
U=[[0 for i in range(10) ]for k in range(13)]
for i in range(13):
    for j in range(10):
        U[i][j]=((i-j)*K)%13
K=modinv(10,13)
dp=[[0 for k in range(13)] for i in range(len(s))]
#dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
num=s[0]
if s[0]=="?":
    for i in range(10):
        dp[0][i]=1
else:
    number=int(s[0])
    dp[0][number]=1

for i in range(1,len(s)):
    if s[i]=="?":
        for k in range(13):
            for j in range(10):
                dp[i][k]+=dp[i-1][U[k][j]]
        dp[i][k]=dp[i][k]%mod
    else:
        number=int(s[i])
        for k in range(13):
            dp[i][k]=dp[i-1][U[k][number]]%mod
print(dp[len(s)-1][5]%mod)


### FIXED CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def main():
    s=list(input())
    mod=10**9+7
    K=modinv(10,13)
    U=[[0 for i in range(10) ]for k in range(13)]
    for i in range(13):
        for j in range(10):
            U[i][j]=((i-j)*K)%13

    dp=[[0 for k in range(13)] for i in range(len(s))]
    #dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
    num=s[0]
    if s[0]=="?":
        for i in range(10):
            dp[0][i]=1
    else:
        number=int(s[0])
        dp[0][number]=1

    for i in range(1,len(s)):
        for k in range(13):
            if s[i]=="?":
                for j in range(10):
                    dp[i][k]+=dp[i-1][U[k][j]]%mod
            else:
                number=int(s[i])
                dp[i][k]=dp[i-1][U[k][number]]%mod
    print(dp[len(s)-1][5]%mod)
if __name__ == "__main__":
    main()
q = int(input())
t = []
for i in range(q):
    X = input()
    Y = input()
    m = len(X)
    n = len(Y)
    c1 = [0] * (n + 1)
    for i in range(m):
        d = X[i]
        c2 = c1[:]
        for j in range(n):
            if (d == Y[j]):
                c1[j + 1] = c2[j] + 1
            elif (c1[j + 1] < c1[j]):
                c1[j + 1] = c1[j]
    return (c1[-1])
    print(Ics(s1, s2))

### FIXED CODE ###

def Ics(X, Y):
    m = len(X)
    n = len(Y)
    c1 = [0] * (n + 1)
    for i in range(m):
        d = X[i]
        c2 = c1[:]
        for j in range(n):
            if (d == Y[j]):
                c1[j + 1] = c2[j] + 1
            elif (c1[j + 1] < c1[j]):
                c1[j + 1] = c1[j]
    return (c1[-1])
 
q = int(input().rstrip())
t = []
for i in range(q):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(Ics(s1, s2))
print(*t, sep = "\n")
a, b, c = input().split()
if a[len(a)] == b[0] and b[len(b)] == b[0]:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

a, b, c = input().split()

print("YES") if a[len(a)-1] == b[0] and b[len(b)-1] == c[0] else print("NO")
def main():
  n, k = map(int, input().split())

  plus = []
  minus = []

  for n in input().split():
    n = int(n)
    if n >= 0:
      plus.append(n)
    else:
      minus.append(n)

  mod = 10 ** 9 + 7

  if len(plus) == 0 and k % 2 == 1:
    minus.sort(reverse=True)
    ans = 1
    for i in range(k):
      ans *= minus[i]

    print(ans % mod)
    return


  plus.sort(reverse = True)
  minus.sort()

  pn = min(len(plus), k)
  mn = k - pn

  if len(plus) >= 2 and len(minus) >= 2:
    while pn >= 2:
      if plus[pn - 2] * plus[pn - 1] > minus[mn] * minus[mn + 1]:
        break

      pn -= 2
      mn += 2

  ans = 1
  for i in range(pn):
    ans = (ans * plus[i]) % mod

  for i in range(mn):
    ans = ans * minus[i]

  print(ans % mod)


main()


### FIXED CODE ###


def main():
  n, k = map(int, input().split())

  mod = 10 ** 9 + 7

  if n == k:
    ans = 1
    for num in input().split():
      ans = (ans * int(num)) % mod

    print(ans % mod)
    return

  plus = []
  minus = []
  for num in input().split():
    num = int(num)
    if num >= 0:
      plus.append(num)
    else:
      minus.append(num)

  pn = len(plus)
  mn = len(minus)

  if pn == 0 and k % 2 == 1:
    minus.sort(reverse = True)
    ans = 1
    for i in range(k):
      ans = (-ans * minus[i]) % mod

    print((-ans) % mod)
    return


  plus.sort(reverse = True)
  minus.sort()

  pi = 0
  mi = 0

  while k > 0:
    if pi + 1 == pn:
      if k % 2 == 0:
        mi += k
      else:
        pi += 1
        mi += k - 1

      break

    if pi == pn:
      mi += k
      break

    if mi + 1 >= mn:
      pi += k
      break

    if k == 1 or plus[pi] * plus[pi + 1] >= minus[mi] * minus[mi + 1]:
      pi += 1
      k -= 1
    else:
      mi += 2
      k -= 2

  ans = 1
  for i in range(pi):
    ans = (ans * plus[i]) % mod

  for i in range(mi):
    ans = (-ans * minus[i]) % mod

  print(ans % mod)


main()
int x = int(input())
print(x*x*x)


### FIXED CODE ###

x = int(input())
x = x*x*x
print(x)
coordinates = list(map(int, input().split()))
w = coordinates[0]
h = coordinates[1]
x = coordinates[2]
y = coordinates[3]
prod1 = x * h
prod2 = y * w
if x == w and y == h:
    prod1 = prod2 = (w * h) / 2
area = min(prod1, prod2)
# area = format(area, '.6f')
addit = 0 if prod1 != prod2 else 1
print(f"{area} {addit}")

### FIXED CODE ###

import sys
from math import ceil

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

def iinput():
    return int(input())

def finput():
    return float(input())

def tinput():
    return input().split()

def rinput():
    return map(int, tinput())

def rlinput():
    return list(rinput())

def nok(a, b):
    m = a * b
    while a != 0 and b != 0:
        if a > b:
            a %= b
        else:
            b %= a
    return m // (a + b)    


def main():
    w, h, x, y = rinput()
    if x == w / 2 and y == h / 2:
        print(w * h / 2, 1)
    else:
        print(w * h / 2, 0)
    
    
    
main()
N, M = map(int, input().split())
print(N*(N-1)/2 + M*(M-1)/2))

### FIXED CODE ###

N, M = map(int, input().split())
print(N*(N-1)//2 + M*(M-1)//2)