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

import sys
input=sys.stdin.readline
N = int(input().rstrip())
S = input().rstrip()

def z_algo(s):
    """
    param s:str
    return list of int with length len(s)
    """
    # initialization
    n=len(s)
    z=[0]*n
    z[0]=n
    # construct
    L,R=0,0
    for i in range(1,n):
        if i>R: # 過去の結果が全く使えない
            L=R=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1 # 0-indexedでiと比較するため
        elif z[i-L]<R-i+1:
            z[i]=z[i-L]
        else:
            L=i
            R+=1 # Rまでは確定しているので、R+1から確認
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1
    return z

ans = 0
for i in range(N-1):
    z = z_algo(S[i:])
    z = z[(len(z)+1)//2:]
    max_z = max(z)
    ans = max(ans, max_z)
print(ans)



### FIXED CODE ###

def resolve():
    import sys
    input=sys.stdin.readline
    N = int(input().rstrip())
    S = input().rstrip()

    def z_algo(s):
        """
        param s:str
        return list of int with length len(s)
        """
        # initialization
        n=len(s)
        z=[0]*n
        z[0]=n
        # construct
        L,R=0,0
        for i in range(1,n):
            if i>R: # 過去の結果が全く使えない
                L=R=i
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1 # 0-indexedでiと比較するため
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 # Rまでは確定しているので、R+1から確認
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

    ans = 0
    for i in range(N-1):
        z = z_algo(S[i:])
        for j, _z in enumerate(z):
            ans=max(ans,min(j,z[j]))
    print(ans)

resolve()
### BUGGY CODE ###

x, y, z, K = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

ans = []
check = [[[False for i in range(K)] for j in range(K)] for k in range(K)]
q = [[0, 0, 0, 0]]
check[0][0][0] = True
while len(q) > 0:
    i, j, k, step = q.pop(0)
    if step < min(K, 3000):
        ans.append(a[i]+b[j]+c[k])
        if i+1 < x:
            if not check[i+1][j][k]:
                check[i+1][j][k] = True
                q.append([i+1, j, k, step+1])
        if j+1 < y:
            if not check[i][j+1][k]:
                check[i][j+1][k] = True
                q.append([i, j+1, k, step+1])
        if k+1 < z:
            if not check[i][j][k+1]:
                check[i][j][k+1] = True
                q.append([i, j, k+1, step+1])

ans = sorted(ans, reverse=True)
for i in range(K):
    print(ans[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    x, y, z, K = map(int, input().split())
    A = sorted(list(map(int, input().split())), reverse=True)
    B = sorted(list(map(int, input().split())), reverse=True)
    C = sorted(list(map(int, input().split())), reverse=True)

    ind = []
    for i in range(x):
        for j in range(y):
            if (i+1)*(j+1) <= K:
                for k in range(z):
                    if (i+1)*(j+1)*(k+1) <= K:
                        ind.append(A[i]+B[j]+C[k])
                    else:
                        break
            else:
                break
    ind = sorted(ind, reverse=True)
    for i in range(K):
        print(ind[i])

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

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

ans = len(S) - 1
for i in range(len(S)):
    _ans = S.count("W", 0, i) + S.count("E", i + 1, len(S))
    ans = ans if ans <= _ans else _ans

print(ans)

### FIXED CODE ###

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

l = 0
r = S.count("E", 1, len(S))
ans = l + r
for i in range(1, len(S)):
    if S[i] == "E":
        r -= 1
    if S[i - 1] == "W":
        l += 1

    ans = ans if ans <= l + r else l + r

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

def cal(N):
  strn = str(N)
  ans = 0
  for s in strn:
    ans += int(s)
  return ans
 
N = int(input())
mmax = 0
for i in range(1, N+1):
  mmax = max(cal(i), mmax)

print(mmax)

### FIXED CODE ###

N = int(input())
K = len(str(N))
c = N // 10**(K-1)

print(c+9*(K-1) if N ==(c+1)*10**(K-1)-1 else c+9*(K-1)-1)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
pt = [K - Q]*(N + 1)

for i in range(Q):
  for n in range(len(pt)):
    if n == A[i]:
      pt[n] += 1

for n in range(1, len(pt)):
  if pt[n] > 0:
    print("Yes")
  else:
    print("No")


### FIXED CODE ###

n,k,q = map(int,input().split())
ans = [0]*n
for i in range(q):
    idx = int(input()) -1
    ans[idx] += 1
for i in ans:
    print('Yes' if q-k<i else 'No')
### BUGGY CODE ###

import sys
input = sys.stdin.readline

INF = float('inf')

N = int(input().strip())
data = [list(map(int, input().split())) for _ in range(N)]
cost_b = []
cost_D = []
for b in range(1<<N):
  towns = []
  cost = INF
  for i in range(N):
    if (b>>i)&1:
      towns.append(data[i])
  for i in range(len(towns)):
    X = towns[i][0]
    cost = min(cost,sum(abs(towns[j][0]-X)*towns[j][2] for j in range(len(towns))))
  for i in range(len(towns)):
    Y = towns[i][1]
    cost = min(cost,sum(abs(towns[j][1]-Y)*towns[j][2] for j in range(len(towns))))
  if len(towns) == 0:
    cost = 0
  cost_b.append(cost)
  cost_D.append(sum(min(abs(towns[j][0]),abs(towns[j][1]))*towns[j][2] for j in range(len(towns))))

dp = [[INF]*(N+1) for i in range(1<<N)]

for i in range(1<<N):
  dp[i][0] = cost_D[i]
count = 0
for k in range(1,N+1):
  for i in range(1<<N):
    x = i
    while x>=0:
      x &= i
      new = dp[i-x][k-1]+cost_b[x]
      if dp[i][k] > new:
        dp[i][k] = new
      x -= 1
for i in range(N+1):
  print(dp[-1][i])

### FIXED CODE ###

import sys
input = sys.stdin.readline

INF = float('inf')

N = int(input().strip())
data = [list(map(int, input().split())) for _ in range(N)]
cost_b = []
cost_D = []
for b in range(1<<N):
  towns = []
  cost = INF
  for i in range(N):
    if (b>>i)&1:
      towns.append(data[i])
  for i in range(len(towns)):
    X = towns[i][0]
    cost = min(cost,sum(abs(towns[j][0]-X)*towns[j][2] for j in range(len(towns))))
  for i in range(len(towns)):
    Y = towns[i][1]
    cost = min(cost,sum(abs(towns[j][1]-Y)*towns[j][2] for j in range(len(towns))))
  if len(towns) == 0:
    cost = 0
  cost_b.append(cost)
  cost_D.append(sum(min(abs(towns[j][0]),abs(towns[j][1]))*towns[j][2] for j in range(len(towns))))

dp = [[INF]*(N+1) for i in range(1<<N)]

for i in range(1<<N):
  dp[i][0] = cost_D[i]
count = 0
for k in range(1,N+1):
  for i in reversed(range(1<<N)):
    x = i
    while x>=0:
      x &= i
      new = dp[i-x][k-1]+cost_b[x]
      if dp[i][k] > new:
        dp[i][k] = new
      if new == 0:
        break
      x -= 1
for i in range(N+1):
  print(dp[-1][i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def main():
    n = int(input())
    a = list(map(int, input().split()))
    sum = 0
    mod = 1000000007
    for i in range(n-1):
        for j in range(i+1, n):
            sum += a[i]*a[j]
    print(sum%mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import accumulate
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a_sum = (accumulate(reversed(a)))
    a_sum = list(reversed(list(a_sum)))
    sum = 0
    mod = 1000000007
    for i in range(n-1):
        sum += a[i]*a_sum[i+1]
    print(sum%mod)

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

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
cntA = 0
ans = 0
p = max(m,n)
if p == n:
  q = a
  r = b
else:
  q = b
  r = a
for i in range(p):
  if cntA+q[i] > k:
    break
  ans += 1
  cntA += q[i]
indA = ans-1
nc = indA+1
for j in range(indA+1):
  temp = 0
  adds = 0
  for v in r:
    adds += v
    if cntA + adds > k:
      break
    temp += 1
  cntA -= q[nc-1-j]
  ans = max(ans,indA+1+temp)
  indA -= 1
print(ans)

### FIXED CODE ###

n,m,k = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

a,b = [0],[0]
for i in range(n):
  a.append(a[i]+A[i])
for i in range(m):
  b.append(b[i]+B[i])

ans,j = 0,m
for i in range(n+1):
  if a[i]>k:
    break
  while b[j]+a[i]>k:
    j -= 1
  ans = max(ans,i+j)

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

N,M=map(int,input().split())
dp_ppp=[-1000000]*(N+1)
dp_mpp=[-1000000]*(N+1)
dp_pmp=[-1000000]*(N+1)
dp_ppm=[-1000000]*(N+1)
dp_mmp=[-1000000]*(N+1)
dp_mpm=[-1000000]*(N+1)
dp_pmm=[-1000000]*(N+1)
dp_mmm=[-1000000]*(N+1)
dp_ppp[0]=0
dp_mpp[0]=0
dp_pmp[0]=0
dp_ppm[0]=0
dp_mmp[0]=0
dp_mpm[0]=0
dp_pmm[0]=0
dp_mmm[0]=0
for i in range(N):
  x,y,z=map(int,input().split())
  for j in range(min(i+1,M),0,-1):
    if dp_ppp[j-1]>=0:
      dp_ppp[j]=max([dp_ppp[j],dp_ppp[j-1]+x+y+z])
    if dp_mpp[j-1]>=0:
      dp_mpp[j]=max([dp_mpp[j],dp_mpp[j-1]-x+y+z])
    if dp_pmp[j-1]>=0:
      dp_pmp[j]=max([dp_pmp[j],dp_pmp[j-1]+x-y+z])
    if dp_ppm[j-1]>=0:
      dp_ppm[j]=max([dp_ppm[j],dp_ppm[j-1]+x+y-z])
    if dp_mmp[j-1]>=0:
      dp_mmp[j]=max([dp_mmp[j],dp_mmp[j-1]-x-y+z])
    if dp_mpm[j-1]>=0:
      dp_mpm[j]=max([dp_mpm[j],dp_mpm[j-1]-x+y-z])
    if dp_pmm[j-1]>=0:
      dp_pmm[j]=max([dp_pmm[j],dp_pmm[j-1]+x-y-z])
    if dp_mmm[j-1]>=0:
      dp_mmm[j]=max([dp_mmm[j],dp_mmm[j-1]-x-y-z])

ans=max([dp_ppp[M],dp_mpp[M],dp_pmp[M],dp_ppm[M],dp_mmp[M],dp_mpm[M],dp_pmm[M],dp_mmm[M]])
if ans>0:
  print(ans)
else:
  print(0)

### FIXED CODE ###

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
dp_ppp=[]
dp_mpp=[]
dp_pmp=[]
dp_ppm=[]
dp_mmp=[]
dp_mpm=[]
dp_pmm=[]
dp_mmm=[]
for i in range(N):
  x,y,z=map(int,input().split())
  dp_ppp.append(x+y+z)
  dp_mpp.append(-x+y+z)
  dp_pmp.append(x-y+z)
  dp_ppm.append(x+y-z)
  dp_mmp.append(-x-y+z)
  dp_mpm.append(-x+y-z)
  dp_pmm.append(x-y-z)
  dp_mmm.append(-x-y-z)
dp_ppp.sort(key=lambda x:-x)
dp_mpp.sort(key=lambda x:-x)
dp_pmp.sort(key=lambda x:-x)
dp_ppm.sort(key=lambda x:-x)
dp_mmp.sort(key=lambda x:-x)
dp_mpm.sort(key=lambda x:-x)
dp_pmm.sort(key=lambda x:-x)
dp_mmm.sort(key=lambda x:-x)
ppp=sum(dp_ppp[0:M])
mpp=sum(dp_mpp[0:M])
pmp=sum(dp_pmp[0:M])
ppm=sum(dp_ppm[0:M])
mmp=sum(dp_mmp[0:M])
mpm=sum(dp_mpm[0:M])
pmm=sum(dp_pmm[0:M])
mmm=sum(dp_mmm[0:M])
ans=max([ppp,mpp,pmp,ppm,mmp,mpm,pmm,mmm])
print(ans)
### BUGGY CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        num = N * h * n
        denom = 4 * h * n - N * n - N * h
        if denom > 0 and num % denom == 0:
            w = num // denom
            break
    else:
        continue
    break
print(h, n, w)


### FIXED CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        num = N * h * n
        denom = 4 * h * n - N * n - N * h
        if denom > 0 and num % denom == 0:
            w = num // denom
            break
    else:
        continue
    break
print(h, n, w)
### BUGGY CODE ###

import heapq

N,K = map(int, input().split())
A = [int(a) for a in input().split()]
F = [int(f) for f in input().split()]

    
if K >= sum(A):
    ans = 0
else:
    A.sort(reverse=True)
    F.sort()
    h = []
    for i in range(N):
        heapq.heappush(h, [-A[i]*F[i], A[i], F[i]])
    while K > 0:
        temp = heapq.heappop(h)
        temp[0] += temp[2]
        temp[1] -= 1
        heapq.heappush(h, temp)
        K -= 1
    L = heapq.heappop(h)
    ans = -L[0]
print(ans)

### FIXED CODE ###

N,K = map(int, input().split())
A = [int(a) for a in input().split()]
F = [int(f) for f in input().split()]

A.sort()
F.sort(reverse=True)

if K >= sum(A):
    ans = 0
else:
    u = 10**13
    l = 0
    while u-l > 1:
        x = (u+l)//2
        cnt = K
        for i in range(N):
            cnt -= max(0, A[i]-x//F[i])
        if cnt >= 0:
            u = x
        else:
            l = x
    cnt = K
    for i in range(N):
        cnt -= max(0, A[i]-l//F[i])
    if cnt >= 0:
        ans = l
    else:
        ans = u
        
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()

w = [0]
e = [0]

for i in range(1, n):

    j = (n - 1) - i

    if (s[i-1] == 'W'):
        w.append(w[-1] + 1)
    else:
        w.append(w[-1])

    if (s[j+1] == 'E'):
        e.insert(0, e[0] + 1)
    else:
        e.insert(0, e[0])


# for j in range(n-2, -1, -1):

#     if (s[j+1] == 'E'):
#         e.insert(0, e[0] + 1)
#     else:
#         e.insert(0, e[0])


result = []

for i in range(n):
    result.append(e[i] + w[i])

print(min(result))

### FIXED CODE ###

n = int(input())
s = input()

w = [0]
e = [0]

tmp_w = 0
tmp_e = 0

for i in range(1, n):

    j = (n - 1) - i

    if (s[i-1] == 'W'):
        w.append(tmp_w + 1)
        tmp_w += 1
    else:
        w.append(tmp_w)

    if (s[j+1] == 'E'):
        e.append(tmp_e + 1)
        tmp_e += 1
    else:
        e.append(tmp_e)

e.reverse()

ans = 10 ** 6 
for i in range(n):
    ans = w[i] + e[i] if w[i] + e[i] < ans else ans

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

H,W = map(int,input().split())


count = 1
que = [(0,0)]
check = set()
check.add((0,0))
while que:
    points = que.pop()

    ru = (points[0]+1,points[1]-1)
    if ru[0]<W and -1<ru[1] and ru not in check:
        que.append(ru)
        check.add(ru)
        count += 1
    
    rd = (points[0]+1,points[1]+1)
    if rd[0]<W and rd[1]<H and rd not in check:
        que.append(rd)
        check.add(rd)
        count += 1
    
    lu = (points[0]-1,points[1]-1)
    if -1<lu[0] and -1<lu[1] and lu not in check:
        que.append(lu)
        check.add(lu)
        count += 1
    
    ld = (points[0]-1,points[1]+1)
    if -1<ld[0] and ld[1]<H and ld not in check:
        que.append(ld)
        check.add(ld)
        count += 1


ans = count
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())

# count = 1
# que = [(0,0)]
# check = set()
# check.add((0,0))
# while que:
#     points = que.pop()

#     ru = (points[0]+1,points[1]-1)
#     if ru[0]<W and -1<ru[1] and ru not in check:
#         que.append(ru)
#         check.add(ru)
#         count += 1
    
#     rd = (points[0]+1,points[1]+1)
#     if rd[0]<W and rd[1]<H and rd not in check:
#         que.append(rd)
#         check.add(rd)
#         count += 1
    
#     lu = (points[0]-1,points[1]-1)
#     if -1<lu[0] and -1<lu[1] and lu not in check:
#         que.append(lu)
#         check.add(lu)
#         count += 1
    
#     ld = (points[0]-1,points[1]+1)
#     if -1<ld[0] and ld[1]<H and ld not in check:
#         que.append(ld)
#         check.add(ld)
#         count += 1

block = H//2 * W
tip = W//2 if W%2==0 else W//2+1
tip = tip if H%2!=0 else 0


ans = 1 if H==1 or W==1 else block+tip
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
MOD = 10**9 + 7
tree = [[] for i in range(N+1)]
for i in range(N-1):
  a, b = map(int, input().split())
  tree[a].append(b)
  tree[b].append(a)

# 頂点1をルートにして各頂点より下にある部分木の頂点数を求めていく
root, par = 1, 0
sizes = [0] * (N+1)
order = [[root, par]]
def calc_nums(node, par):
  global sizes
  global order
  if sizes[node] > 0:
    return sizes[node]
  children = tree[node]
  res = 1
  for child in children:
    if child == par:
      continue
    order.append([child, node])
    res += calc_nums(child, node)
  sizes[node] = res
  return res

_ = calc_nums(root, par)


# 各頂点について、その頂点が穴あき度としてカウントされる状況を独立に計算する
demo = 0 # 分子
div = pow(2, N, MOD) # 分母
base = pow(2, N-1, MOD) - 1
for node, par in order:
  children = tree[node]
  num = base
  num_par = N - 1
  for child in children:
    if child == par:
      continue
    s = sizes[child]
    num_par -= s
    num -= pow(2, s, MOD) - 1
  num -= pow(2, num_par, MOD) - 1
  demo += num
    
ans = demo * pow(div, MOD-2, MOD) % MOD
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
MOD = 10**9 + 7
tree = [[] for i in range(N+1)]
for i in range(N-1):
  a, b = map(int, input().split())
  tree[a].append(b)
  tree[b].append(a)

# 頂点1をルートにして各頂点より下にある部分木の頂点数を求めていく
root, par = 1, 0
sizes = [0] * (N+1)
order = [[root, par]]
def calc_nums(node, par):
  global sizes
  global order
  if sizes[node] > 0:
    return sizes[node]
  children = tree[node]
  res = 1
  for child in children:
    if child == par:
      continue
    order.append([child, node])
    res += calc_nums(child, node)
  sizes[node] = res
  return res

_ = calc_nums(root, par)

# 2の累乗を事前に計算しておく
prod2 = [1]
for i in range(N):
  prod2.append(prod2[-1] * 2 % MOD)

# 各頂点について、その頂点が穴あき度としてカウントされる状況を独立に計算する
demo = 0 # 分子
div = prod2[N] # 分母
base = prod2[N-1] - 1
for node, par in order:
  children = tree[node]
  num = base
  num_par = N - 1
  for child in children:
    if child == par:
      continue
    s = sizes[child]
    num_par -= s
    num -= prod2[s] - 1 
  num -= prod2[num_par] - 1
  demo += num
    
ans = demo * pow(div, MOD-2, MOD) % MOD
print(ans)
### BUGGY CODE ###

import numpy as np


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n = int(input())
A = np.array(list(map(int, input().split())), dtype=np.int)
all_pattern = n * (n+1) // 2
check = all_pattern // 2 + bool(all_pattern % 2)
X = np.sort(A)

left = 0
right = n

while left + 1 < right:
    idx = (left+right) // 2
    x = X[idx]
    up_or_down = np.where(A >= x, 1, -1)
    cumsum = np.hstack([np.array([n]), np.cumsum(up_or_down) + n])

    tree = Bit(2*n+1)
    pattern = 0
    for p in cumsum:
        pattern += tree.sum(p)
        tree.add(p, 1)

    if pattern >= check:
        left = idx
    else:
        right = idx

print(X[left])


### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n = int(input())
A = list(map(int, input().split()))
all_pattern = n * (n+1) // 2
check = all_pattern // 2 + bool(all_pattern % 2)
X = sorted(A)

left = 0
right = n

while left + 1 < right:
    idx = (left+right) // 2
    x = X[idx]
    up_or_down = [1 if num >= x else -1 for num in A]
    cumsum = [n]
    total = n
    for point in up_or_down:
        total += point
        cumsum.append(total)

    tree = Bit(2*n+1)
    pattern = 0
    for p in cumsum:
        pattern += tree.sum(p)
        tree.add(p, 1)

    if pattern >= check:
        left = idx
    else:
        right = idx

print(X[left])
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
sumlist = []
for i in range(N):
    for j in range(i+1):
        sumlist.append(sum(A[j:j+N-i]))
sumlist.sort(reverse=True)
sumlist = np.array(sumlist)
ans = sumlist[0]
for i in range(40, -1, -1):
    tmp = (ans & (2 ** i)) // (2 ** i)
    if tmp:
        start = i
        break
f = lambda x: (x & onehot) // onehot
ans_list = [0]
for i in range(start, -1, -1):
    onehot = 2 ** i
    tmp = sum(map(f, sumlist))
    if tmp >= K:
        and_result = list(map(f, sumlist))
        and_result = np.array(and_result).astype(np.bool)
        sumlist = sumlist[and_result]
        ans = sumlist[0]
        for j in range(1, K):
            ans = ans & sumlist[j]
        ans_list.append(ans)
print(max(ans_list))


### FIXED CODE ###

from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))
cusum = [A[0]]
for i in range(1, N):
    cusum += [cusum[-1]+A[i]]
B = []
for i in range(N):
    B += [cusum[i]]
    for j in range(i+1, N):
        B += [cusum[j] - cusum[i]]
max_bit = 43
ans = 0
while max_bit > 0:
    counter = Counter()
    for b in B:
        for i in range(44):
            if b & 1 == 1:
                counter[i] += 1
            b = b >> 1
    for i in range(max_bit, -1, -1):
        if counter[i] >= K:
            filter_bit = 2 ** i
            B = [b for b in B if b & filter_bit == filter_bit]
            max_bit = i-1
            ans += filter_bit
            break
        max_bit = i
print(ans)
### BUGGY CODE ###

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

F = []
G = []
for i in range(1, N + 1):
    F.append(i + A[i - 1])
    G.append(i - A[i - 1])

for i in range(N):
    for j in range(N):
        if F[i] == G[j]:
            ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
X, Y = [], []
for i in range(N):
    X.append(i + 1 + A[i])
    Y.append(i + 1 - A[i])
XL = Counter(X)
c = 0
for y in Y:
    c += XL.get(y, 0)
print(c)
### BUGGY CODE ###


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

n = int(input())
s = list(input())

# 0 0 1 1 全部黒
# 0 1 2 2
# 0 1 1 1
# 0 1 1 2 全部白
#  # . #


ans = n

for i in range(n+1):
    sum = [0]*(n+1)
    for j in range(0,i):
        # print('i = {}, j = {}'.format(i,j))
        if s[j] == '#':
            sum[j+1] = sum[j] + 1
        else:
            sum[j+1] = sum[j]
        if sum[j+1]>n:
            break

    for k in range(i, n):
        # print('i = {}, k = {}'.format(i,k))
        if s[k] == '.':
            sum[k+1] = sum[k] + 1
        else:
            sum[k+1] = sum[k]
        if sum[k+1]>n:
            break
    ans = min(ans, sum[n])
print(ans)

### FIXED CODE ###


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

n = int(input())
s = list(input())

sum_w = [0]*(n+1)
sum_b = [0]*(n+1)
ans = n

for i in range(n):
    if s[i] == '#':
        sum_b[i+1] = sum_b[i] + 1
    else:
        sum_b[i+1] = sum_b[i]

    if s[i] == '.':
        sum_w[i+1] = sum_w[i] + 1
    else:
        sum_w[i+1] = sum_w[i]

ans = n
for i in range(n+1):
    ans = min(ans, sum_b[i]+sum_w[n]-sum_w[i])
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[0]
for i in range(1,n):
  b=a[i]
  l+=[min(l[j]+abs(b-a[j])for j in range(i-min(k,i),i))]
print(l[-1])

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[0]
for i in range(1,n):
  b=a[i]
  l.append(min(l[j]+abs(b-a[j])for j in range(i-min(k,i),i)))
print(l[-1])
### BUGGY CODE ###

n=int(input())
i = 1
for nn in range(1,n+1):
  i *= nn
  
print(i%(10**9+7))

### FIXED CODE ###

import math
print(math.factorial(int(input()))%(10**9+7))