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

import sys
input = sys.stdin.readline


def main():
    X = int(input())

    B = 0
    while True:
        A = (X + B**5)**(1/5)
        if not isinstance(A, complex) and A.is_integer():
            A = int(A)
            break
        B *= -1
        A = (X + B**5)**(1/5)
        if not isinstance(A, complex) and A.is_integer():
            A = int(A)
            break
        B *= -1
        B += 1

    print(f"{A} {B}")


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline


def main():
    X = int(input())

    for A in range(-200, 201):
        for B in range(-200, 201):
            if A ** 5 - B ** 5 == X:
                print(A, B)
                exit()


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

import operator
from functools import reduce


def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(operator.mul, range(n, n-r, -1), 1)
    denom = reduce(operator.mul, range(1, r+1), 1)
    return numer // denom


def step2patterns(num_step):
    pats = 0
    for j in range(0, (num_step//2)+1):
        pats += ncr(num_step-j, j)
    return pats


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1)

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1)

print(num_pattern % 1000000007)
exit(0)


### FIXED CODE ###

def exec_ncr(max_step, record_dict):
    for i in range(2, max_step+1):
        record_dict[i] = record_dict[i-1] + record_dict[i-2]


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1}
exec_ncr(num_stair, d)

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= d[dry_step-1]

# last step
dry_step = num_stair - last_wet

num_pattern *= d[dry_step-1]

print(num_pattern % 1000000007)
exit(0)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
input()
A = list(map(int,input().split()))
if 0 in A:
    print(0)
    quit()
ans = 1
for a in A:
    ans*=a
print(-1 if ans>10**18 else ans)

### FIXED CODE ###

input()
A = list(map(int,input().split()))
if 0 in A:
    print(0)
    quit()
else:
    prod = 1
    for a in A:
        prod*=a
        if prod > 10**18:
            print(-1)
            quit()
    print(prod)
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''

    N, M, K = [int(item) for item in input().split()]
    As = [int(item) for item in input().split()]
    Bs = [int(item) for item in input().split()]

    res = 0
    time = 0

    memo_A = [0]
    for i in range(N):
        memo_A.append(As[i]+memo_A[-1])

    memo_B = [0]
    for i in range(M):
        memo_B.append(Bs[i]+memo_B[-1])

    res = 0
    for i, av in enumerate(memo_A):
        if av > K:
            break
        else:
            j = M
            for bv in memo_B[::-1]:
                if bv + av  <= K:
                    res = max(res, i+j)

                j -= 1
            
    print(res)

if __name__ == "__main__":
    resolve()
            


### FIXED CODE ###

def resolve():
    '''
    code here
    '''

    N, M, K = [int(item) for item in input().split()]
    As = [int(item) for item in input().split()]
    Bs = [int(item) for item in input().split()]

    res = 0
    time = 0

    memo_A = [0]
    for i in range(N):
        memo_A.append(As[i]+memo_A[-1])

    memo_B = [0]
    for i in range(M):
        memo_B.append(Bs[i]+memo_B[-1])

    res = 0
    j = M
    for i, av in enumerate(memo_A):
        if av > K:
            break
        else:
            
            while av + memo_B[j] > K:
                j -= 1
            res = max(res,j+i)

    print(res)

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

n= int(input())
a= list(map(int,input().split()))
ans=1
for i in a:
    ans= ans*i
if ans > 10**18:
    print("-1")
else:
   print(ans)

### FIXED CODE ###

n= int(input())
l =list(map(int,input().split()))
ans= 1

if 0 in l:
    print("0")
else:
    for i in range(n):
        ans*= l[i]
        if ans> 10**18:
            break
    if ans> 10**18:
        print("-1")
    else:
        print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

def input():
  return sys.stdin.readline()

def get_cost(arr, n, k, dp):
  if dp[n] is not None:
    return dp[n]
  elif n-k <= 0:
    dp[n] = abs(arr[n] - arr[0])
    return dp[n]
  elif n == 0:
    dp[0] = 0
    return dp[0]
  elif n == 1:
    dp[1] = abs(arr[1] - arr[0])
    return dp[1]
  else:
    dp[n] = min(((abs(arr[n] - arr[n-i]) + get_cost(arr, n-i, k, dp)) for i in range(1, k+1)))
    return dp[n]

N, K = input().split()
N = int(N)
K = int(K)
arr = [int(num) for num in input().split()]

dp = [None]*N
print(get_cost(arr, N-1, K, dp))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

def get_cost(arr, n, k, dp):
  min_ = -1
  for i in range(2, n):
    dp[i] = min([(abs(arr[s] - arr[i]) + dp[s]) for s in range(max(0, i-k), i)])
  return dp[-1]
    

N, K = input().split()
N = int(N)
K = int(K)
arr = [int(num) for num in input().split()]

dp = [0]*N
dp[1] = abs(arr[1] - arr[0])
print(get_cost(arr, N, K, dp))
### BUGGY CODE ###

# 解説AC
from collections import deque

N = int(input())
edge = [[] for _ in range(N)]
for n in range(N - 1):
    a,b = map(int, input().split())
    edge[a-1].append([b-1, n])
    edge[b-1].append([a-1, n])

def bfs(s:int, g:int):
    """ 始点sから終点gまでのパスを求める """
    path = [0] * N
    visited = [False] * N
    flag = False # 終点到着フラグ
    
    que = deque([s])
    visited[s] = True
    while que:
        v = que.popleft()
        for w, n in edge[v]:
            if visited[w]: continue
            path[w] = path[v] | (1 << n) # パスを記録
            if w == g: # 終点到着
                flag = True
                break
            que.append(w)
        if flag: break
    return path[g]

def main():
    M = int(input())
    path = [0] * M # 各制約で使用するパス
    for i in range(M):
        u,v = map(int, input().split())
        path[i] = bfs(u - 1, v - 1)

    ans = 0
    # 包除原理
    for bit in range(1 << M):
        val = 0
        for i in range(M):
            if (bit >> i) & 1:
                val |= path[i]
        if bin(bit).count("1") % 2 == 0:
            ans += 1 << (N - 1 - bin(val).count("1"))
        else:
            ans -= 1 << (N - 1 - bin(val).count("1"))

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

# 解説AC
from collections import deque

N = int(input())
edge = [[] for _ in range(N)]
for n in range(N - 1):
    a,b = map(int, input().split())
    edge[a-1].append([b-1, n])
    edge[b-1].append([a-1, n])

def bfs(s:int, g:int):
    """ 始点sから終点gまでのパスを求める """
    in_edge = [-1] * N
    par = [-1] * N
    flag = False # 終点到着フラグ
    
    que = deque([s])
    while que:
        v = que.popleft()
        for w, n in edge[v]:
            if w == par[v]: continue
            in_edge[w] = n
            par[w] = v
            if w == g:
                flag = True
                break
            que.append(w)
        if flag: break
    path = 0
    cur = g
    while in_edge[cur] >= 0:
        path |= 1 << in_edge[cur]
        cur = par[cur]
    return path


M = int(input())
path = [0] * M # 各制約で使用するパス
for i in range(M):
    u,v = map(int, input().split())
    path[i] = bfs(u - 1, v - 1)

ans = 0
# 包除原理
for bit in range(1 << M):
    val = 0
    for i in range(M):
        if (bit >> i) & 1:
            val |= path[i]
    if bin(bit).count("1") % 2 == 0:
        ans += 1 << (N - 1 - bin(val).count("1"))
    else:
        ans -= 1 << (N - 1 - bin(val).count("1"))

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

def min_diff(x, base=0):
    n = len(x)
    ok = - 1  # x[ok] - base < x[n - 1] - x[ok]
    ng = n - 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if x[mid] - base < x[n - 1] - x[mid]:
            ok = mid
        else:
            ng = mid
    d_ok = abs((x[ok] - base) - (x[n - 1] - x[ok]))
    d_ng = abs((x[ng] - base) - (x[n - 1] - x[ng]))
    if d_ok < d_ng:
        return (x[ok] - base), (x[n - 1] - x[ok])
    else:
        return (x[ng] - base), (x[n - 1] - x[ng])


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    X = [0 for _ in range(N)]  # cum sum
    X[0] = A[0]
    for i in range(1, N):
        X[i] = X[i - 1] + A[i]
    # split to 2 parts (X_0, ..., X_(i-1)), (X_i, ..., X_(N-1))
    min_d = 10**10
    for i in range(2, N - 1):
        p, q = min_diff(X[:i])
        r, s = min_diff(X[i:], base=X[i - 1])
        d = max([p, q, r, s]) - min([p, q, r, s])
        min_d = min([min_d, d])
    print(min_d)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    X = [0 for _ in range(N + 1)]  # cum sum
    for i in range(N):
        X[i + 1] = X[i] + A[i]
    # split to 2 parts (X_0, ..., X_i), (X_(i+1), ..., X_N)
    ans = 10**10
    left = 0
    right = 2
    for i in range(1, N):
        while left < i:
            d = abs(X[left] - (X[i] - X[left]))
            d_next = abs(X[left + 1] - (X[i] - X[left + 1]))
            if d_next > d:
                break
            left += 1
        while right < N:
            d = abs((X[N] - X[right]) - (X[right] - X[i]))
            d_next = abs((X[N] - X[right + 1]) - (X[right + 1] - X[i]))
            if d_next > d:
                break
            right += 1
        p, q, r, s = X[left], X[i] - X[left], X[right] - X[i], X[N] - X[right]
        ans = min([ans, max([p, q, r, s]) - min([p, q, r, s])])
    print(ans)


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

import math
import math
import os
import sys
from collections import deque

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W, K = list(map(int, sys.stdin.readline().split()))
A = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)], dtype='S1')

[sh], [sw] = np.where(A == b'S')
A = A == b'.'


def step(h, w):
    return math.ceil(min(h, w, H - h - 1, W - w - 1) / K)


def ok(h, w):
    return 0 <= h < H and 0 <= w < W


dh = [0, 1, 0, -1]
dw = [1, 0, -1, 0]

# 最初の魔法でどこまで端にいけるか
que = deque([(sh, sw, K)])
seen = np.zeros((H, W), dtype=bool)
seen[sh, sw] = True
min_step = step(sh, sw)
while que:
    sh, sw, k = que.popleft()
    for hh, ww in zip(dh, dw):
        h = sh + hh
        w = sw + ww
        if not ok(h, w) or not A[h, w] or seen[h, w]:
            continue
        if k > 0:
            min_step = min(min_step, step(h, w))
            seen[h, w] = True
            que.append((h, w, k - 1))
print(min_step + 1)


### FIXED CODE ###

import math
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W, K = list(map(int, sys.stdin.readline().split()))
A = [sys.stdin.readline().rstrip() for _ in range(H)]

sh = sw = -1
for h, r in enumerate(A):
    if 'S' in r:
        sh = h
        sw = r.index('S')


def step(h, w):
    return math.ceil(min(h, w, H - h - 1, W - w - 1) / K)


def ok(h, w):
    return 0 <= h < H and 0 <= w < W


dh = [0, 1, 0, -1]
dw = [1, 0, -1, 0]

# 最初の魔法でどこまで端にいけるか
que = deque([(sh, sw, K)])
seen = [[0] * W for _ in range(H)]
seen[sh][sw] = True
min_step = step(sh, sw)
while que:
    sh, sw, k = que.popleft()
    for hh, ww in zip(dh, dw):
        h = sh + hh
        w = sw + ww
        if not ok(h, w) or A[h][w] == '#' or seen[h][w]:
            continue
        if k > 0:
            min_step = min(min_step, step(h, w))
            seen[h][w] = True
            que.append((h, w, k - 1))
print(min_step + 1)
### BUGGY CODE ###

L, R = map(int, input().split())

# max_loop = 2019 * 2 + 1
max_loop = 2019 ** 2
count = 0
ans = 2019
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        x = (i * j) % 2019
        ans = min(ans, x)
    if ans == 0:
        break
print(ans)


### FIXED CODE ###

L, R = map(int, input().split())

# max_loop = 2019 * 2 + 1
max_loop = 2019 ** 2
count = 0
ans = 2019
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        x = (i * j) % 2019
        ans = min(ans, x)
        if ans == 0:
            print(0)
            exit()
print(ans)
### BUGGY CODE ###

n = int(input())
num_list = list(map(int,input().split()))
ans = 1
for i in num_list:
    ans *= i
    
if ans > 10**18:
    print(-1)
    
else:
    print(ans)

### FIXED CODE ###

n = int(input())
num_list = list(map(int,input().split()))
ans = 1
if 0 in num_list:
    print(0)
    
else:
    for i in num_list:
        ans *= i
        if ans > 10**18:
            break

    if ans > 10**18:
        print(-1)

    else:
        print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

ans = ""
n, q = [int(item) for item in input().split()]
for i in range(q):
    v, w = [int(item) - 1 for item in input().split()]
    while v != w:
        if v > w:
            v = (v - 1) // n
        else:
            w = (w - 1) // n
    ans += str(v+1) + "\n"
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

ans = ""
n, q = [int(item) for item in input().split()]
if n == 1:
    for i in range(q):
        v, w = [int(item) for item in input().split()]
        print(min(v, w))
    exit()

for i in range(q):
    v, w = [int(item) - 1 for item in input().split()]
    while v != w:
        if v > w:
            v = (v - 1) // n
        else:
            w = (w - 1) // n
    print(v + 1)
### BUGGY CODE ###

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

d = sum(P)
min_i = 0
S_left = 0
S_right= 0

for i in range(N):
    S_left = sum(P[:i])
    S_right = sum(P[-(N-i):])
    d_temp = S_left - S_right
    
    if d >= abs(d_temp):
        d = abs(d_temp)
    
    else:
        break

    if d == 0:
        break

print(abs(d))


### FIXED CODE ###

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

d = sum(P)
L = sum(P)
S_left = 0
S_right= 0

for i in range(N):
    S_left += P[i]
    S_right = L - S_left
    d_temp = S_left - S_right
    
    if d >= abs(d_temp):
        d = abs(d_temp)
    
    else:
        break

    if d == 0:
        break

print(abs(d))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

from copy import deepcopy
n = int(input())
A = list(map(int, input().split()))
for i in range(len(A)):
    A[i] -= i + 1

ans = 10 ** 100
for a in A:
    B = deepcopy(A)
    for i in range(len(A)):
        B[i] -= a
    count = 0
    for b in B:
        count += abs(b)
    ans = min(ans, count)

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

n = int(input())
A = list(map(int, input().split()))
A = [A[i]-(i+1) for i in range(n)]
A.sort()

if n == 1:
    print(0)
    exit()

ans = 10**100
for i in [n//2-1, n//2]:
    ans = min(ans, sum([abs(A[j]-A[i]) for j in range(n)]))

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

import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort()
for _ in range(M):
  a = A.pop(-1) // 2
  A.insert(bisect.bisect_left(A, a), a)

print(sum(A))

### FIXED CODE ###

import heapq

def minus_int(s):
  return -1 * int(s)

N, M = map(int, input().split())
A = list(map(minus_int, input().split()))
heapq.heapify(A)
for _ in range(M):
  tmp = int(heapq.heappop(A) / 2)
  heapq.heappush(A, tmp)

print(sum(A) * (-1))
### BUGGY CODE ###

# import sys
# sys.setrecursionlimit(10 ** 9)
N, X = map(int, input().split())

# def f(a, b):
#     if a == b:
#         return a
#     if a >= b:
#         a, b = b, a
#     return 2 * a + f(a, b - a)

# print (N + f(N - X, X))




ans = N
a = N - X
b = X
while a != b:
    if a >= b:
        a, b = b, a
    ans += 2 * a
    b = b - a
print (ans + a)


    

### FIXED CODE ###

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

ans = N
a = N - X
b = X
while a != b:
    if a >= b:
        a, b = b, a
    if b%a != 0:
        ans += 2 * a * (b//a)
        b = b%a
    else:
        ans += 2 * a * (b//a - 1)
        b = a
print (ans + a)
### BUGGY CODE ###

N=int(input())
A=[int(input()) for n in range(N)]
m=max(A)
for i in range(N):
	if A[i]<m:
		print(m)
	else:
		print(max(A[:i]+A[i+1:]))


### FIXED CODE ###

N=int(input())
A=[int(input()) for n in range(N)]
m=max(A)
n=sorted(A,reverse=True)[1]
for i in range(N):
    if A[i]<m:
        print(m)
    else:
        print(n)
### BUGGY CODE ###

def b_len(v):
    return len(bin(v)[2:])


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

cs = [0]
for aa in a:
    cs.append(cs[-1] + aa)

ps = []
for i in range(1, n + 1):
    for j in range(i):
        ps.append(cs[i] - cs[j])

ps = sorted(ps, reverse=True)

pw = b_len(ps[k - 1])
MOD = 2 ** pw

nps = {i:set() for i in range(pw)}
for i in range(len(ps)):
    t = ps[i] % MOD
    for j in range(pw):
        if 1 << j & t:
            nps[j].add(i)

ans = 0
buf = set(range(len(ps)))
for j in range(pw)[::-1]:
    if len(nps[j]) >= k:
        x = buf & nps[j]
        if len(x) >= k:
            buf = x
            ans += 2 ** j

print(ans)

### FIXED CODE ###

from math import log, ceil

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

A_MAX = 10 ** 9
MAX_BIT_LENGTH = ceil(log(A_MAX * n, 2))

cs = [0]
t = 0
for aa in a:
    t += aa
    cs.append(t)

ps = []
for r in range(1, n + 1):
    for l in range(r):
        ps.append(cs[r] - cs[l])

ans = 0
for b in range(MAX_BIT_LENGTH)[::-1]:
    cnt = 0
    t = ans + (1 << b)
    for p in ps:
        if p & t == t:
            cnt += 1
            if cnt == k:
                ans = t
                break

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

import itertools
heads = ["M","A","R","C","H"]

N = int(input())
S = []

for i in range(N):
  s = input()[0]
  if s in heads:
    S.append(s)

combi = list(itertools.combinations(S,3))
con = 0

for i in combi:
  if len(set(i)) == 3:
    con += 1
    
print(con)

### FIXED CODE ###

import itertools
from operator import mul
from functools import reduce
heads = ["M","A","R","C","H"]

N = int(input())
S = [0,0,0,0,0]

for i in range(N):
  s = input()[0]
  if s in heads:
    n = heads.index(s)
    S[n] += 1

S = [i for i in S if i != 0]

nums = list(itertools.combinations(S,3))

total = 0

for list in nums:
  total += reduce(mul,list)

print(total)
### BUGGY CODE ###

n, p = map(int,input().split())
D = input()
out = 0


if 10 % p == 0:
    out = 0
    for i in range(n):
        if int(D[i]) % p == 0:
            out += i + 1
else:
    mod = 0
    count = [0] * p
    ten = 1
    count[mod] += 1
    for i in range(n):
        mod = (mod + int(D[n-i-1]) * ten) % p
        ten *= 10 % p
        count[mod] += 1
    for c in count:
        out += (c * (c - 1)) // 2
print(out)

### FIXED CODE ###

n, p = map(int,input().split())
D = input()
out = 0


if 10 % p == 0:
    for i in range(n):
        if int(D[i]) % p == 0:
            out += i + 1
else:
    mod = 0
    count = [0] * p
    ten = 1
    count[mod] += 1
    for i in range(n):
        mod = (mod + int(D[n-i-1]) * ten) % p
        ten = ten * 10 % p
        count[mod] += 1
    for c in count:
        out += (c * (c - 1)) // 2
print(out)
### BUGGY CODE ###

MOD = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))

dp = [[0 for i in range(S + 1)] for j in range(N + 1)]

dp[0][0] = 1

for i in range(1, N + 1):
    for j in range(S + 1):
        dp[i][j] += dp[i - 1][j] * 2
        dp[i][j] %= MOD
        if j + A[i - 1] <= S:
            dp[i][j + A[i - 1]] += dp[i - 1][j]
            dp[i][j + A[i - 1]] %= MOD
print(dp[N][S])


### FIXED CODE ###

MOD = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))

dp = [[0 for i in range(S + 1)] for j in range(N + 1)]

dp[0][0] = 1

for i in range(N):
    for j in range(S + 1):
        dp[i+1][j] += dp[i][j] * 2
        dp[i+1][j] %= MOD
        if j + A[i] <= S:
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= MOD
print(dp[N][S])
### BUGGY CODE ###

S = list(input())
S.reverse()
amari = []
A = 0
c = 0
for i in range(len(S)):
    a = (int(A) + int(S[i]) *(10 ** i)) % 2019
    amari.append(a)
    if a == 0:
        c += 1
    A = a
print(c + len(amari) - len(set(amari)))


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    S = input()[::-1] # 入力文字列を逆順で格納
    counts = [0] * 2019
    counts[0] = 1
    num, d = 0, 1

    for char in S:
        num = num + int(char) * d
        num = num % 2019
        d = d * 10
        d = d % 2019
        counts[num] += 1 #余りの数の番号のリストに+1していくことでカウント

    ans = 0
    for cnt in counts:
        ans += cnt * (cnt - 1) // 2
    print(ans)

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

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float('inf') for _ in range(n)]
    dp[0] = 0

    for i in range(n):
        for j in range(1, min(k+1, n-i)):
            num = dp[i]+abs(h[i]-h[i+j])
            if num < dp[i+j]:
                dp[i+j] = num
    print(dp[-1])

main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float('inf')]*n
    dp[0] = 0
    for i in range(n):
        a = h[i]
        for j in range(1, min(k+1, n-i)):
            num = dp[i]+abs(a-h[i+j])
            if num < dp[i+j]:
                dp[i+j] = num
    print(dp[-1])

main()
### BUGGY CODE ###

N,M,L,*X = map(int, open(0).read().split())
ls = X[:3*M]
INF = 10**9
Els = [[INF]*N for i in range(N)]
Q = X[3*M]
query = X[3*M+1:]
for a,b,c in zip(*[iter(ls)]*3):
  if c<=L:
    Els[a-1][b-1] = c
    Els[b-1][a-1] = c
for i in range(N):
  Els[i][i] = 0
for k in range(N):
  for i in range(N):
    for j in range(N):
      Els[i][j] = min(Els[i][j], Els[i][k]+Els[k][j])
      
dist = [[INF]*N for i in range(N)]
for i in range(N):
  for j in range(N):
    if Els[i][j]<=L:
      dist[i][j] = 1
for i in range(N):
  dist[i][i] = 0
for k in range(N):
  for i in range(N):
    for j in range(N):
      dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

for s,t in zip(*[iter(query)]*2):
  if dist[s-1][t-1]>=INF:
    print(-1)
    continue
  print(dist[s-1][t-1]-1)

### FIXED CODE ###

N, M, L = map(int, input().split())
INF = 10**12
dp = [[INF]*N for i in range(N)]
fp = [[INF]*N for i in range(N)]
for i in range(N):
  dp[i][i]=0
  fp[i][i]=0
k = [[0]*N for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  dp[a-1][b-1] = c
  dp[b-1][a-1] = c

for i in range(N):
  for j in range(N):
    for h in range(N):
      dp[j][h] = min(dp[j][h], dp[j][i]+dp[i][h])

for j in range(N):
  for h in range(N):
    if dp[j][h]<=L:
      fp[j][h] = 1
for i in range(N):
  for j in range(N):
    for h in range(N):
      fp[j][h] = min(fp[j][h], fp[j][i]+fp[i][h])
Q = int(input())
for i in range(Q):
  s, t = map(int, input().split())
  s = s-1
  t = t-1
  if fp[s][t]==INF:
    print(-1)
  else:
    print(fp[s][t]-1)
### BUGGY CODE ###

import itertools
n,m = map(int, input().split())
d = [0]*n
for i in range(m):
    l,r = map(int, input().split())
    for i in range(l-1,r):
        d[i]+=1
count = 0
for i in d:
    if i == m:
        count+=1       
print(count)

### FIXED CODE ###

n,m = map(int, input().split())
fn = 1
ln = n
for i in range(m):
    l,r = map(int, input().split())
    fn = max(fn,l)
    ln = min(ln,r)    
print(ln-fn+1 if ln-fn>=0 else 0)