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

import numpy as np
from numba import njit

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

A_list = [0]+list(map(int, input().split()))
A_np=np.array(A_list)
#print(A_np)

@njit
def update(A_np):
  new_A_np=np.array([0]*(N+1))
  for i in range(1,N+1):
    tmp_np=np.array([0]*(N+1))
    #print(A_np)
    mi=i-A_np[i]
    ma=i+A_np[i]
    if mi<0:
      mi=0
    if ma>N:
      ma=N
    #print(mi,ma)
    tmp_np[mi:ma+1]=1
    #print(tmp_np)
    new_A_np+=tmp_np
  #print(new_A_np)
  A_np=new_A_np
  return(A_np)

for j in range(K):
  A_np=update(A_np)
  if sum(A_np[1:N+1])==N*N:
    break
    
for i in range(1,N+1):
  print(A_np[i],end=" ")


### FIXED CODE ###

import numpy as np
from numba import njit

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

A_list = np.array([0]+list(map(int, input().split())))

@njit
def update(A_list):

  for j in range(min(K,46)):
    new_A=np.zeros(N+2,dtype=np.int64)
    for i in range(1,N+1):
      #print(new_A)
      mi=i-A_list[i]
      ma=i+A_list[i]
      if mi<0:
        mi=0
      if ma>N:
        ma=N
      #new_A[mi:ma+1]+=1
      new_A[mi]+=1
      new_A[ma+1]-=1

    A_list=np.cumsum(new_A)
    #if sum(A_list[1:N+1])==N*N:
    #  return(A_list)    
    #  break
      
  return(A_list)

A_list=update(A_list)
for i in range(1,N+1):
  print(A_list[i],end=" ")
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
from itertools import permutations
N,M = map(int, input().split())
cost = [0,2,5,5,4,5,6,3,7,6]
A = list(map(int, input().split()))

p = []
for a in A:
    p.append( (cost[a], a) )
costp = sorted(p)


costX = [ z[0] for z in costp]
A = [ z[1] for z in costp]

dp = [""] * (N+1)

for c,a in zip(costX,A):
    i = N 
    if i-c >= 0:
        dp[i-c] = str(a)

for i in range(N-1, 1, -1):
    if len(dp[i]) == 0:
        continue
    
    for c,a in zip(costX,A):
        for p in permutations( [dp[i], str(a)]):

            if i-c >= 0:
                if dp[i-c] == "":
                    dp[i-c] = str(int( "".join(p)))
                else:
                    dp[i-c] = str(max(int(dp[i-c]), int( "".join(p))))
    
print(dp[0])
    
    
    
    




### FIXED CODE ###

N,M = map(int, input().split())
cost = [0,2,5,5,4,5,6,3,7,6]
A = list(map(int, input().split()))

costp = sorted([ (cost[a] ,a) for a in A], key=lambda x:x[1], reverse=True)
costX = [ z[0] for z in costp]
A = [ z[1] for z in costp]
# print(A,costX)

dp = [-1] * (N+1)
dp[N] = 0

for i in range(N, 1, -1):
    if (dp[i]) == -1:
        continue

    for c,a in zip(costX,A):
        if i-c >= 0:
            dp[i-c] = dp[i] + 1


ans = ""

i = 0
while i<N:
    # print(i)
    for c,a in zip(costX,A):
        # print(c,a,i)
        # if i+c <= N:
        #     print("i: {}, dp[i]=".format(i), dp[i], ", dp[i+c]: ", dp[i+c], "c=",c, "a=",a)
        # else: print("i: {}, dp[i]=".format(i), dp[i], ",c=",c, "a=",a)
        
        if i+c <= N:
            if dp[i]-1 == dp[i+c]:
                ans += str(a)
                i = i+c
                break

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

import sys
import numpy as np
from collections import Counter
input = sys.stdin.readline
n=int(input())
a = tuple(map(int,input().split()))

c = 0
n = 10**7
for i in range(2*n):
  c += 1
print(c)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = tuple(map(int,input().split()))
c1 = a.count(1)
c2 = a.count(2)
c3 = a.count(3)

dp = [[[0.0]*(n+1) for i in range(n+1)] for j in range(n+1)] 
dp[0][0][0] = 0
for i in range(c3+1):
    for j in range(c2+c3-i+1):
        for k in range(n-i-j+1):
            if i == j == k == 0:
                continue
            tmp = n
            if k != 0:
                tmp += k*dp[k-1][j][i]
            if j != 0:
                tmp += j*dp[k+1][j-1][i]
            if i != 0:
                tmp += i*dp[k][j+1][i-1]
            dp[k][j][i] = tmp/(i+j+k)

print(dp[c1][c2][c3])
### BUGGY CODE ###

N, M = map(int, input().split())
ans = 1
for i in range(2, M//N+1):
    if M % i == 0:
        ans = i
print(ans)


### FIXED CODE ###

import math
N, M = map(int, input().split())
tmp = [1]
if N == 1:
    print(M)
else:
    for i in range(2, int(math.ceil(M**0.5))):
        if M % i == 0:
            tmp.append(i)
            tmp.append(int(M/i))
    ans = 1
    for x in tmp:
        if M / x >= N:
            ans = max(ans, x)
    print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A_lis = list(map(int, input().split()))
#A_lis.sort()

def discount(B_lis,delta):
    #B_lis.sort()
    max_index = B_lis.index(max(B_lis))
    delta[max_index] += B_lis[max_index]/2
    B_lis[max_index] = B_lis[max_index]/2
    #B_lis.sort()
    return B_lis,delta

dis = [0]*N
for i in range(M):
    A_lis,dis = discount(A_lis,dis)
    #print(A_lis)
    #print(dis)

ans = 0
for i in range(len(A_lis)):
    ans+=int(A_lis[i])
print(ans)


### FIXED CODE ###

import heapq

N,M = map(int, input().split())
A_lis = list(map(lambda x: int(x)*(-1), input().split()))

heapq.heapify(A_lis)

def discount(A_lis):
    popped = heapq.heappop(A_lis)
    heapq.heappush(A_lis,popped/2)
    return A_lis

for i in range(M):
    A_lis = discount(A_lis)
ans = 0
for i in A_lis:
    ans += int(i)
print(ans*(-1))
### BUGGY CODE ###

N, M = (list)(map(int, input().split()))
A = (list)(map(int, input().split()))
A[0] %= M

for i in range(1, N):
    A[i] += A[i-1]
    A[i] %= M

ans = 0
for i in range(M):
    if i == 0:
        ans += A.count(i)
    c = A.count(i)
    if c >= 2:
        ans += c*(c-1)//2
print(ans)


### FIXED CODE ###

from collections import Counter
N, M = (list)(map(int, input().split()))
A = (list)(map(int, input().split()))
A[0] %= M

for i in range(1, N):
    A[i] += A[i-1]
    A[i] %= M

ans = 0

C = Counter(A)
for num, val in C.items():
    if num == 0:
        ans += val
    if val >= 2:
        ans += val*(val-1)//2
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
Highs = list(map(int, input().split()))
Roads = [list(map(int, input().split())) for _ in range(M)]

goods = [i+1 for i in range(N)]

def remove_if(li, e):
    if e in li:
        li.remove(e)

for road in Roads:
    f = road[0]
    t = road[1]

    f_h = Highs[f-1]
    t_h = Highs[t-1]

    if f_h > t_h:
        remove_if(goods, t)
    elif f_h < t_h:
        remove_if(goods,f)
    else:
        remove_if(goods,f)
        remove_if(goods,t)

print(len(goods))


### FIXED CODE ###

N, M = map(int, input().split())
Highs = list(map(int, input().split()))
Roads = [list(map(int, input().split())) for _ in range(M)]

winner = set()
looser = set()
appears = set()

def devide(w, l):
    if w not in looser:
        winner.add(w)
    if l not in looser:
        looser.add(l)
    if l in winner:
        winner.remove(l)

def remove(e):
    if e not in looser:
        looser.add(e)
    if e in winner:
        winner.remove(e)

for road in Roads:
    f = road[0]
    t = road[1]

    appears.add(f)
    appears.add(t)

    f_h = Highs[f-1]
    t_h = Highs[t-1]

    if f_h > t_h:
        devide(f, t)
    elif f_h < t_h:
        devide(t, f)
    else:
        remove(t)
        remove(f)

print(len(winner)+N-len(appears))
### BUGGY CODE ###

# dfs
import collections
n,m,k = map(int, input().split())

friend = [[]*(n+1) for _ in range(n+1)]
block = [[]*(n+1) for _ in range(n+1)]
friend_candidate = [[0]*(n+1) for _ in range(n+1)]
teams = [0]*(n+1)
for _ in range(m):
  a,b = map(int, input().split())
  friend[a].append(b)
  friend[b].append(a)
for _ in range(k):
  c,d = map(int, input().split())
  block[c].append(d)
  block[d].append(c)
  
def dfs(i):
  teams[i] = team
  for j in friend[i]:
    if teams[j] != 0:
      continue
    teams[j] = team
    dfs(j)

team=1
for i in range(1,n+1):
  if teams[i] != 0:
    continue
  dfs(i)
  team+=1
c = collections.Counter(teams)
for i in range(1,n+1):
  temp = c[teams[i]]-len(friend[i])-1
  for j in block[i]:
    if teams[j] == teams[i]:
      temp -= 1
  print(temp,end='')
  if i != n:
    print(" ",end='')

### FIXED CODE ###

# dfs
import collections,sys
sys.setrecursionlimit(10**9)
n,m,k = map(int, input().split())

friend = [[]*(n+1) for _ in range(n+1)]
block = [[]*(n+1) for _ in range(n+1)]
teams = [0]*(n+1)
for _ in range(m):
  a,b = map(int, input().split())
  friend[a].append(b)
  friend[b].append(a)
for _ in range(k):
  c,d = map(int, input().split())
  block[c].append(d)
  block[d].append(c)
  
def dfs(i):
  teams[i] = team
  for j in friend[i]:
    if teams[j] != 0:
      continue
    dfs(j)

team=1
for i in range(1,n+1):
  if teams[i] != 0:
    continue
  dfs(i)
  team+=1

c = collections.Counter(teams)

for i in range(1,n+1):
  temp = c[teams[i]]-len(friend[i])-1
  for j in block[i]:
    if teams[j] == teams[i]:
      temp -= 1
  print(temp, end='')
  if i != n:
    print(" ", end='')
### BUGGY CODE ###

n = int(input())
l = ([int(input()) for j in range(n)])
a = max(l)
for i in range(n):
  if l[i]==a:
    print(max(l[:i]+l[i+1:]))
  else:
    print(a)

### FIXED CODE ###

n = int(input())
l = ([int(input()) for j in range(n)])
a = sorted(l)[-1]
b = sorted(l)[-2]

for i in range(n):
  if l[i]==a:
    print(b)
  else:
    print(a)
### BUGGY CODE ###

from queue import Queue

'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N = int(input())
q = Queue()
c = [0 for i in range(N)]
l = [0 for i in range(N)]
A = [[] for i in range(N)]
W = [[0 for i in range(N)] for i in range(N)]

for i in range(N-1):
	u, v, w = map(int,input().split())
	u = u - 1
	v = v - 1
	
	A[u].append(v)
	A[v].append(u)
	W[u][v] = w
	W[v][u] = w

q.put(0)
while not q.empty():
	i = q.get()
	c[i] = 1
	for j in A[i]:
		if c[j] == 0:
			q.put(j)
			l[j] = l[i] + W[i][j]

for i in l:
	print('{}'.format(i%2))

### FIXED CODE ###

N = int(input())
q = []
c = [0 for i in range(N)]
l = [0 for i in range(N)]
A = [[] for i in range(N)]
W = [[] for i in range(N)]

for i in range(N-1):
	u, v, w = map(int,input().split())
	u = u - 1
	v = v - 1
	
	A[u].append(v)
	A[v].append(u)
	W[u].append(w)
	W[v].append(w)

q.append(0)
while len(q):
	i = q.pop(0)
	c[i] = 1
	k = 0
	for j in A[i]:
		if c[j] == 0:
			q.append(j)
			l[j] = l[i] + W[i][k]
		k = k + 1

for i in l:
	print('{}'.format(i%2))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
count = [0] * N
answer = [-1] * N
p = []
for i in range(N):
  count[i]  = A.count(i + 1)
  
nanimo = 0 
for i in range(N):
  nanimo += count[i] * (count[i] - 1) // 2
for i in range(N):
  if answer[A[i] - 1] != -1:
    p.append(answer[A[i] - 1])
  else:
    tekito = count[A[i] - 1]
    if tekito == 2:
      s = nanimo - 1
    elif tekito == 1:
      s = nanimo
    else:
      s = nanimo -  ((tekito * (tekito - 1) //2) - ((tekito - 1) * (tekito - 2) //2))
    p.append(s)
    answer[A[i] - 1] = s

for i in p:
  print(i)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
count = [0] * N
for i in range(N):
  count[A[i] - 1]  += 1
  
nanimo = 0 
for i in range(N):
  nanimo += count[i] * (count[i] - 1) // 2
for i in range(N):
  tekito = count[A[i] - 1]
  if tekito == 2:
    s = nanimo - 1
  elif tekito == 1:
    s = nanimo
  else:
    s = nanimo -  ((tekito * (tekito - 1) //2) - ((tekito - 1) * (tekito - 2) //2))
  print(s)
### BUGGY CODE ###

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

x = a[0]
for i in range(n - 1):
    x *= a[i + 1]
if x > 10 ** 18:
    print(-1)
else:
    print(x)

### FIXED CODE ###

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

if 0 in a:
    print(0)
    exit()

x = a[0]
for i in range(n - 1):
    x *= a[i + 1]
    if x > 10 ** 18:
        print(-1)
        exit()
print(x)
### BUGGY CODE ###

#135_D
s=input()
mod=10**9+7

#dp[i][j]...i桁目までで余りがj
dp=[[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1

for i in range(0,len(s)):
    if s[i]=='?':
        for j in range(13):
            for x in range(10):
                dp[i+1][(j*10+x)%13]+=dp[i][j]
    else:
        x=int(s[i])
        for j in range(13):
            dp[i+1][(j*10+x)%13]+=dp[i][j]
    
print(dp[len(s)][5]%mod)

### FIXED CODE ###

#135_D
s=input()
mod=10**9+7

#dp[i][j]...i桁目までで余りがj
dp=[[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1

for i in range(0,len(s)):
    if s[i]=='?':
        for j in range(13):
            for x in range(10):
                dp[i+1][(j*10+x)%13]+=dp[i][j]
                dp[i+1][(j*10+x)%13]%=mod
    else:
        x=int(s[i])
        for j in range(13):
            dp[i+1][(j*10+x)%13]+=dp[i][j]
            dp[i+1][(j*10+x)%13]%=mod
    
print(dp[len(s)][5])
### BUGGY CODE ###

# coding:utf-8
def main():
    # print("start")
    A,B = map(int,input().split())
    # print(A%4)
    point_A = A
    point_B = B
    if A%4 > 0:
        point_A = A - (A%4) + 4
    if B%4 > 0:
        point_B = B - (B%4)

    # print(point_A,point_B)
    # print()
    ans = 0
    for i in range(A,B+1):
        if i in range(point_A,point_B):
            continue
        else:
            ans = ans ^ i
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

# coding:utf-8
def main():
    # print("start")
    A,B = map(int,input().split())
    # print(A%4)
    point_A = A
    point_B = B
    if A%4 > 0:
        point_A = A - (A%4) + 4
    if B%4 > 0:
        point_B = B - (B%4)

    # print(point_A,point_B)
    # print()
    ans = 0
    for i in range(A,point_A):
        ans = ans ^ i

    for i in range(point_B,B+1):
        ans = ans ^ i
    print(ans)


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

N, M = map(int, input().split(" "))
group_list = list()
check = [-1 for i in range(N)]
g_num = 0
for i in range(M):
    x, y, z = map(int, input().split(" "))
    x -= 1
    y -= 1
    if check[x] == -1:
        if check[y] == -1:
            check[x] = g_num
            check[y] = g_num
            g_num += 1
        else:
            check[x] = check[y]
    else:
        if check[y] == -1:
            check[y] = check[x]
        else:
            _from = check[y]
            _to = check[x]
            for i in range(N):
                if check[i] == _from:
                    check[i] == _to

s = set(check)
s.add(-1)
s.remove(-1)
count = 0
for i in range(N):
    if check[i] == -1:
        count += 1
print(count + len(s))


### FIXED CODE ###

class Node:
    def __init__(self, val):
        self.num = val
        self.val = val
        self.is_parent = True
        self.parent = None
        self.childs = []

    def show(self):
        print(self.num, end=" ")
        print(self.is_parent, end=" ")
        for child in self.childs:
            print(child.num, end=" ")

def root(node):
    depth = 0
    while node.parent != None:
        node = node.parent
        depth += 1
    return node, depth

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

roots = [Node(i) for i in range(N)]
count = N

for i in range(M):
    x, y, z = map(int, input().split())
    x = roots[x-1]
    y = roots[y-1]
    if x.is_parent and y.is_parent:
            y.is_parent = False
            y.parent = x
            count -= 1
            x.childs.append(y)
    else:
        root_x, depth_x = root(x)
        root_y, depth_y = root(y)
        if root_x != root_y:
            if depth_x >= depth_y:
                root_y.is_parent = False
                root_y.parent = root_x
                count -= 1
                root_x.childs.append(root_y)
            else:
                root_x.is_parent = False
                root_x.parent = root_y
                count -= 1
                root_y.childs.append(root_x)

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

n,w = map(int, input().split())

item = []
for i in range(n):
    weight, value = map(int, input().split())
    item.append((weight, value))

max_value = [[0]*(w+1) for _ in range(n+1)]
for i in range(1, n+1):
    weight, value = item[i-1]
    for j in range(1, weight):
        max_value[i][j] = max(max_value[i-1][j], max_value[i][j-1])
    for j in range(weight, w+1):
        max_value[i][j] = max(max_value[i-1][j], max_value[i][j-1], max_value[i-1][j-weight] + value)

print(max_value[n][w])

### FIXED CODE ###

n,w = map(int, input().split())
max_value = [[0]*(w+1) for _ in range(n+1)]
for i in range(1, n+1):
    weight, value = map(int, input().split())
    for j in range(1, weight):
        max_value[i][j] = max_value[i-1][j]
    for j in range(weight, w+1):
        max_value[i][j] = max(max_value[i-1][j], max_value[i-1][j-weight] + value)

print(max_value[n][w])
### BUGGY CODE ###

ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

n=ri()
a=rl()
a.sort()
#nCr % MOD
def cmb(n, r, MOD=0):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
            if MOD != 0:
                result %= MOD
 
    return result

import bisect
ans = []
for i in range(1,min(n,len(str(n))+3)):
    p = a[-i]
    p2 = p/2
    q_i = bisect.bisect_left(a,p2)
    if ((a[q_i]-p2) > (p2 - a[q_i-1])) or p==a[q_i] and q_i != 0:
        q_i -= 1
    q = a[q_i]
    ans.append([cmb(p,q),p,q])

ans.sort(key=lambda x:x[0],reverse=True)
print(*ans[0][1:])

### FIXED CODE ###

ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

n=ri()
a=rl()
a.sort()


import bisect

p = a[-1]
p2 = p/2
q_i = bisect.bisect_left(a,p2)
if ((a[q_i]-p2) > (p2 - a[q_i-1]) or p==a[q_i]) and q_i != 0:
    q_i -= 1
q = a[q_i]

print(p,q)
### BUGGY CODE ###

import sys
import itertools
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, A = in_nn()
    X = in_nl()

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

    N1 = N // 2
    N2 = N - N1

    comb1 = itertools.product(range(2), repeat=N1)
    comb2 = itertools.product(range(2), repeat=N2)

    d1 = defaultdict(int)
    d2 = defaultdict(int)

    for comb in comb1:
        sum = 0
        for i, c in enumerate(comb):
            if c == 1:
                sum += X[i]
        d1[sum] += 1

    for comb in comb2:
        sum = 0
        for i, c in enumerate(comb):
            if c == 1:
                sum += X[N1 + i]
        d2[sum] += 1

    ans = 0
    for k, v in d1.items():
        ans += v * d2[-k]

    ans -= 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N, A = in_nn()
    X = in_nl()
    X = [x - A for x in X]

    dp = [0] * 5050
    dp[2525] = 1

    for i in range(N):

        next_dp = copy.copy(dp)
        for t in range(5050):
            if X[i] + t < 5050:
                next_dp[X[i] + t] += dp[t]

        dp = next_dp

    print(dp[2525] - 1)


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

import numpy as np
n,*a=map(int,open(0).read().split())
mod=10**9+7
b0=np.array([0 for i in range(60)])
b1=np.array([0 for i in range(60)])
for i in range(n):
  ai=a[i]
  j=0
  while ai>0:
    if ai&1==1:
      b1[j]+=1
    else:
      b0[j]+=1
    j+=1
    ai>>=1
  b0[j:]+=1
ans=0
for i in range(60):
  ans+=(b0[i]*b1[i]*pow(2,i,mod))
  ans%=mod
print(ans)

### FIXED CODE ###

import numpy as np
n,*a=map(int,open(0).read().split())
mod=10**9+7
a=np.array(a)
ans=0
for i in range(60):
  c=len(a[a&1==1])
  a>>=1
  ans+=c*(n-c)*pow(2,i,mod)
  ans%=mod
print(ans)
### BUGGY CODE ###

import sys
import itertools
import math

A,B,N = map(int, input().split())
a = 0
for i in range(1,N+1):
    a = max(a, math.floor(A*i/B) - A * math.floor(i/B))

print(a)

### FIXED CODE ###

import sys
import itertools
import math

A,B,N = map(int, input().split())
a = 0

i = min(B-1,N)


print(math.floor(A*i/B) - A * math.floor(i/B))
### BUGGY CODE ###

H,W = map(int,input().split())
Ch, Cw = map(lambda x: int(x)-1,input().split())
Dh, Dw = map(lambda x: int(x)-1,input().split())
S = []
for i in range(H):
  S.append(input())


from collections import deque

def bfs(sh,sw):
  queue = deque([(sh,sw)])
  d = {}
  now = set()
  d[(sh,sw)]=0
  
  while queue:
    h,w = queue.popleft()
    now.add((h,w))
    for nh,nw in [(h-1,w),(h+1,w),(h,w-1),(h,w+1)]:
      if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and (nh,nw) not in d) == False: continue
      queue.append((nh,nw))
      now.add((nh,nw))
      d[(nh,nw)]=d[(h,w)]

    if queue: continue
    for h,w in now:
      for i in range(-2,3):
        for j in range(-2,3):
          if i==0 and abs(j)<=1: continue
          if j == 0 and abs(i)<=1: continue
          nh,nw = h-i,w-j
          if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and (nh,nw) not in d) == False: continue
          d[(nh,nw)]=d[(h,w)]+1
          queue.append((nh,nw))
    now = set()
    #print(queue)
  return d

d = bfs(Ch,Cw)
if (Dh,Dw) not in d: 
  print(-1)
  exit()
print(d[(Dh,Dw)])

### FIXED CODE ###

H,W = map(int,input().split())
Ch, Cw = map(lambda x: int(x)-1,input().split())
Dh, Dw = map(lambda x: int(x)-1,input().split())
S = []
for i in range(H):
  S.append(input())


from collections import deque

def bfs(sh,sw):
  queue = deque([(sh,sw)])
  d = [[None]*W for _ in range(H)]
  now = set()
  d[sh][sw]=0
  
  while queue:
    h,w = queue.popleft()
    now.add((h,w))
    for nh,nw in [(h-1,w),(h+1,w),(h,w-1),(h,w+1)]:
      if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
      queue.append((nh,nw))
      now.add((nh,nw))
      d[nh][nw]=d[h][w]

    if queue: continue
    for h,w in now:
      for i in range(-2,3):
        for j in range(-2,3):
          if i==0 and abs(j)<=1: continue
          if j == 0 and abs(i)<=1: continue
          nh,nw = h-i,w-j
          if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
          d[nh][nw] = d[h][w]+1
          queue.append((nh,nw))
    now = set()
    #print(queue)
  return d

d = bfs(Ch,Cw)
if d[Dh][Dw] == None: 
  print(-1)
  exit()
print(d[Dh][Dw])