Harryxun/stf_run huggingface dataset:
from collections import Counter


H, W = map(int, input().split())
A = [input() for _ in range(H)]

char_to_cnt = Counter()
for h in range(H):
    for w in range(W):
        char_to_cnt.update(A[h][w])

def check(table):
    for i in range(H):
        if "".join(table[i]) != "".join(reversed(table[i])):
            return False
    for j in range(W):
        row = [table[i][j] for i in range(H)]
        if "".join(row) != "".join(reversed(row)):
            return False
    return True

ans = False
def dfs(i, j, table, remain):
    global ans
    if ans:
        return
    # print(i, j, table, remain)
    for char, cnt in remain.items():
        if cnt == 0:
            continue

        new_table = list(table)
        new_table[i][j] = char
        if i == H - 1 and j == W - 1:
            if check(new_table):
                ans = True
            return

        new_remain = Counter(remain)
        new_remain[char] -= 1

        if j == W - 1:
            dfs(i + 1, 0, new_table, new_remain)
        else:
            dfs(i, j + 1, new_table, new_remain)

table = [["" for _ in range(W)] for i in range(H)]
dfs(0, 0, table, char_to_cnt)

if ans:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

from collections import Counter


H, W = map(int, input().split())
A = [input() for _ in range(H)]

char_to_cnt = Counter()
for h in range(H):
    for w in range(W):
        char_to_cnt.update(A[h][w])

if H % 2 != 0 and W % 2 != 0:
    g1 = 1
    g2 = H // 2 + W // 2
    g4 = (H // 2) * (W // 2)
else:
    g1 = 0
    if H % 2 == 0 and W % 2 == 0:
        g2 = 0
    else:
        if H % 2 == 0:
            g2 = H // 2
        else:
            g2 = W // 2
    g4 = (H * W - g1 - g2 * 2) // 4

for _ in range(g1):
    for char in char_to_cnt.keys():
        cnt = char_to_cnt[char]
        if cnt % 4 == 1 or cnt % 4 == 3:
            char_to_cnt[char] -= 1
            break

for _ in range(g2):
    for char in char_to_cnt.keys():
        cnt = char_to_cnt[char]
        if cnt % 4 == 2:
            char_to_cnt[char] -= 2
            break

for _ in range(g4):
    for char in char_to_cnt.keys():
        cnt = char_to_cnt[char]
        if cnt != 0 and cnt % 4 == 0:
            char_to_cnt[char] -= 4
            break

for _, cnt in char_to_cnt.items():
    if cnt % 4 != 0:
        print("No")
        exit()

print("Yes")
n=int(input())
hoge=[]
for i in range(n):
  x,y,z=map(int,input().split())
  if(z!=0):
    hoge.append([x,y,z])
  
for i in range(101):
  for j in range(101):
    h=[]
    for k in range(n):
      h.append(hoge[k][2]+abs(hoge[k][0]-i)+abs(hoge[k][1]-j))
      
    if(h.count(h[0])==len(h)):
      print(i,j,h[0])

### FIXED CODE ###

n=int(input())
hoge=[]
for i in range(n):
  x,y,z=map(int,input().split())
  if(z!=0):
    hoge.append([x,y,z])
  

if(len(hoge)==1):
  print(*hoge[0])
  exit()

for i in range(101):
  for j in range(101):
    h=[]
    for k in range(len(hoge)):
      h.append(hoge[k][2]+abs(hoge[k][0]-i)+abs(hoge[k][1]-j))
      
    if(h.count(h[0])==len(h)):
      print(i,j,h[0])
import math
aa=int(input())
N=[0 for i in range(aa)]
for i in range(aa):
  bb=input()
  #print(b)
  N[i]=bb.split()


def so(p,q):
  while p!=q:
    if p>q:
      p-=q
    else:
      q-=p
  return p


#print(so(11,5))

def aaa(n):

  a=int(N[n][0])
  b=int(N[n][1])
  c=int(N[n][2])
  d=int(N[n][3])

  e=a-a//b*b
  f=d-d//b*b
  
  if e*f>0 :
    s=math.gcd(e,f)
  else :
    s=f


  if a<b or d<b :
    return "No"
  
  elif b<=c :
    return "Yes"
  else:
  
    if f!=0 :
      ss=b//s*s
      if ss==b:
        ss-=s

      if ss>c:
        return "No"
          
    

        #print(e)
        #print(f)
  #print("while")
    else:
      if e>c :
        return "No"

  return "Yes"

for i in range(aa):
  print(aaa(i))


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
C = [list(map(int,input().split())) for i in range(n)]

from fractions import gcd

for i in range(n):
    a = C[i][0]
    b = C[i][1]
    c = C[i][2]
    d = C[i][3]
    ng = 0

    e = 0  # 最初に補充が発生する直前の本数
    e0 = a - b
    e1 = ((c - a%b) // b) * b + a%b
    e = min(e0, e1)

    if e < 0 or b > d:
        ng = 1
    else:
        g = gcd(b, d)
        # print(c+1, b-1, g)
        if c+1 <= b-1 and (c - e) // g < (b-1 - e) // g:
            ng = 1

    if ng == 1:
        print("No")
    else:
        print("Yes")
n, m = map(int, input().split())
s = []
d = []
for i in range(n):
    x, y = map(int, input().split())
    s.append([x, y])
for i in range(m):
    x, y = map(int, input().split())
    d.append([x, y])
for i in s:
    a = m
    c = abs(i[0] - d[0][0]) + abs(i[1] - d[1][1])
    for j in range(1, m):
        c_t = abs(i[0] - d[j][0]) + abs(i[1] - d[j][1])
        if c_t < c:
            c = min(c, c_t)
            a = j
    print(a)


### FIXED CODE ###

a, b = map(int, input().split())
if a + b >= 24:
    print(a + b - 24)
else:
    print(a + b)
import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))

ans=0
mod=10**9+7
for i in range(60):
    x=0
    for j in range(n):
        if (a[j] >>i&1) :x+=1

    now = x*(n-x) % mod

    for j in range(i):
        now = now*2 % mod
    ans += now
    ans %= mod

print(ans)

### FIXED CODE ###

# import numpy as np
n=int(input())
# a=np.array(list(map(int,input().split())))
a=list(map(int,input().split()))

ans=0
mod=10**9+7
for i in range(60):
    x=0
    for j in range(n):
        if (a[j] >>i&1) :x+=1

    now = x*(n-x) % mod

    for j in range(i):
        now = now*2 % mod
    ans += now
    ans %= mod

print(ans)
n,k=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(k)]

mod = 998244353

dp = [0] * (n+1)
sdp = [0] * (n+1)
dp[1] = 1
sdp[1] = 1

for i in range(n+1):
  for j in range(k):
    left = max(0, i-lr[j][1])
    right = max(0, i-lr[j][0]+1)
    
    dp[i] += sdp[right] - sdp[left]
  if i+1 <= n:
    sdp[i+1] = sdp[i]%mod + dp[i]%mod

print(dp%mod)

### FIXED CODE ###

n,k=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(k)]

mod = 998244353

dp = [0] * (n+1)
sdp = [0] * (n+1)
dp[1] = 1
sdp[1] = 1

for i in range(n+1):
  for j in range(k):
    left = max(0, i-lr[j][1])
    right = max(0, i-lr[j][0]+1)
    
    dp[i] += sdp[right] - sdp[left]
  if i+1 <= n:
    sdp[i+1] = sdp[i]%mod + dp[i]%mod

print(dp[n]%mod)
M,N=map(int,input().split())
X = list(map(int,input().split()))
X.sort()
xdelta = []

for i in range(len(X)-1):
	xdelta.append(abs(X[i+1]-X[i]))

xdelta.sort()
#print(xdelta)

if M == 1:
	print(0)
elif N == 1:
	print(sum(xdelta))
else:
	for i in range(M-1):
		xdelta.pop(-1)
	print(sum(xdelta))

### FIXED CODE ###

N,M=map(int,input().split())
X = list(map(int,input().split()))
X.sort()
xdelta = []

for i in range(len(X)-1):
	xdelta.append(abs(X[i+1]-X[i]))

xdelta.sort()

if N < M:
	if N == 1:
		print(sum(xdelta))
	else:
		for i in range(N-1):
			xdelta.pop(-1)
		print(sum(xdelta))
else:
	print(0)
import string
s = input()
t = input()
l = []
alp = string.ascii_lowercase
G = dict([(alp[i],-1) for i in range(len(alp))])
for i in range(len(s)-1,-1,-1):
  l.append(G.copy())
  G[s[i]] = i
l = l[::-1]  
stG = G.copy()

cnt = 0
ind = 0
while ind < len(t): 
  if stG[t[ind]] == -1:
    cnt = -1
    break
  else:
    lind = stG[t[ind]]
    ind += 1
    while l[lind][t[ind]] != -1:   
      lind = l[lind][t[ind]]
      ind += 1
      if ind == len(t):
        break   
    if ind == len(t):
      break        
    cnt += 1

###    
if cnt != -1:      
  print(cnt*len(s)+stG[t[-1]]+1)
else:
  print(cnt)  

### FIXED CODE ###

import string
s = input()
t = input()
l = []
alp = string.ascii_lowercase
G = dict([(alp[i],-1) for i in range(len(alp))])
for i in range(len(s)-1,-1,-1):
  l.append(G.copy())
  G[s[i]] = i
l = l[::-1]  
stG = G.copy()

cnt = 0
ind = 0
while ind < len(t): 
  if stG[t[ind]] == -1:
    cnt = -1
    break
  else:
    lind = stG[t[ind]]
    ind += 1
    if ind >= len(t):
      cnt += 1
      break 
    while l[lind][t[ind]] != -1:   
      lind = l[lind][t[ind]]
      ind += 1
      if ind >= len(t):
        break          
    cnt += 1

###    
if cnt != -1:      
  print(cnt*len(s)-(len(s)-(lind+1)))
else:
  print(cnt)
n = input()
    if "1" in n and "9" in n and "7" in n and "4" in n:
        print("YES")
    else:
        print("NO")

### FIXED CODE ###

n = input()
if "1" in n and "9" in n and "7" in n and "4" in n:
	print("YES")
else:
	print("NO")
import numpy as np
INF=10**18
N,M,L=map(int,input().split())
d=np.zeros((N,N))
d[:,:]=INF
for i in range(N):
    d[i,i]=0
for m in range(M):
    A,B,C=map(int,input().split())
    d[A-1,B-1]=C
    d[B-1,A-1]=C

for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i,j]=min(d[i,j],d[i,k]+d[k,j])
for i in range(N):
        for j in range(N):
            if d[i,j]<=L:
                d[i,j]=1
for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i,j]=min(d[i,j],d[i,k]+d[k,j])
ans=[]
Q=int(input())
for i in range(Q):
    s,t=map(int,input().split())
    dis=d[s-1,t-1]
    if dis==INF:
        ans.append(-1)
    else:
        ans.append(dis-1)

for a in ans:
    print(int(a))


### FIXED CODE ###

INF=10**15
N,M,L=map(int,input().split())
d=[[INF for i in range(N)] for j in range(N)]
d1=[[INF for i in range(N)] for j in range(N)]
for i in range(N):
    d[i][i]=0
for m in range(M):
    A,B,C=map(int,input().split())
    d[A-1][B-1]=C
    d[B-1][A-1]=C

for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
for i in range(N):
        for j in range(N):
            if i!=j and d[i][j]<=L:
                d1[i][j]=1
                d1[j][i]=1
for k in range(N):
    for i in range(N):
        for j in range(N):
            d1[i][j]=min(d1[i][j],d1[i][k]+d1[k][j])

Q=int(input())
for _ in range(Q):
    s,t=map(int,input().split())
    dis=d1[s-1][t-1]
    if dis==INF:
        print(-1)
    else:
        print(dis-1)
import fractions
from functools import reduce
MOD = 10**9 + 7

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

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

LCM = lcm(*A)
ans = 0
for a in A:
    ans += LCM/a
    ans %= MOD

print(int(ans))

### FIXED CODE ###

import fractions

N = int(input())
A = list(map(int,input().split()))
MOD = 10** 9 + 7
lcm = 1
for a in A:
    lcm = a // fractions.gcd(a,lcm) * lcm

print(sum(lcm//a for a in A)%MOD)
import collections


S = list(input())

c = collections.Counter(S)

if max(c.values) >= 2:
  print("Bad")
else:
  print("Good")


### FIXED CODE ###

import collections


S = list(input())

answer = 'Good'
for i in range(1, len(S)):
  if S[i] == S[i-1]:
    answer = 'Bad'

print(answer)
import math
import string


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//math.factorial(n-r)*math.factorial(r)


h, w = map(int, input().split())
a = [None]*h
for i in range(h):
    a[i] = input()
# print(a)

dx = [1, 1, 0-1, -1, -1, 0, 1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            print('#', end="")
        else:
            count = 0
            for k in range(8):
                x = i+dx[k]  # (i,j)の位置からk移動させたときのx座標
                y = j+dy[k]  # (i,j)の位置からk移動させたときのy座標
                if (x <= 0 and x < h)and(y <= 0 and y < w)and(a[x][y] == '#'):
                    # x,yが盤面の中に入っていて'#'のとき
                    continue
                if a[x][y] == '#':
                    count += 1
            print(count, end="")
    print('\n', end="")


### FIXED CODE ###

import math
import string


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//math.factorial(n-r)*math.factorial(r)


h, w = map(int, input().split())
a = [None]*h
for i in range(h):
    a[i] = input()
# print(a)

dx = [-1, -1, -1, 0, 1, 1, 1, 0]
dy = [-1, 0, 1, 1, 1, 0, -1, -1]

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            print('#', end="")
        else:
            count = 0
            for k in range(8):
                x = i+dx[k]  # (i,j)の位置からk移動させたときのx座標
                y = j+dy[k]  # (i,j)の位置からk移動させたときのy座標
                if x < 0 or x >= h or y < 0 or y >= w:
                    # x,yが盤面の中に入っていて'#'のとき
                    continue

                if a[x][y] == '#':
                    count += 1

            print(count, end="")

    print('\n', end="")
n = int(input())
a = list(map(int, input().split()))

cnt = 0
pre = 0
for i in range(n):
    if prev == a[i]:
        cnt += 1
        prev = 0
    else:
        prev = a[i]

print(cnt)

### FIXED CODE ###

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

cnt = 0
prev = 0
for i in range(n):
    if prev == a[i]:
        cnt += 1
        prev = 0
    else:
        prev = a[i]

print(cnt)
#! /usr/bin/env python3
# -*- coding: utf-8 -*-
N = int(input())
Hlist = [int(x) for x in input().split()]

count = 0
for i in range (N):
    if Hlist[i] >= max(Hlist[0:i+1]):
        count+= 1

print(count)


### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-
A, B = [int(x) for x in input().split()]
if A>B:
  ans = A + A-1
elif B>A:
  ans = B+B-1
else:
  ans = 2*A

print(ans)
n,k=map(int,input().split())

if(k=1):
    print(0)
else:
    print(n-k)

### FIXED CODE ###

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

if(k==1):
    print(0)
else:
    print(n-k)
x=input()

print(x**3)


### FIXED CODE ###

x=input()
y=int(x)
print(y**3)
s = input()
k = int(input())
onesum = 0
while s[0] == "1":
    s = s[1:]
    onesum += 1
if k <= onesum:
    print(1)
else:
    print(s[0])


### FIXED CODE ###

s = input()
k = int(input())
onesum = 0
while s[0] == "1":
    onesum += 1
    if len(s) == 1:
        break
    s = s[1:]
if k <= onesum:
    print(1)
else:
    print(s[0])
print(pow(int(x),3))

### FIXED CODE ###

x = int(input())
print(x**3)
N = int(input())
L = list(map(int, input().split()))
print("Yes" if pop(index(max(L))) < sum(L) else "No")

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
print("Yes" if max(L) < sum(L)-max(L) else "No")
n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]

class UnionFind(list) :
    def __init__(self, n) :
        super().__init__(range(n))
        self.dic = {i:1 for i in range(n)}
        self.fubensa = n*(n-1)//2

    def find(self, i) :
        if self[i] == i : return i
        self[i] = self.find(self[i])
        return self[i]

    def union(self, x, y) :
        x = self.find(x)
        y = self.find(y)
        self[y] = x
        if x != y :
            self.fubensa -= self.dic[x]*self.dic[y]
            self.dic[x] += self.dic[y]
            del self.dic[y]

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

uf = UnionFind(n)
ans = []
for a, b in reversed(ab) :
    ans.append(uf.fubensa)
    uf.union(a-1, b-1)
    
for a in reversed(ans) :
    print(a)

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10**5)

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

class UnionFind(list) :
    def __init__(self, n) :
        super().__init__(range(n))
        self.dic = {i:1 for i in range(n)}
        self.fubensa = n*(n-1)//2

    def find(self, i) :
        if self[i] == i : return i
        self[i] = self.find(self[i])
        return self[i]

    def union(self, x, y) :
        x = self.find(x)
        y = self.find(y)
        self[y] = x
        if x != y :
            self.fubensa -= self.dic[x]*self.dic[y]
            self.dic[x] += self.dic[y]
            del self.dic[y]

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

uf = UnionFind(n)
ans = []
for a, b in reversed(ab) :
    ans.append(uf.fubensa)
    uf.union(a-1, b-1)
    
for a in reversed(ans) :
    print(a)
n = int(input())
s = input()
M = 10**9 + 7

dp = [[None] * n for _ in range(n)]
def dfs(zk, i=0):
    if dp[zk][i] is not None:
        return dp[zk][i]

    if i == n - 1:
        dp[zk][i] = 1
        return 1

    zj = n - i - zk - 1
    cnt = 0

    if s[i] == "<":
        for v in range(zk):
            cnt += dfs(v, i + 1)
    else:
        for v in range(zj):
            cnt += dfs(zk + v, i + 1)
    dp[zk][i] = cnt
    return cnt

def mod(v):
    if v >= M:
        return v % M
    return v

def cumsum(array):
    array = array.copy()
    for i in range(len(array) - 1):
        array[i + 1] = mod(array[i + 1] + array[i])
    return array + [0]

for i in reversed(range(n)):
    for zk in range(n):
        if i == n - 1:
            dp[i][zk] = 1
            continue

        zj = n - i - zk - 1
        cnt = 0

        if s[i] == "<":
            for v in range(zk):
                # cnt = mod(cnt + dp[i + 1][v])
                cnt = cs[v]
        else:
            for v in range(zj):
                # cnt = mod(cnt + dp[i + 1][zk + v])
                cnt = cs[zk + zj - 1] - cs[zk - 1]
        dp[i][zk] = cnt
    cs = cumsum(dp[i])

# for i in range(n):
#     print(dfs(i))
# print(sum(dfs(i) for i in range(n - 1)) % M)
print(sum(dp[0]) % M)


### FIXED CODE ###

n = int(input())
s = input()
M = 10**9 + 7

def mod(v):
    if v >= M:
        return v % M
    return v


dp = [[1] * n + [0] for _ in range(2)]
s = [v == "<" for v in s]
for i in reversed(range(n - 1)):
    for j in range(n - 1):
        dp[1][j + 1] = dp[1][j + 1] + dp[1][j]
        dp[0][j] = dp[1][j]
    dp[0][-2] = dp[1][-2]

    for zk in range(n - i):
        cnt = 0

        if s[i]:
            cnt = dp[0][zk - 1]
        else:
            zj = n - i - zk - 1
            cnt = dp[0][zk + zj - 1] - dp[0][zk - 1]
        dp[1][zk] = mod(cnt)

print(sum(dp[1]) % M)
#他人のコピー
n=input()
n = int(input())
candy = (1 / 2) * n * (n + 1)
print(int(candy))
#他人のコピー




### FIXED CODE ###





#他人のコピー
n=input()
candy = (1 / 2) * int(n) * (int(n) + 1)
print(int(candy))
#他人のコピー
a,b=input().split()
a=str(int(a)-1)
def f(x):
  c=int(x[0])
  d=int(x[1])
  m=(c-1)*100+d*10
  e=int(x[2])
  g=int(x[3])*10+int(x[4])
  if g<d*10+c:
    m+=e
  else:
    m=m+e+1
  return m
print(f(b)-f(a))
  

### FIXED CODE ###

a,b=input().split()
if a!='10000':
  a=str(int(a)-1)
def f(x):
  c=int(x[0])
  d=int(x[1])
  m=(c-1)*100+d*10
  e=int(x[2])
  g=int(x[3])*10+int(x[4])
  if g<d*10+c:
    m+=e
  else:
    m=m+e+1
  return m
print(f(b)-f(a))
a, b, c = int(input().split())
x = c - (a - b)
print(x)

### FIXED CODE ###

a, b, c = input().split()
x = int(a) - int(b)
if int(c) <= x:
	print(0)
else:
	y = int(c) - x
	print(y)
n, M = map(int, input().split())
A = list(map(int, input().split()))
dp = [-1 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
if 1 in A:
    dp[1] = 0

step = 2
while True:
    if step == n+1:
        break
    
    if step in A:
        dp[step] = 0
    else:
        dp[step] = dp[step-1] + dp[step-2]
        
    step += 1
    
print(dp[n])

### FIXED CODE ###

mod = 1000000007
def add(a, b):
    return (a + b) % mod

N, M = map(int, input().split())
Broken_set = set([])
for _ in range(M):
    Broken_set.add(int(input()))

if 1 in Broken_set:    
    dp = [0]*(N+1)
    dp[0] = 1
    dp[1] = 0
    for i in range(2, N+1):
        if i in Broken_set:
            dp[i] = 0
        else:
            dp[i] = add(dp[i-1], dp[i-2])

else:
    dp = [0]*(N+1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, N+1):
        if i in Broken_set:
            dp[i] = 0
        else:
            dp[i] = add(dp[i-1], dp[i-2])

print(dp[N])
a = input()
s = input()
if a < 3200:
  print("red")
else:
  print(s)

### FIXED CODE ###

a = int(input())
s = input()

if a < 3200:
  print("red")
else:
  print(s)
N, M = map(int,input().split())
path = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a].append(b)

dp = [-1] * N

def chdp(x):
    if dp[x] != -1:
        return(dp[x]) 
    dp[x] = 0
    for t in path[x]:
        dp[x] = max(dp[x], chdp(t)+1)
    return(dp[x])

for i in range(N):
    chdp(i)

print(max(dp))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
N, M = map(int,input().split())
path = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a].append(b)

dp = [-1] * N

def chdp(x):
    if dp[x] != -1:
        return(dp[x]) 
    dp[x] = 0
    for t in path[x]:
        dp[x] = max(dp[x], chdp(t)+1)
    return(dp[x])

for i in range(N):
    chdp(i)

print(max(dp))
a=int(inputu())
b=list(map(int,input().split()))
out=0
for i in range(a):
  for j in range(i-1):
    out=out+b[i]*b[j]
    
print(out)

### FIXED CODE ###

a=int(input())
b=list(map(int,input().split()))
out=0
for i in range(a):

  for j in range(i+1,a):

    out=out+b[i]*b[j]
    
print(out)
while True:
    n,m=input(),input()
    if n==m==0:break
    S,L=set(),[]
    for i in range(m):
        a,b=map(int,raw_input().split())
        if a==1:
            S.add(b)
        elif b==1:
            S.add(a)
        else:
            L.append((a,b))
    for i in S:
        for s in L:
            if i in s:
                S=S.union(s)
    print len(S)

### FIXED CODE ###

while True:
    n=raw_input()
    if n in "0":break
    try:
        m=input()
    except SyntaxError:
        break
    S,L=set(),[]
    for i in range(m):
        a,b=map(int,raw_input().split())
        if a==1:
            S.add(b)
        elif b==1:
            S.add(a)
        else:
            L.append((a,b))
    for i in S:
        for s in L:
            if i in s:
                S=S.union(s)
    print len(S)
def input_from_console():
    n = int(input().strip())
    h_list = list(map(int, input().split()))
    return n, h_list


def solve(n, h_list):
    import sys
    sys.setrecursionlimit(100001)

    dp = [-1] * (n + 2)
    dp[0] = 0
    dp[1] = abs(h_list[1] - h_list[0])

    def recursive_dp_sover(i):
        if dp[i] != -1:
            return dp[i]
        dp[i] = min(
            recursive_dp_sover(i - 1) + abs(h_list[i] - h_list[i - 1]),
            recursive_dp_sover(i - 2) + abs(h_list[i] - h_list[i - 2])
        )
        return dp[i]

    return recursive_dp_sover(n - 1)


def main():
    n, h_list = input_from_console()
    print(solve(n, h_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

def input_from_console():
    n = int(input().strip())
    h_list = list(map(int, input().split()))
    return n, h_list


def solve(n, h_list):
    dp = [-1] * (n+2)
    dp[0] = 0
    dp[1] = abs(h_list[1]- h_list[0])
    def dp_solve(i):
        if dp[i] != -1:
            return dp[i]
        dp[i] = min(
            dp_solve(i-1) + abs(h_list[i] - h_list[i-1]),
            dp_solve(i-2) + abs(h_list[i] - h_list[i-2]),
        )
        return dp[i]
    return dp_solve(n-1)


def main():
    n, h_list = input_from_console()
    print(solve(n, h_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()
import math
def Fib(n):
  Fib=1/math.sqrt(5)*(((1+math.sqrt(5))/2)**(n+1)-((1-math.sqrt(5))/2)**(n+1))
  return int(Fib)
N,M=map(int,input().split())
if M==0:
  print(Fib(N))
  exit()
A=[]
for i in range(M):
  A.append(int(input()))
B=[0]*M
a=0
for i in range(M):
  B[i]=A[i]-1-a
  a=A[i]+1
B.append(N-a)
a=A[0]
for i in range(1,M):
  if A[i]==a+1:
    print(0)
    exit()
  else:
    a=A[i]
ans=1
for i in range(M+1):
  ans*=Fib(B[i])
print(ans%1000000007)

### FIXED CODE ###

N,M=map(int,input().split())
A=[-1]+[int(input()) for i in range(M)]+[N+1]
res=1
for i in range(1,len(A)):
  steps=A[i]-A[i-1]-2
  if steps<0:
    patern_nmu=0
  else:
    p,q=1,0
    for j in range(steps):
      p,q=p+q,p
    patern_nmu=p
  res*=patern_nmu
  res%=1000000007
print(res)
grid=[]
for i in range(3):
    grid.append(list(map(int,input().split())))
S=''
for i in range(3):
    S=S+grid[i][i]
print(S)


### FIXED CODE ###

grid=[]
for i in range(3):
    grid.append(input())
S=''
for i in range(3):
    S=S+grid[i][i]
print(S)