Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import numpy as np
def f(X,A):
    temp_f = [X^A[i] for i in range(len(A))]
    return np.sum(temp_f)
def calc_max_f(A,K):
    temp_max_f = [f(k,A) for k in range(0,K+1)]
    return np.max(temp_max_f)
N,K = (int(x) for x in input().split())
A = [int(x) for x in input().split()]
print(calc_max_f(A,K))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
"""
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
max_A = max(A)
bit = bin(K)
if max_A > K:
    bit = bin(max_A)"""
max_f = 0
#for d in range(1,len(bit))[::-1]:
for d in range(41,-2,-1):
    #d=d-2
    if (d != -1 and not (K & 1 << d)):
        continue
    f=0
    #for e in range(2,len(bit))[::-1]:
    for e in range(41,-1,-1):
        #e=e-2
        mask = 1<<e
        num=0
        for a in A:
            if a&mask:
                num+=1
        n_num = N - num
        if e>d:
            if K&mask:
                f += mask*n_num
            else:
                f += mask*num
        elif e==d:
            f += mask*num
        else:
            f += mask*max(n_num,num)
    max_f = max(f,max_f)
print(max_f)
### BUGGY CODE ###

# coding=utf-8


def solve_recursively(candidate_numbers, target_number):
    """classify if the target number is represented a summation of elements of candidate_numbers

    Args:
        candidate_numbers: candidate_numbers
        target_number: target_number

    Returns:
        if target number is represented a summation of elements of candidate_numbers(book)
    """
    if target_number == 0:
        return True
    elif len(candidate_numbers) == 0:
        return False

    solution = solve_recursively(candidate_numbers[1:], target_number - candidate_numbers[0]) or solve_recursively(
        candidate_numbers[1:], target_number)

    return solution


def main():
    raw_input()  # pass length
    candidate_numbers = [int(x) for x in raw_input().strip().split(' ')]
    raw_input()  # pass length
    target_numbers = [int(x) for x in raw_input().strip().split(' ')]

    for target_number in target_numbers:
        if solve_recursively(candidate_numbers, target_number):
            print "yes"
        else:
            print "no"


if __name__ == "__main__":
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():
    raw_input()  # pass length
    candidate_number_list = [int(x) for x in raw_input().strip().split(' ')]
    raw_input()  # pass length
    target_number_list = [int(x) for x in raw_input().strip().split(' ')]

    representable_number_set = {0}
    for candidate_number in candidate_number_list:
        for num in representable_number_set.copy():
            representable_number_set.add(num + candidate_number)

    for target_number in target_number_list:
        if target_number in representable_number_set:
            print "yes"
        else:
            print "no"

if __name__ == "__main__":
    main()
### BUGGY CODE ###

MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

factorial = [1]
for i in range(1, N + 1):
    factorial.append(factorial[-1] * i % MOD)

inv_factorial = [-1] * (N + 1)
inv_factorial[-1] = pow(factorial[-1], MOD-2, MOD)
for i in reversed(range(N)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD

deg = [0] * N
parent = [0] * N
dp = [0] * N
ans = [0] * N
cnt_leaf = [0] * N

def dfs(v,p = -1):
    deg[v] = len(G[v])
    dp[v] = [0] * deg[v]
    res = 1
    cnt = 0
    for i,e in enumerate(G[v]):
        if e == p:
            parent[v] = i
            continue
        a,b = dfs(e,v)
        dp[v][i] = a*inv_factorial[b]%MOD
        cnt += b
        res *= dp[v][i]
        res %= MOD
    res *= factorial[cnt]%MOD
    cnt_leaf[v] = cnt
    return res,cnt + 1

def bfs(v,res_p = 0,p = - 1):
    if p != -1:
        dp[v][parent[v]] = res_p
    dpl = [1] * (deg[v] + 1)
    for i,x in enumerate(dp[v]):
        dpl[i + 1] = dpl[i]*x%MOD
    dpr = [1] * (deg[v] + 1)
    for i in range(deg[v] - 1,-1,-1):
        dpr[i] = dpr[i + 1]*dp[v][i]%MOD
    
    ans[v] = dpr[0]*factorial[N - 1]%MOD
    for i,e in enumerate(G[v]):
        if e == p:
            continue
        bfs(e,dpl[i]*dpr[i + 1]*pow(N - cnt_leaf[e] - 1,MOD - 2,MOD)%MOD,v)
    
dfs(0)
bfs(0)
print('\n'.join(map(str,ans)))

### FIXED CODE ###

MOD = 10 ** 9 + 7
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

factorial = [1]
for i in range(1, N + 1):
    factorial.append(factorial[-1] * i % MOD)

inv_factorial = [-1] * (N + 1)
inv_factorial[-1] = pow(factorial[-1], MOD-2, MOD)
for i in reversed(range(N)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD

deg = [0] * N
parent = [0] * N
dp = [0] * N
ans = [0] * N
cnt_leaf = [0] * N

def dfs(v,p = -1):
    deg[v] = len(G[v])
    dp[v] = [0] * deg[v]
    res = 1
    cnt = 0
    for i,e in enumerate(G[v]):
        if e == p:
            parent[v] = i
            continue
        a,b = dfs(e,v)
        dp[v][i] = a*inv_factorial[b]%MOD
        cnt += b
        res *= dp[v][i]
        res %= MOD
    res *= factorial[cnt]%MOD
    cnt_leaf[v] = cnt
    return res,cnt + 1

def bfs(v,res_p = 0,p = - 1):
    if p != -1:
        dp[v][parent[v]] = res_p
    dpl = [1] * (deg[v] + 1)
    for i,x in enumerate(dp[v]):
        dpl[i + 1] = dpl[i]*x%MOD
    dpr = [1] * (deg[v] + 1)
    for i in range(deg[v] - 1,-1,-1):
        dpr[i] = dpr[i + 1]*dp[v][i]%MOD
    
    ans[v] = dpr[0]*factorial[N - 1]%MOD
    for i,e in enumerate(G[v]):
        if e == p:
            continue
        bfs(e,dpl[i]*dpr[i + 1]*pow(N - cnt_leaf[e] - 1,MOD - 2,MOD)%MOD,v)
    
dfs(0)
bfs(0)
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,w = map(int,input().split())
wv = [tuple(map(int,input().split())) for i in range(n)]

dp = [0]*(w+1)
for i in range(n):
    for j in range(w,wv[i][0]-1,-1):
        dp[j] = max(dp[j],dp[j-wv[i][0]]+wv[i][1])

print(max(dp))

### FIXED CODE ###

N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0]*100010 for i in range(N+10)]
for i in range(N):
    for now_w in range(W+1):
        if (now_w >= w[i]):
            dp[i+1][now_w] = max(dp[i][now_w-w[i]] + v[i], dp[i][now_w])
        else:
            dp[i+1][now_w] = dp[i][now_w]

print(dp[N][W])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
def recursion(li,i,n,w,dp):
    if i==n or w==0:
        return 0
    if li[i][0]>w:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        return x
    else:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        if dp[i+1][w-li[i][0]]==-1:
            y=recursion(li,i+1,n,w-li[i][0],dp)
            dp[i+1][w-li[i][0]]=y
        else:
            y=dp[i+1][w-li[i][0]]            
        return max(li[i][1]+y,x)

n,w=[int(x) for x in input().split()]
li=[]
for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
dp=[[-1 for j in range(w+1)] for i in range(n+1)]
print(recursion(li,0,n,w,dp))

### FIXED CODE ###

from sys import stdin, gettrace
import sys
sys.setrecursionlimit(1000000)
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()

def recursion(li,i,n,w,dp):
    if i==n or w==0:
        return 0
    if li[i][0]>w:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        return x
    else:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        if dp[i+1][w-li[i][0]]==-1:
            y=recursion(li,i+1,n,w-li[i][0],dp)
            dp[i+1][w-li[i][0]]=y
        else:
            y=dp[i+1][w-li[i][0]]            
        return max(li[i][1]+y,x)

def main():
    n,w=[int(x) for x in input().split()]
    li=[]
    for i in range(n):
        temp=[int(x) for x in input().split()]
        li.append(temp)
    dp=[[-1 for j in range(w+1)] for i in range(n+1)]
    print(recursion(li,0,n,w,dp))
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# 接続最大クラスタのサイズが答え？

N, M = [int(x) for x in input().split(' ')]

from collections import defaultdict
d = defaultdict(set)

for i in range(M):
    a, b = [int(x) for x in input().split(' ')]
    d[a].add(b)
    d[b].add(a)

def bfs(i):
    obs = {i}
    passed = {i}

    # get next_obs
    before = {i}
    while True:
        after = set()
        for i in before:
            after |= d[i]
        before = after - passed
        passed |= after
        if len(after) == 0:
            return len(passed)

print(max([bfs(i) for i in range(1, N+1)]))

### FIXED CODE ###

# 接続最大クラスタのサイズが答え？

N, M = [int(x) for x in input().split(' ')]

# from collections import defaultdict
# d = defaultdict(set)

# for i in range(M):
#     a, b = [int(x) for x in input().split(' ')]
#     d[a].add(b)
#     d[b].add(a)

class UF:
    def __init__(self):
        self.r = [-1] * N

    def root(self, i):
        r = self.r
        if r[i] < 0:
            return i
        else:
            r[i] = self.root(r[i])
            return r[i]

    def union(self, i, j):
        i -= 1
        j -= 1
        ri = self.root(i)
        rj = self.root(j)
        if ri == rj:
            return
        else:
            if not self.r[ri] < self.r[rj]:
                ri, rj = rj, ri
            self.r[ri] += self.r[rj]
            self.r[rj] = ri
            return

    def max_size(self):
        return -min(self.r)

uf = UF()
for i in range(M):
    uf.union(*[int(x) for x in input().split(' ')])
print(uf.max_size())
### BUGGY CODE ###

import collections
n = int(input())

s = [''.join(sorted(list(input()))) for x in range(n)]

ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        if s[i] == s[j]:
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = [''.join(sorted(list(input()))) for x in range(n)]
ans = 0
s_dict = dict()
for v in s:
    if v in s_dict:
      ans += s_dict[v]
      s_dict[v] += 1
    else:
        s_dict[v] = 1
print(ans)
### BUGGY CODE ###

n = int(input())
 
cnt = 0
for r in range(1, n):
    a = r * (n - r)
    for i in range(a, 0, -r):
        if i < n:
            cnt += i // r
            break
 
print(cnt)

### FIXED CODE ###

n = int(input())
print(sum((n - 1) // i for i in range(1, n)))
### BUGGY CODE ###

import sys

r, c, k = map(int, sys.stdin.buffer.readline().split())
items = [[0] * (c + 1) for _ in range(r + 1)]
rcv = map(int, sys.stdin.buffer.read().split())
for r_, c_, v in zip(rcv, rcv, rcv):
    items[r_][c_] = v

dp = [[[0, 0, 0, 0] for _ in range(c + 1)] for _ in range(r + 1)]

for i in range(1, r + 1):
    for j in range(1, c + 1):
        up = dp[i - 1][j][3]
        for w in range(4):
            dp[i][j][w] = max(dp[i][j - 1][w], up)
        v = items[i][j]
        if v == 0:
            continue
        for w in range(2, -1, -1):
            dp[i][j][w + 1] = max(dp[i][j][w + 1], dp[i][j][w] + v)

print(dp[-1][-1][3])


### FIXED CODE ###

import os
import sys

import numpy as np


def solve(inp):
    r, c, k = inp[:3]
    items = np.zeros((r + 1, c + 1), dtype=np.int64)
    rrr = inp[3::3]
    ccc = inp[4::3]
    vvv = inp[5::3]
    for r_, c_, v in zip(rrr, ccc, vvv):
        items[r_][c_] = v

    dp = np.zeros((r + 1, c + 1, 4), dtype=np.int64)

    for i in range(1, r + 1):
        for j in range(1, c + 1):
            up = dp[i - 1][j][3]
            for w in range(4):
                dp[i][j][w] = max(dp[i][j - 1][w], up)
            v = items[i][j]
            if v == 0:
                continue
            for w in range(2, -1, -1):
                dp[i][j][w + 1] = max(dp[i][j][w + 1], dp[i][j][w] + v)

    return dp[-1][-1][3]


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)
### BUGGY CODE ###

N = list(map(int,input().split()))
drinks = [list(map(int,input().split())) for i in range(N[0])]

counter=0
amount=0
flag=0
for i in range(N[0]):
    v = drinks[i]
    x = drinks[i][0]
    j = i-1
    while(j >= 0 and drinks[j][0]>x):
        drinks[j+1] = drinks[j]
        j -= 1
    drinks[j+1] = v
    x = drinks[j+1][0]

for i in range(N[0]):
    if flag==1:
        break
    while(drinks[i][1]!=0):
        drinks[i][1] -=1
        counter +=1
        amount += drinks[i][0]
        if counter==N[1]:
            flag=1
            break
print(amount) 
    


### FIXED CODE ###

N = list(map(int,input().split()))
drinks = [list(map(int,input().split())) for i in range(N[0])]
drinks.sort()

counter=0
amount=0
flag=0

for i in range(N[0]):
    if flag==1:
        break
    while(drinks[i][1]!=0):
        drinks[i][1] -=1
        counter +=1
        amount += drinks[i][0]
        if counter==N[1]:
            flag=1
            break
print(amount)
### BUGGY CODE ###

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

L = len(A)
total = 0

mod = 10**9+7

for x in range(L):
    tmp = 0
    for y in range(x+1, L):
        tmp += A[y]
    total += tmp*A[x]
print(total % mod)


### FIXED CODE ###

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

L = len(A)
total = 0
tmp = 0
mod = 10**9+7
for y in range(L):
    tmp += A[y]

for x in range(L):
    tmp -= A[x] 
    total += tmp*A[x]
print(total % mod)
### BUGGY CODE ###

def E(i,y):
    if i==1:
        return 5*y
    else:
        return (2*i+1)*y

N,X=map(int,input().split())
x=[int(i) for i in input().split()]
a=[0]
for i in range(N):
    a.append(a[-1]+x[i])
ans=10**50
for k in range(1,N+1):
    tmp=(N+k)*X
    for i in range(N//k):
        tmp+=E(i+1,a[N-i*k]-a[N-i*k-k])
        #print(k,i,tmp)
    if N%k!=0:
        tmp+=E(N//k+1,a[N-(N//k)*k])
    #print(tmp)
    if ans>tmp:
        ans=tmp
print(ans)


### FIXED CODE ###

def E(i,y):
    if i==1:
        return 5*y
    else:
        return (2*i+1)*y

def ceil(a,b):
    return -((-a)//b)
N,X=map(int,input().split())
x=[int(i) for i in input().split()]
a=[0]
for i in range(N):
    a.append(a[-1]+x[i])
ans=10**50
for k in range(1,N+1):
    tmp=(N+k)*X
    for i in range(N//k):
        tmp+=E(i+1,a[N-i*k]-a[N-i*k-k])
        #print(k,i,tmp)
    if N%k!=0:
        tmp+=E(N//k+1,a[N-(N//k)*k])
    #print(tmp)
    if ans>tmp:
        ans=tmp
print(ans)
### BUGGY CODE ###

S=input()
MOD=10**9+7
dp=[]
for _ in range(len(S)):
    dp.append([0]*13)
if S[0]=='?':
    for i in range(10):
        dp[0][(i*10**(len(S)-1))%13]=1
else:
    dp[0][(int(S[0])*10**(len(S)-1))%13]=1
for j in range(0,len(S)-1):
    for k in range(13):
        if S[j+1]=='?':
            L=[]
            for l in range(10):
                l=(l*10**(len(S)-j-2)%13)%MOD
                L.append(dp[j][k-l])
            dp[j+1][k]+=sum(L)%(7+10**9)
        else:
            dp[j+1][k]=dp[j][k-(int(S[j+1]))*10**(len(S)-j-2)%13]
print((dp[len(S)-1][5])%(7+10**9))

### FIXED CODE ###

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] += 1
    s=[1]
    for n in range(1,N):
        s.append((s[n-1]*10)%13)
    for i in range(N):
        for k in range(13):
            if S[-(i+1)] != '?':
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*s[i])%13] += dp[i][k]
                    dp[i+1][(k+l*s[i])%13] %= MOD
    print(dp[-1][5])

if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

ans = 0
mod = 10 ** 9 + 7
for i in range(n):
    for j in range(i+1, n):
        ans += a[i] * a[j]
        ans %= mod
print(ans)


### FIXED CODE ###

from itertools import accumulate

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

# 累積和
a_acm = list(accumulate(a[::-1]))

ans = 0
mod = 10 ** 9 + 7
for i in range(n-1):
    ans += a[i] * a_acm[n-2-i]
    ans %= mod
print(ans)
### BUGGY CODE ###

import copy
import itertools
import heapq

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    ans = set()

    X = [i for i in range(N)]
    Y = [perm for perm in itertools.permutations(X, V)]
    Z = [Y for _ in range(M)]
    #print([perm for perm in itertools.product(*Z)])

    for i in [perm for perm in itertools.product(*Z)]:
        # print(i)
        A_copy = copy.copy(A)
        for j in i:
            for k in j:
                A_copy[k] += 1

        # print(A_copy)
        # psbl = sorted(A_copy, reverse=True)[:P]
        psbl_min = min(heapq.nlargest(P, A_copy))
        psbl_index_list = [i for i, a in enumerate(A_copy) if a >= psbl_min]
        # print(psbl_index_list)
        for l in psbl_index_list:
            ans.add(l)
        # print(ans)

    print(len(ans))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    sorted_A = sorted(A, reverse=True)

    def is_possible(i):
        # Aは降順 -> sorted_A、
        # i+1番目以降の問題のスコアをi番目の問題のスコア以下になるように投票すれば
        # i番目の問題に採用される可能性が生まれるという考え方

        # 投票前の上位P問は採用される可能性がある
        if i < P:
            return True

        # 残り投票数
        num_votes = V * M

        # i番目の問題を採用させようとする場合は、M人のジャッジ全員がi番目の問題に投票すればよい
        score_i = sorted_A[i] + M
        num_votes -= M

        # M人のジャッジ全員がi番目の問題に投票しても、上位P問にスコアが上がらない場合は採用される可能性がない
        if sorted_A[P - 1] > score_i:
            return False

        # 上の操作からi+1番目以降のの問題のスコアを、i番目の問題のスコアを超えることがないため、
        # M人のジャッジ全員がi+1番目以降の問題に投票してもよい
        num_votes -= (N - i - 1) * M

        # i番目の問題が上位P問に入ればよいので、P-1位の問題にもM人のジャッジ全員が投票してもよい
        num_votes -= (P - 1) * M

        # P番目からi番目
        # print('margin: {}, num_votes: {}'.format(sum(score_i - j for j in sorted_A[P-1 : i]), num_votes))
        return sum(score_i - j for j in sorted_A[P-1 : i]) >= num_votes

    # 1番目は必ず採用される
    # N番目は採用されるか
    if is_possible(N-1):
        print(N)

    # 1番目:採用、N番目:採用されない
    # -> [1:N-1]のどこに採用の境界があるかを二分探索する
    else:
        low = 0
        hight = N - 1

        while hight - low > 1:
            middle = (hight + low) // 2
            # print('PRE - low:{}, middle:{}, hight:{}'.format(low, middle, hight))
            if is_possible(middle):
                low = middle
            else:
                hight = middle
            # print('AFT - low:{}, middle:{}, hight:{}'.format(low, middle, hight))

        print(low + 1)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

S=input()
N=len(S)

ans=0
for i in range(N-3):
    for j in range(i+4,N+1):
        s=S[i:j]
        s=int(s)
        if s%2019==0:
            ans+=1
print(ans)

### FIXED CODE ###

S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)
### BUGGY CODE ###

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

def solve():
    ans = 0
    for i in range(n):
        for j in range(n):
            if j == i:
                continue
            if a_i[i] % a_i[j] == 0:
                break
        else:
            ans += 1
    return ans

print(solve())

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
num_list = [0] * 1000001
 
def solve():
    ans = 0
    for i in range(n):
        if num_list[a[i]] == 0:
            num_list[a[i]] += 1
            for j in range(2, (1000000 // a[i]) + 1):
                num_list[j * a[i]] += 1
        elif num_list[a[i]] == 1:
            num_list[a[i]] += 1
    for i in range(n):
        if num_list[a[i]] == 1:
            ans += 1
    return ans
 
print(solve())
### BUGGY CODE ###

from collections import deque

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

for i in range(N):
  A[i] -= i


ans = 0
d = deque(A)
for i in range(N):
  a = d.popleft()
  c = d.count(-a - 2 * i)
  ans += c
print(ans)

### FIXED CODE ###

from collections import deque, Counter

N = int(input())

A = [
  int(j) - i  for i, j in enumerate(input().split())
]
cnt_A = Counter(A)

ans = 0
d = deque(A)
for i in range(N):
  a = d.popleft()
  #c = d.count(-a - 2 * i)
  c = cnt_A[-a - 2 * i]
  ans += c
print(ans)
### BUGGY CODE ###

from collections import defaultdict
S = input()[::-1]
mod = 2019
d = defaultdict(int)
s = ""
for i in range(len(S)):
    s += S[i]
    d[int(s[::-1]) % mod] += 1
ans = 0
for k, v in d.items():
    ans += v * (v - 1) // 2
    if k == 0:
        ans += v
print(ans)

### FIXED CODE ###

import collections
S = input()[::-1]
N = len(S)
mod = 2019

ans = 0
x = [0] * N
x[0] = int(S[0]) % mod
ruijo = 10

for i in range(1, N):
    x[i] = (ruijo * int(S[i]) + x[i - 1]) % mod
    if x[i] % mod == 0:
        ans += 1
    ruijo *= 10
    ruijo %= mod
    
d = collections.Counter(x)

for i in d.values():
    ans += i * (i - 1) // 2
    
print(ans)
### BUGGY CODE ###

from numpy import array, sum, argmax

N,M = list(map(int,input().split()))
A = array([int(i) for i in input().split()])

for i in range(M):
  #print(A)
  idx = argmax(A)
  A[idx] //= 2

print(sum(A))


### FIXED CODE ###

import heapq

N,M = list(map(int,input().split()))
A_tmp = [int(i) for i in input().split()]

#print(A_tmp)
A = [-i for i in A_tmp]

heapq.heapify(A)
#print(A)

for i in range(M):
  tmp = heapq.heappop(A)
  heapq.heappush(A, -(-tmp // 2))
  #print(A)

print(-sum(A))
### BUGGY CODE ###

n,m,q = map(int,input().split())
ans = 0
lis = [list(map(int,input().split())) for i in range(q)]
lis.sort(key=lambda x:x[1])
for i in range(2 ** q):
    s = str(format(i,"b").zfill(q))
    num = [-1 for i in range(n)]
    num[0] = 1
    score = 0
    for j in range(q):
        if s[j] == "1":
            if num[lis[j][1]-1] == -1 or num[lis[j][1]-1] == num[lis[j][0]-1] + lis[j][2]:
                num[lis[j][1]-1] = num[lis[j][0]-1] + lis[j][2]
                score += lis[j][3]
            else:
                break
    for j in range(n-1):
        if num[j] == -1:
            num[j] = num[j-1]
    for j in range(n-1):
        if num[j] > num[j+1]:
            break
    if num[-1] <= m:
        ans = max(ans,score)
print(ans)

### FIXED CODE ###

def dfs(x,cnt):
    global ans
    if cnt != n:
        for i in range(x[-1],m+1):
            dfs(x+[i],cnt+1)
    else:
        cnt = 0
        for a,b,c,d in lis:
            if x[a-1] + c == x[b-1]:
                cnt += d
        ans = max(ans,cnt)
n,m,q = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(q)]
ans = 0
dfs([1],0)
print(ans)