Harryxun/stf_run huggingface dataset:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N, Q = map(int, input().split())
    ki = [[] for _ in range(N + 1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        ki[a].append(b)
    PX = [tuple(map(int, input().split())) for _ in range(Q)]

    ans = [0 for _ in range(N + 1)]
    def dfs(i, n):
        ans[i] += n
        for j in ki[i]:
            dfs(j, n)

    for p, x in PX:
        dfs(p, x)
    print(*ans[1:])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().rstrip()

def main():
    N, Q = map(int, input().split())
    ki = [[] for _ in range(N + 1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        ki[a].append(b)
        ki[b].append(a)
    PX = [tuple(map(int, input().split())) for _ in range(Q)]

    ans = [0 for _ in range(N + 1)]
    for p, x in PX:
        ans[p] += x
    visited = set()
    def dfs(i):
        visited.add(i)
        for j in ki[i]:
            if j in visited:
                continue
            ans[j] += ans[i]
            dfs(j)
    dfs(1)
    print(*ans[1:])

if __name__ == '__main__':
    main()
def problem():
    N = int(input())
    V = list(map(int, input().split()))
    C = list(map(int, input().split()))

    print(algorithm(N, V, C))


def algorithm(N: int, V: List[int], C: List[int]):
    indices = list(filter(lambda i: V[i] - C[i] > 0, list(range(0, N))))

    sum = 0
    for i in indices:
        sum += V[i] - C[i]
    return sum
 
problem()


### FIXED CODE ###


def problem():
    N = int(input())
    V = list(map(int, input().split()))
    C = list(map(int, input().split()))

    print(algorithm(N, V, C))


def algorithm(N, V, C):
    indices = list(filter(lambda i: V[i] - C[i] > 0, list(range(0, N))))

    sum = 0
    for i in indices:
        sum += V[i] - C[i]
    return sum

problem()
S=raw_input()
c=[]
cnt=0
for i in S:
	if i=="0":
		cnt+=1
	else:
		if cnt!=0:
			c.append(cnt)
			cnt=0
else:
	if cnt!=0:
		c.append(cnt)

if len(c)==1:
	print c[0]
else:
	print max(c)+1
			



### FIXED CODE ###

S=raw_input()
N=len(S)
TS=N
for k in range(N-1):
	if S[k]!=S[k+1]:
		TS=min(TS, max(k+1, N-k-1))

print TS
from math import gcd
# def lcm(a,b): return a*b//gcd(a,b)

def lcm(a, b):
    return (a * b) // gcd(a, b)

n = int(input())

ans = 1
for i in range(n):
    t = int(input())
    ans = lcm(t, ans)
print(ans)

### FIXED CODE ###

from fractions import gcd
def lcm(a,b): return a*b//gcd(a,b)

n = int(input())

ans = 1
for i in range(n):
    t = int(input())
    ans = lcm(t, ans)
print(ans)
N, K = list(map(int, input().split()))
ab = []
for i in range(N - 1):
    ab.append(list(map(int, input().split())))
    ab[-1][0] -= 1
    ab[-1][1] -= 1

ki = []
for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = []
    ki[-1]["No"] = []
    ki[-1]["iro"] = -1
    ki[-1]["one"] = []

for i in range(N - 1):
    ki[ab[i][0]]["eda"].append([ab[i][0], ab[i][1]])
    ki[ab[i][1]]["eda"].append([ab[i][1], ab[i][0]])
    ki[ab[i][0]]["one"].append(ab[i][1])
    ki[ab[i][1]]["one"].append(ab[i][0])



def tansaku(i, base, ki):
    num = 1
    for node in ki[i]["one"]:
        if ki[node]["iro"] != -1:
            ki[i]["No"].append(ki[node]["iro"])
        for nodenode in ki[node]["one"]:
            if ki[nodenode]["iro"] != -1 and node != i:
                ki[i]["No"].append(ki[node]["iro"])

    num *= K - len(ki[i]["No"])
    num = num % 1000000007
    if num == 0:
        return 0

    for j in range(K):
        if not j in ki[i]["No"]:
            ki[i]["iro"] = j
            break

    for node in ki[i]["one"]:
        if node != base:
            num *= tansaku(node, i, ki)
            num = num % 1000000007

    return num


num = K
ki[0]["iro"] = 0

for node in ki[0]["one"]:
    num *= tansaku(node, 0, ki)
    num = num % 1000000007

print(num)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()
A,B,C,D,E,F=map(int,input().split())
w=set()
s=set()
for i in range(31):
    for j in range(16):
        if 100*(A*i+B*j)<=F:
            w.add(100*(A*i+B*j))
for i in range(1501):
    for j in range(751):
        if C*i+D*j<=F/2:
            s.add(C*i+D*j)
w=list(w)
w.sort()
del w[0]
s=list(s)
s.sort()
M=-1
for i in w:
    for j in range(len(s)-1,-1,-1):
        t=s[j]/i
        if t*100<=E:
            if t>M and i+s[j]<=F:
                W,S=i,s[j]
                M=t
            break
print(W+S,S)

### FIXED CODE ###

A,B,C,D,E,F=map(int,input().split())
w=set()
s=set()
for i in range(31):
    for j in range(16):
        if 100*(A*i+B*j)<=F:
            w.add(100*(A*i+B*j))
for i in range(1501):
    for j in range(751):
        if C*i+D*j<=F/2:
            s.add(C*i+D*j)
w=list(w)
w.sort()
del w[0]
s=list(s)
s.sort()
M=-1
for i in w:
    for j in range(len(s)-1,-1,-1):
        if s[j]*100<=E*i:
            if s[j]>M*i and i+s[j]<=F:
                W,S=i,s[j]
                M=s[j]/i
print(W+S,S)
a,b,c = map(int,input().split())
count = 0
for i in range(a,b+1):
  if i % c == 0:
    count += 1
print(count)

### FIXED CODE ###

a,b,c = input().split()
print("A" +b[0]+ "C")
n,m=map(int,input().split())
print((n+m//2)//2)n,m=map(int,input().split())
m//=2
print((n+(m-n)//2) if n<m else m)

### FIXED CODE ###

n,m=map(int,input().split())
m//=2
print((n+(m-n)//2) if n<m else m)
import sys

S = list(map(int, sys.stdin.readline()))
len_S = len(S)
ans = 0
for i in range(2 ** (len_S - 1)):
  sum_ = S[len_S - 1]
  cursor = len_S - 1
  power = 0
  pattern = i
  while cursor > 0:
    cursor -= 1 
    if pattern % 2 == 1:
      power += 1
    else:
      power = 0
    sum_ += S[cursor] * (10 ** power)
    pattern >>= 1
  ans += sum_
print(ans)


### FIXED CODE ###

import sys

S = list(map(int, sys.stdin.readline().strip()))
len_S = len(S)
ans = 0
for i in range(2 ** (len_S - 1)):
  sum_ = S[len_S - 1]
  cursor = len_S - 1
  power = 0
  while cursor > 0:
    cursor -= 1 
    if i % 2 == 1:
      power += 1
    else:
      power = 0
    sum_ += S[cursor] * (10 ** power)
    i >>= 1
  ans += sum_
print(ans)
import sys
readline = sys.stdin.readline
n, m = map(int, input().split())
a = []
b = []
for _ in range(m):
    aa, bb = list(map(int, readline().split()))
    a.append(aa - 1)
    b.append(bb - 1)
a = a[::-1]
b = b[::-1]
ans = int(n * (n - 1) / 2)
ans_rec = [0] * m
ans_rec[-1] = ans
p = [-1] * n
size = [1] * n
def find(x):
    px = p[x]
    if px < 0:
        return x
    else:
        pxx = find(px)
        p[x] = pxx
        return pxx
for k in range(m - 1):
    pa = find(a[k])
    pb = find(b[k])
    if pa == pb:
        pass
    else:
        ans -= size[pa] * size[pb]
        size[pa] += size[pb]
        p[pb] = pa
    ans_rec[- k - 2] = ans
print(*ans_rec, sep="\n")


### FIXED CODE ###

import sys
readline = sys.stdin.readline
N, M = map(int, input().split())
ab = [tuple(map(lambda x: int(x) - 1, readline().split())) for _ in range(M)]
class UnionFind:
    def __init__(self, size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]
    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x
    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]
uf = UnionFind(N)
p = N * (N - 1) // 2
ans = [p]
for x, y in reversed(ab[1:]):
    px = uf.find(x)
    py = uf.find(y)
    if px != py:
        p -= uf.number[px] * uf.number[py]
        uf.union(px, py)
    ans.append(p)
print(*ans[::-1], sep="\n")
s = input()
num_list = list(map(int, input().split()))
count = -1
while flg_break:
    count+=1
    num_tmp_list = []
    for n in num_list:
        if n % 2 != 0:
            flg_break = False
            break
        else:
            num_tmp = n / 2
            num_tmp_list.append(num_tmp)
    num_list = num_tmp_list
print(count)

### FIXED CODE ###

s = input()
num_list = list(map(int, input().split()))

flg_break = True

count = -1
while flg_break:
    count+=1
    num_tmp_list = []
    for n in num_list:
        if n % 2 != 0:
            flg_break = False
            break
        else:
            num_tmp = n / 2
            num_tmp_list.append(num_tmp)
    num_list = num_tmp_list
    

print(count)
from collections import deque
import sys
#input = sys.stdin.readline

sys.setrecursionlimit(5000)

def get_adj_tiles(v):
    i, j = v
    res = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
    return res

def bfs(point):
    visited = []
    que = deque()
    que.append((point, 1))
    
    while True:
        v, depth = que.popleft()
        visited.append(v)
        adjs = get_adj_tiles(v)
        for a in adjs:
            if field[a[0]][a[1]] == '.' and a not in visited:
                if a == (H, W):
                    return depth + 1
                else:
                    que.append((a, depth+1))
        if len(que) == 0:
            return 0

def main():
    H, W = list(map(int, input().split()))
    field = [['#'] * (W + 2) for _ in range(H + 2)]
    for i in range(H):
        values = list(input())
        field[i+1][1:-1] = values

    number_of_whites = 0
    for i in range(H+2):
        for j in range(W+2):
            if field[i][j] == '.':
                number_of_whites += 1
    shortest_path = bfs((1, 1))
    if shortest_path > 0:
        print(number_of_whites - shortest_path)
    else:
        print(-1)
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

H, W = list(map(int, input().split()))
M = [[-1]*(W+2)]
ans = 0
for _ in range(H):
    s = input()
    ans += s.count('.')
    M.append([-1]+[0 if c=='.' else -1 for c in s]+[-1])
M += [[-1]*(W+2)]

queue = [(1,1)]
M[1][1] = 1
dr = [(+1,0),(-1,0),(0,+1),(0,-1)]
turn = 1
while len(queue)>0:
    turn += 1
    queue_new = []
    for qx, qy in queue:
        for dx, dy in dr:
            x, y = qx+dx, qy+dy
            if M[y][x]==0:
                M[y][x] = turn
                queue_new.append((x,y))
    queue = queue_new

print(ans-M[H][W] if M[H][W]>0 else -1)
K = int(input())
if K==7 or K==1:
  print(1)
else:
  count = 1
  for i in range(K):
    x = (x % K) * 10 + 7
    count += 1
    if x==0:
      print(count)
  if x!=0:
    print(-1)

### FIXED CODE ###

K = int(input())
if K==7 or K==1:
  print(1)
else:
  count = 1
  x = 7%K
  for i in range(K):
    x = (x*10+7)%K
    count += 1
    if x==0:
      print(count)
      break
  if x!=0:
    print(-1)
S = input()
alphabet = list("abcdefghijklmnopqrstuvwxyz")

if S == "zyxwvutsrqponmlkjihgfedcba":
     print(-1)
        
elif len(S) < 26:
    print(S + min(set(alphabet) - set(S)))
    
else:
    for i in range(26):
        if list(S)[-i] > list(S)[-(i + 1)]:
            j = i
            T = list.copy(list(S))
            a = min(T[-j + 1:])
            while a < T[-j + 1]:
                T.remove(a)
                j -= 1
                a = min(T[-i + 1:])
            
            print("".join(S[:-(i + 1)]) + min(list(S)[-i:]))
            break

### FIXED CODE ###

S = input()
alphabet = list("abcdefghijklmnopqrstuvwxyz")

if S == "zyxwvutsrqponmlkjihgfedcba":
     print(-1)
        
elif len(S) < 26:
    print(S + min(set(alphabet) - set(S)))
    
else:
    for i in range(1, 27):
        if list(S)[-i] > list(S)[-(i + 1)]:
            break
    T = sorted(list(S)[-i:])
    #print(T)
    for t in T:
        if t > list(S)[-(i + 1)]:
            break
    print("".join(list(S)[:-(i + 1)]) + t)
N = int(input())
S = []
ans = N


for i in range(N):
    s = input()
    if i == 0:
        S.append(s)
    else:
        flg = 0
        j  = 0
        while(flg == 0 and j < len(S)):
            if S[j] == s:
                ans = ans - 1
                flg = 1
            j = j+1
        if flg == 0:
            S.append(s)
        
print(ans)

### FIXED CODE ###

S, W = map(int, input().split())
if S <= W:
    print('unsafe')
else:
    print('safe')
X = int(input())
for i in range(1, 1000):
    A = i**5
    B = (A-X)**(1/5)
    if B.is_integer():
      a = int(A)
      b = int(B)
print(f"{a} {b}")

### FIXED CODE ###

X = int(input())
flag = 1
a = -1000
b = -1000
for i in range(-1000, 1000):
  for j in range(-1000, 1000):
    if i**5-j**5 ==X:
      a = i
      b = j
print(f"{a} {b}")
import numpy as np
n,s=map(int,input().split())
t=np.zeros(s+1)
m=998244353
a=list(map(int,input().split()))
ans=0
for i in range(n):
    if a[i]<=s:
        t[a[i]:]+=t[:-a[i]]
        t[a[i]]+=i+1
    ans+=t[-1]
    ans%=m
print(int(ans))


### FIXED CODE ###

n,s=map(int,input().split())
t=[0]*(s+1)
m=998244353
a=list(map(int,input().split()))
ans=0
for i in range(n):
    d=t.copy()
    if a[i]<=s:
        for j in range(a[i],s+1):
            t[j]+=d[j-a[i]]
        t[a[i]]+=i+1
    ans+=t[-1]
    ans%=m
print(int(ans))
from math import floor

word = input()
num = int(input())
string = word*num
charlist_size=num*len(word)


char_before= ''
sum=0
count= 0

for index in range(charlist_size):
    if index == 0 :
        char_before = string[index]
        count = 1
        continue
    
    if char_before == string[index] :
        count = count + 1
    else:
        char_before = string[index]
        sum = sum+ floor(count/2)
        count = 1
    
    if index == charlist_size-1:
        sum = sum+ floor(count/2)
    
print(sum)

### FIXED CODE ###

from math import floor

word = input()
num = int(input())
length=len(word)

char_before= ''
sum=0
subsum =0
count= 0
stack=[]

for index in range(length):
    char_now=word[index]
    if index == 0 :
        char_before = char_now
        char_first=char_now
        count = 1
        if length==1:
            char_last=char_now
            stack.append(count)
        continue
    
    if char_before == char_now :
        count = count + 1
    else:
        char_before = char_now
        stack.append(count)
        count = 1
    
    if index == length-1:
        char_last=char_now
        stack.append(count)

for i in stack:
    subsum= subsum + floor(i/2)
    
if (stack[0]%2)==1 and (stack[-1]%2)==1 and char_last==char_first and len(stack)>=2:
    sum =(subsum+1)*num -1
elif len(stack)==1:
    sum = floor(length*num/2)
else:
    sum =(subsum)*num

print(sum)
from sys import stdin
from operator import mul
from functools import reduce
input = stdin.readline().rstrip

"""
まず一般に剰余込みでの組み合わせの計算。
n!, (n!)^{-1} mod pの値を配列にまとめておき、nCr = (n!)/(r!)((n-r)!)をO(1)で計算する。

max = (用意する配列の最大長)
mod = （剰余）

(n!)^{-1}の計算は¥Prod_i i^{-1}を計算して求める。
i^{-1} mod pの計算はフェルマーの小定理より、mod pにおいて
0 = p = (p // i) * i + (p % i)
0 = (p // i) + (p % i) * i^{-1}
i^{-1} = -(p // i) * (p % i)^{-1}
"""

max = 10**6
mod = 10**9+7
fact = [1, 1] # fact[n] = (n! mod p)
factinv = [1, 1] # factinv[n] = ((n!)^{-1} mod p)
inv = [0, 1] # inv[n] = (n^{-1} mod p)

for i in range(2, max+1):
    fact.append(fact[-1] * i % mod)
    inv.append(-inv[mod % i] * (mod // i) % mod)
    factinv.append(factinv[-1] * inv[-1] % mod)

def cmb(n, r):
    if r < 0 or r > n:
        return 0
    else:
        r = min(r, n-r)
        return fact[n] * factinv[r] * factinv[n-r] % mod


"""
いよいよ本題。
まずは¥Sum_{0¥le i¥le x, 0¥le j¥le y} _{i+j}C_iを計算する。
実際今回の問題は容易にこれに帰着可能。

¥Sum_{0¥le i¥le x, 0¥le j¥le y} _{i+j}C_i
    = ¥Sum_i (¥Sum_j _{i+j}C_i)
    = ¥Sum_i {(T+1)^i + (T+1)^{i+1} + ... + (T+1)^{i+y})のT^iの係数}
    = ¥Sum_i {¥frac{(1+T)^{i+y+1} - (1+T)^i}{T}のT^iの係数}
    = ¥Sum_i _{i+y+1}C_{i+1}

    = ¥Sum_i _{i+y+1}C_y
    = _{y+1}C_y + _{y+2}C_y + ... + _{y+x+1}C_y
    = {(1+T)^{y+1} + (1+T)^{y+2} + ... (1+T)^{y+x+1}のT^yの係数}
    = {¥frac{(1+T)^{x+y+2} - (1+T)^{y+1}}{T}のT^yの係数}
    = _{x+y+2}C_{y+1} - 1
"""
r1, c1, r2, c2 = map(int, input().split())
a = cmb(r2+c2+2, c2+1) - 1
b = cmb(r1+c2+1, c2+1) - 1
c = cmb(r2+c1+1, r2+1) - 1
d = cmb(r1+c1, r1) - 1
ans = a - b - c + d
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline().rstrip

"""
まず一般に剰余込みでの組み合わせの計算。
n!, (n!)^{-1} mod pの値を配列にまとめておき、nCr = (n!)/(r!)((n-r)!)をO(1)で計算する。

max = (用意する配列の最大長)
mod = （剰余）

(n!)^{-1}の計算は¥Prod_i i^{-1}を計算して求める。
i^{-1} mod pの計算はフェルマーの小定理より、mod pにおいて
0 = p = (p // i) * i + (p % i)
0 = (p // i) + (p % i) * i^{-1}
i^{-1} = -(p // i) * (p % i)^{-1}
"""

max = 10**6 * 2 + 3 # ここでRE出しまくってた。。。
mod = 10**9+7
fact = [1, 1] # fact[n] = (n! mod p)
factinv = [1, 1] # factinv[n] = ((n!)^{-1} mod p)
inv = [0, 1] # inv[n] = (n^{-1} mod p)

for i in range(2, max+1):
    fact.append(fact[-1] * i % mod)
    inv.append(-inv[mod % i] * (mod // i) % mod)
    factinv.append(factinv[-1] * inv[-1] % mod)

def cmb(n, r):
    if r < 0 or r > n:
        return 0
    else:
        r = min(r, n-r)
        return fact[n] * factinv[r] * factinv[n-r] % mod


"""
いよいよ本題。
まずは¥Sum_{0¥le i¥le x, 0¥le j¥le y} _{i+j}C_iを計算する。
実際今回の問題は容易にこれに帰着可能。

¥Sum_{0¥le i¥le x, 0¥le j¥le y} _{i+j}C_i
    = ¥Sum_i (¥Sum_j _{i+j}C_i)
    = ¥Sum_i {(T+1)^i + (T+1)^{i+1} + ... + (T+1)^{i+y})のT^iの係数}
    = ¥Sum_i {¥frac{(1+T)^{i+y+1} - (1+T)^i}{T}のT^iの係数}
    = ¥Sum_i _{i+y+1}C_{i+1}

    = ¥Sum_i _{i+y+1}C_y
    = _{y+1}C_y + _{y+2}C_y + ... + _{y+x+1}C_y
    = {(1+T)^{y+1} + (1+T)^{y+2} + ... (1+T)^{y+x+1}のT^yの係数}
    = {¥frac{(1+T)^{x+y+2} - (1+T)^{y+1}}{T}のT^yの係数}
    = _{x+y+2}C_{y+1} - 1
"""
r1, c1, r2, c2 = map(int, input().split())
a = cmb(r2+c2+2, c2+1) - 1
b = cmb(r1+c2+1, c2+1) - 1
c = cmb(r2+c1+1, r2+1) - 1
d = cmb(r1+c1, r1) - 1
ans = a - b - c + d
print(ans % mod)
N, M = map(int, input().split())
L, R = 1, N

import math

def merge_list(list):
    # sortずみ
    return (list[-1][0], min(map(lambda x: x[1], list)))

data = []
for i in range(0, M):
    l, r = input().split()
    data.append((int(l), int(r)))
data = sorted(data, key=lambda x: x[0])

# 2つずつくみでしょりしたい
def saiki(totyuu):
    if len(totyuu) < 1000:
        mid = int(math.floor(len(totyuu)/2))
        m1 = merge_list(totyuu[:mid])
        m2 = merge_list(totyuu[mid:])
        return merge_list([m1, m2])
    else:
        return merge_list([saiki(totyuu[:mid]), saiki(totyuu[mid:])])

data = saiki(data)
L = data[0]
R = data[1]

print(max(0, R-L+1))

### FIXED CODE ###

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

Ls = []
Rs = []
for i in range(0, M):
    l, r = input().split()
    Ls.append(int(l))
    Rs.append(int(r))

maxL = max(Ls)
minR = min(Rs)
result = max(0, minR-maxL+1)

print(result)
n, m, k = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]

maxrecord = 0

for i in range(1, n + 1):
    left = k - sum(a[:i])
    if left < 0:
        counter = i - 1
        if maxrecord < counter:
            maxrecord = counter
        break
    counter = i

    for j in range(1, m + 1):
        if left - sum(b[:j]) < 0:
            if maxrecord < counter:
                maxrecord = counter
            break
        counter += 1

print(counter)


### FIXED CODE ###

a = int(input())
ans = a + a ** 2 + a ** 3
print(ans)
import fractions
import numpy as np
n,x=map(int,input().split())
li=np.array(input().split(),dtype=np.int64)

li=abs(li-x)

if len(li)==1:
    print(li[0])
else:
    mini=fractions.gcd(li[0],li[1])
    for i in range(2,n):
        gc=math.gcd(mini,li[i])
        mini=min(mini,gc)
    print(mini)
    

### FIXED CODE ###

import fractions
import numpy as np
n,x=map(int,input().split())
li=np.array(input().split(),dtype=np.int64)

li=abs(li-x)

if n==1:
    print(li[0])
else:
    ans=0
    for i in li:
        ans=fractions.gcd(ans,i)
    print(ans)
import numpy as np
     
n = int(input())
a = []
lcm = 1
for i in range(n - 1):
  t = int(input())
  a.append(t)
      
lc = np.lcm.reduce(a)
     
res = 0;
for i in range(n):
  res = res + lc / a[i];
  res = res % 1000000007
     
print(res)

### FIXED CODE ###

import fractions
def LCM(a, b):
    return(a // fractions.gcd(a, b) * b)

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

for i in range(n):
    lc = LCM(lc, a[i])

res = 0;
for i in range(n):
    res = res + (lc // a[i])

print(res % 1000000007)
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
if N == K:
    result = 1
    for i in range(K):
        result = result * A[i] % M
    print(result)
    exit()
minus = [i for i in A if i < 0]
l_minus = len(minus)
plus = [i for i in A if i >= 0]
l_plus = len(plus)
plus.sort(reverse=1)
minus.sort()
if len(plus) == 0 and K % 2 == 1:
    result = 1
    for i in range(K):
        result = result * minus[-i-1] % M
    print(result)
    exit()

m_x = 0
p_x = 0
max_mm = -1
if (m_x+1) * 2 <= l_minus:
    max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
max_pp = -1
if (p_x+1) * 2 <= l_plus:
    max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
counter = 0
array = []
while counter * 2 + 1 <= K:
    if max_pp > max_mm:
        array.append(plus[p_x * 2])
        array.append(plus[p_x * 2 + 1])
        p_x += 1
        if (p_x+1) * 2 <= l_plus:
            max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
        else:
            max_pp = -1

    else:
        array.append(minus[m_x * 2])
        array.append(minus[m_x * 2 + 1])
        m_x += 1
        if (m_x+1) * 2 <= l_minus:
            max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
        else:
            max_mm = -1
    counter += 1
if K%2 == 1:
    array.append(plus[p_x * 2])
result = 1
for each in array:
    result = result * each % M
print(result)



### FIXED CODE ###

n, k = map(int, input().split())
a_list = list(map(int, input().split()))
mod = 10**9+7
a_list.sort()
ans = 1
if k % 2 == 1 and a_list[-1] < 0:
    for i in range(k):
        ans *= a_list[n - 1 - i]
        ans %= mod
else:
    l = 0
    r = -1
    mlt1 = a_list[0] * a_list[1]
    mlt2 = a_list[-2] * a_list[-1]
    count = 0
    while True:
        if count == k:
            break
        elif count == k - 1:
            ans *= a_list[r] % mod
            ans %= mod
            break
        if mlt1 >= mlt2:
            ans *= mlt1 % mod
            l += 2
            count += 2
            if l <= n - 2:
                mlt1 = a_list[l + 1] * a_list[l]
        else:
            ans *= a_list[r] % mod
            r -= 1
            count += 1
            if r >= - n + 1:
                mlt2 = a_list[r - 1] * a_list[r]
        ans %= mod
print(ans)
a,b=map(int,input())
print(a-b+1)

### FIXED CODE ###

a,b=map(int,input().split())
print(a-b+1)
while True:
    N = int(input())
    if 3
    N == 0:
        break
    S = []
    for i in range(N):
        S.append(int(input()))
    print((sum(S) - max(S) - min(S))//(len(S)-2))


### FIXED CODE ###

while True:
    N = int(input())
    if N == 0:
        break
    S = []
    for i in range(N):
        S.append(int(input()))
    print((sum(S) - max(S) - min(S))//(len(S)-2))
n = int(input())
s = int(math.sqrt(n))
a = 0
for i in range(s, 0, -1):
    if n % i == 0:
        a = i
        break
if a == 0:
    print(n - 1)
else:
    print(int((a - 1) + (n / a - 1)))

### FIXED CODE ###

import math
n = int(input())
s = int(math.sqrt(n))
a = 0
for i in range(s, 0, -1):
    if n % i == 0:
        a = i
        break
if a == 0:
    print(n - 1)
else:
    print(int((a - 1) + (n / a - 1)))