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

from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range((1 << N) + 100)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state + 100][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    stateX = 0
    stateY = 0
    M = N
    for s in state:
        stateX <<= 1
        stateY <<= 1
        if s == 0: M -= 1
        if s == 1: stateX |= 1
        if s == 2: stateY |= 1

    cost = 0
    for x, y in zip(costX[stateX + 100], costY[stateY + 100]):
        cost += min(x, y)

    if ans[M] > cost:
        ans[M] = cost

print(*ans, sep='\n')


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()
### BUGGY CODE ###

import math
from scipy.misc import comb

#def permod(n, r):
  #return (math.factorial(n) // math.factorial(n - r)) % (10 ** 9 + 7)

def main():
  X,Y = map(int,input().split())
  
  if (X + Y) % 3 != 0:
    print(0)
    
  else:
    a = Y - (X + Y) // 3
    b = X - (X + Y) // 3
    
    total = a + b
    m = min(a,b)
    
    ans = comb(total,m,exact = True)
    print(ans)
    
main()

### FIXED CODE ###

def cmb(n, k, mod, fac, infac):
  k = min(k,n-k)
  return fac[n] * infac[k] * infac[n-k] % mod

def tables(mod, n):
  fac = [1, 1] 
  infac = [1, 1] 
  inverse = [0, 1] 
  for i in range(2, n+1):
    fac.append((fac[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    infac.append((infac[-1] * inverse[-1]) % mod)
  return fac,infac

X,Y = map(int, input().split())

if X > Y:
  X, Y = Y, X

move = X + Y

if move % 3 != 0:
  print(0)
else:
  total = move // 3
  n = X - total
  
  if n < 0:
    print(0)
    
  else:
    MOD = 10 ** 9 + 7
    fac, infac = tables(MOD, total)
    ans = cmb(total, n, MOD, fac, infac)
    
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
class UnionFind():
    def __init__(self, n):
        self.n = 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 members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

n,k,l=map(int,input().split())
uf1=UnionFind(n)
for _ in range(k):
    p,q=map(int,input().split())
    uf1.union(p-1,q-1)
uf2=UnionFind(n)
for _ in range(l):
    p,q=map(int,input().split())
    uf2.union(p-1,q-1)
ans=[]
for i in range(n):
    a=set(uf1.members(i))
    b=set(uf2.members(i))
    c=a&b
    print(len(c))


### FIXED CODE ###

import sys
input = sys.stdin.readline
class UnionFind():
    def __init__(self, n):
        self.n = 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 same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

n,k,l=map(int,input().split())
uf1=UnionFind(n)
for _ in range(k):
    p,q=map(int,input().split())
    uf1.union(p-1,q-1)
uf2=UnionFind(n)
for _ in range(l):
    p,q=map(int,input().split())
    uf2.union(p-1,q-1)
from collections import defaultdict
p=defaultdict(int)
for i in range(n):
    a=uf1.find(i)
    b=uf2.find(i)
    p[(a,b)]+=1
ans=[]
for i in range(n):
    ans.append(p[uf1.find(i),uf2.find(i)])
print(*ans)
### BUGGY CODE ###

H,W = map(int,input().split())
State = []
for i in range(H):
    State.append(input())
starts = [(i%H,i//H) for i in range(H*W)]
goals = [(i%H,i//H) for i in range(H*W)]
from collections import deque
def min_dist(start,goal):
    visited = [[False for i in range(W)] for j in range(H)]
    dists = [[float('inf') for i in range(W)] for j in range(H)]
    dists[start[0]][start[1]]=0
    diffs = [(0,1),(1,0),(0,-1),(-1,0)]
    Q = deque([start])
    while Q:
        current_pos = Q.pop()
        for diff in diffs:
            next_pos = (current_pos[0]-diff[0],current_pos[1]-diff[1])
            if next_pos[0] < H and next_pos[0] >= 0 and next_pos[1] < W and next_pos[1] >= 0:
                if State[next_pos[0]][next_pos[1]] == '.':
                    dists[next_pos[0]][next_pos[1]] = min(dists[current_pos[0]][current_pos[1]]+1,dists[next_pos[0]][next_pos[1]])
                    if not visited[next_pos[0]][next_pos[1]]:
                        visited[next_pos[0]][next_pos[1]] = True
                        Q.appendleft(next_pos)
    return dists[goal[0]][goal[1]]
max_dist = -100000
for start in starts:
    for goal in goals:
        a = min_dist(start,goal)
        if a != float('inf'):
            if a > max_dist:
                max_dist = a
print(max_dist)



### FIXED CODE ###

H,W = map(int,input().split())
State = []
for i in range(H):
    State.append(input())
starts = [(i%H,i//H) for i in range(H*W)]
goals = [(i%H,i//H) for i in range(H*W)]
from collections import deque
def min_dist(start):
    visited = [[False for i in range(W)] for j in range(H)]
    dists = [[float('inf') for i in range(W)] for j in range(H)]
    dists[start[0]][start[1]]=0
    diffs = [(0,1),(1,0),(0,-1),(-1,0)]
    Q = deque([start])
    while Q:
        current_pos = Q.pop()
        for diff in diffs:
            next_pos = (current_pos[0]-diff[0],current_pos[1]-diff[1])
            if next_pos[0] < H and next_pos[0] >= 0 and next_pos[1] < W and next_pos[1] >= 0:
                if State[next_pos[0]][next_pos[1]] == '.':
                    dists[next_pos[0]][next_pos[1]] = min(dists[current_pos[0]][current_pos[1]]+1,dists[next_pos[0]][next_pos[1]])
                    if not visited[next_pos[0]][next_pos[1]]:
                        visited[next_pos[0]][next_pos[1]] = True
                        Q.appendleft(next_pos)
    return dists
max_dist = -100000
for start in starts:
    if State[start[0]][start[1]] == '.':
        dists = min_dist(start)
        local_max_dist = -1000000
        for i in range(W):
            for j in range(H):
                if dists[j][i] != float('inf'):
                    if local_max_dist < dists[j][i]:
                        local_max_dist = dists[j][i]
        if local_max_dist > max_dist:
            max_dist = local_max_dist
print(max_dist)
### BUGGY CODE ###

s=input()
q=int(input())

rev = 1
fr = ""
rr = ""

for i in range(q):
    ss=input()
    if int(ss[0])==1:
        rev *= -1
    else:
        f,c=int(ss[2]),ss[4]
        if f == 2:
            f = -1
        
        if f*rev ==1:
            fr+=c
        else:
            rr+=c

if rev == 1:
    ans = fr[::-1]+s+rr
else:
    ans = rr[::-1]+s[::-1]+fr
print(ans)

### FIXED CODE ###

s=input()
q=int(input())

rev = 1
fr = ""
rr = ""

for i in range(q):
    ss=input()
    if int(ss[0])==1:
        rev *= -1
    else:
        f,c=int(ss[2]),ss[4]
        if f == 2:
            f = -1
        
        if f*rev ==1:
            fr+=c
        else:
            rr+=c

if rev == 1:
    ans = fr[::-1]+s+rr
else:
    ans = rr[::-1]+s[::-1]+fr
print(ans)
### BUGGY CODE ###

from sys import stdin


class Node():
    def __init__(self,  key=None, prev=None, next=None):
        self.key = key
        self.prev = prev
        self.next = next


class DoublyLinkedList():
    def __init__(self):
        self.head = Node()
        self.head.next = self.head
        self.head.prev = self.head

    def insert(self, x):
        node = Node(key=x, prev=self.head, next=self.head.next)
        self.head.next.prev = node
        self.head.next = node

    def search(self, x):
        node = self.head.next
        while node is not self.head and node.key != x:
            node = node.next
        return node

    def delete_key(self, x):
        node = self.search(x)
        if node is self.head:
            return None
        self._delete(node)

    def _delete(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def deleteFirst(self):
        self._delete(self.head.next)

    def deleteLast(self):
        self._delete(self.head.prev)

    def getKeys(self):
        node = self.head.next
        keys = []
        while node is not self.head:
            keys.append(node.key)
            node = node.next
        return " ".join(keys)


L = DoublyLinkedList()
n = int(input())
for i in range(n):
    command = stdin.readline().strip().split()
    if command[0] == "insert":
        L.insert(command[1])
    elif command[0] == "delete":
        L.delete_key(command[1])
    elif command[0] == "deleteFirst":
        L.deleteFirst()
    else:
        L.deleteLast()
    # print(L.getKeys())

print(L.getKeys())



### FIXED CODE ###

import sys


class Node():
    def __init__(self,  key=None, prev=None, next=None):
        self.key = key
        self.prev = prev
        self.next = next


class DoublyLinkedList():
    def __init__(self):
        self.head = Node()
        self.head.next = self.head
        self.head.prev = self.head

    def insert(self, x):
        node = Node(key=x, prev=self.head, next=self.head.next)
        self.head.next.prev = node
        self.head.next = node

    def search(self, x):
        node = self.head.next
        while node is not self.head and node.key != x:
            node = node.next
        return node

    def delete_key(self, x):
        node = self.search(x)
        if node is self.head:
            return None
        self._delete(node)

    def _delete(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def deleteFirst(self):
        self._delete(self.head.next)

    def deleteLast(self):
        self._delete(self.head.prev)

    def getKeys(self):
        node = self.head.next
        keys = []
        while node is not self.head:
            keys.append(node.key)
            node = node.next
        return " ".join(keys)


L = DoublyLinkedList()
n = int(input())
for i in sys.stdin:
    if 'insert' in i:
        x = i[7:-1]
        L.insert(x)
    elif 'deleteFirst' in i:
        L.deleteFirst()
    elif 'deleteLast' in i:
        L.deleteLast()
    elif 'delete' in i:
        x = i[7:-1]
        L.delete_key(x)
    else:
        pass
print(L.getKeys())
### BUGGY CODE ###

from collections import Counter

n = int(input())
a = list(map(int,input().split()))
ac = Counter(a)
an = len(ac)

cnt = 0
for i in range(an):
  num, count = ac.most_common()[i]
  if count > num:
    cnt += count - num
  elif count < num:
    cnt += count

print(cnt)

### FIXED CODE ###

from collections import Counter

n = int(input())
a = list(map(int,input().split()))
ac = Counter(a)
an = len(ac)
a_mostcommon = ac.most_common()
cnt = 0
for i in range(an):
  num, count = a_mostcommon[i]
  if count > num:
    cnt += count - num
  elif count < num:
    cnt += count

print(cnt)
### BUGGY CODE ###

N, K = map(int,input().split())
p = list(map(int, input().split()))
exp = list(map(lambda x : (x+1)/2, p))         
ans = 0
for i in range(N-K+1):
  if sum(exp[i:i+K]) > ans: ans = sum(exp[i:i+K])
print(ans)

### FIXED CODE ###

N, K = map(int,input().split())
p = list(map(int, input().split()))
s = [0]
for i in range(N):
  s.append(s[i]+p[i])
num = 0
ans = 0
exp = 0
for i in range(N-K+1):
  sum = s[i+K]-s[i]
  if num<sum: 
    num = sum
    ans = i
for i in range(K):
  exp += (p[ans+i]+1)/2
print(exp)
### BUGGY CODE ###

a, b = map(int, input().split())
ans = a
for i in range(a + 1, b + 1):
    ans ^= i
    
print(ans)

### FIXED CODE ###

a, b = map(int,input().split())
 
def f(n) :
    if n % 4 == 0 :
        return n
    elif n % 4 == 1 :
        return 1
    elif n % 4 == 2 :
        return n + 1
    else :
        return 0

print(f(a - 1) ^ f(b))
### BUGGY CODE ###

N = int(input())
A=list(map(int,input().split()))
i=0
s=[]
for i in range(N):
    s.append(0)
for i in range(N):
    for j in range(N-1):
        if i+1==A[j]:
            s[i]=s[i]+1
for i in range(N):
    print(s[i])

### FIXED CODE ###

import collections
n = int(input())
base = map(int,input().split())
c = collections.Counter(base)
for i in range(1,n):
    print(c[i])
print(0)
### BUGGY CODE ###

import math
from math import gcd,pi
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n = i_input()
    s = s_input()
    l = list(itertools.combinations(list(range(n)), 3))
    ans = 0
    for i in l:
        z = i[0]
        o = i[1]
        t = i[2]
        if o - z != t - o:
            if s[z] != s[o] and s[o] != s[t] and s[t] != s[z]:
                ans += 1
    print(ans)


if __name__=="__main__":
    main()


### FIXED CODE ###

import math
from math import gcd,pi
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n = i_input()
    s = s_input()

    r_cn = s.count("R")
    g_cn = s.count("G")
    b_cn = s.count("B")

    ans = r_cn*g_cn*b_cn

    for i in range(n):
        for d in range(n):
            j = i+d
            k = j+d
            if k >=n:
                break
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                ans -= 1
    print(ans)


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

L, A, B, M = map(int, input().split())

ten = 1

def f(l):
  if l == 0:
    return 0
  if l % 2 == 1:
    pl = l - 1
    x = f(pl)
    return (x * ten + 1) % M
  else:
    pl = l // 2
    x = f(pl)
    return (x * ten ** pl + x) % M

def g(l):
  if l == 0:
    return 0
  if l % 2 == 1:
    pl = l - 1
    x = g(pl)
    return (x * ten + B * pl) % M
  else:
    pl = l // 2
    x = g(pl)
    return (x * ten ** pl + x + B * pl * f(pl)) % M

last = A + B * (L - 1)
ans = 0

for i in range(1, 19):
  l = ten
  r = ten * 10 - 1
  
  if last < l:
    ten *= 10
    continue
  if A > r:
    ten *= 10
    continue
  na = 0 #初項
  nl = 0 #長さ

  if A >= l:
    na = A
  else:
    na = (l - A + B - 1) // B * B + A
    na = min(na, last)
  
  nlast = 0
  if last <= r:
    nlast = last
  else:
    nlast = (r - A) // B * B + A
  nl = (nlast - na) // B + 1

  ten *= 10
  ans *= ten ** nl % M
  ans += (na * f(nl)) % M
  ans += g(nl) % M

print(ans % M)

### FIXED CODE ###

L, A, B, M = map(int, input().split())

ten = 0

def pow_(x, t):
  if t == 0:
    return 1
  if t % 2 == 1:
    return (pow_(x, t - 1) * x) % M
  else:
    y = pow_(x, t // 2)
    return (y * y) % M

def f(l):
  if l == 0:
    return 0
  if l % 2 == 1:
    pl = l - 1
    x = f(pl)
    return x * ten + 1
  else:
    pl = l // 2
    x = f(pl)
    return x * pow_(ten, pl) + x

def g(l):
  if l == 0:
    return 0
  if l % 2 == 1:
    pl = l - 1
    x = g(pl)
    return x * ten + B * pl
  else:
    pl = l // 2
    x = g(pl)
    return x * pow_(ten, pl) + x + B * pl * f(pl)

last = A + B * (L - 1)
ans = 0
ten = 10
for _ in range(18):
  l = ten // 10
  r = ten - 1
  
  if last < l:
    ten *= 10
    continue
  if A > r:
    ten *= 10
    continue
  na = 0 #初項
  nl = 0 #長さ

  if A >= l:
    na = A
  else:
    na = (l - A + B - 1) // B * B + A
    na = min(na, last)
  
  nlast = 0
  if last <= r:
    nlast = last
  else:
    nlast = (r - A) // B * B + A
  nl = (nlast - na) // B + 1

  ans *= pow_(ten, nl) % M
  ans += (na * f(nl)) % M
  ans += g(nl) % M
  ten *= 10

print(ans % M)
### BUGGY CODE ###

import collections, itertools, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    xy = [LI() for _ in range(N)]

    # x, y全ての重複あり組み合わせに対して含まれる点の個数を算出する

    x_cnt = collections.Counter([i[0] for i in xy])
    x_coordinate = list(x_cnt.keys())
    x_coordinate.sort()
    # len_x_c = len(x_coordinate)
    y_cnt = collections.Counter([i[1] for i in xy])
    y_coordinate = list(y_cnt.keys())
    y_coordinate.sort()
    len_y_c = len(y_coordinate)

    ans = INF
    for xl, xh in itertools.combinations(x_coordinate, 2):
        # 4番目の辺の探索は、個数条件を満たしたら終了していよい
        for i in range(len_y_c - 1):
            yl = y_coordinate[i]
            for j in range(i + 1, len_y_c):
                yh = y_coordinate[j]
                cnt = len([(i, j) for i, j in xy if xl <= i <= xh and yl <= j <= yh])
                if cnt >= K:
                    ans = min((xh - xl) * (yh - yl), ans)
                    break

    print(ans)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import collections, itertools, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    xy = [LI() for _ in range(N)]

    # x, y全ての重複あり組み合わせに対して含まれる点の個数を算出する

    x_cnt = collections.Counter([i[0] for i in xy])
    x_coordinate = list(x_cnt.keys())
    x_coordinate.sort()
    # len_x_c = len(x_coordinate)
    y_cnt = collections.Counter([i[1] for i in xy])
    y_coordinate = list(y_cnt.keys())
    y_coordinate.sort()
    len_y_c = len(y_coordinate)

    ans = INF
    for xl, xh in itertools.combinations(x_coordinate, 2):
        # 4番目の辺の探索は、個数条件を満たしたら終了していよい
        for i in range(len_y_c - 1):
            yl = y_coordinate[i]
            for j in range(i + 1, len_y_c):
                yh = y_coordinate[j]
                cnt = len([(i, j) for i, j in xy if xl <= i <= xh and yl <= j <= yh])
                if cnt >= K:
                    ans = min((xh - xl) * (yh - yl), ans)
                    break

    print(ans)

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

n = int(input())
l = [int(input()) for _ in range(n)]

for i in range(n):
  li = l[:i] + l[i+1:]
  print(max(li))

### FIXED CODE ###

n = int(input())
l = [int(input()) for _ in range(n)]
ls = sorted(l)

for i in range(n):
  print(ls[-1] if l[i] != ls[-1] else ls[-2])
### BUGGY CODE ###

from collections import deque

s = deque(input())
q = int(input())

flg_reverse = False


def query_2(s, a, b):
    global flg_reverse
    if flg_reverse is False:
        if a == 2:
            s.append(b)
        elif a == 1:
            s.appendleft(b)
    else:
        if a == 1:
            s.append(b)
        elif a == 2:
            s.appendleft(b)


for i in range(q):
    array = list(input().split())
    if len(array) == 1:
        flg_reverse = not flg_reverse
    else:
        query_2(s, int(array[1]), array[2])

if flg_reverse is False:
    for i in s:
        print(i, end='')
else:
    for i in range(len(s)-1, -1, -1):
        print(s[i], end='')



### FIXED CODE ###

from collections import deque

s = deque(list(input()))
q = int(input())
flg = 1
for i in range(q):
    array = input().split(' ')
    if array[0] == '1':
        flg *= -1
    elif array[0] == '2':
        if array[1] == '1' and flg == 1 or array[1] == '2' and flg == -1:
            s.appendleft(array[2])
        else:
            s.append(array[2])

s = list(s)
if flg == -1:
    s = s[::-1]

s = ''.join(s)
print(s)
### BUGGY CODE ###

import queue
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = float('inf')
q = queue.Queue()

if s[0][0] == '#':
    q.put([0, 0, 1])
else:
    q.put([0, 0, 0])

while not q.empty():
    a = q.get()
    if ans <= a[2]:
        continue
    
    if a[0] == h-1 and a[1] == w-1:
        ans = min(ans, a[2])
        
    if a[0]+1 < h:
        if s[a[0]+1][a[1]] == '#':
            q.put([a[0]+1, a[1], a[2]+1])
        else:
            q.put([a[0]+1, a[1], a[2]])

    if a[1]+1 < w:
        if s[a[0]][a[1]+1] == '#':
            q.put([a[0], a[1]+1, a[2]+1])
        else:
            q.put([a[0], a[1]+1, a[2]])
print(ans)


### FIXED CODE ###

import queue
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = float('inf')
q = queue.Queue()
vals = [[float('inf')]*w for _ in range(h)]
vals[0][0] = 0
q.put([0, 0])

while not q.empty():
    a = q.get()
    for i, j in ((1, 0), (0, 1)):
        x, y = a[0]+i, a[1]+j
        if 0 <= x < h and 0 <= y < w:
            if s[x][y] == '#' and s[a[0]][a[1]] == '.':
                if vals[x][y] > vals[a[0]][a[1]]+1:
                    vals[x][y] = vals[a[0]][a[1]]+1
                    q.put([x, y])
            elif vals[x][y] > vals[a[0]][a[1]]:
                vals[x][y] = vals[a[0]][a[1]]
                q.put([x, y])
ans = vals[-1][-1]
if s[0][0] == '#':
    ans += 1

print(ans)