Harryxun/stf_run huggingface dataset:
import sys
from collections import defaultdict

cnt = [0] * 3 * 10 ** 5
visited = [False] * 3 * 10 ** 5


def dfs(tree, p):
    global cnt, visited
    visited[p] = True
    for c in tree[p]:
        if visited[c]:
            continue
        cnt[c] += cnt[p]
        dfs(tree, c)


def main():
    input = sys.stdin.buffer.readline
    n, q = map(int, input().split())
    tree = defaultdict(list)
    for _ in range(n - 1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)

    # cnt = [0] * (n + 1)
    global cnt
    for _ in range(q):
        p, x = map(int, input().split())
        cnt[p] += x

    dfs(tree, 1)
    print(*cnt[1 : n + 1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import defaultdict


def dfs(tree, p, cnt, visited):
    visited[p] = True
    cnt_here = cnt[p]
    for c in tree.get(p):
        if visited[c]:
            continue
        cnt[c] += cnt_here
        dfs(tree, c, cnt, visited)


def main():
    input = sys.stdin.buffer.readline
    sys.setrecursionlimit(10 ** 9)
    n, q = map(int, input().split())
    tree = defaultdict(list)
    for _ in range(n - 1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    tree = dict(tree)
    cnt = [0] * (n + 1)

    for _ in range(q):
        p, x = map(int, input().split())
        cnt[p] += x
    visited = [False] * (n + 1)
    dfs(tree, 1, cnt, visited)
    print(*cnt[1:])


if __name__ == "__main__":
    main()
i = 1
while (1):
  n = int(raw_input())
  if n == 0:
    break
  print "Case %d: %d" % (i,n):
  i = i + 1

### FIXED CODE ###

i = 1
while(1):
  x = int(raw_input())
  if x == 0:
    break
  print "Case %d: %d" %(i,x)
  i = i + 1
n = input()
    a = list(map(int, input().split()))
    even = True
    count = 0
    while even:
        for ai in range(len(a)):
            if a[ai] % 2 != 0:
                even = False
                break

        if even:
            a = list(map(lambda num: num / 2, a))
            count += 1
        else:
            break
    print(count)

### FIXED CODE ###

n = input()
a = list(map(int, input().split()))
even = True
count = 0
while even:
    for ai in range(len(a)):
        if a[ai] % 2 != 0:
            even = False
            break

    if even:
        a = list(map(lambda num: num / 2, a))
        count += 1
    else:
        break
print(count)
s=input()
if s.count('R')==1: print(1)
elif s.count('R')==3: print(3)
else:
    if s="RSR": print(1)
    else: print(2)


### FIXED CODE ###

s=input().split('S')
if s.count('RRR'): print(3)
elif s.count('RR'): print(2)
elif s.count('R'): print(1)
else: print(0)
N = int(input())
S = [input() for i in range(N)]
 
from collections import defaultdict
def decode(s):
  d = defaultdict(int)
  for c in list(sorted(s)):
    d[c] += 1
  return d
 
decodes = [decode(s) for s in S]
 
hash_table = defaultdict(int)
for decode in decodes:
  hash_table[tuple(decode.items())] += 1
#print(hash_table)
import math
c_list = [int(math.factorial(v)/math.factorial(2)) for v in hash_table.values()]
#print(c_list)
count = sum(c_list)
 
print(count)

### FIXED CODE ###

N = int(input())
S = [input() for i in range(N)]
d = {}
S_trans = [''.join(sorted(list(s))) for s in S]
count = 0
for s in S_trans:
  if s in d:
    count += d[s]
    d[s] += 1
  else:
    d[s] = 1
print(count)
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
BIGNUM = 1000000007

zero_flag = False

last_ana = int(input())
blocks = [last_ana]

for _ in range(1, m):
    ana = int(input())
    blocks.append(ana - last_ana - 1)
    last_ana = ana

blocks.append(n - last_ana)

print(max(blocks))
b_max = max(blocks)

c = [1, 1]
for i in range(2, b_max):
    ctmp = c[i - 1] + c[i - 2]
    c.append(ctmp % BIGNUM)

if 0 in blocks:
    ans = 0
else:
    ans = 1
    for num in blocks:
        if num == 1:
            continue
        ans *= c[num - 1]
        if ans >= BIGNUM:
            ans %= BIGNUM

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n, m = map(int, input().split())
BIGNUM = 10 ** 9 + 7

if m > 0:
    last_ana = int(input())
    blocks = [last_ana]

    for _ in range(1, m):
        ana = int(input())
        blocks.append(ana - last_ana - 1)
        last_ana = ana
    blocks.append(n - last_ana)
else:
    blocks = [n + 1]

if 0 in blocks:
    ans = 0
else:
    b_max = max(blocks)
    c = [1, 1]
    for i in range(2, b_max):
        ctmp = c[i - 1] + c[i - 2]
        c.append(ctmp % BIGNUM)

    ans = 1
    for num in blocks:
        if num == 1:
            continue
        ans = (ans * c[num - 1]) % BIGNUM
        if ans == 0:
            break

print(ans)
a , b, c = map(int, input().split())
X = []
for i in range(min([a,b])):
  if a % i == 0 and b % i == 0:
    X.append(i)
print(X[-c])

### FIXED CODE ###

a , b, c = map(int, input().split())
X = []
for i in range(min([a,b])):
  if a % (i+1) == 0 and b % (i+1) == 0:
    X.append((i+1))
print(X[-c])
#!/usr/bin/env python3
import sys
MOD = 1000000007

def solve(N: int, A: "List[int]"):
    l, r = 0, 1
    sux, su, ans = A[0], A[0], 0
    while l < len(A):
        while r < len(A) and (sux ^ A[r]) == (su + A[r]):
            sux ^= A[r]
            su += A[r]
            r += 1
        ans += r - l
        sux ^= A[l]
        su -= A[l]
        l += 1
    return ans

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
MOD = 1000000007

def solve(N: int, A: "List[int]"):
    l, r = 0, 1
    sux, su, ans = A[0], A[0], 0
    while l < len(A):
        while r < len(A) and (sux ^ A[r]) == (su + A[r]):
            sux ^= A[r]
            su += A[r]
            r += 1
        ans += r - l
        sux ^= A[l]
        su -= A[l]
        l += 1
    return ans

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

if __name__ == '__main__':
    main()
A_count = int(input());
A = [int(n) for n in input().split()];
M_count = int(input());
M = [int(n) for n in input().split()];

def solve(start, target):
    if target == 0:
        return True;
    elif start >= A_count:
        return False;
    else:
        return solve(start + 1, target) or solve(start + 1, target - A[start]);

for m in M:
    if solve(0, m):
        print("yes");
    else:
        print("no");


### FIXED CODE ###

A_count = int(input());
A = [int(n) for n in input().split()];
M_count = int(input());
M = [int(n) for n in input().split()];

memo = [[None for i in range(2000)] for j in range(A_count + 1)];

def solve(start, target):
    if memo[start][target] is not None:
        return memo[start][target];
    if target == 0:
        return True;
    elif start >= A_count:
        return False;
    else:
        result = solve(start + 1, target) or solve(start + 1, target - A[start]);
        if result:
            memo[start][target] = True;
            return True;
        else:
            memo[start][target] = False;
            return False;

for m in M:
    if solve(0, m):
        print("yes");
    else:
        print("no");
while True:
    a,b = map(int,input().split())
    op = map(str,input().split())
    if ap == "?":
        break
    elif ap == "+":
        print (a + b)
    elif ap == "-":
        print (a - b)
    elif ap == "*":
        print (a * b)
    elif ap == "/":
        print (a / b)
    else:
        break

### FIXED CODE ###

while True:
    a,op,b = input().split()
    a = int(a)
    b = int(b)
    if op == '+':
        print (a + b)
    elif op == '-':
        print (a - b)
    elif op == '*':
        print (a * b)
    elif op == '/':
        print (a // b)
    else:
        break
def main():
    MOD = 998244353
    N = int(input())
    D = [int(i) for i in input().split()]
    if D[0] != 0:
        return print(0)
    from collections import Counter
    from math import factorial
    c = Counter(D)
    ans = 1
    for k, v in c.items():
        if k == 0 or k == 1:
            continue
        elif v == 0:
            return print(0)
        else:
            n = v + c[k-1] - 1
            r = c[k-1] - 1
            ans *= factorial(n) / factorial(r) / factorial(n - r)
            ans = int(ans) % MOD
            if c[k-1] > v:
                ans *= (c[k-1] - v)
            ans = int(ans) % MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    MOD = 998244353
    N = int(input())
    D = [int(i) for i in input().split()]
    if D[0] != 0:
        return print(0)
    from collections import Counter
    c = Counter(D)
    ans = 1
    for d in D[1:]:
        if d == 0:
            return print(0)
        ans *= c[d-1]
        ans %= MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()
# 1. S is Palindrome
# 2. S[1, (N-1)//2]
# 3. S[(N+3)//2, N]

def is_palindrome(str):
  i, j = 0, len(str)-1
  while i != j:
    if str[i] != str[j]:
      return False
    i += 1
    j -= 1

  return True

s = input()
n = len(s)
print(is_palindrome(s) and is_palindrome(s[0:((n-1)//2)]) and is_palindrome(s[(n+3)//2-1:n]))

### FIXED CODE ###

def is_palindrome(str):
  i, j = 0, len(str)-1
  while i <= j:
    if str[i] != str[j]:
      return False
    i += 1
    j -= 1

  return True

s = input()
n = len(s)
if is_palindrome(s) and is_palindrome(s[0:((n-1)//2)]) and is_palindrome(s[(n+3)//2-1:]):
  print("Yes")
else:
  print("No")
vN, M = map(int, input().split())
s = [-1]
c = [-1]
OK = True
x = 0
for i in range(M):
    s_, c_ = map(int, input().split())
    if N != 1 and s_ == 1 and c_ == 0:
        OK = False
    ok = True
    for i in range(len(s)):
        if s[i] == s_:
            ok = False
            if c[i] != c_:
                OK = False
                break
            break
    if ok:
        s.append(s_)
        c.append(c_)
        x += (10 ** (N - s_)) * c_

if N != 1 and x < 10 ** (N - 1):
    x += 10 ** (N - 1)

if OK:
    print(x)
else:
    print(-1)


### FIXED CODE ###

N, M = map(int, input().split())
s = [-1]
c = [-1]
OK = True
x = 0
for i in range(M):
    s_, c_ = map(int, input().split())
    if N != 1 and s_ == 1 and c_ == 0:
        OK = False
    ok = True
    for i in range(len(s)):
        if s[i] == s_:
            ok = False
            if c[i] != c_:
                OK = False
                break
            break
    if ok:
        s.append(s_)
        c.append(c_)
        x += (10 ** (N - s_)) * c_

if N != 1 and x < 10 ** (N - 1):
    x += 10 ** (N - 1)

if OK:
    print(x)
else:
    print(-1)
2 1 1 3

### FIXED CODE ###

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

if k<=a:
    print(k)
elif a<k<=a+b:
    print(a)
else:
    print(a-(k-(a+b)))
x = raw_input().split()
y = map(int,x)
a = y[0]
b = y[1]
c = a*b
d = (a+b)*2
print c, d


### FIXED CODE ###

x=int(input())
print(x*x*x)
K = int(input())
S = input()
if len(S) =< K:
 print(S)
else:
 print(S[:K+1] + '...')

### FIXED CODE ###

K = int(input())
S = input()
if len(S) <= K:
 print(S)
else:
 print(S[:K] + '...')
import numpy as np


def function(N, K, A):
    pre = [int(A[i]) for i in range(K)]
    for i in range(1, N-K+1):
        now = [int(A[i]) for i in range(i, K+i)]
        if np.prod(now) > np.prod(pre):
            print('Yes')
        else:
            print('No')
        pre = now


if __name__ == '__main__':
    numbers = input().split()
    N = int(numbers[0])
    K = int(numbers[1])
    A = input().split()
    function(N, K, A)


### FIXED CODE ###

def function(N, K, A):
    for i in range(0, N-K):
        if A[K+i] > A[i]:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    numbers = input().split()
    N = int(numbers[0])
    K = int(numbers[1])
    A = input().split()
    A = [int(a) for a in A]
    function(N, K, A)
N = int(input())

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]



def insu(num):
    from collections import defaultdict
    primes = get_sieve_of_eratosthenes(int(num**(1 / 2)) + 1)
    res = defaultdict(int)
    for p in primes:
        while num % p == 0:
            res[p] += 1
            num //= p
    return res
ins = insu(N)
ans = 0
for v in ins.values():
    counter = 1
    while v >= counter:
        v -= counter
        counter += 1
        ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
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

def insu(num):
    from collections import defaultdict
    div_prime = [d for d in make_divisors(num) if is_prime(d)]
    res = defaultdict(int)
    for d in div_prime:
        while num % d == 0:
            num //= d
            res[d] += 1
    return res
ins = insu(N)
ans = 0
for v in ins.values():
    counter = 1
    while v >= counter:
        v -= counter
        counter += 1
        ans += 1
print(ans)
n = 1
if b == 1:
    print(0)
else:
    while a*n-(n-1) < b:
        n += 1
    print(n)

### FIXED CODE ###

a,b = map(int, input().split())
n = 1
if b == 1:
    print(0)
else:
    while a*n-(n-1) < b:
        n += 1
    print(n)
import math

N,K = map(int,input().rstrip().split(" "))
if N > 0:
  print(math.ceil(math.log(N+1,K)))
else:
  print(1)

### FIXED CODE ###

N,R = map(int,input().rstrip().split(" "))
if N >= 10:
  print(R)
else:
  print(R + (10-N)*100)
c=input()
list=[a,i,u,e,o]
if c in list:
  print('vowel')
else:
  ('consonant')

### FIXED CODE ###

c=input()
list=['a','i','u','e','o']
if c in list:
  print('vowel')
else:
  print('consonant')
n = int(input())

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

s = []
t = []


import collections

for i in range(0,n//2,2):
	s.append(v[i])
for i in range(1,n//2,2):
	t.append(v[i])

S = Counter(s)
	
T = Counter(t)

x = S.most_common()[0][0]  #sの最頻値

y = S.most_common()[1][0]  #sの2番目に多いやつ

z = T.most_common()[0][0]　

w = T.most_common()[1][0]

if x!=z:
	print(n-S.most_common()[0][1]-T.most_common()[0][1])
elif y>w:
	print(n-S.most_common()[0][1]-S.most_common()[1][1])
else:
	print(n-S.most_common()[0][1]-T.most_common()[1][1])


### FIXED CODE ###

import collections

n = int(input())
v = list(map(int,input().split()))
a = [v[i] for i in range(n) if i%2==0]
b = [v[i] for i in range(n) if i%2==1]

a = collections.Counter(a)
b = collections.Counter(b)

A = a.most_common()[:2]
A.append(("x",0))
B = b.most_common()[:2]
B.append(("x",0))
if A[0][0]==B[0][0]:
    print(n-max(A[0][1]+B[1][1],A[1][1]+B[0][1]))
else:
    print(n-A[0][1]-B[0][1])
s=input()
if s.count("1")==len(s):
    print(1)
else:
    i=0
    while s[i]!="1":
        i+=1
    print(s[i])

### FIXED CODE ###

s=input()
k=int(input())-1
if s.count("1")==len(s):
    t=k
    print(1)
else:
    i=0
    while s[i]=="1":
        i+=1
    if k<i:
        print(1)
    else:
        print(s[i])
W, H, x, y, r = map(int, input().split())
if x >= r and x + r <= W and y >= r and y + r <= H
print("Yes")
else:
print("No")


### FIXED CODE ###

W, H, x, y, r = map(int, input().split())
if x >= r and x + r <= W and y >= r and y + r <= H:
  print("Yes")
else:
  print("No")
import math
from sympy import isprime
N = int(input())

z = []

def isprime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
    
def judge(n):
    if isprime(n):
        return True
    for i in range(2, int(math.sqrt(n)+1)):
        if n % i == 0:
            n = n // i
            while n != 1:
                if n % i != 0:
                    return False
                n //= i
            return True
        return False


ans = 0
num = []
i = 2
while N != 1:
    
    if isprime(N):
        ans += 1
        break
    if N % i == 0 and judge(i): 
        N //= i
        ans += 1
        num.append(i)

    i += 1
    



print(ans)

### FIXED CODE ###

import math

N = int(input())

def judge(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            n //= i
            while n != 1:
                if n % i != 0:
                    return False
                n //= i
            return True
    return True


def get_prime(n):
    if n <= 1:
        return []
    prime = [2]
    limit = int(math.sqrt(n))

    data = [i + 1 for i in range(2, n, 2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data

ans = 0
i = 2
limit = int(math.sqrt(N))
while N != 1:
    
    if i > limit:
        if N > i:
            ans += 1
        break
    if N % i == 0 and judge(i): 
        N //= i
        ans += 1
        
    i += 1
    
print(ans)
N,K = map(int,input().split())
A = list(map(int,input().split()))
A_unique = list(set(A))
N_unique = len(A_unique)

a = [A.count(A_unique[i]) for i in range(N_unique)]
a_sort = sorted(a)

M = N_unique-K
if M <= 0:
	print(0)
	exit()

ans = 0
for i in range(0,M):
	ans += a_sort[i]
print(ans)


### FIXED CODE ###

str = input()
list = list(str)

print(int(list[0])+int(list[1])+int(list[2]))
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
    def size(self,x):
      return -self.parents[self.find(x)]
    
    def roots(self):
      return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
      return len(self.roots())
    
n,m = map(int,input().split())  
uf = UnionFind(n)

for i in range(m):
  a, b = map(int,input().split())
  uf.union(a,b)
print(uf.group_count()-1)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
    def size(self,x):
      return -self.parents[self.find(x)]
    
    def roots(self):
      return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
      return len(self.roots())
    
n,m = map(int,input().split())  
uf = UnionFind(n)

for i in range(m):
  a, b = map(int,input().split())
  uf.union(a-1,b-1)
print(uf.group_count()-1)
N = int(input())

cnt = 0
cnt2 = 0
for i in (1, range(N+1), 2):
    cnt = 0
    for j in (1, range(N+1)):
        if j > i:
            cnt = 0
            break
        if i % j == 0:
            cnt += 1

    if cnt == 8:
        cnt2 += 1

print(cnt2)


### FIXED CODE ###

N = int(input())

cnt = 0
cnt2 = 0
for i in range(1, N+1, 2):
    cnt = 0
    for j in range(1, N+1):
        if j > i:
            break
        if i % j == 0:
            cnt += 1

    if cnt == 8:
        cnt2 += 1


print(cnt2)
import itertools

def memo_rec(N):
    L = ['A', 'T', 'G', 'C']
    MOD = 10 ** 9 + 7
    dic = {}
    def rec(l1, l2, l3, k):
        s = l1 + l2 + l3
        if s in ["AGC", "ACG", "GAC"]:
            return 0
        if k == 1:
            if (l1 == 'A' and l2 == 'C') or (l1 == 'C' and l2 == 'G') or (l1 == 'G' and l3 == 'C') or (l2 == 'G' and l3 == 'C') or (l1 == 'G' and l2 == 'C'):
                return 3
            else:
                return 4
        if s + str(k) in dic:
            return dic[s + str(k)]
        else:
            ret = 0
            for x in L:
                ret = (ret + rec(x, l1, l2, k - 1)) % MOD
            dic[s + str(k)] = ret
            return ret
    ret = 0
    for s in itertools.product(L, repeat = 3):
        ret = (ret + rec(s[0], s[1], s[2], N - 3)) % MOD
    return ret

N = int(input())
print(memo_rec(N))


### FIXED CODE ###

import itertools
def memo_rec(N):
    if N == 3:
        return 61
    if N == 4:
        return 230
    L = "ATGC"
    MOD = 10 ** 9 + 7
    dic = {}
    def rec(s, k):
        if s.count("AGC"):
            return 0
        for i in range(3):
            t1, t2 = s[i], s[i + 1]
            if (s[:i] + t2 + t1 + s[i+2:]).count("AGC"):
                return 0
        if k == 0:
            return 1
        if s + str(k) in dic:
            return dic[s + str(k)]
        else:
            ret = 0
            for x in L:
                ret = (ret + rec(str(x + s[:3]), k - 1)) % MOD
            dic[s + str(k)] = ret
            return ret
    ret = 0
    for s in itertools.product(L, repeat = 4):
        t = ''
        for x in s:
            t += x
        ret = (ret + rec(t, N - 4)) % MOD
    return ret

N = int(input())
print(memo_rec(N))
import itertools


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

a = []
b = []
c = []
d = []

for i in range(Q):
    ai, bi, ci, di = map(int, input().split())
    a.append(ai)
    b.append(bi)
    c.append(ci)
    d.append(di)

A = [i for i in range(1, M+1)] # [1, 2, 3, 4, ... M]

A_pattern = list(itertools.combinations_with_replacement(A, M)) # 10^5

ans = 0

for a_pattern in A_pattern: # 数列全部調べる
    ansi = 0
    for i in range(Q): # 得点になるかどうか調べる
        if a_pattern[b[i]] - a_pattern[a[i]] == c[i]: # A[bi] - A[ai] == ci -> ansi += di
            ansi += d[i]

    ans = max(ans, ansi)


print(ans)


### FIXED CODE ###

import itertools


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

a = []
b = []
c = []
d = []

for i in range(Q):
    ai, bi, ci, di = map(int, input().split())
    a.append(ai)
    b.append(bi)
    c.append(ci)
    d.append(di)

A = [i for i in range(1, M+1)] # [1, 2, 3, 4, ... M]

A_pattern = list(itertools.combinations_with_replacement(A, N))

ans = 0

for a_pattern in A_pattern: # 数列全部調べる
    ansi = 0
    for i in range(Q): # 得点になるかどうか調べる
        if a_pattern[b[i]-1] - a_pattern[a[i]-1] == c[i]: # A[bi] - A[ai] == ci -> ansi += di
            ansi += d[i]

    ans = max(ans, ansi)


print(ans)
l = [1,2,3]
a = int(input())
b = int(input())
c = [o for o in l if o in not [a,b]]
print(c[0])

### FIXED CODE ###

l = [1,2,3]
a = int(input())
b = int(input())
c = [o for o in l if o not in [a,b]]
print(c[0])
a=int(input())
b=int(input())
ans= (a+b)//2 if (a+b)%2 == 0 else (a+b)//2+1
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
ans= (a+b)//2 if (a+b)%2 == 0 else (a+b)//2+1
print(ans)
a,b=map(str,input().split())
if a=="H" and b="H" or a=="D" and b="D":
  print("H")
elif a=="H" and b="D" or a=="D" and b="H":
  print("D")


### FIXED CODE ###

a,b=map(str,input().split())
if a==b:
  print("H")
else:
  print("D")