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

from itertools import product
N = int(input())

N_ =str(N)
n_o=len(N_)

# ans:条件を満たす組みの個数
ans=0

def get_ans(A):
    ans=0
    A_=str(A)
    a_s=A_[0]
    a_e=A_[-1]
#     print(a_s,a_e)
    
    if int(a_e) == 0:
        return 0

    if a_s == a_e:
        ans+=1

    for b_o in range(2,n_o+1):
        B_temp = []
        if b_o < n_o:
            ans += 10**(b_o-2)

        elif b_o == n_o:
            if int(a_e) > int(N_[0]):
                break
            elif int(a_e) < int(N_[0]):
                ans += 10**(b_o-2)
            else:      
                for p in product(range(10),repeat=n_o-2):
                    ans_temp=int(a_e+''.join(map(str,p))+a_s)
                    if ans_temp > N:
                        break
                    ans+=1 
                    B_temp.append(ans_temp)
    #                 print(B_temp)

        else:
            break
        
    return ans

for a in range(1,N+1):
#     print('====',a)
    ans_=get_ans(a)
    ans+=ans_
print(ans)

### FIXED CODE ###

N = int(input())

C=[[0]*10 for _ in range(10)]

for n in range(1,N+1):
    n=str(n)
    n_s=int(n[0])
    n_e=int(n[-1])
    
    C[n_s][n_e]+=1
    
ans=0
for c_1 in range(10):
    for c_2 in range(10):
        ans += C[c_1][c_2]*C[c_2][c_1]
        
print(ans)
### BUGGY CODE ###

import sys
 
N, W = map(int, input().split())
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)
MAX_VALUE = sum(value for (weight, value) in WEIGHTS)
 
INF = sys.maxsize
DP = [[INF for _ in range(MAX_VALUE + 1)] for _ in range(M + 1)]
 
for i, (weight, value) in enumerate(WEIGHTS):
    for v in range(MAX_VALUE + 1):
        if v - value >= 0:
            DP[i+1][v] = min(DP[i][v - value] + weight, DP[i][v])
        else:
            DP[i+1][v] = min(DP[i][v], weight)
 
res = 0
for v, w in enumerate(DP[M]):
    if w <= W:
        res = max(res, v)
 
print(res + 1)
 
# dp_ij := 1~jまでのアイテムからいくつかを選んで総価値iを超えないようにしたときの最少重量

### FIXED CODE ###

import sys

N, W = map(int, input().split())
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)
MAX_VALUE = sum(value for (weight, value) in WEIGHTS)

INF = sys.maxsize
DP = [[INF for _ in range(MAX_VALUE + 1)] for _ in range(M + 1)]

for i, (weight, value) in enumerate(WEIGHTS):
    for v in range(MAX_VALUE + 1):
        if v - value >= 0:
            DP[i+1][v] = min(DP[i][v - value] + weight, DP[i][v])
        else:
            DP[i+1][v] = min(DP[i][v], weight)

res = 0
for v, w in enumerate(DP[M]):
    if w <= W:
        res = max(res, v)

print(res + 1)
### BUGGY CODE ###

n,q = (int(i) for i in input().split())
s = input()
x = [[i for i in input().split()] for i in range(q)]
l,r,s = 0,n+1,"#"+s+"#"
while l+1<r:
    now = (l+r)//2
    for i,j in x:
        if s[now]==i:
            if j=="L": now-=1
            else: now+=1
        if now*(now-n-1)==0: break
    if now: r = (l+r)//2
    else: l = (l+r)//2
L,l,r = l,0,n+1
while l+1<r:
    now = (l+r)//2
    for i,j in x:
        if s[now]==i:
            if j=="L": now-=1
            else: now+=1
        if now*(now-n-1)==0: break
    if now-n-1: l = (l+r)//2
    else: r = (l+r)//2
print(r-L-1)

### FIXED CODE ###

n,q = (int(i) for i in input().split())
s = input()
x = [[i for i in input().split()] for i in range(q)]
l,r,s = 0,n+1,"#"+s+"#"
for i,j in x[::-1]:
    if l<=n and s[l+1]==i and  j=="L": l+=1
    elif s[l]==i and j=="R": l-=1
    if s[r-1]==i and j=="R": r-=1
    elif s[r]==i and j=="L": r+=1
print(max(0,r-l-1))
### BUGGY CODE ###

S = input()
q = int(input())
sw = 1
for i in range(q):
  e = list(map(str, input().split()))
  t = int(e[0])

  if t == 1:
    sw = sw * -1
  elif t == 2:
    f = int(e[1])
    if (sw == 1 and f == 1) or (sw == -1 and f == 2):
      S = e[2] + S
    elif (sw == -1 and f == 1) or (sw == 1 and f == 2):
      S = S + e[2]

if sw == -1:
  S = S[::-1]

print(S)

### FIXED CODE ###

S=input()
Q=int(input())
L=list()
B=True
X=''
Y=''
for i in range(Q):
  L=list(input().split())
  if L[0]=='1':
    B=not(B)
  else:
    if ((L[1]=='1' and B) or (not(L[1]=='1' or B))):
      Y=Y+L[2]
    else:
      X=X+L[2]
S=S[::-1]
S=S+Y
S=S[::-1]
S=S+X
if not(B):
  S=S[::-1]
print(S)
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]
set_a = set(a)
ans = 0

for ai in set_a:
  ai_count = a.count(ai)
  ans += ai_count - ai if ai_count >= ai else ai_count

print(ans)

### FIXED CODE ###

from collections import Counter

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

cnt = Counter(a)
ans = 0

for ai, num in cnt.items():
  if num >= ai:
  	ans += num - ai  
  else:
    ans += num

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

N=int(input())
A=list(map(int,input().split()))
import collections as col

for i in range(N):
    ans=0
    k=A[:i]+A[i+1:]
    sk=set(k)
    ck=col.Counter(k)
    for i in sk:
        if ck[i]==1:
            continue
        else:
            ans += (ck[i]*(ck[i]-1))//2
    print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
import collections as col

sa=set(A)
ca=col.Counter(A)
num=0
for i in sa:
    if ca[i]==1:
        continue
    else:
        num += (ca[i]*(ca[i]-1))//2
for i in A:
    ans = num - (ca[i]-1)
    print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
P = [input().split() for i in range(Q)]

count = 0

for query in P:
    if query[0]=="1":
        count+=1
    else:
        if query[1]=="1":
            if count%2==0:
                S=query[2]+S
            else:
                S=S+query[2]
        else:
            if count%2==0:
                S=S+query[2]
            else:
                S=query[2]+S
if count%2==1:
    S=S[::-1]
    
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
P = [input().split() for i in range(Q)]

count = 0
left = ""
right = ""
for query in P:
    if query[0]=="1":
        count+=1
    else:
        if query[1]=="1":
            if count%2==0:
                left+=query[2]
            else:
                right+=query[2]
        else:
            if count%2==0:
                right+=query[2]
            else:
                left+=query[2]
                
S = left[::-1]+S+right
if count%2==1:
    S=S[::-1]
    
print(S)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
v = []
now = 0
for i in range(K):
  p = A[now]
  now = p-1
  if p in v:
    j = v.index(p)
    df = i-j
    Kn = (K-i-1) % df
    for k in range(Kn):
      p = A[now]
      now = p-1
    break
  else:
    v.append(p)
print(p)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
v = []
w = {}
now = 0
for i in range(K):
  p = A[now]
  now = p-1
  if p in w:
    j = v.index(p)
    df = i-j
    Kn = (K-i-1) % df
    p = v[j+Kn]
    break
  else:
    v.append(p)
    w[p] = p
print(p)
### BUGGY CODE ###

n = int(input())
a = [input().split() for i in range(n)]

count = 0
 
for i in a:
    ii = a.count(i)
    if ii%2 ==1:
        count += 1

print(count)

### FIXED CODE ###

n = int(input())
a = [input() for i in range(n)]

count = 0
dic = {}

for i in a:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

for i in dic.values():
    if i%2 == 1:
        count += 1

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

from functools import  reduce
n,k=map(int,input().split())
l=list(map(int,input().split()))
x=reduce(lambda x,y: x*y,l[:k])
temp=[x]
for i in range(k,len(l)):
	if l[i]<=l[i-k]:
		print('No')
	else:
		print('Yes')
		

### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
for i in range(k,len(l)):
	if l[i]<=l[i-k]:
		print('No')
	else:
		print('Yes')
### BUGGY CODE ###

a,b,c,k = map(int,input().split())
num=0
for i in range(1,k+1):
    if i <= a:
        num+=1
        continue
    elif i <= a+b:
        continue
    else:
        num-=1
        continue
print(num)



### FIXED CODE ###

a,b,c,k = map(int,input().split())
if k <= a:
    print(k)
elif k <= a+b:
    print(a)
else:
    print(a-(k-(a+b)))
### BUGGY CODE ###

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

count = 0
for i in range(N[0]+1):
  for j in range(N[0]+1):
    for k in range(N[0]+1):
      s = i + j + k
      if(s == N[1]):
        count += 1
print(count)

### FIXED CODE ###

N = input().split()
N = [int(i) for i in N]
count = 0
for i in range(N[0]+1):
    for j in range(N[0]+1):
        k = N[1] - i - j
        if((k <= N[0])and(k>=0)):
            count += 1
print(count)
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    b=input()
    d=a.count(b)
    if d==0:
        a.append(b)
    else:
        e=1
print(len(a))


### FIXED CODE ###

n=int(input())
a=set()
for i in range(n):
    b=input()
    a.add(b)
print(len(a))
### BUGGY CODE ###

n, m = map(int, input().split())
a = [ int(input()) for _ in range(m) ]
dp = [0]*n
for i in range(n):
  if not i+1 in a:
    if i == 0:
      dp[i] = 1
    elif i == 1:
      dp[i] = 1 + dp[i-1]
    else:
      dp[i] = dp[i-2] + dp[i-1]
  if dp[i] >= 1000000007:
    dp[i] %= 1000000007
print(dp[n-1]%1000000007)

### FIXED CODE ###

n, m = map(int, input().split())
A = [ int(input()) for _ in range(m) ]
dp = [0]*(n+1)
broken = [False]*(n+1)
for i in A:
  broken[i] = True
dp[0] = 1
if not broken[1]:
  dp[1] = 1
for i in range(2, n+1):
  if broken[i]:
    continue
  else:
    dp[i] = dp[i-2] + dp[i-1]

print(dp[n]%(10**9+7))
### BUGGY CODE ###

h,w=map(int,input().split())
w+=2
h+=2
grid='#'*w
for _ in range(h-2):
    grid+='#'+input()+'#'
grid+='#'*w
move=[1,-1,w,-w]
score_a=[0]*(h*w)
score_b=[0]*(h*w)
score_c=[0]*(h*w)
score_d=[0]*(h*w)

for i in range(h*w):
    if grid[i]=='#':
        score_a[i]=0
        score_b[i]=0
    else:
        if i-1>=0 and i-1<=h*w-1:
            score_a[i]+=score_a[i-1]+1
        if i-w>=0 and i-w<=h*w-1:
            score_b[i]+=score_b[i-w]+1
    if grid[h*w-1-i]=='#':
        score_c[h*w-1-i]=0
        score_d[h*w-1-i]=0
    else:
        if h*w-1-i+1<=h*w-1 and h*w-1-i+1>=0:
            score_c[h*w-1-i]+=score_c[h*w-1-i+1]+1
        if h*w-1-i+w<=h*w-1 and h*w-1-i+w>=0:
            score_d[h*w-1-i]+=score_d[h*w-1-i+w]+1
ans=0
for i in range(h*w):
    ans=max(ans, score_a[i]+score_b[i]+score_c[i]+score_d[i]-3)
print(ans)

### FIXED CODE ###

h, w = map(int, input().rsplit())
S = [list(input().rstrip()) for _ in range(h)]
U = [[0] * w for _ in range(h)]
D = [[0] * w for _ in range(h)]
L = [[0] * w for _ in range(h)]
R = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if j == 0:
            if S[i][j] == ".":
                L[i][j] = 1
            continue
        if S[i][j] == "#":
            continue
        else:
            L[i][j] += 1 + L[i][j - 1]
for i in range(h):
    for j in range(w):
        if i == 0:
            if S[i][j] == ".":
                U[i][j] = 1
            continue
        if S[i][j] == "#":
            continue
        else:
            U[i][j] += 1 + U[i - 1][j]
for i in range(h - 1, -1, -1):
    for j in range(w - 1, -1, -1):
        if j == w - 1:
            if S[i][j] == ".":
                R[i][j] = 1
            continue
        if S[i][j] == "#":
            continue
        else:
            R[i][j] += 1 + R[i][j + 1]
for i in range(h - 1, -1, -1):
    for j in range(w - 1, -1, -1):
        if i == h - 1:
            if S[i][j] == ".":
                D[i][j] = 1
            continue
        if S[i][j] == "#":
            continue
        else:
            D[i][j] += 1 + D[i + 1][j]
ans = 0
for i in range(h):
    for j in range(w):
        temp = D[i][j] + U[i][j] + L[i][j] + R[i][j] - 3
        ans = max(temp, ans)
print(ans)
### BUGGY CODE ###

def main():
  from collections import deque
  s,*c=open(0)
  h,w=map(int,s.split())
  c=''.join(t[:w]for t in c)
  f=[-1]*h*w
  q=deque()
  for i,d in enumerate(c):
    if d=='#':
      q.append(i)
      f[i]=0
  while q:
    y=q.popleft()
    v=f[y]
    y,x=divmod(y,w)
    for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
      k=i*w+j
      if h>i>=0<=j<w and f[k]<0:
        f[k]=v+1
        q.append(k)
  print(v)
if __name__=='__main__':
  main()

### FIXED CODE ###

from collections import*
h,w=map(int,input().split())
c=eval('list(input()),'*h)
q=deque()
for i in range(h):
    for j in range(w):
        if c[i][j]=='#':
            q.append((i,j,0))
ans=0
while q:
    y,x,v=q.popleft()
    ans=max(ans,v)
    for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
        if h>i>=0 and w>j>=0 and c[i][j]=='.':
            c[i][j]='#'
            q.append((i,j,v+1))
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
if 14*N <= M:
    print(0)
else:
    sum = sum(A)

    for i in range(M):
        sum -= A[A.index(max(A))] - (A[A.index(max(A))] // 2)
        A[A.index(max(A))] //= 2

    print(sum)


### FIXED CODE ###

import heapq
from math import ceil

N, M = map(int, input().split())
A = [(-1)*int(x) for x in input().split()]

if len(A) == 1:
    for i in range(M):
        A[0] = ceil(A[0]/2)
    A[0] = -A[0]
    print(A[0])
else:
    count = 0
    heapq.heapify(A)
    a = heapq.heappop(A)
    b = heapq.heappop(A)
    while count < M:
        while a <= b:
            a = ceil(a/2)
            count += 1
            if count == M:
                break
        if count == M:
            break
        heapq.heappush(A,a)
        a = b
        b = heapq.heappop(A)
    heapq.heappush(A,a)
    heapq.heappush(A,b)
    ans = (-1)*sum(A)
    print(ans)
### BUGGY CODE ###

length, quests = map(int, input().rstrip().split())
string = input()
positions = []

for i in range(len(string) - 1):
    if string[i] == "A" and string[i+1] == "C":
        positions.append(1)
    else:
        positions.append(0)

for i in range(quests):
    left, right = map(int, input().rstrip().split())
    count = 0
    for j in range(left-1, right-1):
        if positions[j] == 1 and right + 1 != len(positions) and j + 1 != right:
            count += 1
    print(count)


### FIXED CODE ###

length, quests = map(int, input().rstrip().split())
string = input()
totals = [0]

count = 0
for i in range(1, len(string)):
    if string[i-1] == "A" and string[i] == "C":
        count += 1
    totals.append(count)

for i in range(quests):
    left, right = map(int, input().rstrip().split())
    print(totals[right-1] - totals[left-1])
### BUGGY CODE ###

import numpy as np

def main():
  n=int(input())
  s=np.array([ord(i) for i in input()])
  dp=np.zeros((n+1,n+1),dtype=int)
  ans=0
  for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
      if s[i]==s[j]:
        dp[i][j]=dp[i+1][j+1]+1
        ans=max(ans,min(dp[i][j],j-i))
  #for i in dp:
  #  print(i)
  print(ans)      
        

if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  n=int(input())
  s=input()
  dp=[[0]*(n+1) for i in range(n+1)]
  for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
      if s[i]==s[j]:
        dp[i][j]=dp[i+1][j+1]+1
  #for i in dp:
  #  print(i)
  
  ans=0
  for i in range(n-1):
    for j in range(i+1,n):
      ans=max(ans,min(j-i,dp[i][j]))
  print(ans)      
        

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

h,w=map(int,input().split())
a,s=[],[["x"for i in range(w+2)]]
for i in range(h):
  t,tt=input(),[]
  for j in range(w):
    if t[j]=="#":a.append([i+1,j+1])
    tt.append(t[j])
  s.append(["x"]+tt+["x"])
s.append(["x"for i in range(w+2)])
f=1
while 1:
  b=[]
  for k in a:
    i,j=k[0],k[1]
    if s[i-1][j]==".":
      s[i-1][j]=f
      b.append([i-1,j])
    if s[i+1][j]==".":s[i+1][j]=f;b.append([i+1,j])
    if s[i][j-1]==".":s[i][j-1]=f;b.append([i,j-1])
    if s[i][j+1]==".":s[i][j+1]=f;b.append([i,j+1])
  a=b.copy()
  f+=1
  if len(a)==0:break
print(f-2)

### FIXED CODE ###

from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
d=deque()
dc=0
b=[]
for i in range(h):
  t=[]
  s=input()
  for j in range(w):
    if s[j]=="#":d.append((i,j));dc+=1;t.append(1)
    else:t.append(0)
  b.append(t)
count=0
while dc!=0:
  ld=dc
  dc=0
  for i in range(ld):
    x=d.popleft()
    if x[0]<h-1:
      if b[x[0]+1][x[1]]==0:b[x[0]+1][x[1]]=1;d.append((x[0]+1,x[1]));dc+=1
    if 0<x[0]:
      if b[x[0]-1][x[1]]==0:b[x[0]-1][x[1]]=1;d.append((x[0]-1,x[1]));dc+=1
    if x[1]<w-1:
      if b[x[0]][x[1]+1]==0:b[x[0]][x[1]+1]=1;d.append((x[0],x[1]+1));dc+=1
    if 0<x[1]:
      if b[x[0]][x[1]-1]==0:b[x[0]][x[1]-1]=1;d.append((x[0],x[1]-1));dc+=1
  count+=1
print(count-1)
### BUGGY CODE ###

from bisect import bisect_left
n = int(input())
A=[int(input()) for _ in range(n)]
row = [A[0]]
for a in A[1:]:
    index = bisect_left(row[::-1],a)
    if index==0:
        row.append(a)
    else:
        row[len(row) - index] = a
print(len(row))

### FIXED CODE ###

from bisect import bisect_left
from collections import deque
n = int(input())
A=[int(input()) for _ in range(n)]
q=deque()
for a in A:
    i=bisect_left(q,a)
    if not i:
        q.appendleft(a)
    else:
        q[i-1]=a
print(len(q))
### BUGGY CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, M, K = lr()
    fri = [[] for _ in range(N)]
    for i in range(M):
        a, b = lr()
        fri[a-1].append(b-1)
        fri[b-1].append(a-1)
    blo = [[] for _ in range(N)]
    for i in range(K):
        c, d = lr()
        blo[c-1].append(d-1)
        blo[d-1].append(c-1)

    graph = [0 for _ in range(N)]
    for i in range(N):
        vis = [False for _ in range(N)]
        s = [i]
        vis[i] = True
        while len(s) > 0:
            v = s.pop()
            vis[v] = True
            if v in blo[i]:
                graph[i] -= 1
            for j in fri[v]:
                if vis[j]:
                    continue
                s.append(j)
                vis[j] = True
        graph[i] += sum(vis)
    ans = []
    for i in range(N):
        ans.append(graph[i]-len(fri[i])-1)
    print(*ans, sep=' ')
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def resolve():
    N, M, K = lr()
    uf = UnionFind(N)
    fr = [0]*N
    for i in range(M):
        a, b = lr()
        uf.union(a-1, b-1)
        fr[a-1] += 1
        fr[b-1] += 1
    ans = [uf.size(x) - fr[x] - 1 for x in range(N)]
    for i in range(K):
        c, d = lr()
        if uf.same(c-1, d-1):
            ans[c-1] -= 1
            ans[d-1] -= 1
    print(*ans, sep=' ')
resolve()
### BUGGY CODE ###

import numpy as np
from operator import itemgetter
N,M=(int(x) for x in input().split())
A=[]
for i in range(N):
  D=[int(x) for x in input().split()]
  A=A+[D]  
result=A.sort(key=itemgetter(0))
count=M
sum=0
for i in range(N):
  if count-A[i][1]>0:
    count=count-A[i][1]
    sum=sum+A[i][0]*A[i][1]
  else:
    sum=sum+count*A[i][0]
    break
print(sum)    

### FIXED CODE ###

import numpy as np
from operator import itemgetter
N,M=(int(x) for x in input().split())
A=[]
 
for i in range(N):
  D=[int(x) for x in input().split()]
  A+=[D]    
result=A.sort(key=itemgetter(0))
count=M
sum=0
for i in range(N):
  if count-A[i][1]>0:
    count=count-A[i][1]
    sum+=A[i][0]*A[i][1]
  else:
    sum+=count*A[i][0]
    break
print(sum)
### BUGGY CODE ###

N,M,L=map(int,input().split())
inf=float("inf")
distance=[[inf for n in range(N)] for n in range(N)]

for n in range(N):
    distance[n][n]=0

for m in range(M):
    a,b,c=map(int,input().split())
    distance[a-1][b-1]=c
    distance[b-1][a-1]=c

for k in range(N):
    for i in range(N):
        for j in range(N):
            distance[i][j]=min(distance[i][j],distance[i][k]+distance[j][k])          

distance2=[[inf for n in range(N)] for n in range(N)]

for i in range(N):
    for j in range(N):
        if distance[i][j]<=L:
            distance2[i][j]=1

for n in range(N):
    distance2[n][n]=0

for k in range(N):
    for i in range(N):
        for j in range(N):
            distance2[i][j]=min(distance2[i][j],distance2[i][k]+distance2[j][k])

Q=int(input())
for q in range(Q):
    s,t=map(int,input().split())
    if distance2[s-1][t-1]==inf:
        print(-1)
    else:
        print(distance2[s-1][t-1]-1)

### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall
N,M,L=map(int,input().split())
inf=10**9+1

distance=[[inf for n in range(N)] for n in range(N)]
for n in range(N):
    distance[n][n]=0
for m in range(M):
    a,b,c=map(int,input().split())
    distance[a-1][b-1]=c
    distance[b-1][a-1]=c
distance=floyd_warshall(distance)

distance2=[[inf for n in range(N)] for n in range(N)]
for i in range(N):
    for j in range(N):
        if distance[i][j]<=L:
            distance2[i][j]=1
for n in range(N):
    distance2[n][n]=0
distance2=floyd_warshall(distance2)

Q=int(input())
for q in range(Q):
    s,t=map(int,input().split())
    if distance2[s-1][t-1]==inf:
        print(-1)
    else:
        print(int(distance2[s-1][t-1]-1))
### BUGGY CODE ###

from collections import deque

def bfs(grid, costs, queue, wall, res):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while res:
        y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([y_,x_])
            grid[y_][x_] = wall
            costs[y_][x_] = costs[y][x] + 1
            ans = max(ans, costs[y_][x_])
            res -= 1
    return ans

import sys
input = sys.stdin.readline
H,W = map(int, input().split())
wall = '#'
queue = deque([])
edges = [wall for _ in range(W+2)]
grid = [edges]
costs = [[0] * (W+2)]

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([i,j])
    grid.append(S)
    costs.append([0] * (W+2))
grid.append(edges)
print(bfs(grid, costs, queue, wall, H*W - len(queue)))


### FIXED CODE ###

from collections import deque

def bfs(grid, queue, wall):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        cnt,y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([cnt+1,y_,x_])
            grid[y_][x_] = wall
            ans = max(ans, cnt+1)
    return ans

H,W = map(int, input().split())
wall = '#'
queue = deque([])
edges = [wall for i in range(W+2)]
grid = [edges]

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([0,i,j])
    grid.append(S)
grid.append(edges)
print(bfs(grid, queue, wall))
### BUGGY CODE ###

n, k = map(int, input().split())
pList = list(map(int, input().split()))
pListMax = 0

for i in range(n-k+1):
    pListSlice = pList[i:k+i]
    sumA = (sum(pListSlice) + k)/2
    if sumA > pListMax:
        pListMax = sumA
print(pListMax)


### FIXED CODE ###

n, k = map(int, input().split())
pList = list(map(int, input().split()))
pKList = [(1 + p)/2 for p in pList]
pListMax = 0

for i in range(n-k+1):
    if i == 0:
        res = sum(pKList[i:i+k])
    else:
        res = res - pKList[i-1] + pKList[i+k-1]
    pListMax = max(pListMax, res)
print(pListMax)