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

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


from numba import njit
import numpy as np


N, K = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)


# @njit('(i8,i8,i8[:],i8[:])', cache=True)
def main(N, K, W, V):
    dp = np.zeros((N + 1, K + 1), dtype=np.int64)
    for i in range(N + 1):
        dp[i, 0] = 0

    for i in range(N):
        w, v = W[i], V[i]
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1, sum_w] = dp[i, sum_w]
            else:
                dp[i + 1, sum_w] = max(
                    dp[i, sum_w],
                    dp[i, sum_w - w] + v)
    print(dp[-1, -1])


main(N, K, W, V)


### FIXED CODE ###

import sys
read = sys.stdin.readline


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


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()

    dp = [[-10 for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print(dp[-1][-1])


main()

# pythonでもpypyでもTLE
### BUGGY CODE ###

N=int(input())
A = []
for i in range(N):
    A.append(int(input()))

ans =[]
for i in range(len(A)):
    if A[i] not in ans:
        ans.append(A[i])

    else:
        ans.remove(A[i])

print(len(ans))


### FIXED CODE ###

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

for i in range(N):
    new = int(input())
    A.append(new)

A.sort()
A.append(0)

start=A[0]
cnt=1
anscnt=0

for i in range(1,len(A)):

    if A[i]==start:
        cnt+=1
    elif A[i]!=start:
        if cnt%2==0:
            anscnt+=cnt
        elif cnt%2!=0:
            anscnt+=cnt-1    
        cnt=1
        start=A[i]


print(N-anscnt)
### BUGGY CODE ###

n,k = map(int, input().split())
mod = 10**9+7
cnts=[0]*(k+1)

for x in reversed(range(1,k+1)):
    num= k//x

    c = num**n
    for j in range(2,num+1):
        c-= cnts[x*j]
    cnts[x]=c

ans=0
for i in range(1,k+1):
    ans+=(i*cnts[i])
print(ans%mod)

### FIXED CODE ###

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

mod = 10**9+7
cnts=[0]*(k+1)

for x in reversed(range(1,k+1)):
    num= k//x

    c = pow(num,n,mod)
    for j in range(2,num+1):
        c-= cnts[x*j]
    cnts[x]=c

ans=0
for i in range(1,k+1):
    ans+=(i*cnts[i])
print(ans%mod)
### BUGGY CODE ###

def main():
    s = list(input())
    n = len(s)
    dp = [[0 for _ in range(13)] for _ in range(n+1)]
    dp[0][0] = 1
    mod = 10**9+7
    for i in range(n):
        if s[i] != '?':
            for j in range(13):
                index = (j*10+int(s[i]))%13
                dp[i+1][index] = (dp[i+1][index]+dp[i][j])%mod
        else:
            for j in range(10):
                for k in range(13):
                    index = (k*10+j)%13
                    dp[i+1][index] = (dp[i+1][index]+dp[i][k])%mod
    print(dp[n][5])

if __name__ == "__main__":
    main()

### FIXED CODE ###

mod = 10**9+7
def main():
    s = list(input())
    n = len(s)
    dp = [[0 for _ in range(13)] for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        if s[i] != '?':
            s[i] = int(s[i])
            for k in range(13):
                index = (k*10+s[i])%13
                dp[i+1][index] += dp[i][k]
        else:
            for j in range(10):
                for k in range(13):
                    index = (k*10+j)%13
                    dp[i+1][index] += dp[i][k]
        for j in range(13):
            dp[i+1][j] %= mod
    print(dp[n][5])

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

import sys

input = lambda: sys.stdin.readline()


def cin_int_list():
    return [int(x) for x in input().split()]


def cin_int_iter():
    return (int(x) for x in input().split())


def cin_int():
    return int(input())


def cout_int_iter(a):
    print(' '.join(map(str, a)))


def iota(n, start=0):
    return list(range(start, n))


def cin_digits_list():
    return [ord(x) - ord('0') for x in input()]


def main():
    n, k = cin_int_iter()

    g = {}

    cycle_starts = None
    for u, x in enumerate(cin_int_list()):
        v = x - 1
        g[u] = v
        if v in g:
            cycle_starts = v

    if cycle_starts is not None:
        cycle_len = 0

        u = cycle_starts
        cycle = []
        while True:
            cycle.append(u)
            u = g[u]

            if u == cycle_starts:
                break

        before_cycle = []
        u = 0

        while u != cycle_starts:
            before_cycle.append(u)
            u = g[u]

        if k < len(before_cycle):
            print(before_cycle[k] + 1)
            return

        if before_cycle:
            k -= len(before_cycle)

        print(cycle[k % len(cycle)] + 1)
        return

    u = 0
    while k:
        u = g[u]
        k -= 1

    print(u + 1)




main()


"""
6 1
6 5 2 5 3 2

6 2
6 5 2 5 3 2

6 3
6 5 2 5 3 2

6 4
6 5 2 5 3 2

6 6
6 5 2 5 3 2

6 5
6 5 2 5 3 2


no cycle

4 1
2 3 4 5

4 111111111111111111
2 3 4 1
"""

### FIXED CODE ###

import sys

input = lambda: sys.stdin.readline()


def cin_int_list():
    return [int(x) for x in input().split()]


def cin_int_iter():
    return (int(x) for x in input().split())


def cin_int():
    return int(input())


def cout_int_iter(a):
    print(' '.join(map(str, a)))


def iota(n, start=0):
    return list(range(start, n))


def cin_digits_list():
    return [ord(x) - ord('0') for x in input()]


def main():
    n, k = cin_int_iter()

    g = {}

    for u, x in enumerate(cin_int_list()):
        v = x - 1
        g[u] = v

    visited = set()

    u = 0
    while u not in visited:
        visited.add(u)
        u = g[u]

    cycle_starts = u

    u = cycle_starts
    cycle = []
    while True:
        cycle.append(u)
        u = g[u]

        if u == cycle_starts:
            break

    before_cycle = []
    u = 0

    while u != cycle_starts:
        before_cycle.append(u)
        u = g[u]

    if k < len(before_cycle):
        print(before_cycle[k] + 1)
        return

    if before_cycle:
        k -= len(before_cycle)

    print(cycle[k % len(cycle)] + 1)




main()


"""
6 1
6 5 2 5 3 2

6 2
6 5 2 5 3 2

6 3
6 5 2 5 3 2

6 4
6 5 2 5 3 2

6 6
6 5 2 5 3 2

6 5
6 5 2 5 3 2


no cycle

4 1
2 3 4 5

4 111111111111111111
2 3 4 1

1 111111111111111111
1

2 1999999999999999999
2 1

3 99999999999999999999
2 3 2

3 99999999999999999999
2 3 4
"""
### BUGGY CODE ###

n, h = map(int, input().split())
a = []
b = []
for i in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
b.append(0)
b = sorted(b, reverse=True)

count = 0
while True:
    if max(b) < max(a):
        count += -(-h // max(a))
        break
    else:
        h -= b.pop(0)
        count += 1

print(count)


### FIXED CODE ###

n, h = map(int, input().split())
a = []
b = []
for i in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
b.append(0)
a2 = sorted(a, reverse=True)
b2 = sorted(b, reverse=True)

count = 0
while True:
    if h <= 0:
        break
    elif b2[0] <= a2[0]:
        count += -(- h // a2[0])
        break
    else:
        h -= b2.pop(0)
        count += 1

print(count)
### BUGGY CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
import math


N = int(input())
An = list(map(int, input().split()))
Bn = []
for a in An:
  Bn = [a] + Bn[::-1]

for b in Bn:
  print(b,end=" ")

### FIXED CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
import math


N = int(input())
An = list(map(int, input().split()))

if N%2 == 0:
  Bn = An[-1::-2] + An[0::2]
else:
  Bn = An[-1::-2] + An[1::2]

for b in Bn:
  print(b,end=" ")
### BUGGY CODE ###

import numpy as np


def simple_solution(N, A, B):
    ret = 0
    for a in A:
        for b in B:
            ret ^= a + b
    return ret


def solution(N, A, B):
    pow_2_k = 1
    ans = 0
    A = np.array(A)
    B = np.array(B)
    for k in range(30):
        MA = A % (2 * pow_2_k)
        MB = np.sort(B % (2 * pow_2_k))
        # [2**k, 2 * (2**k)) か [3 * (2**k), 4 * (2**k)) の中に入るとk-bit目が1。
        # この a + b の数をカウントする。
        # → [2**k - a, 2 * (2**k) - a) か [3 * (2**k) - a, 4 * (2**k) - a) の中に入る b の数をカウント。
        cnt = 0
        for a in MA:
            index_1 = np.searchsorted(MB, pow_2_k - a, side='left')
            index_2 = np.searchsorted(MB, 2 * pow_2_k - a, side='left')
            index_3 = np.searchsorted(MB, 3 * pow_2_k - a, side='left')
            cnt += (N - index_1) - (N - index_2) + (N - index_3)
        if cnt % 2 == 1:
            ans += pow_2_k
        pow_2_k *= 2
    return ans


def check():
    import random
    random.seed(0)
    for N in range(1, 101):
        A = random.choices(range(2 ** 28), k=N)
        B = random.choices(range(2 ** 28), k=N)
        print('Checking the case with size: {}'.format(N))
        assert simple_solution(N, A, B) == solution(N, A, B)
    print('OK')


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    print(solution(N, A, B))


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

### FIXED CODE ###

import numpy as np


def main():
    N = int(input())
    A = np.array(list(map(int, input().split())))
    B = np.array(list(map(int, input().split())))
    pow_2_k = 1
    ans = 0
    for k in range(30):
        MA = A % (2 * pow_2_k)
        MB = B % (2 * pow_2_k)
        MB.sort()
        # [2**k, 2 * (2**k)) か [3 * (2**k), 4 * (2**k)) の中に入るとk-bit目が1。
        # この a + b の数をカウントする。
        # → [2**k - a, 2 * (2**k) - a) か [3 * (2**k) - a, 4 * (2**k) - a) の中に入る b の数をカウント。
        cnt = 0
        indices_1 = np.searchsorted(MB, pow_2_k - MA, side='left')
        indices_2 = np.searchsorted(MB, 2 * pow_2_k - MA, side='left')
        indices_3 = np.searchsorted(MB, 3 * pow_2_k - MA, side='left')
        cnt += ((N - indices_1) - (N - indices_2) + (N - indices_3)).sum()
        if cnt % 2 == 1:
            ans += pow_2_k
        pow_2_k *= 2
    print(ans)


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

import math
L,R = map( int,input().split() )
ans = ( L * (L+1) ) % 2019  
for i in range(L,R):
    if ans == 0:
        break
    j = i + 1
    a = ( i * j ) % 2019
    ans = min(a, ans)
    plus = i % 2019
    while(True):
        over = math.ceil( ( 2019 - a ) / plus )
        j = j + over
        if j > R:
            break
        a = ( i * j) % 2019
        ans = min(a,ans)
print(ans)

### FIXED CODE ###

import math
L,R = map( int,input().split() )
ans = ( L * (L+1) ) % 2019  
for i in range(L,R):
    if ans == 0:
        break
    j = i + 1
    a = ( i * j ) % 2019
    ans = min(a, ans)
    plus = i % 2019
    while(True):
        over = math.ceil( ( 2019 - a ) / plus )
        j = j + over
        if j > R:
            break
        a = ( i * j) % 2019
        ans = min(a,ans)
        if ans == 0:
            break
print(ans)
### BUGGY CODE ###

n=int(input())
ans=1
for i in range(1,n+1):
  ans*=i
print(ans%(10**9+7))

### FIXED CODE ###

n=int(input())
ans=1
for i in range(1,n+1):
  ans*=i
  if ans>10**9+7:
      ans=ans%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000)

def uclid_gcm(a, b):
  if a < b:
    a += b
    b = a-b
    a=a-b
  if b == 0:
    return a
  r = a%b
  return b if r == 0 else uclid_gcm(b, r)

def gcm_all(array):
  l = len(array)
  if l == 1:
    return array[0]
  else:
    tmp = []
    for i in range(l//2):
      tmp.append(uclid_gcm(array[i*2], array[i*2+1]))
    if l %2 == 1:
      tmp.append(uclid_gcm(array[-2],array[-1]))
    return gcm_all(tmp)

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

ans = 0
for i in range(N):
  t  = A[i]
  A[i] = 0
  ans = max(ans, gcm_all(A))
  A[i] = t
print(ans)



### FIXED CODE ###

from collections import deque
def gcm(a, b):
  if a < b:
    a = a+b
    b=a-b
    a = a-b
  if b == 0:
    return a
  else:
    r = a%b
    return b if r == 0 else gcm(b, r)
N = int(input())
A = list(map(int, input().split()))
L = deque([0])
for i in range(1, N):
  L.append(gcm(L[-1],A[i-1]))
R = deque([0])
for i in reversed(range(N-1)):
  R.appendleft(gcm(R[0],A[i+1]))
ans = 0
for i in range(N):
  ans = max(ans, gcm(L[i],R[i]))
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
Mod = 1000000007
dp = [1]*(N+1) #dp[i]...i番目にいる時の移動方法の数

count = 0
for i in range(1,N):
    if i in a:
        count += 1
        if count == 2:
            print(0)
            exit()
    else:
        count = 0

for i in range(N):
    if i in a:
        dp[i] = 0
if 1 in a:
    for i in range(1,N-1):
        if dp[i+2] != 0:
            dp[i+2] = dp[i+1] + dp[i]
            dp[i+2] %= Mod
else:
    dp[1] = 1
    for i in range(N-1):
        if dp[i+2] != 0:
            dp[i+2] = dp[i+1] + dp[i]
            dp[i+2] %= Mod

print(dp[N])

### FIXED CODE ###

N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
Mod = 1000000007
dp = [1]*(N+1) #dp[i]...i番目にいる時の移動方法の数

count = 0
for i in a:
    if i+1 in a:
        print(0)
        exit()

for i in a:
    dp[i] = 0
if dp[1] == 0:
    for i in range(1,N-1):
        if dp[i+2] != 0:
            dp[i+2] = dp[i+1] + dp[i]
            dp[i+2] %= Mod
else:
    dp[1] = 1
    for i in range(N-1):
        if dp[i+2] != 0:
            dp[i+2] = dp[i+1] + dp[i]
            dp[i+2] %= Mod

print(dp[N])
### BUGGY CODE ###

n, m, k = list(map(int, input().split()))
link = {i: (set(), set()) for i in range(1, n+1)}

friends = 0
blocked = 1

groups = []
for _ in range(m):
    a, b = list(map(int, input().split()))
    link[a][friends].add(b)
    link[b][friends].add(a)
    holders = []
    for i, g in enumerate(groups):
        if a in g or b in g:
            g.add(a)
            g.add(b)
            holders.append(i)
    if len(holders) >= 2:
        ng = set()
        for h in reversed(holders):
            ng |= groups[h]
            groups.pop(h)
        groups.append(ng)
    elif len(holders) == 0:
        groups.append(set([a,b]))

for _ in range(k):
    c, d = list(map(int, input().split()))
    link[c][blocked].add(d)
    link[d][blocked].add(c)

for i in range(1, n+1):
    for g in groups:
        if i in g:
            cnt = len(g - link[i][blocked] - link[i][friends]) - 1 
            break
    else:
        cnt = 0
    print(cnt, end="" if i == n else " ")


### FIXED CODE ###

class Tree:
    def __init__(self, v: int):
        self.value = v
        self.size = 1
        self.depth = 1
        self.parent = None
        self.friends = set()
        self.blocked = 0

    def get_root(self):
        t = self
        while(t.parent != None):
            t = t.parent
        return t

    def merge(self, t):
        p, c = (self, t) if self.depth > t.depth else (t, self)
        c.parent = p
        p.depth = max(p.size, c.size + 1)
        p.size += c.size

def main():
    n, m, k = [int(s) for s in input().split()]
    forest = [Tree(i+1) for i in range(n)]

    for i in range(m):
        a, b = [int(s) for s in input().split()]
        ta, tb = forest[a-1], forest[b-1]
        ta.friends.add(b)
        tb.friends.add(a)
        ra = ta.get_root()
        rb = tb.get_root()
        if ra != rb:
            ra.merge(rb)

    roots = [t.get_root() for t in forest]
    for i in range(k):
        c, d = [int(s) for s in input().split()]
        tc, td = forest[c-1], forest[d-1]
        rc = roots[c-1]
        rd = roots[d-1]
        if rc == rd:
            tc.blocked +=1
            td.blocked +=1

    cands = []
    for t in forest:
        root = roots[t.value - 1]
        cand = root.size - len(t.friends) - t.blocked - 1
        cands.append(str(cand))
    print(" ".join(cands))

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

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

def main():
    flag = 0
    for i in range(len(A)-1):
        for j in range(i+1, len(A)):
            if A[i] == A[j]:
                flag = 1
                break
            else:
                continue

        if flag == 1:
            break
        else:
            continue

    if flag == 0:
        print('YES')
    else:
        print('NO')


if __name__ == "__main__":
    main()
    

### FIXED CODE ###

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

def main():
    flag = 0
    new_A = sorted(A)

    for i in range(S-1):
        if new_A[i] == new_A[i+1]:
            flag = 1
            break
        else:
            continue

    if flag == 0:
        print('YES')
    else:
        print('NO')


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

def get(text,n):
    ans = [""]*n
    i = 0
    for x in text:
        if x==" ":
            i = i + 1
        ans[i] = ans[i]+x
    return ans

nk = input()
textp = input()

N = int(get(nk,2)[0])
K = int(get(nk,2)[1])
ps = get(textp,N)
for i in range(N):
    ps[i] = int(ps[i])

exp = [0] * N
for i in range(N):
    exp[i] = (ps[i]+1)/2

m = 0
for i in range(N-K+1):
    s = 0
    for j in range(K):
        s = s + exp[i+j]
    if m < s:
        m = s

print(m)

### FIXED CODE ###

def get(text,n):
    ans = [""]*n
    i = 0
    for x in text:
        if x==" ":
            i = i + 1
        ans[i] = ans[i]+x
    return ans

nk = input()
textp = input()

N = int(get(nk,2)[0])
K = int(get(nk,2)[1])
ps = get(textp,N)
for i in range(N):
    ps[i] = int(ps[i])

exp = [0] * N
for i in range(N):
    exp[i] = (ps[i]+1)/2

s = 0
for j in range(K):
    s = s + exp[j]
m = s
for i in range(N-K):
    s = s - exp[i] + exp[i+K]
    if m < s:
        m = s

print(m)
### BUGGY CODE ###

import numpy as np

h, w = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
b = [list(map(int,input().split())) for i in range(h)]

a = np.array(a)
b = np.array(b)
ab = abs(a - b)
ab0 = ab[0][0]
size = 80*h*w 
dp = np.zeros((h, w, 1 + size), dtype='bool')
dp[0][0][size//2 + ab0] = True # size//2が0に相当
dp[0][0][size//2 - ab0] = True
for ch in range(h):
    for cw in range(w):
        for ck in range(1 + size): 
            if dp[ch][cw][ck]:
                if ch < h-1:
                    dp[ch+1][cw][ck + ab[ch+1][cw]] = True
                    dp[ch+1][cw][ck - ab[ch+1][cw]] = True
                if cw < w-1:
                    dp[ch][cw+1][ck + ab[ch][cw+1]] = True
                    dp[ch][cw+1][ck - ab[ch][cw+1]] = True

for i in range(1 + size//2):
    for j in [1, -1]:
        if dp[h-1][w-1][size//2 + i*j]:
            print(i)
            exit()

### FIXED CODE ###

h, w = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
b = [list(map(int,input().split())) for i in range(h)]

ab = [[0]*w for i in range(h)]
for ch in range(h):
    for cw in range(w):
        ab[ch][cw] = abs(a[ch][cw] - b[ch][cw])

ab0 = ab[0][0]
size = 80*(h+w)
dp = [[0]*w for hh in range(h)]
dp[0][0] |= 2**(size + ab0)
dp[0][0] |= 2**(size - ab0)
for ch in range(h):
    for cw in range(w):
        if ch < h-1:
            dp[ch+1][cw] |= dp[ch][cw] << ab[ch+1][cw]
            dp[ch+1][cw] |= dp[ch][cw] >> ab[ch+1][cw]
        if cw < w-1:
            dp[ch][cw+1] |= dp[ch][cw] << ab[ch][cw+1]
            dp[ch][cw+1] |= dp[ch][cw] >> ab[ch][cw+1]

a = dp[h-1][w-1]>>size
m = a&(-a)
print(m.bit_length()-1)
### BUGGY CODE ###

N=int(input())
A=map(int,input().split())
Q=int(input())
numbers=[]
for _ in range(Q):
    B,C=map(int,input().split())
    numbers.append([B,C])
answers=[0 for _ in range(1000001)]
for a in A:
    answers[a]+=1
for number in numbers:
    suuji=answers[number[0]]
    answers[number[0]]=0
    answers[number[1]]+=suuji
    answer=0
    n=0
    for a in answers:
        answer+=n*a
        n+=1
    print(answer)
    

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=map(int,input().split())
Q=int(input())
numbers=[]
for _ in range(Q):
    B,C=map(int,input().split())
    numbers.append([B,C])
answers=[0 for _ in range(100001)]
for a in A:
    answers[a]+=a
whole=sum(answers)
for number in numbers:
    suuji=answers[number[0]]//number[0]
    answers[number[0]]=0
    answers[number[1]]+=suuji*number[1]
    whole+=(number[1]-number[0])*suuji
    print(whole)
### BUGGY CODE ###

N = int(input())


def tester(n, k):
    temp = n
    while temp % k == 0:
        temp /= k

    if temp % k == 1:
        return True
    else:
        return False

answer= []

for i in range(2, N + 1):
    if tester(N, i):
        answer.append(i)

print(len(answer))

### FIXED CODE ###

n = int(input())

def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table


def tester(n, k):
    if k == 1:
        return False

    temp = n
    while temp % k == 0:
        temp /= k

    if temp % k == 1:
        return True
    else:
        return False

answer = []
for i in (divisor(n - 1) + divisor(n)):
    if tester(n, i):
        answer.append(i)

print(len(answer))
### BUGGY CODE ###

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

stepper = 0
gate = []

for j in range(M):
    gate_1, gate_2 = map(int, input().split())
    gate.append([gate_1, gate_2])


def numJudge(arr, num):
    if arr[0] <= num <= arr[1]:
        return 1
    else:
        return 0


def judge(num):
    num += 1
    ctr = 0
    for k in range(M):
        if gate[k][0] <= num <= gate[k][1]:
            ctr += 1
    if ctr == M:
        return 1
    else:
        return 0


ans = map(judge, range(N))
print(sum(list(ans)))


### FIXED CODE ###

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

stepper = 0
gate = []

for j in range(M):
    gate_1, gate_2 = map(int, input().split())
    gate.append([gate_1, gate_2])

gate_min = 0
gate_max = N

for m in range(M):
    if gate[m][0] > gate_min:
        gate_min = gate[m][0]

    if gate[m][1] < gate_max:
        gate_max = gate[m][1]

#print(gate_min, gate_max)
for k in range(N):
    k = k+1
    if gate_min <= k <= gate_max:
        stepper += 1

print(stepper)