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

import bisect
import sys

sys.setrecursionlimit(10**6)
x = g = used = ans = None


def dfs(v):
    global x, g, used, ans
    used[v] = True
    res = x[v]
    for e in g[v]:
        if used[e[0]]:
            continue
        r = dfs(e[0])
        if r:
            ans.append(e[1])
        res ^= r
    return res


def main():
    global x, g, used, ans
    n, m = map(int, input().split())
    ab = [[] for _ in range(n)]
    ans = []
    g = [[] for _ in range(n+1)]
    used = [False] * (n+1)

    for i in range(n):
        ab[i] = list(map(int, input().split()))
    ab = sorted(ab, key=lambda x: x[0])
    al = list(map(lambda x: x[0], ab))
    for i in range(m):
        l, r = map(int, input().split())
        l = bisect.bisect_left(al, l)
        r = bisect.bisect_right(al, r)
        g[l].append((r, i+1))
        g[r].append((l, i+1))

    x = [0] * (n+1)
    x[0] = ab[0][1]
    for i in range(n-1):
        x[i+1] = ab[i][1] ^ ab[i+1][1]
    x[n] = ab[n-1][1]

    for i in range(n+1):
        if used[i]:
            continue
        if dfs(i):
            print(-1)
            return

    ans.sort()
    print(len(ans))
    print(*ans)


main()


### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dfs(v, x, g, used, ans):
    used[v] = True
    res = x[v]
    for e in g[v]:
        if used[e[0]]:
            continue
        r = dfs(e[0], x, g, used, ans)
        if r:
            ans.append(e[1])
        res ^= r
    return res


def main():
    n, m = map(int, input().split())
    ab = [[] for _ in range(n)]
    ans = []
    g = [[] for _ in range(n+1)]
    used = [False] * (n+1)

    for i in range(n):
        ab[i] = list(map(int, input().split()))
    ab = sorted(ab, key=lambda x: x[0])
    al = list(map(lambda x: x[0], ab))
    for i in range(m):
        l, r = map(int, input().split())
        l = bisect.bisect_left(al, l)
        r = bisect.bisect_right(al, r)
        g[l].append((r, i+1))
        g[r].append((l, i+1))

    x = [0] * (n+1)
    x[0] = ab[0][1]
    for i in range(n-1):
        x[i+1] = ab[i][1] ^ ab[i+1][1]
    x[n] = ab[n-1][1]

    for i in range(n+1):
        if used[i]:
            continue
        if dfs(i, x, g, used, ans):
            print(-1)
            return

    ans.sort()
    print(len(ans))
    print(*ans)


main()
### BUGGY CODE ###


def main():
    S = list(input())

    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    # 上からj桁目までの数を13で割ったあまりがiであるものの個数

    for i, sk in enumerate(S):
        if i == 0:
            if sk == '?':
                for j in range(10):
                    dp[0][j] = 1
            else:
                s = int(sk)
                dp[0][s] = 1
            continue
        if sk == '?':
            for j in range(13):
                for l in range(10): # 上からi桁目に入れる数字
                    k = (10*j+l)%13
                    dp[i][k] += dp[i-1][j]
        else:
            s = int(sk)
            for j in range(13):
                k = (10*j+s)%13
                dp[i][k] += dp[i-1][j]
        for j in range(13):
            dp[i][j] = dp[i][j] % 1000000007

    print(dp[-1][5])

if __name__ == '__main__':
    main()

### FIXED CODE ###


def main():
    S = list(input())

    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    # 上からj桁目までの数を13で割ったあまりがiであるものの個数

    for i, sk in enumerate(S):
        if i == 0:
            if sk == '?':
                for j in range(10):
                    dp[0][j] = 1
            else:
                s = int(sk)
                dp[0][s] = 1
            continue
        if sk == '?':
            for j in range(13):
                for l in range(10): # 上からi桁目に入れる数字
                    k = (10*j+l)%13
                    dp[i][k] += dp[i-1][j]
        else:
            s = int(sk)
            for j in range(13):
                k = (10*j+s)%13
                dp[i][k] += dp[i-1][j]
        for j in range(13):
            dp[i][j] = dp[i][j] % 1000000007

    print(dp[-1][5])

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

def answer(arr, k):
    _mod = (10**9+7)
    left = 0
    right = 0
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            if arr[i] > arr[j]:
                left += 1
            if arr[i] < arr[j]:
                right += 1
    leftStack = 0
    rightStack = 0
    for i in range(1, k+1):
        leftStack = (leftStack+(i*left))%_mod
        if i != k:
            rightStack = (rightStack + (i*right))%_mod

    return (leftStack + rightStack)%_mod

n, k = map(int, input().split())
arr = list(map(int, input().split()))
print(answer(arr, k))

### FIXED CODE ###

def answer(arr, k):
    _mod = (10**9+7)
    left = 0
    right = 0
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            if arr[i] > arr[j]:
                left += 1
            if arr[i] < arr[j]:
                right += 1
    
    left = (left * (k*(k+1))//2)
    right = (right * (k*(k-1))//2)
    return int((left+right)%_mod)
    
n, k = map(int, input().split())
arr = list(map(int, input().split()))
print(answer(arr, k))
# print(answer2(arr, k))
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

s = input()
k = ni()
li = []
for i in range(len(s)):
    for j in range(i, len(s)):
        t = s[i:j+1]
        if t not in li:
            li.append(s[i:j+1])
li.sort()
print(li[k-1])

### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

s = input()
k = ni()
li = []
for i in range(len(s)):
    for j in range(i, i+k+1):
        li.append(s[i:j+1])
li = list(set(li))
li.sort()
print(li[k-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = map(int,input().split())
ab = []
c = []
def bit(st):
    ls = list(st)
    res = 0
    for elem in ls:
        res += 2**(elem-1)
    return res

for i in range(M):
    ab.append(list(map(int,input().split())))
    c.append(set(map(int,input().split())))
dp = [10**6]*(2**N)
dp[0] = 0
for i in range(M):
    for j in range(2**N):
        dp[bit(c[i]) | j] = min(dp[bit(c[i]) | j], dp[j]+ab[i][0])
if dp[2**N-1] == 10**6:
    print(-1)
else:
    print(dp[2**N-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = map(int,input().split())
ab = []
c = []
def bit(ls):
    res = 0
    for elem in ls:
        res += 2**(elem-1)
    return res

for i in range(M):
    ab.append(list(map(int,input().split())))
    l = list(map(int,input().split()))
    val = bit(l)
    c.append(val)
dp = [10**6]*(2**N)
dp[0] = 0
for i in range(M):
    for j in range(2**N):
        dp[c[i] | j] = min(dp[c[i] | j], dp[j]+ab[i][0])
if dp[2**N-1] == 10**6:
    print(-1)
else:
    print(dp[2**N-1])
### BUGGY CODE ###

H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]
    
cum = np.array(cum)
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  q = list(q)
  p = deque()
  judge = False
  for a in range(len(q)-1):
    x = cum[q[a+1]]-cum[q[a]]
    if (x>K).any():
      judge = True
      break
    else:
      p.append(list(x))

  if judge:
    continue
  p = list(p)
  t_a = len(q)-2
  n = len(p)
  l = [0]*n
  for w in range(W):
    for x,a in enumerate(p):
      y = l[x]+a[w]
      if y>K:
        t_a+=1
        l = [0]*n
        for z,b in enumerate(p):
          l[z] = b[w]
        break
      else:
        l[x]=y
  ans = min(ans,t_a)
    
print(ans)

### FIXED CODE ###

def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    j = 0
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    t_a = len(q)-2
    if t_a>=ans:
      continue
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
        if t_a>=ans:
          judge = True
          break
      else:
        l = y
    if judge:
      continue
    ans = min(ans,t_a)

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

N, K = map(int, input().split())
p = list(map(int, input().split()))
temp = 0
for i in range(N - K + 1):
    temp = max(temp, sum(p[i:i + K]))
# print(temp)
print((temp + K) / 2)


### FIXED CODE ###

import collections

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

# サイコロ（1...p）の期待値は(1+p)/2
cum_sum = [0]
for i in range(0, N):
    cum_sum.append(cum_sum[i] + (1 + p[i]) / 2)
# print(cum_sum)
# 調べる区間は[1,...,K],...,[N-K+1,...N]
ans = 0
for i in range(1, N - K + 2):
    temp = cum_sum[i + K - 1] - cum_sum[i - 1]
    # print(temp)
    ans = max(ans, temp)
print(ans)
### BUGGY CODE ###

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

count = 1
for i in range(N-1):
    if min(P[:i+1]) > P[i+1]:
        count+=1
print(count)

### FIXED CODE ###

# https://atcoder.jp/contests/abc152/submissions/9600286
N = int(input())
P = list(map(int, input().split()))
c = 10**9
count = 0
for i in P:
    #リストの始めから探索
    #minを保持していく
    if i < c:
        c=i
        count+=1
print(count)
### BUGGY CODE ###

import heapq
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
road_map = []
for i in range(h):
    road = input()
    road_map.append(road)
queue = []
heapq.heappush(queue,[0,ch-1,cw-1])
used_map = [[-1]*w for _ in range(h)]

while queue != []:
    dot = heapq.heappop(queue)
    if dot[1] < 0 or dot[2] < 0 or dot[1] >= h or dot[2] >= w:
        continue
    if used_map[dot[1]][dot[2]] > -1 and used_map[dot[1]][dot[2]] <= dot[0]:
        continue
    if road_map[dot[1]][dot[2]] == "#":
        continue
    used_map[dot[1]][dot[2]] = dot[0]
    if used_map[dh-1][dw-1] > -1 and dot[0] >= used_map[dh-1][dw-1]:
        break

    if not (dot[2] - 1 < 0):
        heapq.heappush(queue,[dot[0],dot[1],dot[2]-1])
    if not (dot[2] + 1 >= w):
        heapq.heappush(queue,[dot[0],dot[1],dot[2]+1])
    if not (dot[1]+1 >= h):
        heapq.heappush(queue,[dot[0],dot[1]+1,dot[2]])
    if not (dot[1]-1 < 0):
        heapq.heappush(queue,[dot[0],dot[1]-1,dot[2]])

    for x in range(-2,3,1):
        for y in range(-2,3,1):
            if not(dot[1]+ x < 0 or dot[2]+y < 0 or dot[1]+x >= h or dot[2]+y >= w):
                if not(used_map[dot[1]+x][dot[2]+y] > -1 and used_map[dot[1]+x][dot[2]+y] <= dot[0]+1):
                    heapq.heappush(queue,[dot[0]+1,dot[1]+x,dot[2]+y])
    
print(used_map[dh-1][dw-1])

### FIXED CODE ###

#shotoyooさんのコードをお借りしてテスト

import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
hlist = np.array(list(map(int, input().split()))).astype(np.int64)
ab = [list(map(int, input().split())) for _ in range(m)]
ab = np.array(ab)
ba = ab[:, ::-1]

ans = 0
for i in range(1, n+1):
  t = np.zeros(n)
  for j in ab[ab[:,0] == i, 1]:
    t[j-1] = 1
  for j in ab[ba[:,0] == i, 0]:
    t[j-1] = 1
  if (t*hlist >= hlist[i-1]).sum() == 0:
    ans += 1
print(ans)

### FIXED CODE ###

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

maxh = [0]*n
for a, b in ab:
  maxh[a-1] = max(maxh[a-1], hlist[b-1])
  maxh[b-1] = max(maxh[b-1], hlist[a-1])
ans = 0
for i in range(n):
  if maxh[i] < hlist[i]:
    ans += 1
print(ans)
### BUGGY CODE ###


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

RD = []
p = []
rank = []

for i in range(N):

    RD.append([])
    p.append(i)
    rank.append(1)


for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    

end = [0] * N
endp = 0
endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp] == 0:
        Q.append(endp)
    else:
        continue

    while len(Q) > 0:

        q = Q.pop(0)
        end[q] = 1

        if cor[q] == "x":
            cor[q] = 0

        for r,d in RD[q]:

            if cor[r] == "x":
                cor[r] = cor[q] + d
                Q.append(r)

            elif cor[r] != cor[q] + d:
                ans = "No"
                break

        if ans == "No":
            break

    if ans == "No":
        break

print (ans)


### FIXED CODE ###

from collections import deque

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

RD = [deque() for i in range(N)]
end = [False] * N

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = deque()

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q.append(endp)


        while len(Q) > 0:

            q = Q.pop()
            end[q] = False

            if cor[q] == "x":
                cor[q] = 0

            for r,d in RD[q]:

                if cor[r] == "x":
                    cor[r] = cor[q] + d
                    Q.append(r)

                elif cor[r] != cor[q] + d:
                    print ("No")
                    exit()


print ("Yes")
### BUGGY CODE ###

n = int(input())

output = 0
for i in range(n):
    output += i
print(output)

### FIXED CODE ###

n = int(input())

output = (n * (n - 1)) // 2
print(output)
### BUGGY CODE ###

A, B, M = map(int, input().split())
Ma = [int(_) for _ in input().split()]
Mb = [int(_) for _ in input().split()]
Mm = [[int(_) for _ in input().split()] for __ in range(M)]

r = 10 ** 5
for i in range(A):
  for j in range(B):
    c = 0
    for x, y, z in Mm:
      if i == (x - 1) and j == (y - 1):
        c = max(c, z)
    r = min(r, Ma[i] + Mb[j] - c)
print(r)

### FIXED CODE ###

# AtCoder Hitachi B
A, B, M = map(int, input().split())
Ma = [int(_) for _ in input().split()]
Mb = [int(_) for _ in input().split()]
Mm = [[int(_) for _ in input().split()] for __ in range(M)]
# unuse vaucher
r0 = min(Ma) + min(Mb)
# use vaucher
r1 = min([Ma[x-1]+Mb[y-1]-c for x,y,c in Mm])
print(min(r0,r1))
### BUGGY CODE ###

N=int(input())
S=input()

ans = N

for n in range(N):
	blk=S[:n].count("#")
	white=S[n+1:].count(".")
	ans=min(blk+white,ans)


print(ans)

### FIXED CODE ###

N=int(input())
S=input()

blk=0
white=S.count(".")

ans=white

for n in range(N):
	if S[n]=="#":
		blk += 1
	else:
		white -= 1
	# print(blk,white)
	ans=min(blk+white,ans)


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

def main():
  s=input()
  q=int(input())
  turn = 2
  tmp=[]
  for i in s:
      tmp.append(i)
  for _ in [0]*q:
      query = input()
      try:
          t = int(query)
          turn = 3 - turn
      except ValueError:
          t,f,c = map(str,query.split())
          if (int(f) + turn)% 2  == 0:
              tmp.append(c)
          else:
              tmp = [c] + tmp
  if turn == 2:
      print("".join(tmp))
  else:
      print("".join(tmp[::-1]))
main()

### FIXED CODE ###

def main():
  from collections import deque
  s=input()
  q=int(input())
  turn = 2
  d=deque(s)

  for _ in [0]*q:
      query = input()
      if query[0] == "1":
          t = int(query)
          turn = 3 - turn
      else:
          t,f,c = map(str,query.split())
          if (int(f) + turn)% 2  == 0:
              d.append(c)
          else:
              d.appendleft(c)
  if turn == 2:
      print("".join(d))
  else:
      print("".join(list(d)[::-1]))
main()
### BUGGY CODE ###

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

li2 = li[::2]
li3 = li[1::2]
max2 = 0
max22 = 0
max3 = 0
max33 = 0

for i in range(int(n/2)):
    a = li2[i]
    count = 0
    for j in range(int(n/2)):
        if li2[j] == a:
            count += 1
    if count > max2:
        max22 = max2
        max2 = count
        b = a
    elif count > max22 and a != b:
        max22 = count


for i in range(int(n/2)):
    a = li3[i]
    count = 0
    for j in range(int(n/2)):
        if li3[j] == a:
            count += 1
    if count > max3:
        max33 = max3
        max3 = count
        c = a
    elif count > max33 and a != c:
        max33 = count

if b == c:
    print(max(n-max22-max3,n-max2-max33))
else:
    print(n-max2-max3)


### FIXED CODE ###

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

cnt1 = {}
cnt2 = {}

for i in range(n):
    if i % 2 == 0:
        if v[i] in cnt1:
            cnt1[v[i]] += 1
        else:
            cnt1[v[i]] = 1
    else:
        if v[i] in cnt2:
            cnt2[v[i]] += 1
        else:
            cnt2[v[i]] = 1

sorted_cnt1 = sorted(cnt1.items(), key = lambda x: x[1], reverse = True)
sorted_cnt2 = sorted(cnt2.items(), key = lambda x: x[1], reverse = True)

sorted_cnt1.append((-1,0))
sorted_cnt2.append((-1,0))

if sorted_cnt1[0][0] != sorted_cnt2[0][0]:
    print(n - sorted_cnt1[0][1] - sorted_cnt2[0][1])
else:
    print(n - max(sorted_cnt1[0][1] + sorted_cnt2[1][1], sorted_cnt1[1][1]+sorted_cnt2[0][1]))
### BUGGY CODE ###

import heapq
from collections import defaultdict

def dijkstra(i, V, E, INF=1e9):
    D = {v: INF for v in V}
    D[i] = 0
    Q = [(d, v) for v, d in D.items()]
    heapq.heapify(Q)
    prev = {v: None for v in V}

    while len(Q) > 0:
        du, u = heapq.heappop(Q)
        for v, duv in E[u].items():
            dv = du + duv
            if D[v] > dv:
                D[v] = dv
                prev[v] = u
                heapq.heappush(Q, (dv, v))
    return D

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1

s = [list(input()) for _ in range(h)]
V = []
E = defaultdict(dict)
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        V.append((i, j))

        for k in range(-2, 3):
            for l in range(-2, 3):
                if k == 0 and l == 0:
                    continue
                x = i + k
                y = j + l
                if x < 0 or x >= h or y < 0 or y >= w or s[x][y] == '#':
                    continue
                if (k, l) in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                    E[(i, j)][(x, y)] = 0
                    E[(x, y)][(i, j)] = 0
                else:
                    E[(i, j)][(x, y)] = 1
                    E[(x, y)][(i, j)] = 1

INF = 1e9
D = dijkstra((ch, cw), V, E, INF=INF)

if D[(dh, dw)] == INF:
    print(-1)
else:
    print(D[(dh, dw)])


### FIXED CODE ###

def dfs(xt, yt, S, V, w):
    B = set()
    while(len(S) > 0):
        xi, yi = S.pop()
        A = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                xj, yj = xi + i, yi + j
                if xj < 0 or len(V) <= xj or yj < 0 or len(V[0]) <= yj:
                    continue
                if -1 <= i <= 1 and -1 <= j <= 1 and i * j == 0:
                    A.append((xj, yj))
                else:
                    B.add((xj, yj))

        for xj, yj in A:
            if xj == xt and yj == yt:
                return False, B, V, w
            if V[xj][yj] > 0:
                V[xj][yj] = -1
                S.append((xj, yj))

    B_new = []
    for x, y in B:
        if x == xt and y == yt:
            return False, B, V, w + 1
        if V[x][y] > 0:
            V[x][y] = -1
            B_new.append((x, y))
    return True, B_new, V, w

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1

s = [list(map(lambda x: int(x == '.'), list(input()))) for _ in range(h)]

flag = True
B = [(ch, cw)]
w = -1
s[ch][cw] = -1
while flag:
    flag, B, s, w = dfs(dh, dw, B, s, w + 1)
    if flag and len(B) == 0:
        print(-1)
        break
else:
    print(w)
### BUGGY CODE ###

k, s = map(int, input().split())

ans = 0

for x in range(0, k+1):
    for y in range(0, k+1):
        for z in range(0, k+1):
            if x+y+z == s:
                ans += 1

print(ans)


### FIXED CODE ###

k, s = map(int, input().split())

ans = 0

for x in range(k+1):
    for y in range(k+1):
        if 0 <= s-x-y <= k:
            ans += 1

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

n = int(input())
a = list(map(int, input().split()))
cnt = 1
i = -1
flg = True
while True:
  i += 1
  if i >= n-1:
    break
  if a[i] < a[i+1]:
    flg = True
  elif a[i] > a[i+1]:
    flg = False
  else:
    continue
  for k in range(i, n-1):
    if (flg and a[k] > a[k+1]) or ((not flg) and a[k] < a[k+1]):
      cnt += 1
      i = k
      break
print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = 1
b = [0] + a
c = [(i-j)//abs(i-j) for i, j in zip(a, b) if i != j]
del c[0]
if c:
  mae=c[0]
  d=iter(c)
  for x in d:
    if x != mae:
      cnt += 1
      try:
        mae = d.__next__()
      except StopIteration:
        break
print(cnt)