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

from collections import deque
N,Q = map(int,input().split())
ab = [[] for i in range(N)]
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    ab[a].append(b)
    ab[b].append(a)
px = [0 for i in range(N)]
for i in range(Q):
    p,x = list(map(int,input().split()))
    px[p-1] += x
que = deque()
alr = [0]
que.append(0)
while que:
    q = que.popleft()
    sumq = px[q]
    for i in ab[q]:
        if i not in alr:
            que.append(i)
            alr.append(i)
            px[i] += sumq
print(*px)

### FIXED CODE ###

from collections import deque
N,Q = map(int,input().split())
ab = [[] for i in range(N)]
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    ab[a].append(b)
    ab[b].append(a)
px = [0 for i in range(N)]
for i in range(Q):
    p,x = list(map(int,input().split()))
    px[p-1] += x
que = deque()
alr = set()
alr.add(0)
que.append(0)
while que:
    q = que.popleft()
    sumq = px[q]
    for i in ab[q]:
        if i in alr:
            continue
        else:
            que.append(i)
            alr.add(i)
            px[i] += sumq
print(*px)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))
query = [list(map(int, input().split())) for i in range(q)]

for n, x, m in query:
    l = [d[i]%m for i in range(k)]
    n -= 1
    zero = l.count(0)
    count = n // k
    zero_total = zero*count
    total = sum(l)*count + x%m
    rem = n % k
    total += sum(l[:rem])
    zero_total += l[:rem].count(0)

    print(n-total//m-zero_total)


### FIXED CODE ###

import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))
query = [None]*q
for i in range(q):
    query[i] = list(map(int, input().split()))

def answer_query(n, x, m):
    l = [m if i%m == 0 else i%m for i in d]
    count = n // k
    rem = n % k
    s = sum(l)
    total = s%m * count + x%m
    for i in range(rem):
        total += l[i]

    total //= m
    total += s//m * count

    print(n-total)


for n, x, m in query:
    answer_query(n-1, x, m)
### BUGGY CODE ###

import bisect
def main():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    m = max(X,Y,Z)
    if Y == m:
        B, A = A, B
    if Z == m:
        C, A = A, C
    D = []
    for i in B:
        for j in C:
            D.append(i+j)
    D.sort()
    A.sort(reverse=True)
    r = max(A) + D[0]
    l = 0
    ti = 0
    while l != r:
        k = (l + r + 1) // 2
        t = 0
        fin = False
        for i in A:
            for j, v in enumerate(D[ti:]):
                if i + v >= k:
                    t += (len(D) - j - ti)
                    ti += j
                    break
            else:
                fin = True
            if fin:
                break
        if t > K:
            l = k
        else:
            r = k - 1
    rl = []
    for i in A:
        ii = bisect.bisect_left(D, k-i)
        rl.extend([w+i for w in D[ii:]])
    rl.sort(reverse=True)
    print('\n'.join(str(i) for i in rl[:K]))
main()


### FIXED CODE ###

# damedatta
def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l
def main():
    X, Y, Z, K = map(int, input().split())
    D = sorted(map(int, input().split()), reverse=True)
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    A = sorted((i + j for i in B for j in C), reverse=True)
    def calc(x):
        t = 0
        ii = len(D) - 1
        for i in A:
            while ii >= 0 and D[ii] + i < x:
                ii -= 1
            t += ii + 1
            if t >= K:
                return True
            if ii < 0:
                return False
        return t >= K
    l = binsearch(D[-1] + A[-1], D[0] + A[0]+1, calc)
    ii = len(D) - 1
    rl = []
    for i in A:
        while ii >= 0 and D[ii] + i < l + 1:
            ii -= 1
        if ii < 0:
            break
        rl.extend(i + j for j in D[:ii+1])
    rl.sort(reverse=True)
    rl += [l] * (K - len(rl))
    print('\n'.join(str(i) for i in rl))
main()
### BUGGY CODE ###

# coding: utf-8
# Your code here!
def LI():return list(map(int,input().split()))

n,k=LI()
import numpy as np
a=np.array(LI(),dtype=np.int32)

while k>0:
    b=np.zeros(n,dtype=np.int32)
    for i in range(n):
        b[max(0,i-(a[i])):min(n-1,i+(a[i]))+1]+=1
    a=b
    k-=1
print(*a)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import time
t1=time.time()
def LI():return list(map(int,input().split()))
n,k=LI()
a=LI()

for _ in range(k):
    tab=[0]*(n)
    for i in range(n):
        q=a[i]
        if 0<=i-q:
            tab[i-q]+=1
        else:
            tab[0]+=1
        if i+q+1<=n-1:
            tab[i+q+1]-=1
        else:
            pass
    b=[tab[0]]
    for i in range(n-1):
        b.append(tab[i+1]+b[-1])
    a=b[:]
    if time.time()-t1>1.5:
        print(*a)
        exit()
print(*a)
### BUGGY CODE ###

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

cnt1 = a.count(1)
cnt2 = a.count(2)
cnt3 = a.count(3)

memo = {}
memo[(0, 0, 0)] = 0

def solve(c3, c2, c1):
    if (c3, c2, c1) in memo:
        return memo[(c3, c2, c1)]
    tmp = 0
    num = c1 + c2 + c3
    # c3を選ぶ
    if c3 != 0:
        tmp += (c3 / n) * solve(c3 - 1, c2 + 1, c1)
    # c2を選ぶ
    if c2 != 0:
        tmp += (c2 / n) * solve(c3, c2 - 1, c1 + 1)
    # c1を選ぶ
    if c1 != 0:
        tmp += (c1 / n) * solve(c3, c2, c1 - 1)
    memo[(c3, c2, c1)] = n / num * (tmp + 1)
    return memo[(c3, c2, c1)] 

print(solve(cnt3, cnt2, cnt1))

### FIXED CODE ###

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

dp = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 0

cnt1 = a.count(1)
cnt2 = a.count(2)
cnt3 = a.count(3)

for i in range(cnt3 + 1):
    for j in range(cnt3 + cnt2 + 1 - i):
        for k in range(cnt3 + cnt2 + cnt1 + 1 - i - j):
            if i + j + k == 0:
                continue
            res = 1
            if k > 0:
                res += (k/n) * dp[i][j][k-1]
            if j > 0:
                res += (j/n) * dp[i][j-1][k+1]
            if i > 0:
                res += (i/n) * dp[i-1][j+1][k]
            dp[i][j][k] = (n/(i+k+j)) * res

print(dp[cnt3][cnt2][cnt1])
### BUGGY CODE ###

def main():
	N,M = map(int,input().split())
	array = []
	array2 = [[] for i in range(N)]
	for i in range(M):
	    array.append(list(map(int,input().split())))
	    array2[array[i][0]-1].append(array[i][1])

	for i in range(N):
	    array2[i] = sorted(array2[i])

	for i in range(M):
	    pnum = str(array[i][0])
	    cnum = str(array2[array[i][0]-1].index(array[i][1])+1)
	    print('0'*(6-len(pnum)) + pnum + '0'*(6-len(cnum)) + cnum)
main()

### FIXED CODE ###

N,M = map(int,input().split())
PY = []
for i in range(M):
    P,Y = map(int,input().split())
    PY.append([P,Y,i])

PY.sort()
ans = [0 for i in range(M)]
count = 0
old = 0
for j in range(M):
    p,y,inum = PY[j]
    if old == p:
        pnum = p
        cnum = count
    else:
        old = p
        count = 1
        pnum = p
        cnum = 1

    count += 1
    pnum = str(pnum)
    cnum = str(cnum)
    ans[inum] = '0'*(6-len(pnum)) + pnum + '0'*(6-len(cnum)) + cnum

for i in range(M):
    print(ans[i])
### BUGGY CODE ###

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

from operator import itemgetter
AB.sort(key = itemgetter(0))
AB.sort(key = itemgetter(1),reverse = True)

days = [0]*(M+1)
for a,b in AB:
    point = M - a
    if point >= 0:
        while point >= 0:
            if days[point] == 0:
                days[point] = b
                break
            else:
                point -= 1
print(sum(days))

### FIXED CODE ###

import heapq
from operator import itemgetter

def main():
    N, M = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    AB.sort(key = itemgetter(0))
    heap = []
    ans = 0
    cnt = 0
    for i in range(1,M + 1):
        while cnt < N and AB[cnt][0] <= i:
            heapq.heappush(heap,-1*AB[cnt][1])
            cnt += 1
        if len(heap) > 0:
            ans += heapq.heappop(heap)*-1
    print(ans)
    return

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

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

count = 0


for c in C:
    for b in B:
        if b >= c:
            continue
        for a in A:
            if a >= b:
                continue
            else:
                
                count+=1
                
print(count)

### FIXED CODE ###

import bisect
 
def main():
    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()
    ans = 0
    for y in b:
        i = bisect.bisect_left(a, y)
        j = bisect.bisect_right(c, y)
        if i > 0 and j != len(c):
            ans += i * (n - j)
 
    print(ans)
 
main()
### BUGGY CODE ###

# input
n = int(input())
alist = list(map(int, list(input().split())))

# process/output
if not 1 in alist:
    print(-1)

else:
    ans = 0
    i = 1
    while len(alist) > 0:
        if i in alist:
            index = alist.index(i)
            alist = alist[index+1:]
            ans += index
            i += 1
            
        else:
            ans += len(alist)
            break
        
    print(ans)


### FIXED CODE ###

# input
n = int(input())
alist = list(map(int, input().split()))

# process/output
if not 1 in alist:
    print(-1)

else:
    i = 1
    for j in range(n):
        if alist[j] == i:
            i+=1
                    
    print(n-i+1)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
score = [0 for i in range(n)]
cnt = 1
for i in range(n):
    if i < k - 1:
        score[i] = a[i]
        cnt *= score[i]
    elif i == k - 1:
        cnt *= a[i]
        score[i] = cnt
    else:
        cnt *= a[i]
        cnt /= a[i - k]
        score[i] = cnt
# print("score =", score)
for i in range(k, n):
    if score[i] > score[i - 1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
# score = [0 for i in range(n)]
# # cnt = 1
# for i in range(n):
#     if i < k - 1:
#         score[i] = a[i]
#     elif i == k - 1:
#         score[i] = score[i - 1] * a[i]
#     else:
#         score[i] = score[i - 1] * a[i] / a[i - k]
# # print("score =", score)
# for i in range(k, n):
#     if score[i] > score[i - 1]:
#         print("Yes")
#     else:
#         print("No")
for i in range(k, n):
    if a[i - k] < a[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

class SegmentTree():
    # リストSの部分リストからなる集合を葉とするセグメント木
    def __init__(self, S, n):
        self.size = n
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        # 配列のi番目をcに更新する
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


def main():
    n = int(input())
    S = list(input())
    S = [ord(s) for s in S]
    segtree = SegmentTree(S, 19)
    for _ in range(int(input())):
        t, i, c = input().split()
        if t == '1':
            segtree.update(int(i)-1, ord(c))
        if t == '2':
            print(segtree.query(int(i)-1, int(c)))


main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, S):
        self.size = 19
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


def main():
    N = int(input())
    S = [ord(_) - 97 for _ in list(input())]
    Q = int(input())
    tree = SegmentTree(S)
    for q in range(Q):
        t, i, c = input().split()
        if t == '1':
            i = int(i) - 1
            tree.update(i, ord(c) - 97)
        else:
            l, r = int(i) - 1, int(c)
            print(tree.query(l, r))


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

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for k in range(N-2):
  for j in range(k+1, N-1):
    for l in range(j+1, N):
      if L[k] + L[j] > L[l]:
        ans += 1
      else:
        break

print(ans)

### FIXED CODE ###

# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


N = int(input())
L = list(map(int, input().split()))
L.sort()
bit = BIT(L[-1]*2+1)
bit.add(L[0]+L[1], 1)
total = 1
ans = 0
for k in range(2, N):
  ans += total - bit.sum(L[k])
  for j in range(k):
    bit.add(L[j]+L[k], 1)
    total += 1

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

import functools

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

l_gcd = []

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

for i in range(len(A)):
    B = A[i]
    A.pop(i)
    l_gcd.extend([functools.reduce(gcd,A)])
    A.insert(i,B)

print(max(l_gcd))


### FIXED CODE ###

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

w_min = A[1]

for i in range(w_min,0,-1):
    count = 0
    for j in A:
        if j%i != 0:
            count = count + 1
            if count > 1:
                break
    if count < 2:
        print(i)
        break
### BUGGY CODE ###

from math import factorial
def comb(n, k, p):
    """power_funcを用いて(nCk) mod p を求める"""
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n-k) % p
    return (a*power_func(b, p-2, p)*power_func(c, p-2, p)) % p

def power_func(a, b, p):
    """a^b mod p を求める"""
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b//2, p)
        return d*d % p
    if b % 2 == 1:
        return (a*power_func(a, b-1, p)) % p

n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10**9 + 7

a.sort()

ans = 0

# pos
for i in range(1, n):
    ans += a[i] * comb(i, k-1, MOD)
    ans %= MOD

for i in range(n-1):
    ans -= a[i] * comb(n-1-i, k-1, MOD)
    ans %= MOD
print(ans)



### FIXED CODE ###

from math import factorial
MOD = 10**9 + 7

# 階乗を用意
fact = [1] * (10**5 + 1)
for i in range(1, 10**5 + 1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD

def comb(n, k, p):
    """power_funcを用いて(nCk) mod p を求める"""
    global fact
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = fact[n]
    b = fact[k]
    c = fact[n-k]
    return (a*power_func(b, p-2, p)*power_func(c, p-2, p)) % p

def power_func(a, b, p):
    """a^b mod p を求める"""
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b//2, p)
        return d*d % p
    if b % 2 == 1:
        return (a*power_func(a, b-1, p)) % p

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

ans = 0

# pos
for i in range(n-1):
    c = comb(n-1-i, k-1, MOD)
    ans += a[n-1-i] * c
    ans %= MOD
    ans -= a[i] * c
    ans %= MOD
print(ans)
### BUGGY CODE ###

N = int(input())
A = [0]*(N)
H = list(map(int, input().split()))
ans = "Yes"

hmax = max(H)
k = H.index(hmax)
Hd = [0]*k

for i in range(k):
    Hd[i]=H[i]
    if H[i]<max(Hd)-1:
        ans = "No"


for i in range(k,N,1):
    if H[i]<hmax-1:
        ans = "No"


print(ans)



### FIXED CODE ###

N = int(input())
A = [0]*(N)
H = list(map(int, input().split()))
ans = "Yes"

hmax = max(H)
k = H.index(hmax)
Hd = [0]*k
Hdmax=int(0)
for i in range(k):
    Hd[i] = H[i]
    Hdmax = max(Hdmax,Hd[i])
    if H[i] < Hdmax - 1:
        ans = "No"

for i in range(k,N,1):
    if H[i]<hmax-1:
        ans = "No"


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

# /user/bin/python
# -*- coding: utf-8 -*-
import math
import sys

n,w = map(int, sys.stdin.readline().rstrip().split())
weight = [0] * n
value = [0] * n
for i in range(n):
  weight[i], value[i] = list(map(int, sys.stdin.readline().rstrip().split()))

dp = [[0 for _ in range(w+1)] for _ in range(n+1)]

for i in range(n):
  for j in range(w+1):
    if j >= weight[i]:
      dp[i+1][j] = max(dp[i][j], dp[i][j-weight[i]]+value[i])
    else:
      dp[i+1][j] = dp[i][j]

print(dp[n][w])

### FIXED CODE ###

# /user/bin/python
# -*- coding: utf-8 -*-
import numpy as np
import sys

N,W = map(int, sys.stdin.readline().rstrip().split())

dp = np.zeros(W+1, dtype=np.int64)

for _ in range(N):
  w,v = map(int, sys.stdin.readline().rstrip().split())
  np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

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

L, R = map(int, input().split())

ans = 2018
for i in range(L, R):
    for j in range(i+1, R + 1):
        tmp = (i * j) % 2019
        if ans  > tmp:
            ans = tmp

print(ans)


### FIXED CODE ###

L, R = map(int, input().split())

ans = 2018
for i in range(L, R):
    for j in range(i+1, R + 1):
        tmp = (i * j) % 2019
        if ans  > tmp:
            ans = tmp
        if tmp == 0:
            ans = 0
            print(ans)
            exit()

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

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

def binary_search(val):
    left, right = 0, n-1
    while right - left >= 1:
        mid = (right+left)//2
        if a[mid] == val: return 1
        if a[mid] < val:
            left = mid
        elif val < a[mid]:
            right = mid
    return 0

q = int(input())
for i in range(q):
    k = int(input())
    print(binary_search(k))



### FIXED CODE ###

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

def binary_search(val):
    left, right = 0, n-1
    while right - left >= 0:
        mid = int((right+left)/2)
        if a[mid] == val: return 1
        if a[mid] < val:
            left = mid+1
        elif val < a[mid]:
            right = mid-1
    return 0

q = int(input())
for i in range(q):
    k = int(input())
    print(binary_search(k))
### BUGGY CODE ###

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

while len(a) > 1:
    mina = min(a)
    for i in a:
        if i == mina:
            continue
        elif i % mina == 0:
            a.remove(i)
        else:
            a[a.index(i)] = i % mina
            
print(a[0])

### FIXED CODE ###

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

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

g = a[0]

for i in a:
    g = gcd(g, i)

print(g)
### BUGGY CODE ###

k = int(input())
if(k < 10):
    print(k)
else:
    n = 9
    p = 9
    while(p < k):
        n += 1
        t = str(n)
        x = 0
        for i in range(len(t)-1):
            if(abs(int(t[i])-int(t[i+1])) > 1):
                x = 1
        if(x == 0):
            p += 1
        
    print(n)

### FIXED CODE ###

def add(n):
    l = []
    if(n%10 == 0):
        l.append(n*10)
        l.append(n*10+1)
    elif(n%10 == 9):
        l.append(n*10+8)
        l.append(n*10+9)
    else:
        l.append(n*10+n%10-1)
        l.append(n*10+n%10)
        l.append(n*10+n%10+1)
    return l
k = int(input())
list = [1,2,3,4,5,6,7,8,9]
i = 0
while(len(list)<k):
    list += add(list[i])
    i += 1
print(list[k-1])
### BUGGY CODE ###

n = int(input())
T = list(map(int,input().split()))
V = list(map(int,input().split()))

M = [] #t = i秒の最高速度
for i in range(n) :
    for j in range(T[i] * 10) :
        M.append(V[i])

R = [0] + T[:]
for i in range(n) :
    R[i+1] += R[i]


for i in range(n) :

    le = R[i] * 10
    ri = R[i+1] * 10

    
    j = 0
    while le >= 0 :
        M[le] = min(M[le], V[i] + j*0.1)
        #print(M[le])
        j += 1
        le -= 1
    j = 0
    while ri < len(M) :
        M[ri] = min(M[ri], V[i] + j*0.1)
        j += 1
        ri += 1

for i in range(len(M)) :
    M[i] = min(i*0.1, (len(M)-i)*0.1, M[i])

M += [0]

ans = 0
for i in range(len(M)-1) :
    ans += (M[i] + M[i+1]) * 0.1 * 0.5

print(ans)


### FIXED CODE ###

n = int(input())
T = list(map(int,input().split()))
V = list(map(int,input().split()))

b = 2
bg = 1.0 / b

M = [] #t = i秒の最高速度
for i in range(n) :
    for j in range(T[i] * b) :
        M.append(V[i])

R = [0] + T[:]
for i in range(n) :
    R[i+1] += R[i]


for i in range(n) :

    le = R[i] * b
    ri = R[i+1] * b

    
    j = 0
    if i-1 >= 0 and V[i-1] > V[i] :
        while le >= 0 :
            M[le] = min(M[le], V[i] + j*bg)
            #print(M[le])
            j += 1
            le -= 1
    j = 0
    if i+1 < n and V[i+1] > V[i] :
        while ri < len(M) :
            M[ri] = min(M[ri], V[i] + j*bg)
            j += 1
            ri += 1

for i in range(len(M)) :
    M[i] = min(i*bg, (len(M)-i)*bg, M[i])

M += [0]

ans = 0
for i in range(len(M)-1) :
    ans += (M[i] + M[i+1]) * bg * 0.5

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

def main():
    n=int(input())
    s=[input() for _ in [0]*n]
    s=[i+i[:-1] for i in s]+[i+i[:-1] for i in s][:-1]
    ans=[[True]*n for _ in [0]*n]
    for i in range(1,2*n-1):
        for j in range(2*n-2):
            for k in range(1,n):
                if i-k>=0 and j+k<2*n-1:
                    if s[i][j]!=s[i-k][j+k]:
                        if i-k<n and j<n:
                            ans[i-k][j]=False
                        if i-n-1>=0 and j+k-n-1>=0:
                            ans[i-n-1][j+k-n-1]=False
    print(sum([sum(a) for a in ans]))
main()

### FIXED CODE ###

def main():
    n=int(input())
    nn=2*n-1
    s=[input() for _ in [0]*n]
    s=[i+i[:-1] for i in s]+[i+i[:-1] for i in s][:-1]
    ans=[[0]*n for _ in [0]*n]
    for i in range(1,nn):
        m=min(i+1,n)
        for j in range(nn-1):
            for k in range(max(i-j-n,0)+1,min(m,nn-j,i-j+n)):
                ii=i-k
                if s[i][j]!=s[ii][j+k]:
                    l=min(n-k+1,ii,j)
                    width=l-max(-1,ii-n,j-n)
                    ans[ii-l][j-l]=max(ans[ii-l][j-l],width)
    for i in range(1,n):
        for j in range(1,n):
            ans[i][j]=max(ans[i][j],ans[i-1][j-1]-1)
    print(sum([sum([i==0 for i in a]) for a in ans]))
main()