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

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, Q = map(int, input().split())
graph = [[] for _ in range(N)]
point = [0]*N
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
for i in range(Q):
    p, x = map(int, input().split())
    point[p-1] += x
def dfs(s,parent):
    for i in graph[s]:
        if i == parent:
            continue
        point[i] += point[s]
        dfs(i,s)
dfs(0,-1)
print(*point)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, Q = map(int, input().split())
graph = [[] for _ in range(N)]
point = [0]*N
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
for i in range(Q):
    p, x = map(int, input().split())
    point[p-1] += x
def dfs(s,parent):
    for i in graph[s]:
        if i == parent:
            continue
        point[i] += point[s]
        dfs(i,s)
dfs(0,-1)
print(*point)
### BUGGY CODE ###

N = int(input())
N = list(str(N))
N = list(map(int, N))

ans = 0
for i in range(len(N)-1, -1, -1):

    if i < len(N)-1 and N[i+1] == 5 and N[i] >= 5:
        N[i] += 1
    x = N[i]
    if x > 5:
        ans += (10 - x)
        if i > 0:
            N[i-1] += 1
        else:
            ans += 1
    else:
        ans += x
print(ans)

### FIXED CODE ###

N = tuple(input())
N = tuple(map(int, N))

ans = 0
flag = False
flag5 = False
i = len(N)-1


for x in reversed(N):
    if flag or (flag5 and x >= 5):
        x += 1
    flag5 = False
    flag = False
    if x > 5:
        ans += (10 - x)
        flag = True
        if i == 0:
            ans += 1
    else:

        ans += x
    if x == 5:
        flag5 = True
    i -= 1

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

h, w, d = map(int, input().split())
n = h*w
a = []
for i in range(h):
    a+=[i-1 for i in list(map(int, input().split()))]

def dist(i, j):
    dh = abs(i//w - j//w)
    dw = abs(i%w - j%w)
    return dh + dw

idx_list = [a.index(i) for i in range(n)]
dist_list = [0]*n
for i in range(n):
    if i < d:
        dist_list[i] = 0
    else:
        dist_list[i] = dist_list[i-d] + dist(idx_list[i-d], idx_list[i])

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    l-=1; r-=1
    print(dist_list[r] - dist_list[l])



### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w, d = map(int, input().split())
n = h*w
a = [0]*n
for i in range(h):
    t = list(map(int, input().split()))
    for j in range(w):
        a[w*i+j] = t[j]-1

def dist(i, j):
    dh = abs(i//w - j//w)
    dw = abs(i%w - j%w)
    return dh + dw

idx_list = [0] * n
for i in range(n):
    idx_list[a[i]] = i

dist_list = [0]*n
for i in range(n):
    if i < d:
        dist_list[i] = 0
    else:
        dist_list[i] = dist_list[i-d] + dist(idx_list[i-d], idx_list[i])

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    l-=1; r-=1
    print(dist_list[r] - dist_list[l])
### BUGGY CODE ###

def main():
    N = int(input())
    ans = sum(range(1, N + 1)) - N
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    ans = N * (N - 1) // 2
    print(ans)


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

N,M = map(int, input().split())
A = []
for X in input().split():
	A.append(int(X))

for x in range(M):
	max_num = A.index(max(A))
	A[max_num] = A[max_num] / 2

sum = 0
for x in range(len(A)):
	sum += int(A[x])

print(sum)


### FIXED CODE ###

import heapq

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

heapq.heapify(A)
for x in range(M):
	heapq.heappush(A, heapq.heappop(A)/2)
A_int = map(int, A)
print(-sum(A_int))
### BUGGY CODE ###


n, m = map(int,input().split())
h = list(map(int,input().split()))
l = [list(map(int, input().split())) for _ in range(m)]

x = [[] for _ in range(n)]

for i in range(m):
    if l[i][1] not in x[l[i][0]-1]:
        x[l[i][0]-1].append(l[i][1])

for j in range(m):
    if l[j][0] not in x[l[j][1]-1]:
        x[l[j][1]-1].append(l[j][0])

y = 0
for a in range(n):
    for c in range(len(x[a])):
        if h[a] <= h[x[a][c]-1]:
            break
    else:
        y += 1

print(y)

### FIXED CODE ###

n, m = map(int,input().split())
h = list(map(int,input().split()))
l = [list(map(int, input().split())) for _ in range(m)]

x = [[] for _ in range(n)]

for i in range(m):
    if l[i][1] not in x[l[i][0]-1]:
        x[l[i][0]-1].append(l[i][1])

for j in range(m):
    if l[j][0] not in x[l[j][1]-1]:
        x[l[j][1]-1].append(l[j][0])

y = 0
for a in range(n):
    for c in range(len(x[a])):
        if h[a] <= h[x[a][c]-1]:
            break
    else:
        y += 1

print(y)
### BUGGY CODE ###

N=int(input())
S=[''.join(sorted(input())) for _ in range(N)]
import itertools
l=itertools.combinations(range(N), 2)
cnt=0
for x,y in l:
     if S[x]==S[y]: cnt+=1
print(cnt)

### FIXED CODE ###

N=int(input())
S=[''.join(sorted(input())) for _ in range(N)]
ans=0
import collections
from math import factorial
c = collections.Counter(S)
for i in c.values():
    if 2<=i:
        ans+=factorial(i)//(factorial(i-2)*factorial(2))

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

import collections
N = int(input())
A = list(map(int, input().split()))
indices = collections.defaultdict(list)
for i, a in enumerate(A):
  indices[a].append(i)
Q = int(input())
for _ in range(Q):
  B, C = map(int, input().split())
  for i in indices[B]:
    indices[C].append(i)
    A[i] = C
  print(sum(A))

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
count = collections.defaultdict(int)
currSum = 0
for a in A:
  count[a] += 1
  currSum += a
Q = int(input())
for _ in range(Q):
  B, C = map(int, input().split())
  currSum += (count[B] * (C - B))
  count[C] += count[B]
  count[B] = 0
  print(currSum)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
for i in range(n):
    removed = a[:i] + a[i + 1:]
    print(max(removed))

### FIXED CODE ###

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

global_max = max(a)
count = 0
for i in range(n):
    if a[i] == global_max:
        count += 1
    if count == 2:
        break

for i in range(n):
    if a[i] == global_max:
        if count == 1:
            print(max(a[:i] + a[i + 1:]))
        else:
            print(global_max)
    else:
        print(global_max)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

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

for i in a:
    li = factorization(i)
    for j in li:
        if j[0] == 2:
            ans += j[1]

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int,input().split()))
    ans = 0

    for i in a:
        count = 0
        while i // 2 * 2 == i:
            i = i // 2
            count += 1
        ans += count

    print(ans)

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

a,b=map(int,input().split())
def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf
cm=cf(a,b)
cnt=1
z=len(cm)
for j in range(z):
  for k in range(j+1,z):
    if cm[k]*cm[j]!=0 and cm[k]%cm[j]==0:
      cm[k]=0
cm=list(set(cm))
if 0 in cm:
  cm.remove(0)
print(len(cm)+1)

### FIXED CODE ###

A,B=map(int,input().split())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
c=set(prime_factorize(A))
d=set(prime_factorize(B))
ans=len(c.intersection(d))
print(ans+1)
### BUGGY CODE ###

import math
K = int(input())
ans = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            ans = ans + math.gcd(math.gcd(i+1,j+1),k+1)
print(ans)


### FIXED CODE ###

import math
K = int(input())
ans = 0
for i in range(1,K+1,1):
    for j in range(i,K+1,1):
        for k in range(j,K+1,1):
            if i == j and j==k:
                ans = ans + math.gcd(math.gcd(i,j),k)
            elif i == j and j != k:
                ans = ans + 3*math.gcd(math.gcd(i,j),k)
            elif i != j and j == k:
                ans = ans + 3*math.gcd(math.gcd(i,j),k)
            elif i != j and j != k:
                ans = ans + 6*math.gcd(math.gcd(i,j),k)
print(ans)
### BUGGY CODE ###

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

for i in range(n):
	if max(a) == a[i]:
		print(sorted(a)[-2])
	else:
		print(max(a))


### FIXED CODE ###

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

a_sort = sorted(a)
max = a_sort[-1]
second = a_sort[-2]

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

import math
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def dijkstra(graph: list, node: int, start: int) -> list:
    # graph[node] = [(cost, to)]
    inf = 3 * 10 ** 9
    dist = [inf] * node

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode] + NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode], NextNode))
    return dist
    # dist = [costs to nodes]

xs, ys, xt, yt = map(int, input().split())
n = int(input())
circles = [(xs, ys, 0), (xt, yt, 0)] + [tuple(map(int, input().split())) for i in range(n)]
n += 2

edges = [[] for i in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            continue

        dist = math.sqrt((circles[i][0] - circles[j][0]) ** 2 + (circles[i][1] - circles[j][1]) ** 2)
        edges[i].append((max(0, dist - circles[i][2] - circles[j][2]), j))

dist = dijkstra(edges, n, 0)

print(dist[1])


### FIXED CODE ###

import sys
input = sys.stdin.readline

def dijkstra(edge_adj: list, node: int, start: int) -> list:
    # graph[node] = [(cost, to)]
    inf = 3 * 10 ** 9
    dist = [inf] * node
    used = [False] * node

    dist[start] = 0
    while True:
        v = -1
        for i in range(node):
            if not used[i] and (v == -1 or dist[v] > dist[i]):
                v = i

        if v == -1:
            break

        used[v] = True
        for i in range(node):
            if dist[i] > dist[v] + edge_adj[v][i]:
                dist[i] = dist[v] + edge_adj[v][i]

    return dist
    # dist = [costs to nodes]

xs, ys, xt, yt = map(int, input().split())
n = int(input())
circles = [(xs, ys, 0), (xt, yt, 0)]
for i in range(n):
    circles.append(tuple(map(int, input().split())))
n += 2

edges = [[0] * n for i in range(n)]
for i in range(n):
    for j in range(i+1, n):
        dist = ((circles[i][0] - circles[j][0]) ** 2 + (circles[i][1] - circles[j][1]) ** 2) ** 0.5
        cost = max(0, dist - circles[i][2] - circles[j][2])
        edges[i][j] = cost
        edges[j][i] = cost


dist = dijkstra(edges, n, 0)

print(dist[1])
### BUGGY CODE ###

a,b,x = map(int, input().split())
c = 0
for i in range(a, b+1):
    if i % x == 0:
        c += 1

print(c)

### FIXED CODE ###

a,b,x = map(int, input().split())
b = b // x+1
if a != 0:
    a = (a-1) // x+1

print(b - a)
### BUGGY CODE ###

import itertools
n , k = map(int, input().split())
A = list(map(int, input().split()))

combi = list(itertools.combinations(A,2))
combi_multi = [a*b for a,b in combi]
combi_multi = sorted(combi_multi)

print(combi_multi[k-1])


### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
A = np.sort(np.array(input().split(),np.int64))
z = A[A == 0]
p = A[A > 0]
n = A[A < 0]



def check(x):
    # x以下の数がK個以上ある時、Trueを返す
    count = 0 #最後に２で割る
    if x >= 0:
        count += len(z) * N
    count += (np.searchsorted(A, x//p, side='right')).sum()
    count += (N - np.searchsorted(A, (-x-1)//(-n), side='right')).sum()
    count -= np.count_nonzero(A * A <= x) #ペアなので自分自身は駄目
    assert count % 2 == 0
    count //= 2
    return count >= K

left = - 10 ** 19 # NG
right = 10 ** 19 # OK
while right > left + 1:
    mid = (left+right) // 2
    if check(mid):
        right = mid
    else:
        left = mid

print(right)
### BUGGY CODE ###

S = input()[::-1]
L = len(S)
ans = 0
now = 0
A = [0] * 2019
A[0] = 1
d = 0
for i in range(L):
    now = now + int(S[i]) * 10**d % 2019
    now %= 2019
    d += 1
    A[now] += 1

for i in A:
    ans += i * (i-1) // 2

print(ans)

### FIXED CODE ###

p=d=2019
z=[0]*p
for i,j in enumerate(input()[::-1]):
	d=d+int(j)*pow(10,i,p)
	z[d%p]+=1
r=z[0]
for i in z:
	r+=i*(i-1)//2
print(r)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
N, u, v = map(int, input().split())
u -= 1
v -= 1

G = [[] for _ in range(N)]
elens = [0] * N

for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    elens[a] += 1
    elens[b] += 1
depths = [0] * N
dists = [0] * N

def dfs(cur: int, past: int, d: int, ds):
    ds[cur] = d

    for nx in G[cur]:
        if nx == past:
            continue
        dfs(nx, cur, d + 1, ds)

TAKAHASHI = [0] * N
AOKI = [0] * N

dfs(u, -1, 0, TAKAHASHI)
dfs(v, -1, 0, AOKI)

ans = 0

for i in range(N):
    if TAKAHASHI[i] < AOKI[i]:
        ans = max(ans, AOKI[i] - 1)

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
N, u, v = map(int, input().split())
u -= 1
v -= 1

G = [[] for _ in range(N)]
elens = [0] * N

for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    elens[a] += 1
    elens[b] += 1
depths = [0] * N
dists = [0] * N


TAKAHASHI = [0] * N
AOKI = [0] * N

def dfs_aoki(cur: int, past: int, d: int):
    AOKI[cur] = d

    for nx in G[cur]:
        if nx == past:
            continue
        dfs_aoki(nx, cur, d + 1)

def dfs_takahashi(cur: int, past: int, d: int):
    TAKAHASHI[cur] = d

    for nx in G[cur]:
        if nx == past:
            continue
        dfs_takahashi(nx, cur, d + 1)

dfs_takahashi(u, -1, 0)
dfs_aoki(v, -1, 0)

ans = 0

for i in range(N):
    if TAKAHASHI[i] < AOKI[i]:
        ans = max(ans, AOKI[i] - 1)

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

N = int(input())
A = input().split()

def func01(S):
    sum_count=0
    B = set(S)
    if len(B) == N:
        sum_count = 0
    else:
        for s in B:
            count_s = S.count(s)
            sum_count += (count_s * (count_s - 1) // 2)
    print(sum_count)

for i in range(N):
    X = A[0:i] + A[i + 1:N]
    func01(X)


### FIXED CODE ###

import collections

N = int(input())
A = input().split()

#A_set = set(A)

#ボールに書かれている 数字の内訳を辞書に登録
A_dic = collections.Counter(A)

#すべてのボールから同じボールを取り出す方法数
all_count = 0

for a in A_dic.keys():
    count_a = A_dic.get(a)
    all_count += (count_a * (count_a - 1) // 2)

#n個あるボールから 1個取り除いた場合の方法数
#すべてのボールから取り出す方法数 - (n-1)通り

for i in range(N):
    print(all_count - A_dic.get(A[i])+1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

s = input().rstrip()
t = input().rstrip()
ls = len(s)
lt = len(t)
dp = [[0]*(lt+1) for _ in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j] + 1
    else:
      dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
ans = ""
while ls > 0 and lt > 0:
  if dp[ls][lt] == dp[ls-1][lt]:
    ls -= 1
  elif dp[ls][lt] == dp[ls][lt-1]:
    lt -= 1
  else:
    ans = s[ls-1] + ans
    ls -= 1
    lt -= 1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

s = input().rstrip()
t = input().rstrip()
ls = len(s)
lt = len(t)
dp = [[0]*(lt+1) for _ in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j] + 1
    else:
      dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
ans = ""
while ls > 0 and lt > 0:
  if dp[ls][lt] == dp[ls-1][lt]:
    ls -= 1
  elif dp[ls][lt] == dp[ls][lt-1]:
    lt -= 1
  else:
    ans = s[ls-1] + ans
    ls -= 1
    lt -= 1
print(ans)
### BUGGY CODE ###

import math
a, b, n = map(int, input().split())
ma = -1
for x in range(n, -1, -1):
    tmp = math.floor(a*x/b) - a*math.floor(x/b)
    if ma < tmp:
        ma = tmp
print(ma)

### FIXED CODE ###

import math
a, b, n = map(int, input().split())
def f(x):
    return math.floor(a*x/b) - a*math.floor(x/b)
print(f(min(b-1, n)))
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()
    dp = [0] *(N+1)
    dp[1] = 1
    for i in range(2, N + 1):
        for l,r in LR:
            if i-l>0:
                dp[i] += sum(dp[max(1,i-r):min(N,i-l+1)]) % M
                dp[i] %= M
            else:
                break
    print(dp[N])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def segfunc(x, y):
    return x + y


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()

    A = [0] * (N + 1)
    A[1] = 1
    seg = SegTree(A, segfunc=segfunc, ide_ele=0)
    for i in range(2, N + 1):
        for l, r in LR:
            if i - l > 0:
                total = (seg.tree[i + seg.num] + seg.query(max(1, i - r), min(N, i - l + 1)) % M)
                seg.update(i, total)
            else:
                break
    print(seg.tree[seg.num + N] % M)


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


#####

import numpy as np
# from numpy import int32, int8
# from collections import defaultdict

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def travel(colors, h, w, row0, col0, targetColor, flipSize):
	
# 	print()
# 	print("row0",row0,"col0",col0,"flipSize",flipSize)
	
	visited=np.zeros((h, w), np.bool)
	visited[row0,col0]=True
	next=set()
	for hi in range(row0, h):
		for wi in range(col0, w):
			c=colors[hi,wi]==targetColor
			if hi>0 and visited[hi-1,wi]:
				if c:
					visited[hi,wi]=True
				else:
					next.add((hi,wi))
			if wi>0 and visited[hi,wi-1]:
				if c:
					visited[hi,wi]=True
				else:
					next.add((hi,wi))
	
	if visited[h-1,w-1]:
# 		print("found")
		return flipSize
					
# 	print(next)
	if len(next)==0: return None
	minFlipSize=None
	if targetColor: nextFlipSize=flipSize+1
	else: nextFlipSize=flipSize
	for nr,nc in next:
		fs=travel(colors, h, w, nr, nc, not targetColor, nextFlipSize)
		if fs is None: continue
		if minFlipSize is None or fs<minFlipSize: minFlipSize=fs
	return minFlipSize
				

def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."
# 	print(colors)
	
	if colors[0,0]: nextFlipSize=0
	else: nextFlipSize=1
	flipSize=travel(colors, h, w, 0, 0, colors[0,0], nextFlipSize)
# 	print("flipSize",flipSize)
	print(flipSize)
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)



### FIXED CODE ###


#####

import numpy as np
# from numpy import int32, int8
# from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs



def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."

# 	h=20
# 	w=20
# 	np.random.seed(0)
# 	colors=np.random.randint(0,2,(h,w))

# 	from matplotlib import pyplot as plt
# 	for hi in range(h):
# 		for wi in range(w):
# 			plt.annotate(str((hi,wi)), (wi-0.5,hi), color="g")
# 	plt.imshow(colors)
# 	plt.show()
			
# 	print(colors.astype(np.int32))
	
	flipSize=np.empty((h,w), np.int32)
	
	if colors[0,0]: flipSize[0,0]=0
	else: flipSize[0,0]=1
	
	for hi in range(h):
		for wi in range(w):
			if hi==0 and wi==0: continue
			c=colors[hi,wi]
			fs=[]
			if hi>0:
				d=int(colors[hi-1,wi] and (not c))
				s=flipSize[hi-1, wi]+d
				fs.append(s)
				
			if wi>0:
				d=int(colors[hi,wi-1] and (not c))
				s=flipSize[hi, wi-1]+d
				fs.append(s)
			
			fs=min(fs)
			flipSize[hi,wi]=fs
	
	print(flipSize[h-1,w-1])
	

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

import math

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

for i in range(N-1):
    for j in range(i+1,N):
        #print("i="+str(i)+"\tj="+str(j)+"\t[i]="+str(A[i])+"\t[j]="+str(A[j]))
        ans+=A[i]*A[j]
print(ans%((10**9)+7))

### FIXED CODE ###

import math

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

for i in range(N-1):
    tmp+=A[i]
    ans+=tmp*A[i+1]
print(ans%((10**9)+7))
### BUGGY CODE ###

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

ruiseki = [0] * 1001
for i in range(1, 1001):
    ruiseki[i] = ruiseki[i-1] + i

dp = [0] * n
for i in range(k - 1, n):
    for j in range(i + 1 - k, i + 1):
        dp[i] += p[j]

maxs = max(dp)
index = dp.index(maxs)

ans = 0
for l in range(index + 1 - k,index + 1):
    ans += ruiseki[p[l]] / p[l]

print(ans)

### FIXED CODE ###

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

saikoro = [0] * 1001
for i in range(1, 1001):
    saikoro[i] = (saikoro[i-1] + i)

s = [0] * (n + 1)
for u in range(1,n + 1):
    s[u] = saikoro[p[u - 1]] / p[u - 1] + s[u - 1]

ans = 0
for j in range(k - 1,n):
    ans = max(ans, s[j + 1] - s[j + 1 - k])
 
print(ans)
### BUGGY CODE ###

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

for i in range(1, n+1):
  print(a.count(i))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ary = [0]*n

for x in a:
  ary[x-1] += 1

print('\r'.join(map(str, ary)))