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

from operator import mul
from functools import reduce

def comb(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
    
r1, c1, r2, c2 = [int(i) for i in input().split()]
 
def calc(r, c):
    a = comb(r + c + 2, r + 1) - r - c - 2
    b = r * (r + 3) / 2
 
    if c == 1:
        return b
    else:
        return a
 
result = calc(r2, c2) - calc(r2, c1 - 1) - calc(r1 - 1, c2) + calc(r1 - 1, c1 - 1)
 
print(result %  (10**9+7))

### FIXED CODE ###

from operator import mul
from functools import reduce

def comb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 3 * 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
    
    
r1, c1, r2, c2 = [int(i) for i in input().split()]
 
def calc(r, c):
    a = comb(r + c + 2, r + 1, mod) - r - c - 2
    b = r * (r + 3) / 2
 
    if c == 1:
        return b
    else:
        return a
 
result = calc(r2, c2) - calc(r2, c1 - 1) - calc(r1 - 1, c2) + calc(r1 - 1, c1 - 1)
result %= mod
if result < 0:
  result += mod
print(result)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000000001)

def ab(x):
	return x * (-1 if x<0 else 1)

def mn(t,m):
	return t if t<m else m

def solve(n,k,ar,dp,x):
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	m = 1e9
	for i in range(x+1,mn(n,x+k+1)):
		m = mn(m,ab(ar[x]-ar[i])+solve(n,k,ar,dp,i))
	dp[x] = m
	# pr(f'{x} => {dp[x]}')
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [ab(ar[-2]-ar[-1]),0]
	# pr((n,k,ar,dp))
	pr(solve(n,k,ar,dp,0))

main()

### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
### BUGGY CODE ###

n, m = map(int, input().split())
s = input()
dp = [[-1, float("inf")] for _i in range(n+1)]
dp[0] = [0,0]
for i in range(1, n+1):
    for j in range(max(0,i-m), i):
        if s[j]=="0" and dp[j][0] >= 0:
            if dp[i][1] > dp[j][1]+1:
                dp[i][0] = j
                dp[i][1] = dp[j][1] + 1 
            elif dp[i][1] == dp[j][1]+1:
                dp[i][0] = min(dp[i][0], j)
if dp[n][0] >= 0:
    r = []
    p = n
    while p > 0:
        nex = dp[p][0]
        r.append(p-nex)
        p = nex
    print(*r[::-1])
else:
    print(-1)

### FIXED CODE ###

n, m = map(int, input().split())
s = input()
dp = [-1 for _i in range(n+1)]
dp[0] = 0
f = 0
from collections import deque
q = deque([0])
c = 0
for i in range(1, n+1):
    if s[i]=="0":
        c = 0
        while i-f > m:
            f = q.popleft()
        dp[i] = f
        q.append(i)
    else:
        c += 1
        if c >= m:
            break

if dp[n] >= 0:
    r = []
    p = n
    while p > 0:
        nex = dp[p]
        r.append(p-nex)
        p = nex
    print(*r[::-1])
else:
    print(-1)
### BUGGY CODE ###

import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    UV = [[int(x) for x in input().split()] for _ in range(N - 1)]

    T = [[] for j in range(N + 1)]

    for u, v in UV:
        T[u].append(v)
        T[v].append(u)

    s = collections.deque()

    lis = []
    s.append([1, lis])

    v = set()

    ans = [0] * (N + 1)

    while s:
        c = s[-1]
        ci, clis = c[0], c[1]

        # lis処理
        if ci not in v:
            if len(clis) == 0:
                clis.append(A[ci - 1])
            else:
                if clis[-1] < A[ci - 1]:
                    clis.append(A[ci - 1])
                else:
                    i = bisect.bisect_left(clis, A[ci - 1])
                    clis[i] = A[ci - 1]

            v.add(ci)
            ans[ci] = len(clis)

        if len(T[ci]) >= 1:
            n = T[ci].pop()
            if n in v:
                continue
            s.append([n, clis.copy()])
            continue

        s.pop()

    for i in range(1, N + 1):
        print(ans[i])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    UV = [[int(x) for x in input().split()] for _ in range(N - 1)]

    T = [[] for j in range(N + 1)]

    for u, v in UV:
        T[u].append(v)
        T[v].append(u)

    s = collections.deque()

    lis = []
    s.append([1, lis])

    v = set()

    ans = [0] * (N + 1)
    memo = [[] for j in range(N + 1)]

    while s:
        c = s[-1]
        ci, clis = c[0], c[1]

        # lis処理
        if ci not in v:
            if len(clis) == 0:
                clis.append(A[ci - 1])
                memo[ci].append(-1)
            else:
                if clis[-1] < A[ci - 1]:
                    clis.append(A[ci - 1])
                    memo[ci].append(-1)
                else:
                    i = bisect.bisect_left(clis, A[ci - 1])
                    memo[ci].append(i)
                    memo[ci].append(clis[i])
                    clis[i] = A[ci - 1]

            v.add(ci)
            ans[ci] = len(clis)

        if len(T[ci]) >= 1:
            n = T[ci].pop()
            if n in v:
                continue
            s.append([n, clis])
            continue

        if memo[ci][0] == -1:
            if len(clis) >= 1:
                clis.pop()
        else:
            clis[memo[ci][0]] = memo[ci][1]

        s.pop()

    for i in range(1, N + 1):
        print(ans[i])


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

#! python


#K, X = [int(x) for x in input().split()]

N = int(input())
S = []
for _i in range(N):
    S.append(input())

sortedS = [sorted(s) for s in S]

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        if sortedS[i] == sortedS[j]:
            cnt += 1
print(cnt)



### FIXED CODE ###

#! python

from collections import defaultdict

#K, X = [int(x) for x in input().split()]

N = int(input())
S = []
for _i in range(N):
    S.append(input())

sortedS = ["".join(sorted(s)) for s in S]

cnt = defaultdict(int)
for s in sortedS:
    cnt[s] += 1

ans = 0
for s,c in cnt.items():
    if c >= 2:
        ans += c * (c-1) // 2
print(ans)
### BUGGY CODE ###

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

A.sort()
B.sort()
C.sort()

def b_search_l(B,key):
    #key < B[s]を満たす最小のs
    if key < B[0]:
        return 0
    elif key >= B[N-1]:
        return N-1
    else:
        left,right = 0,N
        while left < right:
            mid = (left+right)//2
            if B[mid] <= key and key < B[mid+1]:
                return mid+1
            elif B[mid] > key:
                right = mid
            else:
                left = mid

def b_search_r(B,key):
    #key > B[t]を満たす最大のt
    if B[0] >= key:
        return 0
    elif B[N-1] < key:
        return N-1
    else:
        left,right = 0,N
        while left < right:
            mid = (left+right)//2
            if B[mid] < key and key <= B[mid+1]:
                return mid
            elif B[mid] >= key:
                right = mid
            else:
                left = mid

ans = 0
for i in range(N):
    for j in range(N):
        if A[i] +1 < C[j]:
            ans += (b_search_r(B,C[j]) - b_search_l(B,A[i])+1)

print(ans)


### FIXED CODE ###

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

A.sort()
B.sort()
C.sort()

def b_search_l(B,key):
    #key < B[s]を満たすsの個数
    if key < B[0]:
        return N
    elif key >= B[N-1]:
        return 0
    else:
        left,right = 0,N
        while left < right:
            mid = (left+right)//2
            if B[mid] <= key and key < B[mid+1]:
                return N-(mid+1)
            elif B[mid] > key:
                right = mid
            else:
                left = mid

def b_search_r(B,key):
    #key > B[t]を満たすtの個数
    if B[0] >= key:
        return 0
    elif B[N-1] < key:
        return N
    else:
        left,right = 0,N
        while left < right:
            mid = (left+right)//2
            if B[mid] < key and key <= B[mid+1]:
                return mid+1
            elif B[mid] >= key:
                right = mid
            else:
                left = mid

#b_l:keyより多い奴の個数
#b_r:key未満の奴の個数
ans = 0
for i in range(N):
    b_l,b_r = b_search_l(C,B[i]),b_search_r(A,B[i])
    ans += (b_l)*(b_r)
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]
flag = 0
for i in range(M):
    if ab[i][0] == 1:
        j = 0
        for j in range(M):
            if ab[j] == [ab[i][1],N]:
                print("POSSIBLE")
                flag = 1
                break
    if flag == 1:
        break
if flag == 0:
    print("IMPOSSIBLE")

### FIXED CODE ###

N,M = map(int,input().split())
voy = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    voy[a-1].append(b)
alen = len(voy[0])
flag = 0
for j in range(alen):
    qu = voy[0][j]-1
    if N in voy[qu]:
        print("POSSIBLE")
        flag = 1
        break
if flag == 0:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import itertools
N = int(input())
L = list(map(int,input().split()))
tri = list(itertools.combinations(L,3))
cnt = 0
for a,b,c in tri:
    if a < (b+c):
        if b < c+a:
            if c < a+b:
                cnt += 1
print(cnt)
    

### FIXED CODE ###

import bisect
n=int(input())
l = list(map(int,input().split()))
l.sort()
うんち = 0
for i in range(1,n):
    for j in range(i):
        p = l[i] + l[j]
        q = bisect.bisect_left(l,p)
        うんち += q-i-1
print(うんち)
### BUGGY CODE ###

from functools import reduce
from fractions import gcd


def least_common_multiple(iter):
    '''
    最小公倍数を返す
    '''
    lcm = lambda x, y: x*y//gcd(x, y)
    return reduce(lcm, iter)


N = int(input())
A = list(map(int, input().split()))
l = least_common_multiple(A)
ans = 0
MOD = 10**9+7
for a in A:
    ans = (ans + l // a) % MOD
print(ans)


### FIXED CODE ###

from fractions import gcd


N = int(input())
A = list(map(int, input().split()))
lcm = lambda x, y: x*y//gcd(x, y)
l = 1
for a in A:
    l = lcm(l, a)
ans = 0
MOD = 10**9+7
for a in A:
    ans += l // a
print(ans % MOD)
### BUGGY CODE ###

import sys


def main():
    input = sys.stdin.buffer.readline
    h, n = map(int, input().split())
    a = [0] * n
    b = [0] * n
    for i in range(n):
        a[i], b[i] = map(int, input().split())
    max_a = max(a)
    # dp[j]:jダメージ与える魔力の最小値
    dp = [1e9] * (h + max_a + 1)
    dp[0] = 0
    for i in range(n):
        for j in range(1, h + max_a + 1):
            dp[j] = min(dp[j], dp[max(j - a[i], 0)] + b[i])
    print(min(dp[h:]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.buffer.readline
    h, n = map(int, input().split())
    a = [0] * n
    b = [0] * n
    for i in range(n):
        a[i], b[i] = map(int, input().split())
    max_a = max(a)
    # dp[j]:jダメージ与える魔力の最小値
    dp = [1e9] * (h + max_a + 1)
    dp[0] = 0
    for i in range(n):
        for j in range(1, h + max_a + 1):
            dp[j] = min(dp[j], dp[max(j - a[i], 0)] + b[i])
    print(min(dp[h:]))


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

inf = 10**18
H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
dp = [[inf]*(N+1) for _ in range(H+1)]
for h in range(H+1):
    for i in range(N+1):
        if i > 0 and h - AB[i - 1][0] > 0:
            dp[h][i] = min(dp[h][i-1], dp[h-AB[i-1][0]][i] + AB[i-1][1])
        elif i > 0:
            dp[h][i] = min(dp[h][i-1], AB[i-1][1])

print(dp[H][N])

### FIXED CODE ###

inf = 10**18
H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
dp = [[inf]*(N+1) for _ in range(H+1)]
for h in range(H+1):
    for i in range(N+1):
        if i > 0 and h - AB[i - 1][0] > 0:
            dp[h][i] = min(dp[h][i-1], dp[h-AB[i-1][0]][i] + AB[i-1][1])
        elif i > 0:
            dp[h][i] = min(dp[h][i-1], AB[i-1][1])

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

N = int(input())
P = []
ans = 0
for i in range(N):
    s = int(input())
    P.append(s)
    if P.count(s) % 2 == 0:
        ans -= 1
    else:
        ans += 1
print(ans)

### FIXED CODE ###

s = set()
N = int(input())
for _ in range(N):
    x = int(input())
    if x in s:
        s.remove(x)
    else:
        s.add(x)
print(len(s))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
d = [a[i]-b[i] for i in range(n)]
e = [i for i in d if i > 0]
f = [i for i in d if i < 0]
e.sort(reverse = True)
f.sort()
if sum(d) < 0:
    print(-1)
else:
    if f == []:
        print(0)
    else:
        for i in range(len(e)+1):
            if sum(e[0:i]) >=  abs(sum(f)):
                print(i+len(f))
                break


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
d = [a[i]-b[i] for i in range(n)]
e = [i for i in d if i > 0]
f = [i for i in d if i < 0]
e.sort(reverse = True)
g = abs(sum(f))
if sum(d) < 0:
    print(-1)
else:
    if f == []:
        print(0)
    else:
        sum = 0
        for i in range(len(e)):
            sum += e[i]
            if sum >=  g:
                print(i+len(f)+1)
                break
### BUGGY CODE ###

from collections import Counter
from collections import deque
import math

def combination(n, r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

N = int(input())
que = deque()
for _ in range(N):
    s = input()
    que.append(Counter(s))

ans = 0
while len(que):
    c1 = que.pop()
    num = 0
    for c2 in list(que):
       if c1 == c2:
            num += 1
            que.remove(c2)
    if num > 0:
        ans += combination(num+1, 2)
print(ans)

### FIXED CODE ###

from collections import Counter
from collections import defaultdict
import math

def combination(n, r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

N = int(input())
L = defaultdict(int)
ans = 0
for _ in range(N):
    s = sorted(list(input()))
    L[str(s)] += 1

for c in L.values():
    if c > 1:
        ans += combination(c, 2)
print(ans)
### BUGGY CODE ###

import heapq

def setNode(n):
    global G
    global H
    G = [{} for i in range(n)]
    H = [{} for i in range(n)]

def addEdge(s, t, p, q):
    global G
    global H
    G[s][t]=p
    G[t][s]=p
    H[s][t]=q
    H[t][s]=q

# dijkstra shortest path solver
def shortest_path(G, s, t):
    fixed = {}
    q = list()
    heapq.heappush(q, (0, s))

    while q:
        w,x = heapq.heappop(q)
        if x == t: return w
        if x in fixed: continue;
        fixed[x] = w

        for y in G[x]:
            if (y in fixed) == False:
                heapq.heappush(q, (w + G[x][y] , y))
    return None

if __name__ == '__main__':
    G = [{}] # JPY
    H = [{}] # SNK
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    setNode(n)

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        U = u-1
        V = v-1
        addEdge(U, V, p, q)

    for year in range(n):
        cost = None
        for exg in range(year, n):
            min_jpy = shortest_path(G, S, exg)
            min_snk = shortest_path(H, T, exg) # = shortest_path(exg, T)
            total = min_jpy + min_snk
            if cost is None:
                cost = total
            else:
                if cost > total:
                    cost = total
            #print("year:{}\t{}->{}->{}: JPY:{}, SNK:{}: total:{}".format(year, S,exg,T,min_jpy,min_snk, total))
        #print("year:{}\tminimum cost:{}, money:{}".format(year, cost, money-cost))
        print(money-cost)

### FIXED CODE ###

import heapq
from itertools import accumulate

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    while (len(q) != 0):
    #while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    # pre calc minimum cost for all year
    fl = list(accumulate(total[::-1], min))[::-1]

    for year in range(n):
        print(money - fl[year])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(set(A))
x = int()
y = int()
count = 0 
for i in range(len(B)):
  x = B[i]
  y = 0
  y += A.count(x)
  y += A.count(x+1)
  y += A.count(x-1)
  if count <= y:
    count = y
print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [0]*(10**6)
c = int()
ans = int(0)
for i in range(len(A)):
  B[A[i]] += 1

for i in range(1,len(B)-2):
  c = 0
  c += B[i-1]
  c += B[i]
  c += B[i+1]
  if ans <= c:
    ans = c
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 0


def factorize(n):
    fct = []
    for i in range(1, n):
        if n % (i + 1) == 0:
            fct.append(i + 1)
    return fct


def check(num, mod):
    if num % mod == 1:
        return 1
    elif num % mod == 0:
        num = num / mod
        return check(num, mod)
    else:
        return 0


nfct = factorize(n)
n_1fct = factorize(n - 1)

ans += len(n_1fct)
for mod in nfct:
  ans += check(n,mod)
print(ans)






### FIXED CODE ###

n = int(input())
ans = 0
def factorize(n):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.append(n)
    return divisors

def check(num, mod):
    if num % mod == 1:
        return 1
    elif num % mod == 0:
        num = num / mod
        return check(num, mod)
    else:
        return 0


nfct = factorize(n)
n_1fct = factorize(n - 1)
if n_1fct != [1]:
  ans += len(n_1fct)
for mod in nfct:
  ans += check(n,mod)
print(ans)
### BUGGY CODE ###

def run(N, K, A):
    ret = 0
    for i in range(K+1):
        ret = max(xxor(i, A), ret)
    return ret


def xxor(X, A):
    ret = 0
    for i in range(len(A)):
        ret += X ^ A[i]
    return ret


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


if __name__ == '__main__':
    main()

### FIXED CODE ###

def run(N, K, A):
    '''
    K <= 10^12 ~= 2^40
    Kの2進数における各桁ごとの最大となるKを求めることができる(O(logK))
    Kの2進数における最初の1を0に変える位置をk_nとする
    最初に変える位置の前はすべてKと同じ、それ以降は最大を取るものを選択する(O(log(K)))
    k_nが0の場合は、全て同じパターンとしてスキップする
    上記の最大のものを習得する
    '''
    cnt1 = []

    # Kの2進数の桁を取得
    k_n = len(bin(K)) - 2

    # Aの2進数の最大桁を取得
    max_a = len(bin(max(A))) - 2
    max_a = max(max_a, k_n)

    # 数値をビットに変換
    K_bit = '{:b}'.format(K).zfill(max_a)
    A_bit = []
    for i in range(len(A)):
        A_bit.append('{:b}'.format(A[i]).zfill(max_a))

    # 2進数の各桁の値を事前計算
    bit_v = []
    for i in range(max_a):
        bit_v.append(2**(max_a-i-1))

    # A_bitの各桁の1の数を数える(O(NlogK))
    for j in range(max_a):
        cnt = 0
        for i in range(N):
            if A_bit[i][j] == '1':
                cnt += 1
        cnt1.append(cnt)

    # Kの上からi+1桁目を1=>0にすると考える
    # k_n+1桁目の場合はすべて同じ場合
    ret = 1
    for i in range(k_n+1):
        tmp1 = 0
        max_flg = False
        for j in range(max_a):
            if max_a - j == k_n - i:  # Kの対象桁を0とするパターン
                # 1だと0に変える、0だと0のまま
                tmp1 += bit_v[j] * cnt1[j]
                # 1=>0の時はフラグを付与
                if K_bit[j] == '1':
                    max_flg = True
            elif not max_flg:  # Kの各桁をそのままに使うパターン
                # K[j]が0だとcnt1[j]を、1だとN-cnt1[j]をかける
                tmp1 += bit_v[j] * (cnt1[j]**(1-int(K_bit[j]))) * ((N-cnt1[j])**(int(K_bit[j])))
            else:  # Kの前の桁で1=>0として、その後は最大になるようにとるパターン
                tmp1 += bit_v[j] * max(cnt1[j], N - cnt1[j])
        ret = max(ret, tmp1)
    return ret


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


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

N,Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

L = [(max(-0.5,s-x-0.5),max(-0.5,t-x-0.5),x) for s,t,x in STX] + [(d,-1) for d in D]
L.sort()

import heapq
hp = [] # (x,t-x)を入れる

for l in L:
  if l[1] == -1:
    while hp and l[0] > hp[0][1]:
      heapq.heappop(hp)
    if hp:
      print(hp[0][0])
    else:
      print(-1)
  else:
    heapq.heappush(hp, (l[2],l[1]))

### FIXED CODE ###

N,Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

L = [(s-x-0.5, t-x-0.5,x) for s,t,x in STX] + [(d,) for d in D]
L.sort()

import heapq
hp = [] # xを入れる
memo = {} # x:t-x

for l in L:
  if len(l)==1:
    while hp and l[0] > memo[hp[0]]:
      heapq.heappop(hp)
    if hp:
      print(hp[0])
    else:
      print(-1)
  else:
    heapq.heappush(hp, l[2])
    memo[l[2]]=l[1]
### BUGGY CODE ###

from collections import deque
N = int(input())
D = deque()
cnt = 0
for _ in range(N):
    s = input()
    if not s in D:
        D.append(s)
print(len(D))

### FIXED CODE ###

from collections import deque
N = int(input())
D = deque()
for _ in range(N):
    D.append(input())
print(len(set(D)))
### BUGGY CODE ###

import math

k=int(input())

ans=0

for l in range(1,k+1):
  for m in range(1,k+1):
    for n in range(1,k+1):
      a=math.gcd(l,m)
      if a==1:
        ans+=1
      else:
        ans+=math.gcd(a,n)
        
print(ans)

### FIXED CODE ###

import math

k=int(input())

ans=0

for l in range(1,k+1):
  for m in range(1,k+1):
    tmp=math.gcd(l,m)
    for n in range(1,k+1):
      gcd=math.gcd(tmp,n)
      ans+=gcd
      
print(ans)