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

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort(key=lambda z:z[0])
y.sort(key=lambda z:z[0])
ans=(10**18)*5
ra=range(n)
for i1 in ra:
    for l1 in range(n-i1,0,-1):
        for i2 in ra:
            for l2 in range(n-i2,0,-1):
                if l1*l2<k:
                    break
                z=[0]*n
                for i in range(i1,i1+l1):
                    l=x[i][1]
                    z[l]=1
                for i in range(i2,i2+l2):
                    l=y[i][1]
                    z[l]=1
                if sum(z)>=k:
                    x_sub1,y_sub1=10**9+1,10**9+1
                    x_sub2,y_sub2=-10**9-1,-10**9-1
                    for i in range(n):
                        if z[i]==1:
                            x_sub1=min(xy[i][0],x_sub1)
                            x_sub2=max(xy[i][0],x_sub2)
                            y_sub1=min(xy[i][1],y_sub1)
                            y_sub2=max(xy[i][1],y_sub2)
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

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

    def pleaceAC():
        for i in range(N):
            a = reduce(gcd, [0]+A[:i])
            b = reduce(gcd, reversed(A[i+1:]+[0]))
            yield gcd(a, b)

    print(max(pleaceAC()))


main()

### FIXED CODE ###

from fractions import gcd
from itertools import accumulate

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

    def pleaceAC():
        left = list(accumulate([0]+A, gcd))
        right = list(accumulate(reversed(A+[0]), gcd))
        for i in range(N):
            yield gcd(left[i], right[~(i+1)])

    print(max(pleaceAC()))


main()
### BUGGY CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def main():
    ans = [0] * 4001
    for line in stdin:
        n = int(line)

        if not ans[n]:
            count = 0
            for a in xrange((n if n < 1000 else 1000) + 1):
                e1 = n-a-1001 if n-a-1001 >= 0 else -1
                for nab in xrange(n-a, e1, -1):
                    ran = ((nab if nab < 1000 else 1000) -
                           ((nab-1001) if nab > 1000 else -1))
                    if ran >= 0:
                        count += ran

            ans[n] = count
        print(ans[n])
    exit()


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def make_combination_list():
    cmb = [0] * 4001
    count = minus = n = s = 0

    for i in range(1001):
        count += (i+1) * (i+2) // 2
        cmb[i] = cmb[4000-i] = count

    for i in range(1001, 2001):
        count += (i+1) * (i+2) // 2
        n += 1
        s += n
        minus += 4 * s
        cmb[i] = cmb[4000-i] = count - minus

    return cmb


def main():
    ans = make_combination_list()
    for line in stdin:
        print(ans[int(line)])


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

n, q = map(int, input().split())
s = input()
ans = [0 for _ in range(n)]
for i in range(len(s) - 1):
    if s[i] == "A" and s[i + 1] == "C":
        ans[i] = 1
for j in range(q):
    l, r = map(int, input().split())
    print(sum(ans[l - 1:r - 1]))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ans = [0 for _ in range(n)]
for i in range(len(s) - 1):
    if s[i:i+2] == "AC":
        ans[i+1] = ans[i]+1
    else:
        ans[i+1] = ans[i]
    #1indexの累積和

for j in range(q):
    l, r = map(int, input().split())
    print(ans[r-1]-ans[l-1])
### BUGGY CODE ###

N, M= (int(i) for i in input().split())  
A = [int(i) for i in input().split()]
BC = [[int(i) for i in input().split()] for i in range(M)] 	
BClist = []
for i in range(M):
	for g in range(BC[i][0]):
		BClist.append(BC[i][1])
A.sort()
BClist.sort()

for i in range(len(BClist)):
	if A[i]<BClist[-1]:
		A[i]=BClist[-1]
		BClist.pop(-1)
	else:
		break
print(sum(A))

### FIXED CODE ###

import heapq

n,m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]
bc.sort(key=lambda x: x[1],reverse=True)

heapq.heapify(a)

for i in range(m):
    b,c=bc[i]
    for g in range(b):
        _min = heapq.heappop(a)
        if _min<c:
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,_min)
            break
print(sum(a))
### BUGGY CODE ###

from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))


def main():
    n = int(input())
    a = readLine_int_list()
    set_a = sorted(list(set(a)), reverse=True)
    
        
    
    pair = []
    
    ans = 0
    if len(a) - len(set_a) == 1:
        print(ans)
    else:
        for i in set_a:
            c = a.count(i)
            if c > 3:
                pair.append(i)
                pair.append(i)
            elif c > 1:
                pair.append(i)
                
            if len(pair) >= 2:
                ans = pair[0] * pair[1]
                break
    
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))


def main():
    n = int(input())
    a = sorted(readLine_int_list(),reverse=True)
    a.append(-1)
    pair = []
    ans = 0
    t = 1
    
    for i in range(n):
        
        if a[i] == a[i+1]:
            t += 1
        else:
            if t > 1:
                pair.append(a[i])
                if len(pair) == 2:
                    ans = pair[0] * pair[1]
                    break
            t = 1
        
        if t > 3:
            if pair:
                ans = max(a[i-1]*a[i], pair[0]*a[i])
            else:
                ans = a[i]**2
            break

        
        

    print(ans)


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

# https://atcoder.jp/contests/abc122/tasks/abc122_c

N, Q = [int(x) for x in input().split()]
S = input().strip()

for i in range(Q):
    l, r = [int(x) for x in input().split()]
    res = 0
    for j in range(l - 1, r - 1):
        if S[j:j+2] == 'AC':
            res += 1
    print(res)


### FIXED CODE ###

# https://atcoder.jp/contests/abc122/tasks/abc122_c

N, Q = [int(x) for x in input().split()]
S = input().strip()
m = [0] * N
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        m[i] = m[i-1] + 1
    else:
        m[i] = m[i-1]

for i in range(Q):
    l, r = [int(x) for x in input().split()]
    print(m[r - 1] - m[l - 1])
### BUGGY CODE ###

N = int(input())
S = input()
a = N

for n in range(N):
  a = min(a,S[n:].count("E")+S[:n].count("W"))

print(a)

### FIXED CODE ###

n = int(input())
s = input()
c = s.count("E")
d = c
for i in s:
  if i == "E":
    d -= 1
  else:
    d += 1
  c = min(c,d)
print(c)
### BUGGY CODE ###

S = int(input())
a, b = 0, 0
for i in range(1, S+1):
    if S % i == 0:
        if S // i <= 10**9:
            a, b = S // i, i
            break
print("0 0 " + str(a) + " 0 1 " + str(b))


### FIXED CODE ###

import math
S = int(input())
a1, b2 = math.ceil(S**0.5), math.ceil(S**0.5)
c = a1*b2 - S

print("0 0 " + str(a1) + " " + str(c) + " 1 " + str(b2))
### BUGGY CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 引かれる数の左からi桁目に+10 & 引く数のi-1桁目に+1 を適宜行う

def calc(x):
    if 0 <= x <= 5:
        return x
    else:
        return 10-x+1

N = I()
S = str(N)
L = len(S)

dp0 = [0]*L
dp1 = [0]*L
dp0[0] = calc(int(S[0]))
dp1[0] = calc(int(S[0])+1)

for i in range(1,L):
    n = int(S[i])
    if n == 0:
        dp0[i] = dp0[i-1]
    else:
        dp0[i] = min(dp0[i-1]+n, dp1[i-1]+10-n)
    if n == 9:
        dp1[i] = dp1[i-1]
    else:
        dp1[i] = min(dp0[i-1]+n+1, dp1[i-1]+9-n)

print(dp0[-1])

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 引かれる数の左からi桁目に+10 & 引く数のi-1桁目に+1 を適宜行う

def calc(x):
    if 0 <= x <= 5:
        return x
    else:
        return 10-x+1

S = list(input())
L = len(S)

dp0 = [0]*L
dp1 = [0]*L
dp0[0] = calc(int(S[0]))
dp1[0] = calc(int(S[0])+1)

for i in range(1,L):
    n = int(S[i])
    if n == 0:
        dp0[i] = dp0[i-1]
    else:
        dp0[i] = min(dp0[i-1]+n, dp1[i-1]+10-n)
    if n == 9:
        dp1[i] = dp1[i-1]
    else:
        dp1[i] = min(dp0[i-1]+n+1, dp1[i-1]+9-n)

print(dp0[-1])
### BUGGY CODE ###

import random
from fractions import gcd
lim=10**9+7
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return int(x)
n=int(input())
#A=random.sample(list(range(1, 10**6)), k=10**4)
A=[int(i) for i in input().split()]
Z=lcm(A)
ans=0
for a in A:
    ans += Z//a
print(ans % lim)


### FIXED CODE ###

from fractions import gcd
lim=10**9+7
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return int(x)


n=int(input())
A=[int(i) for i in input().split()]
A_inv = [pow(a,lim-2,lim) for a in A]

Z = A[0]
k=1
for i in range(1, n):
    Z = Z // gcd(Z, A[i]) * A[i]
ans=0

Z=Z % lim
for i in range(n):
    ans = ( ans + Z*A_inv[i] ) % lim
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
countr = []
liss = []
s = [0] * N
for i in range(N):
  s[i] = input()

for ss in s:
  a = collections.Counter(ss)
  if a in liss:
    ind = liss.index(a)
    countr[ind] += 1
  else:
    liss.append(a)
    countr.append(1)


ans = 0
for cc in countr:
  ans = ans + (cc * (cc - 1) / 2)
print(int(ans))


### FIXED CODE ###

N = int(input())
liss = {}
for i in range(N):
  s = input()
  a = "".join(sorted(s))
  if a in liss:
    liss[a] += 1
  else:
    liss[a] = 1

ans = 0
for cc in liss:
  ans = ans + (liss[cc] * (liss[cc] - 1) / 2)
print(int(ans))
### BUGGY CODE ###

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

cond = []
for i in range(len(a)):
    for j in range(i, len(a)):
        cond.append(sum(a[i:j+1]))

ans = 0
for i in reversed(range(40)):
    b = ans + 2**i
    cnt = 0
    for c in cond:
        if c&b==b:
            cnt += 1
    if cnt>=K:
        ans = b

print(ans)

### FIXED CODE ###

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

b = [0]
for ai in a:
    b.append(b[-1]+ai) 

cond = []
for i in range(N+1):
    for j in range(i+1, N+1):
        cond.append(b[j]-b[i])

ans = 0
for i in reversed(range(40)):
    b = ans + 2**i
    cnt = 0
    for c in cond:
        if c&b==b:
            cnt += 1
    if cnt>=K:
        ans = b

print(ans)
### BUGGY CODE ###

N,M,*a=map(int,open(0).read().split())
dp=[1]*(N+1)
for i in a:
    dp[i]=0
for i in range(2,N+1):
    if i in a:
        continue
    dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%1000000007)    


### FIXED CODE ###

N,M=map(int,input().split())
dp=[1]*(N+1)
for i in range(M):
    dp[int(input())]=0
for i in range(2,N+1):
    if dp[i]!=0:
        dp[i]=(dp[i-1]+dp[i-2])
print(dp[-1]%1000000007)
### BUGGY CODE ###

S = list(map(int, input()))
L = len(S)
mod = 2019
T = []
t = 0
p = 1
for i in range(L-1, -1, -1):
  t = (t + S[i] * p) % mod
  T.append(t)
  p = (p * 10) % mod
R = [T.count(t) for t in set(T)]
print(T.count(0) + sum([r * (r-1) // 2 for r in R]))

### FIXED CODE ###

S = list(map(int, input()))
L = len(S)
mod = 2019
T = []
A = [0 for i in range(mod)]
t = 0
p = 1
for i in range(L-1, -1, -1):
  t = (t + S[i] * p) % mod
  A[t] += 1
  p = (p * 10) % mod
print(A[0] + sum([a * (a-1) // 2 for a in A]))
### BUGGY CODE ###

import bisect

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

a.sort()
memo = [0 for i in range(n)]

count = 0
for t in reversed(range(1, 31)):
    for i in reversed(range(n)):
        if memo[i] == 1:
            continue
        front = bisect.bisect_left(a, (1 << t) - a[i])
        back = bisect.bisect_right(a, (1 << t) - a[i])
        while front != back:
            if i <= front:
                break
            if memo[front] == 0:
                memo[i] = 1
                memo[front] = 1
                count += 1
                break
            front += 1

print(count)

### FIXED CODE ###

from collections import defaultdict

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

a.sort()
memo = defaultdict(int)
for i in range(n):
    memo[a[i]] += 1

count = 0
for i in reversed(range(n)):
    if memo[a[i]] == 0:
        continue
    if (memo[(1 << (len(bin(a[i])) - 2)) - a[i]] > 0 and (1 << (len(bin(a[i])) - 2)) - a[i] != a[i]) or memo[(1 << (len(bin(a[i])) - 2)) - a[i]] > 1:
        memo[a[i]] -= 1
        memo[(1 << (len(bin(a[i])) - 2)) - a[i]] -= 1
        count += 1

print(count)
### BUGGY CODE ###

n, k = [int(x) for x in input().split()]
hs = [int(x) for x in input().split()]
dp = [0 for _ in range(n+1)]
mx = 1 << 50
for i in range(2, n + 1):
    mn = mx
    minIndex = max(1, i - k)
    for j in range(minIndex, i):
        v = dp[j] + abs(hs[i-1] - hs[j-1])
        if v < mn:
          mn = v
        mn = min(mn, v)
    dp[i] = mn
print(dp[n])

### FIXED CODE ###

n, k = [int(x) for x in input().split()]

hs = [int(x) for x in input().split()]

dp = [0] * n

for i in range(1, min(k,n)):
	dp[i] = min([dpj + abs(hs[i] - hj) for dpj, hj in zip(dp[:i], hs[:i])])

if k < n:
	for i in range(k, n):
		dp[i] = min([dpj + abs(hs[i] - hj) for dpj, hj in zip(dp[i-k:i], hs[i-k:i])])

print(dp[-1])
### BUGGY CODE ###

def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table

n = int(input())
s = 0
for i in range(2, n+1):
  s += i*num_divisors_table(i)[-1]
print(s+1)
  

### FIXED CODE ###

n = int(input())
ans = 0
for j in range(1, n+1):
  count = n//j
  ans += count*((count * j) + j)//2


print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
s=input()
for i in range(q):
    l,r=map(int,input().split())
    ss = s[l-1:r]
    print(ss.count('AC'))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()

ac_count=[]
ac=0

for i in range(n-1):
    if s[i:i+2]=='AC':
        ac+=1
    ac_count.append(ac)
    
for i in range(q):
    l,r=map(int,input().split())
    if l==1:
        print(ac_count[r-2])
    else:
        print(ac_count[r-2]-ac_count[l-2])
### BUGGY CODE ###

import math


def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False

q = input()
lr = []
max_num = 0
input_list = sieve_of_erastosthenes(100000)
prime_list = [i for i, b in enumerate(input_list) if b == True]
for ii in xrange(q):
    tmp = map(int, raw_input().split(" "))
    count = 0
    # max_num = max(max(tmp), max_num)
    # lr.append(tmp)
    for j in xrange(tmp[0], tmp[1] + 1):
        if j in prime_list and (j + 1) / 2 in prime_list:
            count += 1

    print count


### FIXED CODE ###

import math
import sys

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False

q = input()
lr = []
max_num = 0
INF = sys.maxint
input_list = sieve_of_erastosthenes(100000)
# prime_list = [i for i, b in enumerate(input_list) if b == True]
prime_list_append = []
sum_count = 0
for index, i in enumerate(input_list):
    if i and input_list[(index + 1) / 2]:
        # print i, (index + 1)/2, sum_count
        sum_count += 1
        prime_list_append.append(sum_count)
    else:
        prime_list_append.append(sum_count)

for ii in xrange(q):
    tmp = map(int, raw_input().split(" "))
    # count = 0
    # for j in prime_list_append[tmp[0]:tmp[1]]:
    #     count += 1
    print prime_list_append[tmp[1]] - prime_list_append[tmp[0]-1]
### BUGGY CODE ###

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

number_list = []

sum_max = 0
for index, p in enumerate(p_list):
    number_list.append((p * (p + 1)) / 2 / p)
    if index >= K - 1:
        sum_total = sum(number_list[index-(K - 1):index + 1])
        if sum_max < sum_total:
            sum_max = sum_total

print('{:.12f}'.format(float(sum_max)))

### FIXED CODE ###

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

number_list = []

sum_max = 0
tmp_max = 0
past_max = 0
tmp_max_list = []
for index, p in enumerate(p_list):
    if index >= K:
        tmp_max += (p * (p + 1)) / 2 / p
        tmp_max -= tmp_max_list[index - K]
        if sum_max < tmp_max:
            sum_max = tmp_max
        tmp_max_list.append((p * (p + 1)) / 2 / p)
    else:
        tmp_max += (p * (p + 1)) / 2 / p
        tmp_max_list.append((p * (p + 1)) / 2 / p)

if N == 1:
    print('{:.12f}'.format(float(p_list[0] * (p_list[0] + 1) / 2 / p_list[0])))
elif N == K:
    print('{:.12f}'.format(float(sum(tmp_max_list))))
else:
    print('{:.12f}'.format(float(sum_max)))
### BUGGY CODE ###

n=int(input())
L=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int, input().split())
    u-=1
    v-=1
    L[u].append([v,w])
    L[v].append([u,w])
ans=[-1]*n
ans[0]=0
stack=[0]
while stack:
    v=stack[0]
    stack=stack[1:]
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        stack.insert(0,u)
for a in ans:
    print(a)

### FIXED CODE ###

n=int(input())
L=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int, input().split())
    u-=1
    v-=1
    L[u].append([v,w])
    L[v].append([u,w])
ans=[-1]*n
ans[0]=0
que=[0]
while que:
    v=que.pop()
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        que.append(u)
for a in ans:
    print(a)
### BUGGY CODE ###

n, k = map(int,input().split())
al = list(map(int,input().split()))
dics = {}

for i in range(n):
    if al[i] in dics:
        dics[al[i]] = dics[al[i]] + 1
    else:
        dics.update({al[i]:1})
        
counts = len(dics.values())
kesu = 0
sortv = list(sorted(list((dics.values()))))

while len(sortv) > k:
    kesu = kesu + sortv[0]
    sortv.remove(sortv[0])
print(kesu)

### FIXED CODE ###

n, k = map(int,input().split())
al = list(map(int,input().split()))
dics = {}
 
for i in range(n):
    if al[i] in dics:
        dics[al[i]] = dics[al[i]] + 1
    else:
        dics.update({al[i]:1})
        
counts = len(dics.values())
kesu = 0
sortv = list(sorted(list((dics.values()))))

i = counts
j = 0
while i > k:
    kesu = kesu + sortv[j]
    i = i - 1
    j = j + 1
print(kesu)
### BUGGY CODE ###

N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
count = 0
for i in range(N+1):
    for t in range(N+1):
        count+=1 if sum(A[i:t])%M==0 and sum(A[i:t]) != 0 else  0
print(count)

### FIXED CODE ###

import collections
import numpy as np

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

A = np.array(A,dtype='int64')
C = np.append([0],np.cumsum(A))
L = [i%M for i in C]
L_c = collections.Counter(L)

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

from operator import itemgetter
n = int(input())

list_p = []
for i in range(1, n):

    j = n / i

    if j.is_integer():
        list_p.append([i, j, i+j])
list_sorted = sorted(list_p, key=itemgetter(2))
print(int(list_sorted[0][0] + list_sorted[0][1] - 2))

### FIXED CODE ###

from operator import itemgetter
n = int(input())

list_p = []
for i in range(1, int(n**0.5)+1):

    j = n / i

    if j.is_integer():
        list_p.append([i, j, i+j])

list_sorted = sorted(list_p, key=itemgetter(2))
print(int(list_sorted[0][0] + list_sorted[0][1] - 2))
### BUGGY CODE ###

s = input()
l = len(s)
d = [0] * l

for i in range(2, l - 1):
    cnt = 0
    for j in range(i):
        if int(s[j:i+2]) % 2019 == 0:
            cnt += 1
    d[i + 1] += d[i] + cnt

print(d[l - 1])

### FIXED CODE ###

S = input() [::-1]
ans = 0
mod = 0
ten = 1
count = [0]* 2019
count[0] = 1
for i in range(len(S)):
    mod = (mod + int(S[i]) * ten) % 2019
    ten = ten*10 % 2019
    count[mod] += 1
for c in count:
    ans += c*(c-1)//2
print(ans)
### BUGGY CODE ###

a, b, c, d = map(int, input().split())
num = [i for i in range(b + 1) if i >= a]
cnt = 0
for i in num:
  if i % c != 0 and i % d != 0:
    cnt += 1
    
print(cnt)

### FIXED CODE ###

from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

a, b, c, d = map(int, input().split())
cnt = (b // c + b // d - b // lcm(c, d)) - ((a - 1) // c + (a - 1) // d - (a - 1) // lcm(c, d))
print((b - a + 1) - cnt)
### BUGGY CODE ###

K,S=input().split()
L=""
for i in range(0,int(K)+1):
    X=i
    if 0<int(S)-X<int(K)*2:
        for j in range(0,int(K)+1):
            Y=j
            Z=int(S)-(X+Y)
            if 0<=Z<=int(K):
                L+="A"
            else:
                L=L
    if int(S)-X==0 or int(S)-X==int(K)*2:
        L+="A"
    else:
        L=L
print(L.count("A"))        

### FIXED CODE ###

K,S=input().split()
k=int(K)
s=int(S)
L=0
for X in range(0,k+1):
    for Y in range(0,k+1):
        Z=s-(X+Y)
        if 0<=Z<=k:
            L+=1
        
print(L)
### BUGGY CODE ###

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

INF = 10 ** 9 + 7

dp = [0] * (n+1)
dp[0] = 1

if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0

for i in range(2, n+1):
    if i in a:
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= INF

print(dp[n])


### FIXED CODE ###

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

INF = 1000000007

dp = [0] * (n+1)
dp[0] = 1

if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0

for i in range(2, n+1):
    if i in a:
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= INF

print(dp[n])