Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=input()
p=0
q=0
r=0
i=0
while i<n-1:
  while a[i]=="<":
    i+=1
    p+=1
    if i==n-1:
      print(r+p*(p+1)//2)
      exit(0)
  while a[i]==">":
    i+=1
    q+=1
    if i==n-1:
      break
  r+=p*(p+1)//2+q*(q+1)//2-min(p,q)
  p=0
  q=0
print(r)

Fixed submission:
a=input()
n=len(a)
p=0
q=0
r=0
i=0
while i<n:
  while a[i]=="<":
    i+=1
    p+=1
    if i==n:
      print(r+p*(p+1)//2)
      exit(0)
  while a[i]==">":
    i+=1
    q+=1
    if i==n:
      break
  r+=p*(p+1)//2+q*(q+1)//2-min(p,q)
  p=0
  q=0
print(r)
Buggy python submission (verdict: Runtime Error):
import math
a,b=map(int,input().split())
c=math.gcd(a,b)
d=[]
for i in range(2,int(c**0.5)+2):
    while c%i==0:
        c//=i
        d.append(i)
if c!=1:
    d.append(c)
print(d)
print(len(set(d))+1)

Fixed submission:
import math
a,b=map(int,input().split())
while b!=0:
    a,b=b,a%b
c=a
d=[]
for i in range(2,int(c**0.5)+2):
    while c%i==0:
        c//=i
        d.append(i)
if c!=1:
    d.append(c)
print(len(set(d))+1)

Buggy python submission (verdict: Runtime Error):
import math
a,b=map(int,input().split())
c=math.gcd(a,b)
d=[]
for i in range(2,int(c**0.5)+2):
    while c%i==0:
        c//=i
        d.append(i)
if c!=1:
    d.append(c)
print(len(set(d))+1)

Fixed submission:
import math
a,b=map(int,input().split())
while b!=0:
    a,b=b,a%b
c=a
d=[]
for i in range(2,int(c**0.5)+2):
    while c%i==0:
        c//=i
        d.append(i)
if c!=1:
    d.append(c)
print(len(set(d))+1)

Buggy python submission (verdict: Runtime Error):
import math
a,b=map(int,input().split())
c=math.gcd(a,b)
d=[]
for i in range(2,int(c**0.5)+1):
    while c%i==0:
        c//=i
        d.append(i)
print(len(set(d))+1)

Fixed submission:
import math
a,b=map(int,input().split())
while b!=0:
    a,b=b,a%b
c=a
d=[]
for i in range(2,int(c**0.5)+2):
    while c%i==0:
        c//=i
        d.append(i)
if c!=1:
    d.append(c)
print(len(set(d))+1)
Buggy python submission (verdict: Runtime Error):
s=input()
n=len(s)
for i in range(n//2):
    if s[2*i]=="L":
        print("No")
        break
else:
    for j in range((n+1)//2):
        if s[2*i+1]=="R":
            print("No")
            break
    else:print("Yes")

Fixed submission:
s=input()
n=len(s)
p=0
for i in range(n):
  if i%2==0:
    if s[i]=="L":
      p=1
  else:
    if s[i]=="R":
      p=1
if p==0:
  print("Yes")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
s=input()
n=len(s)
for i in range((n+1)//2):
    if s[2*i]=="L":
        print("No")
        exit()
for j in range(n//2):
    if s[2*i+1]=="R":
        print("No")
        exit()
print("Yes")

Fixed submission:
s=input()
n=len(s)
p=0
for i in range(n):
  if i%2==0:
    if s[i]=="L":
      p=1
  else:
    if s[i]=="R":
      p=1
if p==0:
  print("Yes")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
s=input()
n=len(s)
for i in range(n//2):
    if s[2*i]=="L":
        print("No")
        exit()
for j in range((n+1)//2):
    if s[2*i+1]=="R":
        print("No")
        exit()
print("Yes")

Fixed submission:
s=input()
n=len(s)
p=0
for i in range(n):
  if i%2==0:
    if s[i]=="L":
      p=1
  else:
    if s[i]=="R":
      p=1
if p==0:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Time Limit Exceeded):
n,k,q=map(int,input().split())
a=[int(input()) for i in range(q)]
for j in range(n):
    if k+a.count(j+1)-q>0:
        print("Yes")
    else:
        print("No")

Fixed submission:
n,k,q=map(int,input().split())
a=[0]*n
for i in range(q):
  b=int(input())
  a[b-1]+=1
for i in range(n):
  if k-q+a[i]>0:
    print("Yes")
  else:
    print("No")

Buggy python submission (verdict: Time Limit Exceeded):
n,k,q=map(int,input().split())
a=[input() for i in range(q)]
for j in range(n):
    if k+a.count(str(j+1))-q>0:
        print("Yes")
    else:
        print("No")

Fixed submission:
n,k,q=map(int,input().split())
a=[0]*n
for i in range(q):
  b=int(input())
  a[b-1]+=1
for i in range(n):
  if k-q+a[i]>0:
    print("Yes")
  else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    a.sort()
    a[n-1]/=2
a=[int(b) for b in a]
print(sum(a))

Fixed submission:
import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]*=-1
heapq.heapify(a)
for i in range(m):
  heapq.heappush(a,(heapq.heappop(a)+1)//2)
print(-sum(a))
Buggy python submission (verdict: Runtime Error):
print((int(input())**3)

Fixed submission:
print((int(input()))**3)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
q=0
for i in range(0,n):
    p=0
    for j in range(i,n-1):
        if a[j]>=a[j+1]:
          p+=1
        else:
            break
    if p>q:
        q=p
print(q)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
i=0
p=q=0
for i in range(n-1):
  if a[i]>=a[i+1]:
    p+=1
  else:
    q=max(p,q)
    p=0
q=max(p,q)
print(q)
Buggy python submission (verdict: Runtime Error):
a=input()
if a[0]==a[1]:
  print("Bad")
  elif a[1]==a[2]:
    print("Bad")
    elif a[2]==a[3]:
      print("Bad")
      else:
        print("Good")

Fixed submission:
s=input()
if s[0]==s[1] or s[1]==s[2] or s[2]==s[3]:
  print("Bad")
else:
  print("Good")

Buggy python submission (verdict: Runtime Error):
a=list(input())
if a[0]==a[1]:
  print("Bad")
  elif a[1]==a[2]:
    print("Bad")
    elif a[2]==a[3]:
      print("Bad")
      else:
        print("Good")

Fixed submission:
s=input()
if s[0]==s[1] or s[1]==s[2] or s[2]==s[3]:
  print("Bad")
else:
  print("Good")

Buggy python submission (verdict: Runtime Error):
a=map(int,input().split())
if a[0]==a[1]:
  print("Bad")
  elif a[1]==a[2]:
    print("Bad")
    elif a[2]==a[3]:
      print("Bad")
      else:
        print("Good")

Fixed submission:
s=input()
if s[0]==s[1] or s[1]==s[2] or s[2]==s[3]:
  print("Bad")
else:
  print("Good")

Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
if a==b:
  print("Bad")
  elif b==c:
    print("Bad")
    elif c==d:
      print("Bad")
      else:
        print("Good")

Fixed submission:
s=input()
if s[0]==s[1] or s[1]==s[2] or s[2]==s[3]:
  print("Bad")
else:
  print("Good")

Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
if a==b:
  print("bad")
  elif b==c:
    print("bad")
    elif c==d:
      print("bad")
      else:
        print("good")

Fixed submission:
s=input()
if s[0]==s[1] or s[1]==s[2] or s[2]==s[3]:
  print("Bad")
else:
  print("Good")

Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
if a==b:
  print("bad")
  else if b==c:
    print("bad")
    else if c==d:
      print("bad")
      else:
        print("good")

Fixed submission:
s=input()
if s[0]==s[1] or s[1]==s[2] or s[2]==s[3]:
  print("Bad")
else:
  print("Good")

Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
if a=b:
  print("bad")
  else if b=c:
    print("bad")
    else if c=d:
      print("bad")
      else:
        print("good")

Fixed submission:
s=input()
if s[0]==s[1] or s[1]==s[2] or s[2]==s[3]:
  print("Bad")
else:
  print("Good")
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=[0]*(n+1)
b=[int(input()) for i in range(m)]
a[0]=1
j=0
if b[0]==1:
  a[1]=0
  if j!=1:
    j=1
else:
  a[1]=1
for i in range(2,n+1):
  if i==b[j]:
    if j<m-1:
      j+=1
  else:
    a[i]=(a[i-1]+a[i-2])%(10**9+7)
print(a[n])

Fixed submission:
n,m=map(int,input().split())
a=[0]*(n+1)
b=[int(input()) for i in range(m)]
a[0]=a[1]=1
if m==0:
  for i in range(2,n+1):
    a[i]=(a[i-1]+a[i-2])%(10**9+7)
else:
  j=0
  if b[0]==1:
    a[1]=0
    if m>1:
      j=1
  for i in range(2,n+1):
    if i==b[j]:
      if j<m-1:
        j+=1
    else:
      a[i]=(a[i-1]+a[i-2])%(10**9+7)
print(a[n])

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=[0]*(n+1)
b=[int(input()) for i in range(m)]
a[0]=1
j=0
if b[0]==1:
  a[1]=0
  j=1
else:
  a[1]=1
for i in range(2,n+1):
  if i==b[j]:
    if j<m-1:
      j+=1
  else:
    a[i]=(a[i-1]+a[i-2])%(10**9+7)
print(a[n])

Fixed submission:
n,m=map(int,input().split())
a=[0]*(n+1)
b=[int(input()) for i in range(m)]
a[0]=a[1]=1
if m==0:
  for i in range(2,n+1):
    a[i]=(a[i-1]+a[i-2])%(10**9+7)
else:
  j=0
  if b[0]==1:
    a[1]=0
    if m>1:
      j=1
  for i in range(2,n+1):
    if i==b[j]:
      if j<m-1:
        j+=1
    else:
      a[i]=(a[i-1]+a[i-2])%(10**9+7)
print(a[n])

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=[0]*(n+1)
b=[int(input()) for i in range(m)]
a[0]=1
j=0
if b[0]==1:
  a[1]=0
  j=1
else:
  a[1]=1
for i in range(2,n+1):
  if i==b[j]:
    if j<m-1:
      j+=1
  else:
    a[i]=a[i-1]+a[i-2]
print(a[n])

Fixed submission:
n,m=map(int,input().split())
a=[0]*(n+1)
b=[int(input()) for i in range(m)]
a[0]=a[1]=1
if m==0:
  for i in range(2,n+1):
    a[i]=(a[i-1]+a[i-2])%(10**9+7)
else:
  j=0
  if b[0]==1:
    a[1]=0
    if m>1:
      j=1
  for i in range(2,n+1):
    if i==b[j]:
      if j<m-1:
        j+=1
    else:
      a[i]=(a[i-1]+a[i-2])%(10**9+7)
print(a[n])
Buggy python submission (verdict: Runtime Error):
s=input()
print(700+s.count(o)*100)

Fixed submission:
s=input()
print(700+s.count("o")*100)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

MAXNUM = 10 ** 6 + 10
a = [i for i in range(1, MAXNUM)]

def calc(i):
    l, r = 0, MAXNUM
    while r-l > 1:
        mid = (l+r)//2
        if mid * i < N:
            l = mid
        else:
            r = mid
    return l

cnt = 0
for i in range(1, MAXNUM):
    cnt += calc(i)

print(cnt)


Fixed submission:
N = int(input())

MAXNUM = 10 ** 6 + 10
a = [i for i in range(1, MAXNUM)]

def calc(i):
    l, r = 0, MAXNUM
    while r-l > 1:
        mid = (l+r)//2
        if mid * i < N:
            l = mid
        else:
            r = mid
    return l

cnt = 0
for i in range(1, MAXNUM):
    cnt += calc(i)

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353

N, K = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(K)]

S = set()
for l, r in lr:
    for j in range(l, r+1):
        S.add(j)

dp = [0] * (N+1)
dp[1] = 1
for i in range(1, N+1):
    for s in S:
        if i+s <= N:
            dp[i+s] += dp[i]
            dp[i+s] %= MOD

print(dp[-1])


Fixed submission:
N, K = map(int, input().split())
# N: 処理する区間の長さ

data0 = [0]*(N+1)
data1 = [0]*(N+1)
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        s %= MOD
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

MOD = 998244353


lr = [list(map(int, input().split())) for _ in range(K)]

dp = [0] * (N+10)
add(1, 2, 1)
for i in range(1, N+1):
    dp[i] = query(i, i+1) % MOD
    for l, r in lr:
        if i+l > N+1: continue
        add(l+i, min(i+r+1, N+1), dp[i])
    

print(dp[N])
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1,b-1
    edge[a].append(b)
    edge[b].append(a)

visited = [0] * N
cnt = 0
def dfs(n):
    global cnt
    if visited[n]: return
    cnt += 1
    visited[n] = True
    for nv in edge[n]:
        dfs(nv)

ans = 0
for i in range(N):
    cnt = 0
    dfs(i)
    ans = max(ans, cnt)
print(ans)


Fixed submission:
N, M = map(int, input().split())

class UnionFind():
    '''
    UnionFindでグラフの状態を管理する
    '''
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        '''
        ルートのノードを見つける
        '''
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        '''
        ノード同士を連結する
        '''
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]

uf = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    uf.unite(a-1, b-1)

ans = 0
for i in range(N):
    ans = max(ans, uf.count(i))

print(ans)
Buggy python submission (verdict: Runtime Error):
import math
NOTCOM = "not coprime"
SETWISE = "setwise coprime"
PAIRWISE = "pairwise coprime"
MAX_A = 100

def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = [0] * MAX_A
    for a in A:
        c[a] += 1
    pairwse = True
    for i in range(2, MAX_A):
        cnt = 0
        for j in range(i, MAX_A, i):
            cnt += c[j]
        if cnt > 1: pairwse = False
    if pairwse:
        return PAIRWISE
    
    allgcd = A[0]
    for a in A:
        allgcd = math.gcd(allgcd, a)
    if allgcd == 1: return SETWISE
    return NOTCOM

print(main())


Fixed submission:
import math
NOTCOM = "not coprime"
SETWISE = "setwise coprime"
PAIRWISE = "pairwise coprime"

def calc_prime(N):
    prime, i = set(), 1
    while i * i <= N:
        if N % i == 0:
            yield i
            if i != N//i: yield N//i
        i += 1

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = list(set(A))
    cnt2 = 0
    cnt3 = 0
    allgcd = A[0]
    for a in A:
        allgcd = math.gcd(allgcd, a)
        if a % 2 == 0:
            cnt2 += 1
        if a % 3 == 0:
            cnt3 += 1
    if allgcd != 1:
        return NOTCOM
    
    if cnt2 >= 2 or cnt3 >= 2:
        return SETWISE

    allprime = set()
    for a in A:
        for t in calc_prime(a):
            if t in allprime and t != 1:
                return SETWISE
            allprime.add(t)
    return PAIRWISE

print(main())
Buggy python submission (verdict: Time Limit Exceeded):
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))

def check(k):
    cnt = 0
    for a in A:
        cnt += math.ceil(a/k) - 1
    return cnt <= K

l, r = 0, 10**30
while r - l > 1:
    mid = (r + l) // 2
    if check(mid):
        r = mid
    else:
        l = mid

print(r)


Fixed submission:
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))

def check(k):
    cnt = 0
    for a in A:
        cnt += math.ceil(a/k) - 1
    return cnt <= K

l, r = 0, 10**10
while r - l > 1:
    mid = (r + l) // 2
    if check(mid):
        r = mid
    else:
        l = mid

print(r)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))
tmp = 1
ans = []
for i in range(N):
    if i+1 < K:
        tmp *= A[i]
        continue
    tmp *= A[i]
    ans.append(tmp)
    tmp //= A[i-K+1]

for i in range(1,len(ans)):
    if ans[i-1] < ans[i]:
        print("Yes")
    else:
        print("No")



Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
tmp = 1
ans = []
for i in range(N):
    if i+1 <= K:
        continue
    if A[i-K] < A[i]:
        print("Yes")
    else:
        print("No")
Buggy python submission (verdict: Runtime Error):
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

cnt = 0
def dfs(a, b, t):
    global cnt
    cnt = max(cnt, a+b)
    if a < N and t + A[a] <= K:
        dfs(a+1, b, t+A[a])
    if b < M and t + B[b] <= K:
        dfs(b+1, a, t+B[b])
    
dfs(0, 0, 0)
print(cnt)


Fixed submission:
from itertools import accumulate
from bisect import bisect_right
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

def ruiseki(lst):
    return [0]+list(accumulate(lst))

ar = ruiseki(A)
br = ruiseki(B)
ans = 0
for i in range(1+N):
    left = K - ar[i]
    if left < 0:
        continue
    bidx = bisect_right(br, left) - 1
    ans = max(ans,i+bidx)

print(ans)
Buggy python submission (verdict: Runtime Error):
from itertools import product
import numpy as np

N, M, X = map(int, input().split())
C = [0] * N
A = [[0] * M for _ in range(N)]
for i in range(N):
    c = list(map(int, input().split()))
    C[i] = c[0]
    A[i] = c[1:]

def calc(p):
    cnt = np.dot(np.array(list(p)), np.array(A))
    return np.dot(np.array(list(p)), np.array(C)) if all(i >= X for i in cnt) else 10 ** 30

ans = 10 ** 30
for p in product(range(2), repeat=N):
    ans = min(ans, calc(p))

print(ans if ans < 10 ** 30 else -1)


Fixed submission:
from itertools import product
N, M, X = map(int, input().split())
C = [0] * N
A = [[0] * M for _ in range(N)]
for i in range(N):
    c = list(map(int, input().split()))
    C[i] = c[0]
    A[i] = c[1:]

def calc(p):
    ret = 0
    cnt = [0] * M
    for i, v in enumerate(p):
        if v == 1:
            for ia, a in enumerate(A[i]):
                cnt[ia] += a
            ret += C[i]
    return ret if all(i >= X for i in cnt) else 10 ** 30
    

ans = 10 ** 30
for p in product(range(2), repeat=N):
    ans = min(ans, calc(p))

print(ans if ans < 10 ** 30 else -1)
Buggy python submission (verdict: Runtime Error):
N, M, K = map(int, input().split())
mod = 998244353
# 全て異なる色で塗った場合のリストを作る
d = [0] * (N+1)
d[0] = M
for i in range(N):
    d[i+1] = d[i] * (M-1) % mod

def createFacArr(n, mod):
    '''
    二項係数計算用の配列の作成

    Parameters
    n : int
        配列のサイズ
    mod : int
        あまり

    Returns
    fac : list
        階乗のリスト
    finv : list
        modの逆元のリスト
    ivn : list
    '''
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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
    return fac, finv

def comb(n ,k, mod, fac, finv):
    '''
    二項係数の計算

    Parameters
    n : int
        元集合
    k : int
        元集合から選択する数
    mod : int
        あまり
    fac : list
        階乗のリスト
    finv : list
        逆元のリスト
    
    Returns
    c : int
        nCkの組み合わせの数
    '''
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

fac, finv = createFacArr(N, mod)
ans = d[N-1]
#print(d)
for i in range(K):
    ans += d[N-2-i] * comb(N-1, i+1, mod, fac, finv)
    ans %= mod

print(ans)


Fixed submission:
N, M, K = map(int, input().split())
mod = 998244353
# 全て異なる色で塗った場合のリストを作る
d = [0] * (N+1)
d[0] = M
for i in range(N):
    d[i+1] = d[i] * (M-1) % mod

def createFacArr(n, mod):
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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
    return fac, finv

def comb(n ,k, mod, fac, finv):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

fac, finv = createFacArr(N+10, mod)
ans = d[N-1]
#print(d)
for i in range(K):
    ans += d[N-2-i] * comb(N-1, i+1, mod, fac, finv)
    ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]

def calc(p):
    ret = 0
    # 各条件を満たしていれば、dを加算していく
    for a, b, c, d in abcd:
        if p[b-1] - p[a-1] == c:
            ret += d
    return ret

ans = [0]
def dfs(s, n):
    if n == N:
        ans[0] = max(ans[0], calc(list(map(int,s))))
        return
    for i in range(int(s[-1]),M+1):
        dfs(s+str(i), n+1)

for i in range(1, M+1):
    dfs(str(i), 1)

print(ans[0])


Fixed submission:
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]

def calc(p):
    ret = 0
    # 各条件を満たしていれば、dを加算していく
    for a, b, c, d in abcd:
        if p[b-1] - p[a-1] == c:
            ret += d
    return ret

ans = [0]
def dfs(s):
    if len(s) == N:
        ans[0] = max(ans[0], calc(s))
        return
    for i in range(s[-1],M+1):
        dfs(s+[i])

for i in range(1, M+1):
    dfs([i])

print(ans[0])

Buggy python submission (verdict: Runtime Error):
from itertools import permutations
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]

def calc(p):
    ret = 0
    # 各条件を満たしていれば、dを加算していく
    for a, b, c, d in abcd:
        if p[b-1] - p[a-1] == c:
            ret += d
    return ret

ans = 0
for p in permutations(range(1,1+M)):
    p = list(p)[:N]
    ans = max(ans, calc(p))
print(ans)


Fixed submission:
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]

def calc(p):
    ret = 0
    # 各条件を満たしていれば、dを加算していく
    for a, b, c, d in abcd:
        if p[b-1] - p[a-1] == c:
            ret += d
    return ret

ans = [0]
def dfs(s):
    if len(s) == N:
        ans[0] = max(ans[0], calc(s))
        return
    for i in range(s[-1],M+1):
        dfs(s+[i])

for i in range(1, M+1):
    dfs([i])

print(ans[0])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
S = list(input())
S.reverse()
L = len(S)
dp = [0] * (L+1)
tmp = 0
for i in range(L):
    tmp += int(S[i]) * pow(10, i)
    tmp %= 2019
    dp[i] = tmp

c = Counter(dp)
ans = 0
for i, v in c.items():
    ans += v * (v-1) // 2

print(ans)


Fixed submission:
from collections import Counter
S = list(input())
S.reverse()
L = len(S)
dp = [0] * (L+1)
tmp = 0
for i in range(L):
    tmp += int(S[i]) * pow(10, i, 2019)
    tmp %= 2019
    dp[i] = tmp

c = Counter(dp)
ans = 0
for i, v in c.items():
    ans += v * (v-1) // 2

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import Counter
N, X, Y = map(int, input().split())
ans = []

for i in range(N):
    for j in range(i+1, N):
        ans.append(min(j-i, 1+abs(i-x)+abs(j-Y)))

c = Counter(ans)
for i in range(1,N):
    print(c[i])


Fixed submission:
from collections import Counter
N, X, Y = map(int, input().split())
X, Y = X-1, Y-1
ans = []

for i in range(N):
    for j in range(i+1, N):
        ans.append(min(j-i, 1+abs(i-X)+abs(j-Y)))

c = Counter(ans)
for i in range(1,N):
    print(c[i])
Buggy python submission (verdict: Runtime Error):
n, a, b = map(int,input().split())

c = n // (a + b)
if c == 0:
    d = a + b
    assert False
else:
    d = n - (c * (a+b))

if d > a:
    ans = (c*a) + a
else:
    ans = (c*a) + d
    
print(ans)


Fixed submission:
N, A, B = map(int, input().split())
s = A+B
num = N // s * A
mod = N % s
num += min(mod, A)
print(num)