Harryxun/stf_run huggingface dataset:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

from collections import defaultdict, deque
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
S = input()

    while len(S) >= 5:
        # Sを４つの単語で順に調べて刈っていく
        if len(S) >= 7 and S[-7:] == "dreamer":
            S = S[:-7]
            continue

        if len(S) >= 6 and S[-6:] == "eraser":
            S = S[:-6]
            continue

        elif S[-5:] == "dream" or S[-5:] == "erase":
            S = S[:-5]
            continue

        else:
            break

    if len(S) == 0:
        print("YES")
    else:
        print("NO")

### FIXED CODE ###

def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

from collections import defaultdict, deque
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
S = input()

while len(S) >= 5:
    # Sを４つの単語で順に調べて刈っていく
    if len(S) >= 7 and S[-7:] == "dreamer":
        S = S[:-7]
        continue

    if len(S) >= 6 and S[-6:] == "eraser":
        S = S[:-6]
        continue

    elif S[-5:] == "dream" or S[-5:] == "erase":
        S = S[:-5]
        continue

    else:
        break

if len(S) == 0:
    print("YES")
else:
    print("NO")
import sys
input = sys.stdin.readline

strA = str(input())

if strA == 'ABC':
  print('ARC')
elif strA == 'ARC':
  print('ABC')
else
  print('')

### FIXED CODE ###

import sys

import math
input = sys.stdin.readline

hoge = str(input().strip())
if hoge == "ABC":
   print("ARC".strip())
if hoge == "ARC":
       print("ABC".strip())
import collections
n,m = map(int,raw_input().split(' '))

costs = [map(int, raw_input().split(' ')) for _ in range(n)]
costs.sort(key = lambda x:-x[0])
q = collections.deque(costs)
while(m):
	u,v = q.popleft()
	t = min(v,m)
	m -=t
	r += t * u
print r

### FIXED CODE ###


import collections
n,m = map(int,raw_input().split(' '))

costs = [map(int, raw_input().split(' ')) for _ in range(n)]
costs.sort(key = lambda x:-x[0])
q = collections.deque(costs)
r = 0
while(m):
	u,v = q.pop()
	t = min(v,m)
	m -=t
	r += t * u
print r
import sys
from sys import stdin
input = stdin.readline

INF = 10**9

s = input()
t = input()
ans = 10**10
ls = len(s)
lt = len(t)
for i in range(ls - lt + 1):
  cnt = 0
  for j in range(lt:
    if (s[i+j] != t[j]): cnt += 1
  ans = min(cnt, ans)
print(ans)

### FIXED CODE ###

s = input()
t = input()
ans = 10 ** 10
ls = len(s)
lt = len(t)
for i in range(ls - lt + 1):
    cnt = 0
    for j in range(lt):
        if s[i + j] != t[j]:
            cnt += 1
    ans = min(ans, cnt)
print(ans)
// https://atcoder.jp/contests/arc061/tasks/arc061_a
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  string S;
  cin >> S;

  ll ans = 0;
  int m = S.size() - 1;

  rep(bit, 1 << m) {
    ll cur = S[0] - '0';
    rep(i, m) {
      if (bit & (1 << i)) {
        ans += cur;
        cur = 0;
      }
      cur = cur * 10 + S[i + 1] - '0';
    }
    ans += cur;
  }
  cout << ans << endl;
  return 0;
}


### FIXED CODE ###

s = input()
n = len(s) - 1
ans = 0
for bit in range(1 << n):
    now = 0
    for i in range(bit):
        if bit & (1 << i):
            ans += int(s[now : i + 1])
            now = i + 1
    ans += int(s[now : len(s)])
print(ans)
def main():
    s = input()
    for i in range(len(s)):
        if s[i]=="C":
            idx = i
            break

    for i in range(idx+1,len(s)):
        if s[i]=="F":
            print("Yes")
            exit()

    print("No")

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    s = list(input())
    for i in range(len(s)):
        for j in range(i+1,len(s)):
            if s[i]=="C" and s[j]=="F":
                print("Yes")
                exit()
    print("No")

if __name__ == '__main__':
    main()
N, K = map(int, input().split())
H = map(int, input().split())

H.sort(reverse=True)

if K >= N:
    print(0)
else:
    print(sum(H[K:]))


### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))

H.sort(reverse=True)

if K >= N:
    print(0)
else:
    print(sum(H[K:]))
for i in range(N-1):
    tmp+=A[i]
    ans+=tmp*A[i+1]
print(ans%((10**9)+7))

### FIXED CODE ###

import math

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

for i in range(N-1):
    tmp+=A[i]
    ans+=tmp*A[i+1]
print(ans%((10**9)+7))
n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))

dp = [0 for _ in range(n + 2)] #i-1段目に登る方法の数
dp[0] = 0
dp[1] = 1
tmp = 0
for i in range(n):
    if i + 1 != a[tmp]:
        dp[i + 2] = (dp[i] + dp[i + 1]) % (pow(10, 9) + 7)
    elif i + 1 == a[tmp]:
        if tmp < m - 1:
            tmp += 1
        dp[i + 2] = 0
#print(dp)
print(dp[n + 1])


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))

if m == 0:
    dp = [0 for _ in range(n)] #i + 1段目に登る方法の数
    dp[0] = 1
    if n >= 2:
        dp[1] = 2
    for i in range(2, n):
        dp[i] = (dp[i - 1] + dp[i - 2]) % (pow(10, 9) + 7)
    print(dp[n - 1])
    exit()

tmp = 0
dp = [0 for _ in range(n)]
if 1 == a[tmp]:
    dp[0] = 0
    tmp += 1
else:
    dp[0] = 1
if n >= 2 and tmp < m and 2 == a[tmp]:
    dp[1] = 0
    tmp += 1
elif n >= 2 and (tmp >= m or 2 != a[tmp]):
    dp[1] = dp[0] + 1

for i in range(2, n):
    if tmp < m and i + 1 == a[tmp]:
        dp[i] = 0
        tmp += 1
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % (pow(10, 9) + 7)
#print(dp)
print(dp[n - 1] % (pow(10, 9) + 7))
N = int(input())
A=list(map(int,input().split())
B=list(map(int,input().split())
ans = 0
for j in range(N):
    temp = 0
    for k in range(j+1):
        temp += A[k]
    for l in range(j,N):
        temp += B[l]
    ans = max(ans,temp)
print(ans)


### FIXED CODE ###

N = int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
ans = 0
for j in range(N):
    temp = 0
    for k in range(j+1):
        temp += A[k]
    for l in range(j,N):
        temp += B[l]
    ans = max(ans,temp)
print(ans)
import numpy as np
from collections import defaultdict

def rec(start, p):
    if ans[start] != -1:
        return p
    ans[start] = C[p]
    p += 1
    for node in tree[start+1]:
        p = rec(node-1, p)
    return p

N = int(input())
tree = defaultdict(list)
degree = [0 for i in range(N)]
edges = [0 for i in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[i] = (a, b)
    tree[a].append(b)
    tree[b].append(a)
for k, v in tree.items():
    degree[k-1] = len(v)
# print(degree)
sort_i = np.argsort(degree)[::-1]
# max_di = sort_i[-1]
# print(sort_i)
C = list(map(int, input().split()))
C = sorted(C, reverse=True)
# C = list(sorted(zip(sorted(C), list(sort_i)),key=lambda x: x[1]))
# print(C[sort_i])
ans = 0
visited_e = []
# start = max_di + 1
visited = [False for i in range(N)]
p = 0
ans = [-1 for i in range(N)]
M = 0

rec(sort_i[0], p)

for e in edges:
    M += min(ans[e[0]-1], ans[e[1]-1])
    # print(ans)
print(M)
print(' '.join(list(map(lambda x: str(x), ans))))


### FIXED CODE ###

import numpy as np
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
def rec(start, p):
    if ans[start] != -1:
        return p
    ans[start] = C[p]
    p += 1
    for node in tree[start+1]:
        p = rec(node-1, p)
    return p

N = int(input())
tree = defaultdict(list)
degree = [0 for i in range(N)]
edges = [0 for i in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[i] = (a, b)
    tree[a].append(b)
    tree[b].append(a)
for k, v in tree.items():
    degree[k-1] = len(v)
# print(degree)
sort_i = np.argsort(degree)[::-1]
# max_di = sort_i[-1]
# print(sort_i)
C = list(map(int, input().split()))
C = sorted(C, reverse=True)
# C = list(sorted(zip(sorted(C), list(sort_i)),key=lambda x: x[1]))
# print(C[sort_i])
ans = 0
visited_e = []
# start = max_di + 1
visited = [False for i in range(N)]
p = 0
ans = [-1 for i in range(N)]
M = 0

rec(sort_i[0], p)

for e in edges:
    M += min(ans[e[0]-1], ans[e[1]-1])
    # print(ans)
print(M)
print(' '.join(list(map(lambda x: str(x), ans))))
a,b,c=map(int,input().split())
if(((a==5)or(a==7)) and ((b==5)or(b==7)) and ((c==5)or(c==7))):
  if(a+B+c==17):
    print("YES")
  else:
    print("NO")
else:
  print("NO")  

### FIXED CODE ###

a,b,c=map(int,input().split())
if(((a==5)or(a==7)) and ((b==5)or(b==7)) and ((c==5)or(c==7))):
  if(a+b+c==17):
    print("YES")
  else:
    print("NO")
else:
  print("NO")
s=input()
x=[0 for _ in range(26)]
if len(s)<26:
    for i in range(len(s)):
        x[ord(s[i])-ord('a')]=1
    for j in range(len(s)):
        if x[j]==0:
            k=j
            break
    print("".join([s,chr(ord('a')+k)]))
elif s=="zyxwvutsrqponmlkjihgfedcba":
    print(-1)
else:
    mi=-1
    for i in range(1,26):
        if s[i]<s[i-1]:
            x[i]=1
            if mi==-1:
                mi=i
    print(s[:mi-2]+mx)

### FIXED CODE ###

s=input()
x=[0 for _ in range(26)]
if len(s)<26:
    for i in range(len(s)):
        x[ord(s[i])-ord('a')]=1
    for j in range(26):
        if x[j]==0:
            k=j
            break
    print("".join([s,chr(ord('a')+k)]))
elif s=="zyxwvutsrqponmlkjihgfedcba":
    print(-1)
else:
    for i in range(2,27):
        if s[-i]<s[-i+1]:
            break
    for j in sorted(s[-i+1:]):
        if j>s[-i]:
            break
    print(s[:-i]+j)
A,B,C,D=map(int,input().split())

while True:
  C-=B
  if C<=0:
    input("Yes")
    break
  A-=D
  elif A<=0:
    input("No")
    break

### FIXED CODE ###

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

while True:
  C-=B
  if C<=0:
    print("Yes")
    break
  A-=D
  if A<=0:
    print("No")
    break
H,W=int(input())
h,w=int(input())
print((H-h)*(W-w))


### FIXED CODE ###

s1 = list(map(int, input().split()))
s2 = list(map(int, input().split()))
print((s1[0]-s2[0])*(s1[1]-s2[1]))
N = input()
if 7 in N:
    print(yes)
else:
    print(no)


### FIXED CODE ###

n = input()
N = str(n)
if "7" in N:
    print("Yes")
else:
    print("No")
#一個だけRE、わからねえ
#解答見る
import sys
sys.setrecursionlimit(500)
h,w=map(int,input().split())

def go_next(I,J):
    global dp,w,h
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])


### FIXED CODE ###

#一個だけRE、わからねえ
#解答見る
import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())

def go_next(I,J,n):
    n+=1
    global dp,w,h
    if n>1000:
        return
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J,n)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J,n)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1,n)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1,n)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])
import math

def fact(N):
    total = 1
    for i in range(1, N+1):
        total = total * i
    return total

def comb(a, b):
    return fact(a) / (fact(a-b) * fact(b))

def main():
    N, K = list(map(int, input().split(" ")))
    mod = 1000000007
    for i in range(1, K+1):
        # blue cluster
        comb1 = int(comb(N-K+1, i))
        comb2 = int(comb(K-1, i-1))
        ans = ((comb1 % mod) * (comb2 % mod)) % mod
        print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math

def fact(N):
    total = 1
    for i in range(1, N+1):
        total = total * i
    return total

def comb(a, b):
    return fact(a) // (fact(a-b) * fact(b))


def main():
    N, K = list(map(int, input().split(" ")))
    a = N - K + 1
    b = 1
    mod = 1000000007
    ans = ((a % mod) * (b % mod)) % mod
    print(ans)
    for i in range(1, K):
        tmp_a = (N-K+1-i)
        if tmp_a == 0:
            tmp_a = 1
        tmp_b = (K-1-i+1)
        if tmp_b == 0:
            tmp_b = 1
        a = (a * tmp_a) // (i+1)
        b = (b * tmp_b) // i
        ans = ((a % mod) * (b % mod)) % mod
        print(ans)

if __name__ == '__main__':
    main()
import heapq

n,m=map(int,input().split())
X=[]
for i in range(n):
    a,b=map(int,input().split())
    X.append([a,-b])
Y=sorted(X,key=lambda x:(x[0]))
ans=0
c=0
x=[0]*n
heapq.heapify(x)
flag=True
for i in range(1,m+1):
    if flag:
        while Y[c][0]<=i:
            heapq.heappush(x,Y[c][1])
            c+=1
            if c==len(Y):
                flag=False
                break
    ans+=heapq.heappop(x)*(-1)
print(ans)

### FIXED CODE ###

import heapq

n,m=map(int,input().split())
X=[[] for _ in range(10**5+5)]
for i in range(n):
    a,b=map(int,input().split())
    X[a-1].append(-b)

ans=0
p=[]
heapq.heapify(p)
for i in range(m):
    if len(p)==0 and len(X[i])==0:
        continue
    for j in range(len(X[i])):
        heapq.heappush(p,X[i][j])
    a=heapq.heappop(p)
    ans+=a*-1
print(ans)
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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

def main():
  N=I()
  A=LI()
  
  l=[0]*1000100
  pairwise=True
  for i in range(2,1000100):
    cnt=0
    for j in range(i+1,1000100):
      cnt+=A[j]
    if cnt>1:
      pairwise=False

  if pairwise:
    return 'pairwise coprime'

  f1=True
  f2=False
  for x in l:
    if x>1:
      f1=False

  if f1:
    return 'pairwise coprime'

  g=0
  for x in A:
    g=math.gcd(g,x)

  if g==1:
    return 'setwise coprime'

  return 'not coprime'

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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

def main():
  N=I()
  A=LI()

  g=0
  for x in A:
    g=math.gcd(g,x)
  if g>1:
    return 'not coprime'

  sosu=[0]*1000100
  for x in A:
    if x==1:
      continue
    sosu[x]+=1
    if sosu[x]>1:
      return 'setwise coprime'
    for y in range(2,int(math.sqrt(x))+1):
      if x%y!=0:
        continue
      z=x//y
      if y==z:
        sosu[y]+=1
        if sosu[y]>1:
          return 'setwise coprime'
      else:
        sosu[y]+=1
        if sosu[y]>1:
          return 'setwise coprime'
        sosu[z]+=1
        if sosu[z]>1:
          return 'setwise coprime'

  return 'pairwise coprime'

# main()
print(main())
import sys
input = sys.stdin.buffer.readline


def main():
  	K = int(input())
	A, B = map(int, input().split())
    for i in range(A, B + 1):
        if i % K == 0:
            print('OK')
            sys.exit()
    print('NG')


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

K = int(input())

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


def main(K, A, B):
    for i in range(A, B + 1):
        if i % K == 0:
            print('OK')
            sys.exit()
    print('NG')


if __name__ == '__main__':
    main(K, A, B)
A = int(input()) #500
B = int(input()) #100
C = int(input()) #50
X = int(input())
count = 0 //初期値
           
#全件走査
maxA = X // 500 if 500 * A > X else A
for i in range(maxA + 1):
  maxB = (X - 500 * i ) // 100 if 100 *B > (X - 500 * i) else B
  for j in range(maxB + 1):
    q,mod = divmode (X - 500 * i - 100 * j ,50)
    count += 1 if mod == 0 and q <= C     
print(count)

### FIXED CODE ###

A = int(input()) #500
B = int(input()) #100
C = int(input()) #50
X = int(input())
count = 0 #初期値
           
#全件走査
maxA = X // 500 if 500 * A > X else A
for i in range(maxA + 1):
  maxB = (X - 500 * i) // 100 if 100 * B > (X - 500 * i) else B
  for j in range(maxB + 1):
    q,mod = divmod (X - 500 * i - 100 * j ,50)
    if mod == 0 and q <= C:count += 1    
print(count)
from sys import stdin
import fractions
 
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
 
res = []
 
for i in range(N):
    B = A[:]
    del B[i]
    B.sort()

    gcd_num = fractions.gcd(B[0], B[1])

    res.append(gcd_num)

 
print(max(res))

### FIXED CODE ###

from sys import stdin
import fractions

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
# インデックスを直感で使えるように先頭にダミーを入れる
A = [0] + A

"""
L(i) := A_1, A_2, ..., A_i-1 の最大公約数
R(i) := A_i, A_i+1, ..., A_N の最大公約数
Aiを書き換えることにした場合の最大公約数をM_iとすると
M_i = gcd(L(i), R(i+1))

ただし L(0)=0, R(N+1)=0
"""

L = [0 for _ in range(N+1)]
R = [0 for _ in range(N+2)]

for i in range(N):
    L[i+1] = fractions.gcd(L[i], A[i])


for i in range(N, 0, -1):
    R[i] = fractions.gcd(R[i+1], A[i])

M = []

for i in range(1, N+1):
    M_i = fractions.gcd(L[i], R[i+1])
    M.append(M_i) 

print(max(M))
S = raw_input()
print "Bad" if A[0]==A[1] or A[1]==A[2] or A[2]==A[3] else "Good"


### FIXED CODE ###

S = raw_input()
print "Bad" if S[0]==S[1] or S[1]==S[2] or S[2]==S[3] else "Good"
n=int(input())
t=list(map(int,input().split()))
m=int(input())
p=[0]*m
x=[0]*m
for i in range(m):
  p[i],x[i]=map(int,input().split())  
for i in range(m):
  print(sum(t)-t[p[i]-1]+x[i])

### FIXED CODE ###

s = list(input().split())
if (s[1]=='+'):
    print(int(s[0])+int(s[2]))
if (s[1]=='-'):
    print(int(s[0])-int(s[2]))
n=int(input())
X=[]
Y=[]
A=[0]*n
for i in range(n):
  A[i]=int(input())
  a=A[i]
  for j in range(a):
    x=[0]*a
    y=[0]*a
    x[j],y[j]=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  

c=0
for i in range(n):
  l=[1]*n
  for j in range(i,n-i):
    if l[j]==0:continue
    for k in range(A[j]):
      b=X[j][k]
      l[b] *= 2
      #Y[j][k]

if c < l.count(1):
  c=l.count(1) 
  
        
  
print(c)  
   

### FIXED CODE ###

n=int(input())
X=[]
Y=[]
A=[0]*n
for i in range(n):
  A[i]=int(input())
  a=A[i]
  x=[0]*a
  y=[0]*a
  for j in range(a):
    x[j],y[j]=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
s=0
for i in range(2**n):
  c=0
  d=0
  B=[0]*n
  for j in range(n):
    if((i >> j) & 1):
      c=c+1
      B[j]=1
  for k in range(n):
    if B[k]==1:
      for j in range(A[k]):
        if Y[k][j]!=B[X[k][j]-1]:
          d=-1
          break
    if d<0:
      break
  if s<c and d==0:
    s=c
      
      
print(s)
import sys
sys.setrecursionlimit(10**6)
n,q = map(int,input().split())
a=[[] for i in range(n)]
p=[]*n
l=[0]*n
ans=[0]*n

def dfs(parent,current,value):
    value += l[current]
    ans[current] = value
    for i in a[current]:
        if i == parent:
            continue
        dfs(current,i,value)


for i in range(n-1):
    t1,t2 = map(int,input().split())
    a[t1-1].append(t2-1)
    a[t2-1].append(t1-1)
    
for i in range(q):
    t1,t2 = map(int,input().split())
    l[t1-1]+=t2
dfs(-1,0,0)

print(" ".join(map(str,ans)))

### FIXED CODE ###

a=int(input())
s=input()


if a>=3200:
    print(s)
else:
    print("red")
n, k = map(int, input().split())
a = 0
li = []
for x in range(n):
    li.append(input().split())
    if n - k == 0:
        a = n - 1
    else:
        a = n - k
print(a)

### FIXED CODE ###

N, K = map(int, input().split())
j = 0
ls1 = []
ls2 = []

for i in range(1, K+1):
    d = int(input())
    ls1.append(input().split())
for i in range(len(ls1)):
    for j in ls1[i]:
        ls2.append(j)
        x = set(ls2)
print(N - len(x))
#!/usr/bin/env python

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

    ret = 0
    comb = 1
    x = m * ((m-1) ** (n-1))
    for i in range(k+1):
        if i >= 1:
            comb = comb * (n-i) // i % div
            x = x // (m-1)
        ret += comb * x % div
        ret %= div

    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
def modpow(x, y, mod):
    ret = 1
    z = x
    n = len(bin(y)) - 2
    for i in range(n):
        if ((y >> i) & 1):
            ret = ret * z % mod
        z = z * z % mod
    return ret

def modinv(x, mod):
    return modpow(x, mod-2, mod)

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

    c1 = 1
    c2 = 1
    for i in range(1, n):
        c1 = c1 * i % mod
        if i == k:
            c2 = modinv(c1, mod)
    c3 = modinv(c1, mod)
    c3_list = [0] * (k+1)
    c3_list[k] = c3
    for i in range(k-1, -1, -1):
        c3 = c3 * (n-(k-i)) % mod
        c3_list[i] = c3
    comb = (c1 * c2 % mod) * c3_list[0] % mod

    x = m * modpow(m-1, n-k-1, mod) % mod

    ret = x * comb % mod

    for i in range(1, k+1):
        c2 =c2 * (k-i+1) % mod
        comb = (c1 * c2 % mod) * c3_list[i] % mod
        x = x * (m-1) % mod

        ret += x * comb % mod
        ret %= mod

    print(ret)


if __name__ == '__main__':
    main()
# This program computes GCD and LCM
# -*- coding: utf-8
import sys


def gcd(a, b):
    while True:
        tmpb = b
        b = a % b
        a = tmpb
        if(b == 1):
            break
    return a


def lcm(a, b):
    for i in range(max([a, b]), a*b + 1):
        if(i % a == 0 and i % b == 0):
            return i
    return a*b


for i in sys.stdin:
    try:
        line = [int(k) for k in i.split(" ")]
        g = gcd(line[0], line[1])
        print(str(g) + " " + str(line[0]*line[1]//g))  # + str(lcm(line[0], line[1]))
    except:
        raise
        exit()

### FIXED CODE ###

# This program computes GCD and LCM
# -*- coding: utf-8
import sys


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


for i in sys.stdin:
    try:
        line = [int(k) for k in i.split(" ")]
        g = gcd(min(line), max(line))
        print(str(g) + " " + str(line[0]*line[1]//g))
    except:
        exit()
a,p = map(int,input().split())
print((3*a+b)//2)

### FIXED CODE ###

a,p = map(int,input().split())
print((3*a+p)//2)