Harryxun/stf_run huggingface dataset:
#https://atcoder.jp/contests/abc076/tasks/abc076_c

s=input()
t=input()

for i in range(len(s)-len(t)+1):
    flag=0
    n= len(s)-i-len(t)
    temp=s[n:n+len(t)]
    for j in range(len(t)):
        if temp[j]!=t[j] and temp[j]!="?":
            flag=1
    if flag==0:
        break

if flag==1:
    print("UNRESTORABLE")
    exit()
temp=s[:n]+t+s[n+len(t):]
print(temp.replace("?","a"))


### FIXED CODE ###

s=list(input())
t=input()

for i in range(len(s)-len(t)+1):
    flag=0
    i=len(s)-len(t)-i
    #print(i)
    for j in range(len(t)):
        if t[j]!=s[i+j] and s[i+j]!="?":
            flag=1
            #print(j,t[j],s[i+j])
    if flag==0:
        for j in range(len(t)):
            s[i+j]=t[j]
        result=""
        for item in s:
            result=result+str(item)
        result=result.replace("?","a")
        print(result)
        exit()
print("UNRESTORABLE")
# coding: utf-8

    count = 1

### FIXED CODE ###

# coding: utf-8
# Here your code !
count = 1

while 1:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    data =[]
    dp = [[[-1,0]for i in range(W+1)]for i in range(N+1)]
    for i in range(N):
        data.append(input().split(","))

    for i in range(W+1):
        dp[N][i][0] = 0
    for i in reversed(range(N)):
        for capa in range(W+1):
            if int(data[i][1]) > capa:
                dp[i][capa][0] = dp[i+1][capa][0]
                dp[i][capa][1] = dp[i+1][capa][1]
            else:
                dp[i][capa][0] = max(int(data[i][0])+dp[i+1][capa-int(data[i][1])][0],dp[i+1][capa][0])
                dp[i][capa][1] = dp[i+1][capa][1]
                if dp[i][capa][0] != dp[i+1][capa][0]:
                    dp[i][capa][1] = int(data[i][1])+dp[i+1][capa-int(data[i][1])][1]
    print("Case " + str(count) +":")
    print(max(max(dp))[0])
    print(max(max(dp))[1])
 
    count += 1
import numpy as np
N, M, C = map(int, input().split()) 
B = np.array(list(map(int, input().split())))
A = np.array([list(map(int,list(input()))) for i in range(N)])

ans = 0
for i in range(N):
    val = np.sum(A[i, :] * B) + C
    if val > 0:
        ans += 1
print(ans)


### FIXED CODE ###

import numpy as np
N, M, C = map(int, input().split()) 
B = np.array(list(map(int, input().split())))
A = np.array([list(map(int,list(input().split()))) for i in range(N)])
 
ans = 0
for i in range(N):
    val = np.sum(A[i, :] * B) + C
    if val > 0:
        ans += 1
print(ans)
N = int(input())
arr = [int(n) for n in input().split()]

swap_cnt = 0
for i in range(0, N):
    minj = i
    for j in range(i + 1, N - 1):
        if arr[j] < arr[minj]
            minj = j
        arr[i], arr[minj] = arr[minj], arr[i]
        swap_cnt += 1 if i != minj else 0

print(' '.join(map(str, arr)))
print(swap_cnt)



### FIXED CODE ###

N = int(input())
arr = [int(n) for n in input().split()]

swap_cnt = 0
for i in range(0, N):
    minj = i
    for j in range(i, N):
        if arr[j] < arr[minj]:
            minj = j
    if (i != minj):
        arr[i], arr[minj] = arr[minj], arr[i]
        swap_cnt += 1

print(' '.join(map(str, arr)))
print(swap_cnt)
import sys

sys.setrecursionlimit(10000)

N, M = map(int, input().split())
A = []
ANS = []
for i in range(N + 10):
    ANS.append(None)

for _ in range(M):
    a = int(input())
    A.append(a)
    ANS[a] = 0


def f(x):
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    if ANS[x + 1] is None:
        x1 = f(x + 1)
        ANS[x + 1] = x1
    else:
        x1 = ANS[x + 1]

    if ANS[x + 2] is None:
        x2 = f(x + 2)
        ANS[x + 2] = x1
    else:
        x2 = ANS[x + 2]

    ans = x1 + x2
    # ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
A = []
ANS = []
for i in range(N + 10):
    ANS.append(None)

for _ in range(M):
    a = int(input())
    A.append(a)
    ANS[a] = 0


def f(x):
    # print(ANS)
    # if x in A:
    #     print('::::', x)
    #     d[x] = 0
    #     return 0
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    # if d.get(x + 1):
    #     x1 = d.get(x + 1)
    # else:
    #     x1 = f(x + 1)
    #     d[x + 1] = x1
    #
    # if d.get(x + 2):
    #     x2 = d.get(x + 2)
    # else:
    #     x2 = f(x + 2)
    #     d[x + 2] = x2

    # ans = x1 + x2
    ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)
import numpy as np
N = int(input())
data_xy = []
for i in range(N):
    A = int(input())
    xy = []
    for i in range(A):
        [x,y] = list(map(int,input().split()))
        xy.append([x-1, y])
    data_xy.append(xy)
ans = 0
for i in range(2**N):
    p_list = [0]*N
    for j in range(N):
        if (i>>j) & 1 == 1:
            p_list[j] = 1
    flag = True
    for j in range(N):
        if p_list[j] == 1:
            for k in range(len(data_xy[j])):
                x = data_xy[j][k][0]
                y = data_xy[j][k][1]
                if p_list[x] != y:
                    flag = False
    if flag == True:
        ans = max(sum(p_list),ans)
print(ans)

### FIXED CODE ###

A = list(map(int,input().split()))
if sum(A) >= 22:
    print('bust')
else:
    print('win')
a, b = map(int, input().split())
if (a*b) % 2 == 0:
  print('Even')
else:
  print(Odd)

### FIXED CODE ###

a, b = map(int, input().split())
if int((a*b)%2) == 0:
  print('Even')
else:
  print('Odd')
prices = list(map(int,input().split()))
price.sort()
print(price[0]+price[1])

### FIXED CODE ###

prices = list(map(int,input().split()))
prices.sort()
print(prices[0]+prices[1])
n, x = map(int, input().split())
def doit(l, x):
    layers = 2 ** (l + 1) - 3
    if x >= layers + 2:
        return doit(l - 1, x - layers - 2) + 2 ** l
    elif x >= 1:
        return doit(l - 1, x - 1)
    else:
        return 0
print(doit(n, x))

### FIXED CODE ###

n, x = map(int, input().split())
def layers(l):
    return 2 ** (l + 2) - 3
def patties(l):
    return 2 ** (l + 1) - 1
def doit(l, x):
    if x >= layers(l):
        return patties(l)
    y = layers(l - 1)
    ret = 0
    if x >= 1:
        ret += doit(l - 1, x - 1)
    if x >= y + 2:
        ret += 1
        ret += doit(l - 1, x - y - 2)
    return ret
print(doit(n, x))
N=int(input())
a = list(map(int, input().split()))
cnt=[0]*10000
for t in a:
    cnt[t] += 1
    cnt[t-1] += 1
    cnt[t+1] += 1
print(max(cnt))

### FIXED CODE ###

N=int(input())
a = list(map(int, input().split()))
cnt=[0]*100009
for t in a:
    cnt[t] += 1
    cnt[t-1] += 1
    cnt[t+1] += 1
print(max(cnt))
n,m = map(int,input().split())
t=0
if n==2: t=10
if n==3: t=100
t=str(t)
tt = list()
for i in range(n):
    tt.append(int(t[i]))
f=[0]*len(tt)
for i in range(m):
    ans = -1
    s,c = map(int,input().split())
    s-=1
    if c <  tt[s]: break
    if c >  tt[s]:
        if f[s]==0:
            f[s],tt[s]=1,c
        elif f[s]==1:
            break
    if n==1: ans=tt[0]
    if n==2: ans=tt[0]*10+tt[1]
    if n==3: ans=tt[0]*100+tt[1]*10+tt[2]

print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
t='000'
if n==2: t='010'
if n==3: t='100'
f=[0]*len(t)
t=[int(t[0]),int(t[1]),int(t[2])]
ans = t[0]*100+t[1]*10+t[2] 
for i in range(m):
    ans = -1
    s,c = map(int,input().split())
    s=s-(n-2)
    if c <  t[s]: break
    if c >  t[s]:
        if f[s]==0:
            f[s],t[s]=1,c
        elif f[s]==1:
            break
    ans=t[0]*100+t[1]*10+t[2]
print(ans)
#!/usr/bin/env python3
import sys


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):
    edges = [[] for _ in range(N+1)]
    for aa, bb, cc in zip(a, b, c):
        edges[aa].append((bb, cc))
        edges[bb].append((aa, cc))
    costs = [None] * (N + 1)
    def dfs(n, c):
        if costs[n] is not None:
            return
        costs[n] = c
        for nn, cc in edges[n]:
            dfs(nn, c+cc)
    dfs(K, 0)
    for xx, yy in zip(x, y):
        print(costs[xx]+costs[yy])
    return

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    c = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (Q)  # type: "List[int]"
    y = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, a, b, c, Q, K, x, y)

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(200000)

def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):
    edges = [[] for _ in range(N+1)]
    for aa, bb, cc in zip(a, b, c):
        edges[aa].append((bb, cc))
        edges[bb].append((aa, cc))
    costs = [None] * (N + 1)
    def dfs(n, cost):
        if costs[n] is not None:
            return
        costs[n] = cost
        for nn, cc in edges[n]:
            dfs(nn, cost+cc)
    dfs(K, 0)
    for xx, yy in zip(x, y):
        print(costs[xx]+costs[yy])
    return

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    c = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (Q)  # type: "List[int]"
    y = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, a, b, c, Q, K, x, y)

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()
import numpy as np
import math

N = int(input())
A = np.array([int(i) for i in (input()).split(" ")])
minA = np.min(A)

if(minA == np.max(A)):
    print(minA)
else:
    check = np.unique(minA // np.arange(1,minA))
    #check = minA // np.arange(1,minA)
    for i in check[::-1]:
        #全てのAに対してiで割り切れるか＝最大公約数
        #iで割り切れた数＝len(A)-1なら，残りの数にiをかけて最大公約数に出来る．
        num = np.sum((A % i>0))
        if(num < 2):
            j = A[np.where(A % i>0)][0]
            #print(i,j,i*j//math.gcd(i,j))
            if(i*j//math.gcd(i,j) < 10**9):
                print(i)
                break

### FIXED CODE ###

import numpy as np
import fractions

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

maxA = np.max(A)


if(maxA == np.min(A)):
    print(maxA)
elif(N==2):
    print(maxA)
else:
    R=np.zeros((N))
    L=np.zeros((N))
    M=np.zeros((N))

    L[0] = 0
    R[N-1] = 0
    for i in range(1,N):
        #0~i-1番目までの最大公約数
        L[i] = fractions.gcd(A[i-1],L[i-1])
        #i~N番
        R[N-1-i] = fractions.gcd(A[N-1-i+1],R[N-1-i+1])

    M[0] = R[0]
    M[-1] = L[-1]
    for i in range(1,N-1):
        M[i] = fractions.gcd(L[i],R[i])

    print("{}".format(int(np.max(M))))
n = int(input())
dic_items = {-1:'z',0:'a',1:'b',2:'c',3:'d',4:'e',5:'f',6:'g',7:'h',8:'i',9:'j',10:'k'\
             ,11:'l',12:'m',13:'n',14:'o',15:'p',16:'q',17:'r',18:'s'
             ,19:'t',20:'u',21:'v',22:'w',23:'x',24:'y',25:'z'}
ans = []
while n != 0:
  ans.append(n%26)
  n = n//26
#print(ans)
for i in range(len(ans)):
  if ans[i] == 0:
    j = i+1
    if j < len(ans):
      ans[j] -= 1
      if j == len(ans)-1:
        ans[i] = 26
    else:
      ans.pop()
for i in range(len(ans)):
  print(dic_items[ans[len(ans)-1-i]-1],end='')

### FIXED CODE ###

n = int(input())
dic_items = {0:'a',1:'b',2:'c',3:'d',4:'e',5:'f',6:'g',7:'h',8:'i',9:'j',10:'k'\
             ,11:'l',12:'m',13:'n',14:'o',15:'p',16:'q',17:'r',18:'s'
             ,19:'t',20:'u',21:'v',22:'w',23:'x',24:'y',25:'z'}
ans = []
while n != 0:
  n -= 1
  ans.append(n%26)
  n = n//26
for i in range(len(ans)):
  print(dic_items[ans[len(ans)-1-i]],end='')
#!/usr/bin/env python
# -*- coding:utf-8 -*-
import sys
import io
import re
import math

while True:
    n = int(raw_input())
    l = map(float, raw_input().split())
    if n==0:
    break
# hyojunhensa**2 = sum(tokuten-heikinten)**2)/ninzu
    avg=sum(l)/len(l)
    print avg
    naka=0
    for i in l:
        print naka
        naka+=(i-avg)**2
    hyo2 = naka/n
    print (hyo2)**0.5

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-
import sys
import io
import re
import math

while True:
#    i = 0
    n = int(raw_input())
    if n==0: break
    l = map(float, raw_input().split())
# hyojunhensa**2 = sum(tokuten-heikinten)**2)/ninzu
    avg=sum(l)/len(l)
    naka=0
    for i in l:
        naka+=(i-avg)**2
    hyo2 = naka/n
    print (hyo2)**0.5
a=input().split()
a=list(a)
b=input().split()
b=list()
n=len(a)
N=1
for i in range(n):
  if(a[i]!=b[-(i+1)]):
    N=0
if(N==1):
  print("YES")
else:
  print("NO")
  

### FIXED CODE ###

a=input()
a=list(a)
b=input()
b=list(b)
n=len(a)
j=1
for i in range(n):
  if(a[i]!=b[-(i+1)]):
    j=0
if(j==1):
  print("YES")
else:
  print("NO")
print('TBD'if int(input().split()[1])>4 else 'Heisei')

### FIXED CODE ###

print('TBD'if int(input().split('/')[1])>4 else 'Heisei')
from sys import stdin
 
input_num = stdin.readline().strip().split(" ")

X = int(input_num[0])
N = int(input_num[1])
num_list = [int(x) for x in stdin.readline().strip().split(" ")]

minv = 10000
num = 0

if N == 0:
  print(X)
else:
  for i in range(len(num_list)):
    if minv > abs(X - num_list[i]):
      minv = abs(X - num_list[i])
      num = i
  print(num_list[num])

### FIXED CODE ###

from sys import stdin
 
input_num = stdin.readline().strip().split(" ")

X = int(input_num[0])
N = int(input_num[1])
num_list = []
if N != 0:
    num_list = [int(x) for x in stdin.readline().strip().split(" ")]


dec_num = X
inc_num = X
if N == 0:
    print(X)
elif X not in num_list:
    print(X)
else:
    while True:
        dec_num += -1
        inc_num += 1
        if dec_num not in num_list:
            print(dec_num)
            break
        if inc_num not in num_list:
            print(inc_num)
            break
a = int(input()) 
b = [int(input()) for i in range(a)] 
 
m=max(b)
for i in range(a):
  if m>b[i]:
    print(m)
  else:
    d=b[i]
  	b.pop(i)
  	print(max(b))
  	b.insert(i,d)

### FIXED CODE ###

a = int(input()) 
b = [int(input()) for i in range(a)] 
 
m=max(b)
sorted(b)
s=sorted(b)[-2]
for i in range(a):
  if m>b[i]:
    print(m)
  else:
    print(s)
def solve( ):
    for a in ["+", "-"]:
        for b in ["+", "-"]:
            for c in ["+", "-"]:
                if eval('S[0] + a + S[1] +b + S[2] + c + S[3]') == 7:
                    return 'S[0] + a + S[1] +b + S[2] + c + S[3]=7'
                    break
 
S = input()
print(solve(S))

### FIXED CODE ###

S = input()


for i in range(8):
    f = ""
    B = ["-"]*3

    for j in range(3):
        if ((i>>j)&1):
            B[j] = "+"
    for a,b in zip(S, B+[""]):
        f += (a+b)
    
        
    if eval(f) == 7:
        print(f+"=7")
        break
N,T = map(int, input().split())

ans = []

for i in range(N):
    c,t = map(int, input().split())
    if T > t:
        ans.appned(c)
    

if len(ans) == 0:
    print("TLE")
else:
    print(min(ans))        
    


### FIXED CODE ###

N, T = map(int,input().split())
c = []
t = []

for i in range(N):
  c1, t1 = map(int,input().split())
  c.append(c1)
  t.append(t1)
  
ans = []

for i in range(N):
  if t[i] <= T:
    ans.append(c[i])

if len(ans) == 0:
  print("TLE")
else:
  print(min(ans))
N = int(input())

number = list()

for i in range( N - 1 ):
  number.append(int(input()))

for i in range( N - 1 ):
  del number[i]
  print( max( number ) )
  

### FIXED CODE ###

N = int(input())
li = [int(input()) for _ in range(N)]

lis = sorted(li)
for i in range(N):
  if lis[-1] == li[i]:
    print(lis[-2])
  else: print(lis[-1])
from collections import defaultdict, deque
def sub():

    N, M = [int(e) for e in input().split()]
    es = [[int(x) for x in input().split()] for _ in range(N)]

    outs = defaultdict(list)
    ins = defaultdict(int)
    for v1, v2 in es:
        outs[v1].append(v2)
        ins[v2] += 1

    q = deque(v1 for v1 in range(1, N+1) if ins[v1] == 0)
    dp_table = [0 for i in range(N+1)]
    res = []
    while q:
        v1 = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append(v2)
                dp_table[v2] = max(dp_table[v2], dp_table[v1] + 1)
    print(max(dp_table))

if __name__ == "__main__":
    sub()


### FIXED CODE ###

from collections import defaultdict, deque
def sub():

    N, M = [int(e) for e in input().split()]
    es = [[int(x) for x in input().split()] for _ in range(M)]

    outs = defaultdict(list)
    ins = defaultdict(int)
    for v1, v2 in es:
        outs[v1].append(v2)
        ins[v2] += 1

    q = deque(v1 for v1 in range(1, N+1) if ins[v1] == 0)
    dp_table = [0 for i in range(N+1)]
    res = []
    while q:
        v1 = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append(v2)
                dp_table[v2] = max(dp_table[v2], dp_table[v1] + 1)
    print(max(dp_table))

if __name__ == "__main__":
    sub()
#!/usr/bin/env python3
from itertools import accumulate

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = list(accumulate(a))
    
    if a[0] != 0:
        ans = 0
        diff = 0
        for i in range(1,n):
            p = a[i] + diff
            q = a[i-1] + diff
            if p * q >= 0:
                tmp = -q//abs(q) - p
                ans += abs(tmp)
                diff += tmp
        print(ans)
    else:
        ans = 10**18
        for d in [-1,1]:
            ans2 = 1
            for i in range(1,n):
                p = a[i] + d
                q = a[i-1] + d
                if p * q >= 0:
                    tmp = -q//abs(q) - p
                    ans2 += abs(tmp)
                    diff += tmp
            ans = min(ans, ans2)
        print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
from itertools import accumulate

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

    ans = 10**18

    for j in range(2):# 偶数行が正か奇数行が正
        ans2 = 0
        diff = 0
        for i in range(n):
            p = a[i] + diff
            # print(a[i],diff)
            if (i+j) % 2 == 0 and p <= 0:# 正になる
                ans2 += abs(p)+1
                diff += abs(p)+1
            elif (i+j) % 2 == 1 and p >= 0:# 負になる
                ans2 += abs(p)+1
                diff -= abs(p)+1

        ans = min(ans, ans2)
    print(ans)

if __name__ == "__main__":
    main()
#!/usr/bin/env python3

from itertools import product

def main():
    a, b, c, d = map(int, input())
    for x, y, z in product(("+", "-"), repeat=3):
        eq = f"a{x}b{y}c{z}d"
        val = eval(eq)
        if val == 7:
            print(f"{a}{x}{b}{y}{c}{z}{d}=7")
            return

main()


### FIXED CODE ###

#!/usr/bin/env python3

from itertools import product

def main():
    a, b, c, d = map(int, input())
    for x, y, z in product(("+", "-"), repeat=3):
        eq = "a{x}b{y}c{z}d".format(x=x, y=y, z=z)
        val = eval(eq)
        if val == 7:
            print("{a}{x}{b}{y}{c}{z}{d}=7".format(x=x, y=y, z=z, a=a, b=b, c=c, d=d))
            return

main()
DVSR = 1000000007
    def POW(x, y): return pow(x, y, DVSR)
    def INV(x, d=DVSR): return pow(x, d - 2, d)
    def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
    def LI(): return [int(x) for x in input().split()]
    def LF(): return [float(x) for x in input().split()]
    def LS(): return input().split()
    def II(): return int(input())
    
    n = II()
    n = str(n)
    if '7' in n:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n = input()
if '7' in n:
    print('Yes')
else:
    print('No')
n, k = map(int, input().split())
h = [int(x) for x in input().split()]
dp = [None] * n
 
INF = float('inf')
 
dp[0] = 0
for x in range(1, n):
  for j in range(min(k, x) + 1):
    dp[x] = min(dp[x], dp[x - j] + abs(h[x] - h[x - j]) 
 
print(dp[n-1])

### FIXED CODE ###

dp = {}

n = int(input())
h = [int(x) for x in input().split()]

dp[0] = 0
dp[1] = abs(h[1] - h[0])

for x in range(2, n):
  dp[x] = min(
    dp[x - 1] + abs(h[x] - h[x - 1]),
    dp[x - 2] + abs(h[x] - h[x - 2])
  )

print(dp[n-1])
import functools
import operator
q=int(input())
for i in range(q):
    x,d,n=map(int,input().split())
    a=range(x,x+d*(n-1)+1,d)
    print(functools.reduce(operator.mul,a)%1000003)

### FIXED CODE ###

q=int(input())
m=10**6+3
f=[1]
for i in range(1,m):
    f.append(f[-1]*i%m)
for i in range(q):
    x,d,n=map(int,input().split())
    if d==0:
        print(pow(x,n,m))
    else:
        t=x*pow(d,m-2,m)%m
        if t==0 or t+n-1>=m:
            print(0)
        else:
            print(f[t+n-1]*pow(f[t-1],m-2,m)*pow(d,n,m)%m)
a = input()
x = [a[i:i+1] for i in range(len(a))]
r = len([s for s in l if s.endswith('x')])
if r >= 8:
	print('NO')
else:
	print('YES')

### FIXED CODE ###

a = input()
x = [a[i:i+1] for i in range(len(a))]
r = len([s for s in x if s.endswith('x')])
if r >= 8:
	print('NO')
else:
	print('YES')
S = input()
List = list(S)
s_l = set(List)
n = 10
res= ""
for i in range(97,113):
  n = s_l.count(chr(i))
  if n == 0:
    res = chr(i)
    break
print(res)

### FIXED CODE ###

S = input()
List = list(S)
s_l = set(List)
n = 10
res= ""
flag = False
for i in range(97,123):
  if not chr(i) in s_l:
    res = chr(i)
    flag = True
    break
if flag:
  print(res)
else:
  print("None")
N, M, K = map(int, input().split())


def power_func(a,n,p):
    bi = str(format(n,"b"))#2進表現に
    res = 1
    for i in range(len(bi)):
        res = (res*res) % p
        if bi[i] == "1":
            res = (res*a) % p
    return res

P = 998244353
inv_t = [0] + [1]
for i in range(2, N+2):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

ans = (M * power_func(M-1, N-1, P))%P
curr = ans
for k in range(K):
    curr = (curr*(N-k-1)*inv_t[k+1]*inv_t[M-1]) % P
    ans += curr
    ans %= P

print(ans)

### FIXED CODE ###

import sys
N, M, K = map(int, input().split())

if M == 1 :
    if K == N-1:
        print(1)
    else:
        print(0)
    sys.exit()

def power_func(a, n, p):
    bi = str(format(n,"b"))#2進表現に
    if a == 0:
        return 0
    res = 1
    for i in range(len(bi)):
        res = (res*res) % p
        if bi[i] == "1":
            res = (res*a) % p
    return res

P = 998244353
inv_t = [0] + [1]
for i in range(2, max(M,K)+2):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

ans = (M * power_func(M-1, N-1, P))%P
curr = ans
for k in range(K):
    curr = (curr*(N-k-1)*inv_t[k+1]*inv_t[M-1]) % P
    ans += curr
    ans %= P

print(ans)