Harryxun/stf_run huggingface dataset:
N, Q = map(int, input().split())
S = input()

nums = [0] * (N+1) 
count = 0
for i in range(len(S)):
    nums[i] = count
    if S[i] == "A" and S[i+1] == "C":
        count += 1

"""
for _ in range(Q):
    l,r = map(int, input().split())
    print(nums[r-1] - nums[l-1])
"""

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

nums = [0] * N
count = 0
for i in range(len(S)-1):
    nums[i] = count
    if S[i] == "A" and S[i+1] == "C":
        count += 1
nums[-1] = count

for _ in range(Q):
    l,r = map(int, input().split())
    print(nums[r-1] - nums[l-1])
import sys
input = sys.stdin.readline

def main():
    N, M, P = map( int, input().split())
    d = dict()
    for _ in range(M):
        a, b, c = map( int, input().split())
        a, b = a-1, b-1
        d[(a,b)] = P-c

    V = [None]*N
    V[0] = 0
    for _ in range(N-1):
        for e in d:
            s, t = e
            if V[s] == None:
                continue
            if V[t] == None:
                V[t] = V[s] + d[e]
                continue
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]
    W = [V[i] for i in range(N)]
     for _ in range(1):
        for e in d:
            s, t = e
            if V[s] == None:
                continue
            if V[t] == None:
                V[t] = V[s] + d[e]
                continue
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]
    for i in range(N):
        if V[i] < W[i]:
            V[i] = -10**14*2
    for _ in range(1):
        for e in d:
            s, t = e
            if V[s] == None:
                continue
            if V[t] == None:
                V[t] = V[s] + d[e]
                continue
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]
    # ans = V[N-1]
    # for _ in range(N):
    #     for e in d:
    #         s, t = e
    #         if V[s] + d[e] < V[t]:
    #             V[t] = V[s] + d[e]

    # if V[N-1] < ans:
    #     print(-1)
    #     return
    # print( max(-ans,0))
    if V[-1] <= -10**14:
        print(-1)
    else:
        print(max(-V[-1],0))
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
from copy import deepcopy
def main():
    N, M, P = map( int, input().split())
    E = []
    rE = [[] for _ in range(N)]
    
    for _ in range(M):
        a, b, c = map( int, input().split())
        a, b = a-1, b-1
        E.append((a,b,c-P))
        rE[b].append(a)
    # 頂点Nに到達する頂点
    G = [False]*N
    G[N-1] = True
    q = deque([N-1])
    while q:
        v = q.popleft()
        for w in rE[v]:
            if G[w] == False:
                G[w] = True
                q.append(w)
    # Bellman-Ford
    V = [None]*N
    V[0] = 0
    I = sum([1 for i in range(N) if G[i] == True])
    for _ in range(I-1):
        for s, t, cost in E:
            if V[s] == None or G[t] == False:
                continue
            if V[t] == None:
                V[t] = V[s] + cost
                continue
            if V[s] + cost > V[t]:
                V[t] = V[s] + cost
    W = deepcopy(V) #[ V[i] for i in range(N)]
    for _ in range(I-1):
        for s, t, cost in E:
            if V[s] == None or G[t] == False:
                continue
            if V[t] == None:
                V[t] = V[s] + cost
                continue
            if V[s] + cost > V[t]:
                V[t] = V[s] + cost
    for i in range(N):
        if W[i] == None or G[i] == False:
            continue
        if V[i] > W[i]: # 頂点iは、頂点Nに到達するので、負（正？）閉路は伝播する
            print(-1)
            return

    print( max(W[-1], 0))
if __name__ == '__main__':
    main()
a,b,h = map(int,input().split())

answer = (a + b) * h / 2

print(int(answer))

### FIXED CODE ###

a =int(input())
b =int(input())
h = int(input())

answer = (a + b) * h / 2

print(int(answer))
n, m, k = map(int, input().split(' '))
list_a = list(map(int, input().split(' ')))
list_b = list(map(int, input().split(' ')))

a_sum=[list_a[0]]
for i in range(1, n):
  sum=list_a[i]+a_sum[i-1]
  a_sum.append(sum)
  
b_sum=[list_b[0]]
for i in range(1, m):
  sum=list_b[i]+b_sum[i-1]
  b_sum.append(sum)
  
ans=[]
if (a_sum[0]>k) & (b_sum[0]>k):
  print(0)
else:
  for i in range(n):
    for j in range(m):
      if a_sum[i]+b_sum[j] <= k:
        key=i+j+2
        if key not in ans:
          ans.append(key)

print(max(ans))

### FIXED CODE ###

n, m, k = map(int, input().split(' '))
list_a = list(map(int, input().split(' ')))
list_b = list(map(int, input().split(' ')))
 
a_sum=[list_a[0]]
for i in range(1, n):
  a_sum.append(list_a[i]+a_sum[i-1])
  
b_sum=[list_b[0]]
for i in range(1, m):
  b_sum.append(list_b[i]+b_sum[i-1])

  
ans=0 
if (a_sum[0]>k) and (b_sum[0]>k):
  print(0)
else:
  for j in range(m):
    if b_sum[j]<=k:
      ans=max(ans, j+1)
  j=m-1
  for i in range(n):
    if a_sum[i]<=k:
      ans=max(ans, i+1)
      while a_sum[i] + b_sum[j] > k and j>0:
        j-=1
      if a_sum[i]+b_sum[j]<=k:
        ans=max(ans, i+j+2)
  print(ans)
n, k = map(int, input().split())
p = list(map(int, input().split()))
  
s = []
sump = 0
for i in range(n):
  sump += (p[i] + 1) / 2
  s.append(sump)
  
ans = set()
for i in range(k, n):
  ans.add(s[i]-s[i-1])
  
if n == 1:
  print(s[0])
else:
  print(max(ans))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
  
m = sum(p[0: k])
sump = m

for i in range(1, n-k+1):
  sump = sump - p[i-1] + p[i+k-1]
  if m < sump:
    m = sump

ans = (m + k) / 2

print(ans)
a,b,c,k=map(int,input().split())
l=[1]*a+[0]*b+[-1]*c
print(sum(l[:k]))

### FIXED CODE ###

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

a,b,c,k = iim()
if k < a:
    print(k)
elif k <= a+b:
    print(a)
else:
    print(a+(k-a-b)*(-1))
S=input().split(“ “)
A=int(S[0])
B=int(S[2])
C=S[1]
if S[1]==“+”
    print(A+B)
if S[1]==“-”
    print(A-B)

### FIXED CODE ###

S=input().split()
A=int(S[0])
B=int(S[2])
C=S[1]
if S[1]=="+":
    print(A+B)
if S[1]=="-":
    print(A-B)
n = int(input())
s = 0
for i in n:
    s += n[i]

print(["No","Yes"][n%s == 0])

### FIXED CODE ###

n = int(input())
s = 0
for i in str(n):
    s += int(i)
print("Yes" if n%s == 0 else "No")
# coding: utf-8
# Your code here!

import numpy as np
import bisect

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

ab = []
for _ in range(n):
    ab.append(list(map(int, list(input().split()))))
ab = np.array(ab)
max_a = max(ab[:,0])

dp = [int(1e9)] * int(1e6)
checked = [False] * int(1e6)
dp[0] = 0

sorted_list = [0]
while len(sorted_list) > 0:
    v = sorted_list.pop(0)
    
    if v > h:
        break
    
    for i in range(n):
        if checked[v + ab[i, 0]] == False:
            bisect.insort_right(sorted_list, v + ab[i, 0])
            checked[v + ab[i, 0]] = True
        dp[v + ab[i,0]] = min(dp[v + ab[i,0]], dp[v] + ab[i,1])
    
print(min(dp[v-1:]))


### FIXED CODE ###

# coding: utf-8
# Your code here!

import bisect

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

ab = []
max_a = 0
for _ in range(n):
    ab.append(list(map(int, list(input().split()))))
    max_a = max(max_a, ab[-1][0])

dp = [int(1e9)] * int(1e6)
checked = [False] * int(1e6)
dp[0] = 0

sorted_list = [0]
while len(sorted_list) > 0:
    v = sorted_list.pop(0)
    
    if v > h:
        break
    
    for i in range(n):
        if checked[v + ab[i][0]] == False:
            bisect.insort_right(sorted_list, v + ab[i][0])
            checked[v + ab[i][0]] = True
        dp[v + ab[i][0]] = min(dp[v + ab[i][0]], dp[v] + ab[i][1])
    
print(min(dp[v-1:]))
n = int(input())
ans = factorial(n) % (10 ** 9 + 7)
print(ans)


### FIXED CODE ###

from math import factorial

n = int(input())
ans = factorial(n) % (10 ** 9 + 7)
print(ans)
import itertools

s = 'ACGT'
s = [a+b+c for a,b,c in itertools.product(s,s,s)]
n = {s_:1 for s_ in s}
n['AGC'] = 0
n['GAC'] = 0
n['ACG'] = 0

N = int(input())

for i in range(N-3):
    count = {s_:0 for s_ in s}
    for _ in s:
        for a in 'ACGT':
            x = _+a
            if 'GAC' in x or 'ACG' in x or ('A' == x[0] and 'GC' == x[2:]) or ('AG' == x[:2] and 'C' == x[3]):
                pass
            else:
                count[x[1:]] += n[_]
    count['AGC'] = 0
    count['GAC'] = 0
    count['ACG'] = 0
    n = count
print(sum([value for value in count.values()])%(10**9+7))

### FIXED CODE ###

import itertools

s = 'ACGT'
s = [a+b+c for a,b,c in itertools.product(s,s,s)]
n = {s_:1 for s_ in s}
n['AGC'] = 0
n['GAC'] = 0
n['ACG'] = 0

N = int(input())
if N == 3:
    count = n
else:
    for i in range(N-3):
        count = {s_:0 for s_ in s}
        for _ in s:
            for a in 'ACGT':
                x = _+a
                if 'GAC' in x or 'ACG' in x or ('A' == x[0] and 'GC' == x[2:]) or ('AG' == x[:2] and 'C' == x[3]):
                    pass
                else:
                    count[x[1:]] += n[_]
        count['AGC'] = 0
        count['GAC'] = 0
        count['ACG'] = 0
        n = count
print(sum([value for value in count.values()])%(10**9+7))
a, p = map(int, input().split())
print(sum(3 * a + p)//2)


### FIXED CODE ###

a, p = map(int, input().split())
total = 3 * a + p
print(total//2)
N, K = map(int, input().split())
TD = []
for _ in range(N):
    TD.append(list(map(int, input().split())))
TD.sort(key=lambda x: -x[1])

tmp_list = TD[:K]
removable_list = []
S = set()
base_pt = 0
for t, d in tmp_list:
    if t in S:
        removable_list.append([t, d])
    else:
        S.add(t)
    base_pt += d
kind = len(S)
removable_list.sort(key=lambda x: x[1])

pt = [base_pt + kind*kind]
i = 0
for t, d in TD[K:]:
    if t in S:
        continue
    kind += 1
    base_pt += d - removable_list[i][1]
    pt.append(base_pt + kind*kind)
    i += 1
print(max(pt))

### FIXED CODE ###

N, K = map(int, input().split())
TD = []
for _ in range(N):
    TD.append(list(map(int, input().split())))
TD.sort(key=lambda x: -x[1])

removable_list = []
S = set()
base_pt = 0
for t, d in TD[:K]:
    if t in S:
        removable_list.append([t, d])
    else:
        S.add(t)
    base_pt += d
kind = len(S)
removable_list.sort(key=lambda x: x[1])

addable_list = []
for t, d in TD[K:]:
    if t in S:
        continue
    addable_list.append([t, d])
    S.add(t)

pt = [base_pt + kind*kind]
l = min(len(removable_list), len(addable_list))

for rl, al in zip(removable_list[:l], addable_list[:l]):
    kind += 1
    base_pt += al[1] - rl[1]
    pt.append(base_pt + kind*kind)
print(max(pt))
N = int(input())

ans1 = 0

A = '1'
B = str(N)

if len(A)>=len(B):
    ans = len(A)
else:
    ans = len(B)
    
for i in range(2,int(math.sqrt(N)+1):
    A = i
    if N%A==0:
        B = int(N / A)
        A = str(A)
        B = str(B)
        if len(A)>=len(B):
            ans1 = len(A)
        else:
            ans1 = len(B)
        if ans1 <= ans:
            ans = ans1
    if len(str(A))==len(str(B)):
        break
print(ans)


### FIXED CODE ###

import math

N = int(input())

ans1 = 0

A = '1'
B = str(N)

if len(A)>=len(B):
    ans = len(A)
else:
    ans = len(B)
    
for i in range(2,int(math.sqrt(N))+1):
    A = i
    if N%A==0:
        B = int(N / A)
        A = str(A)
        B = str(B)
        if len(A)>=len(B):
            ans1 = len(A)
        else:
            ans1 = len(B)
        if ans1 <= ans:
            ans = ans1
    if len(str(A))==len(str(B)):
        break
print(ans)
N = int(input())
A = list(map(int,input().split()))
A.sort()
sum = 0
ans = 0
zeroflg = 0

for i in range(len(A)-2):
    if N%2 == 0 and A[0] == 1 and A[N-1] == N-1:
        if N == 2:
            if A[0] == A[1]:
                sum = 2**(N/2)
            else:
                zeroflg = 1
        elif N > 2:
            if A[0] == A[1]:
                if  i%2 == 0 and A[i + 2] - A[i] == 2 and A[i + 1] - A[i] == 0:
                    sum = 2**(N/2)
                elif i%2 == 1 and A[i + 2] - A[i] == 2 and A[i + 1] - A[i] == 2:
                    sum = 2**(N/2)
                else:
                    zeroflg = 1
            else:
                zeroflg = 1
    elif N%2 == 1 and A[0] == 0 and A[N-1] == N-1:
        if N == 1:
            sum = 2**(N//2)
        elif N > 1: 
            if i%2 == 0 and A[i + 2] - A[i] == 2 and A[i + 1] - A[i] == 2:
                sum = 2**(N//2)
            elif i%2 == 1 and A[i + 2] - A[i] == 2 and A[i + 1] - A[i] == 0:
                sum = 2**(N//2)
            else:
                zeroflg = 1

if zeroflg == 1:
    print(ans)
else:
    ans = int(sum)
    ans%(10**9+7)
    print(ans)


    

### FIXED CODE ###

# ABC050 C - Lining Up
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
a.sort()

if n%2==0:
    for aa in a:
        if aa%2==0:
            print(0)
            exit()
    
    for i in range(n):
        if i%2==0:
            if a[i]!=a[i+1]:
                print(0)
                exit()
    print((2**(n//2))%mod)
else:
    for aa in a:
        if aa%2==1:
            print(0)
            exit()
    for i in range(n-1):
        if a[0]!=0:
            print(0)
            exit()
        if i%2==1:
            if a[i]!=a[i+1]:
                print(0)
                exit()
    print((2**(n//2))%mod)
n,m = map(int,input().split())
a = []
a.append(0)
for i in range(m):
    b = int(input())
    b -= 1
    a.append(b)
a.append(n)
b = []

for i in range(1,n):
    b.append(fib(i))

c = []
if a[1] == 0:
    c.append(1)
else:
    c.append(b[a[1] - a[0] ])
i = 1
while i <= m:
    if a[i + 1] - a[i] - 2 >= 0:
        c.append(b[a[i + 1] - a[i]  - 2])
        i += 1
    #elif a[i + 1] - a[i] - 2 == 0:
        #c.append(1)
    else:
        c.append(0)
        break
#print(c)
d = c[0] 
i = 1
#print(d)
while i < len(c):
    d = d * c[i]
    i += 1
e = 1000000007
print(d % e)
#print(b[0])

### FIXED CODE ###

n,m = map(int,input().split())
mod = 10**9 + 7
a = [1] * (n+1)
for i in range(m):
    b = int(input())
    a[b] = 0

        
for i in range(2,n+1):
    if a[i] != 0:
        a[i] = a[i-1] + a[i-2]
#print(a)
print(a[n] % mod)
import string


S = input()
retS = ''
alphabetsStr = string.ascii_lowercase
alphabets = list(map(lambda x: x, string.ascii_lowercase))
lastWord = ''.join(alphabets[::-1])

if len(S) == 26:
    if S == lastWord: print(-1)
    else:
        for i  in S:
            if alphabets[i] != S[i]:
                retS = S[:i] + alphabets[i]
                break
else:
    for s in alphabets:
        if s not in S:
            retS = S + s
            break
print(retS)

### FIXED CODE ###

import string

S = input()
reversedS = ''.join(list(S)[::-1])
alphabets = list(string.ascii_lowercase)
lastWord = ''.join(alphabets[::-1])
cnt = [S.count(chr(ord('a')+i)) for i in range(26)]
if len(S) == 26:
    if S == lastWord: print(-1)
    else:
        found = False
        for i in range(len(reversedS)):
            s = reversedS[i]
            largeS = alphabets[ord(s)-ord('a')+1:]
            tailS = list(S)[26-i-1:]
            for lS in largeS:
                if lS in tailS:
                    print(S[:26-i-1]+lS)
                    found = True
                    break
            if found: break
else:
    for j in range(26):
        if cnt[j] == 0:
            S += chr(ord('a')+j)
            print(S)
            break
n,m = map(int,input().split())

if n==1 and m==1:
    ans = 1
elif n==1 or m==1:
    ans = n*m-2
else:
    ans = (n-2)*(m-2)

print(ans)

### FIXED CODE ###

n = 3
ans = ""
for i in range(n):
    text = input()
    ans += text[i]

print(ans)
K = int(input())
n = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(n[K])

### FIXED CODE ###

K = int(input())
n = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(n[K-1])
N = input()
ans = 0
for n in N:
  ans += int(ans)
if int(N) % ans == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = input()
ans = 0
for n in N:
  ans += int(n)
if int(N) % ans == 0:
  print("Yes")
else:
  print("No")
def answer(H,W,ans):
    for x in range(1,W):
        y1 = H // 2
        Sa1 = H * x
        Sb1 = (W - x) * y1
        Sc1 = (W - x) * (H - y1)
        M = max(Sa1,Sb1,Sc1)
        m = min(Sa1,Sb1,Sc1)

        y2 = (W - x) // 2
        Sa2 = H * x
        Sb2 = H * y2
        Sc2 = H * (W - x - y2)
        M2 = max(Sa2,Sb2,Sc2)
        m2 = min(Sa2,Sb2,Sc2)

        if ans > min(M-m,M2-m2):
            ans = min(M-m,M2-m2)

        return ans

if __name__ == '__main__':
    H,W = [int(i) for i in input().split()]
    ans = H * W
    ans = answer(H,W)
    
    H,W = W,H

    if answer(H,W) < ans:
        ans = answer(H,W)

    print(ans)


### FIXED CODE ###

H,W = [int(i) for i in input().split()]
ans = H * W

for x in range(1,W):
    y1 = H // 2
    Sa1 = H * x
    Sb1 = (W - x) * y1
    Sc1 = (W - x) * (H - y1)
    M = max(Sa1,Sb1,Sc1)
    m = min(Sa1,Sb1,Sc1)

    y2 = (W - x) // 2
    Sa2 = H * x
    Sb2 = H * y2
    Sc2 = H * (W - x - y2)
    M2 = max(Sa2,Sb2,Sc2)
    m2 = min(Sa2,Sb2,Sc2)

    if ans > min(M-m,M2-m2):
        ans = min(M-m,M2-m2)

H,W = W,H
for x in range(1,W):
    y = H // 2
    Sa1 = H * x
    Sb1 = (W - x) * y
    Sc1 = (W - x) * (H - y)
    M = max(Sa1,Sb1,Sc1)
    m = min(Sa1,Sb1,Sc1)

    y2 = (W - x) // 2
    Sa2 = H * x
    Sb2 = H * y2
    Sc2 = H * (W - x - y2)
    M2 = max(Sa2,Sb2,Sc2)
    m2 = min(Sa2,Sb2,Sc2)

    if ans > min(M-m,M2-m2):
        ans = min(M-m,M2-m2)

print(ans)
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
diff = abs(K - N)

if N < K:
    print(N)
    exit()

if N % K == 0:
    print(0)
else:
    print(min(K - N%K), N%K)



### FIXED CODE ###

import sys

input = sys.stdin.readline

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

if N < K:
    print(min(N, K - N))
    exit()

if N % K == 0:
    print(0)
else:
    print(min(K - N%K, N%K))
a = input()
K = int(a)

x = 'ACL'

for i in K:
    print(x, end = "")


### FIXED CODE ###

a = input()
K = int(a)

x = 'ACL'

for i in range(K):
    print(x, end = "")
W,H,N=map(int,input().split())
x1=0
x2=W
y1=0
y2=H
for i in range(N):
    x,y,a=map(int,input().split())
    if a==1:
        x1=max(x1,x)
    elif a==2:
        x2=min(x,x2)
    elif a==3:
        y1=max(y1,y)
    elif a==4:
        y2=min(y,y2)
if x2<x1 or y2<y1:
    print(0)
    sys.exit()
print(x1,x2,y1,y2)
xx=x2-x1
yy=y2-y1
print(xx*yy)

### FIXED CODE ###

W,H,N=map(int,input().split())
x1=0
x2=W
y1=0
y2=H
for i in range(N):
    x,y,a=map(int,input().split())
    if a==1:
        x1=max(x1,x)
    elif a==2:
        x2=min(x,x2)
    elif a==3:
        y1=max(y1,y)
    elif a==4:
        y2=min(y,y2)
if x2<x1 or y2<y1:
    print(0)
    exit()
xx=x2-x1
yy=y2-y1
print(xx*yy)
import sys
from functools import lru_cache
sys.setrecursionlimit(10000)

@lru_cache(maxsize = None)
def rec(i, j):
    flag = False
    flag_ = False
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - i)
    if tmp > dp[i+1][j]:
        dp[i+1][j] = tmp
        flag = True
    tmp_ = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - N + j + 1)
    if tmp_ > dp[i][j+1]:
        dp[i][j+1] = tmp_ if tmp_ > dp[i][j+1] else dp[i][j+1]
        flag_ = True
    if i + j == N - 1:
        return
    if flag:
        rec(i + 1, j)
    if flag_:
        rec(i, j + 1)
    
N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]

dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
rec(0, 0)
ans = -1
for i in range(N):
    for j in range(N):
        if dp[i][j] > ans:
            ans = dp[i][j]
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
B = [0]*N
for i in A:
    B[i-1] += 1
for i in B:
    print(i)
N = int(input())
A = N.split(" ")
A = list(map(int, A))
result = A[0]
for i in range(1,N):
  result = result*A[i]
  if result*A[i] > 10**18:
    result = -1
print(result)

### FIXED CODE ###

N = int(input())
A = input()
A = A.split(" ")
A = list(map(int, A))
result = 1
for i in range(N):
  result = result*A[i]
  if result > 10**18:
    result = 10**18 + 1
if result == 10**18 + 1:
   result = -1
print(result)
#!/mnt/c/Users/moiki/bash/env/bin/python
N,P = list(map(int, input().split()))
import math


def get_prime(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]

primax = int(1e7) + 9 * int(1e6)
primes = get_prime(primax)
# print(primes)



def df(P, p):
    if P >= p:
        cnt = 0
        while P >= p and P % p == 0:
            P = int(P//p)
            cnt += 1
        return cnt
    else:
        raise "P , p error."

gc = []
for p in primes:
    if P % p == 0:
        cnt = df(P, p)
        P = int( P // int(p**cnt))
        gc.append([p, cnt])
ans = 1
for g,cnt in gc:
    if cnt >= N:
        ans *= g**(cnt//N)

debug = 1
for g,cnt in gc:
    debug *= g**cnt

# N > 100:  why WA
# debug < P: under 3 RE
# debug*2 > P:  None
if P > 1e9 and debug != P and  debug < P and N == 1:
    raise "errror"
print(ans)


### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,P = list(map(int, input().split()))
import math

if N == 1:
    print(P)
    exit(0)

def get_prime(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]

primax = int(1e7) + 9 * int(1e6)
primes = get_prime(primax)
# print(primes)



def df(P, p):
    if P >= p:
        cnt = 0
        while P >= p and P % p == 0:
            P = int(P//p)
            cnt += 1
        return cnt
    else:
        raise "P , p error."

gc = []
for p in primes:
    if P % p == 0:
        cnt = df(P, p)
        P = int( P // int(p**cnt))
        gc.append([p, cnt])
ans = 1
for g,cnt in gc:
    if cnt >= N:
        ans *= g**(cnt//N)

debug = 1
for g,cnt in gc:
    debug *= g**cnt

# N > 100:  why WA
# debug < P: under 3 RE
# debug*2 > P:  None
if P > 1e9 and debug != P and  debug < P and N == 1:
    raise "errror"
print(ans)
s=[int,input() for _ in range(6)]
print(':(') if s[4]-s[0]>s[5] else print('Yay!')

### FIXED CODE ###

s=[int(input()) for _ in range(6)]
print(':(') if s[4]-s[0]>s[5] else print('Yay!')
map(print,[int(n) for n in stdin].sort(reverse=True)[0:3])

### FIXED CODE ###

from sys import stdin

for x in sorted([int(l) for l in stdin],reverse=True)[0:3]:
  print(x)
n,k = map(int,input().split())
p_list = list(map(int,input().split()))
ruiseki = []
a = 0
for i in range(n):
  a += p_list[i]
  ruiseki.append(a)
res = -1
val_list = []
for m in range(n-k):
  val = ruiseki[k+m] - ruiseki[m]
  val_list.append(val)
print((max(val_list)+k)/ 2) 


### FIXED CODE ###

n,k = map(int,input().split())
p_list = list(map(int,input().split()))
ruiseki = []
a = 0
for i in range(n):
  a += p_list[i]
  ruiseki.append(a)
res = -1
val_list = []
for m in range(n-k):
  val = ruiseki[k+m] - ruiseki[m]
  val_list.append(val)
if n ==k :
  	print((sum(p_list) + k)/2)
else:
	print((max(val_list)+k)/ 2)
import math
n, x = map(int, input().split())
a = list(map(int, input().split()))
a.append(x)
a.sort()
t = 0
for i in range(n):
    if i == 0:
        t = a[1] - a[0]
    else:
        t = math.gcd(t, a[i + 1] - a[i])
print(t)


### FIXED CODE ###

from fractions import gcd
N, X = map(int, input().split())
kotae = list(map(int, input().split()))
kotae.append(X)
kotae.sort()
t = kotae[1]-kotae[0]
for i in range(len(kotae)-1):
    t = gcd(t, abs(kotae[i + 1] - kotae[i]))
print(t)