Harryxun/stf_run huggingface dataset:
# XとYの二部グラフの最大マッチング X={0,1,2,...|X|-1} Y={0,1,2,...,|Y|-1}
#   edges[x]: xとつながるYの頂点のset
#   matched[y]: yとマッチングされたXの頂点(暫定)
 
def dfs(v, visited):
    """
    :param v: X側の未マッチングの頂点の1つ
    :param visited: 空のsetを渡す（外部からの呼び出し時）
    :return: 増大路が見つかればTrue
    """
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False
 
 
# 標準入力からのグラフ読み取り
n = int(input())

r = [[0,0] for i in range(n)]
for i in range(n) :
  x,y = map(int,input().split())
  r[i][0],r[i][1] = x,y
  
b = [[0,0] for i in range(n)]
for i in range(n) :
  x,y = map(int,input().split())
  b[i][0],b[i][1] = x,y

edges = [set() for _ in range(n)]
matched = [-1] * n
  
for i in range(n) :
  for j in range(n) :
    if r[i][0] < b[j][0] and r[i][1] < b[j][1] :
      edges[i].add(j)
      
# 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる
print(sum(dfs(s, set()) for s in range(xn)))

### FIXED CODE ###

n = int(input())

r = [[0,0,1] for i in range(n)]
for i in range(n) :
  x,y = map(int,input().split())
  r[i][0],r[i][1] = x,y
  
b = [[0,0,1] for i in range(n)]
for i in range(n) :
  x,y = map(int,input().split())
  b[i][0],b[i][1] = x,y
  
r.sort(key=lambda x: x[0],reverse=True)
b.sort(key=lambda x: x[1])

ans = 0
for i in range(n) :
  for j in range(n) :
    if r[i][2] == 0 or b[j][2] == 0 :
      continue
    if r[i][0] < b[j][0] and r[i][1] < b[j][1] :
      r[i][2] = 0 ; b[j][2] = 0
      ans += 1
      
print(ans)
N = int(input())
a = list(map(int, input().split()))
a.soat(reverse=True)
A = sum([i for i in a[::2]])
B = sum([j for j in a[1::2]])
print(A - B)


### FIXED CODE ###

N = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
A = sum([i for i in a[::2]])
B = sum([j for j in a[1::2]])
print(A - B)
a=map(int, raw_input().split())
a=sorted(a)
for i in range 2:
    print a[i] 

### FIXED CODE ###

a = map(int, raw_input().split())
a.sort()
for i in range(len(a)):
    print a[i],
import math
a = list(map(int,input().split()))
print(math.gcd(a[0],a[1]))

### FIXED CODE ###

a = input().split()
x = int(a[0])
y = int(a[1])
while y:
    x, y = y, x%y
print(x)
a = raw_input()
b = raw_input()
c = raw_input()
 
print(a[0])
print(b[1])
print(c[2])

### FIXED CODE ###

a = input()
b = input()
c = input()
 
print(a[0]+b[1]+c[2])
import sys
v = iter(sys.stdin.readlines())
for i, j in v, v:
    a, b = list(i.sprit()), list(j.split())
    k = len([n for n in a for m in b if n == m])
    l = len(set(a) & set(b))
    print(l, k-l)

### FIXED CODE ###

while True:
    try:
        a, b = list(map(int,input().split())), list(map(int, input().split()))
        print(sum([1 for i in range(4) if a[i] == b[i]]),
              sum([1 for i in range(4) for j in range(4) if i != j and a[i] == b[j]]))
    except:
        break
num = input()

for i in range(1,9):
    q, mod = divmod(num, i)
    if q == 0 and 1 < q < 10:
        print("Yes")
        return
print("No")


### FIXED CODE ###

def main():
	num = int(input())
	for i in range(1,10):
		q, mod = divmod(num, i)
		if mod == 0 and q < 10:
			return "Yes"

	return "No"
if __name__ == "__main__":
    print(main())
import heapq
import sys
N,M=map(int,input().split())
A=sorted(list(map(int,input().split())))
lst=[[0,0] for _ in range(M)]
h=[]
for i in range(M):
  lst[i]=list(map(int,input().split()))
  heapq.heappush(h,[-1*lst[i][1],lst[i][0]])
i=0
while len(h)!=0:
    v=heapq.heappop(h)
    v1,v2=-1*v[0],v[1]
    if A[i]>=v1:
      print(sum(A))
      sys.exit()
    while A[i]<v1 and v2!=0:
        A[i]=v1
        i+=1
        v2-=1
    if v2>=1:
        print(sum(A))
        sys.exit()
print(sum(A))  

### FIXED CODE ###

import heapq
import sys
N,M=map(int,input().split())
A=sorted(list(map(int,input().split())))
lst=[[0,0] for _ in range(M)]
h=[]
for i in range(M):
  lst[i]=list(map(int,input().split()))
  heapq.heappush(h,[-1*lst[i][1],lst[i][0]])
i=0
while len(h)!=0:
    v=heapq.heappop(h)
    v1,v2=-1*v[0],v[1]
    while i<=N-1 and A[i]<v1 and v2!=0:
        A[i]=v1
        i+=1
        v2-=1
    if v2>=1:
        print(sum(A))
        sys.exit()
print(sum(A))
import math


def main():
    a, b, x = map(int, input().split())
    y = x / a
    s = a * b
    if y >= s / 2:
        y = (a * b) - (x / a)
        # a, b = b, a
        b_temp = 2 * y / a
        angle = math.atan(a / b_temp)
        print(90 - math.degrees(angle))
    else:
        a_temp = 2 * y / b
        angle = math.atan(b / a_temp)
        print(math.degrees(angle))



if __name__ == '__main__':
    main()


### FIXED CODE ###

import math


def main():
    a, b, x = map(int, input().split())
    y = x / a
    s = a * b
    if y == s:
        print('0.0')
    elif y >= s / 2:
        y = (a * b) - (x / a)
        b_temp = 2 * y / a
        angle = math.atan(a / b_temp)
        print(90 - math.degrees(angle))
    else:
        a_temp = 2 * y / b
        angle = math.atan(b / a_temp)
        print(math.degrees(angle))



if __name__ == '__main__':
    main()
while(1):
  H,W = map(int, raw_input().split())
  if H==0 and W==0:
    break
  for i in range(H):
    if i == 0 or i == H-1:
      print "#"*W
    else:
      print "#" + "."*(W-2)" + "#"
  print ""

### FIXED CODE ###

while(1):
  H,W = map(int, raw_input().split())
  if H == 0 and W == 0:
    break
  for i in range(H):
    if i == 0 or i == H-1:
      print "#"*W
    else:
      print "#" + "."*(W-2) + "#"
  print ""
a, b, c, x = map(int, input().split())
ans = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if x == i*500 + j*100 + k*50:
                ans +=1
print(ans)

### FIXED CODE ###

a, b, c, x = map(int, [input() for i in range(4)])
ans = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if x == i*500 + j*100 + k*50:
                ans += 1
print(ans)
line = input()

num = int(line)

if line < 1000:
    print("ABC")
else:
    print("ABD")

### FIXED CODE ###

line = input()

num = int(line)

if num < 1000:
    print("ABC")
else:
    print("ABD")
S=input()

if S=='SAT':
  print(1)
elif S=='FRI':
  print(2)
elif S=='THU':
  print(3)
elif S=='WED':
  print(4)
elif S=='TUE':
  print(5)
elif S=='MON':
  print(6)
else S=='SUN':
  print(7)


### FIXED CODE ###

S = input()

if S == "SUN":
    print(7)
elif S == "MON":
    print(6)
elif S == "TUE":
    print(5)
elif S == "WED":
    print(4)
elif S == "THU":
    print(3)
elif S == "FRI":
    print(2)
else:
    print(1)
N=int(input())
a=[]
b=[]
for i in range(N):
  a=a.append(float(input().split()))
  b=b.append(input().split())
total=0
for j in range(N):
  if b[j]=='JPY':
    total = total+ a[j]
  else:
    total = total+380000.0*a[j]
print(total)


### FIXED CODE ###

N=int(input())
a=[]
b=[]
for i in range(N):
  x,y=input().split()
  a.append(float(x))
  b.append(y)
total=0
for j in range(N):
  if b[j]=='JPY':
    total += a[j]
  else:
    total += 380000.0*a[j]
print(total)
from itertools import permutations
import sys


input = sys.stdin.readline


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

#dest = (list)(map(lambda x: (int)(x)-1, input().split()))
dest = [x-1 for x in input().split()]


inf = float('inf')
mat = [[inf]*N for _ in range(N)]
for _ in range(M):
    a, b, c = (list)(map(int, input().split()))
    mat[a-1][b-1] = mat[b-1][a-1] = c


for i in range(N):
    for j in range(N):
        for k in range(N):
            mat[j][k] = min(mat[j][k], mat[j][i]+mat[i][k])


ans = inf
for l in permutations(dest):
    tmp = 0
    for u, v in zip(l, l[1:]):
        tmp += mat[u][v]
    ans = min(ans, tmp)

print(ans)


### FIXED CODE ###

from itertools import permutations
import sys


input = sys.stdin.readline


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

dest = [x-1 for x in map(int, input().split())]


inf = float('inf')
mat = [[inf]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    mat[a-1][b-1] = mat[b-1][a-1] = c


for i in range(N):
    for j in range(N):
        for k in range(N):
            mat[j][k] = min(mat[j][k], mat[j][i]+mat[i][k])


ans = inf
for l in permutations(dest):
    tmp = 0
    for u, v in zip(l, l[1:]):
        tmp += mat[u][v]
    ans = min(ans, tmp)

print(ans)
from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = accumulate([0]+ A)
C = [(b-i)%K for i, b in enumerate(B)]
cnt = [0]*N
cnt[C[0]] = 1
res = 0
for i in range(1, N+1):
    if i >= K:
        cnt[C[i-K]] -= 1
    res += cnt[C[i]]
    cnt[C[i]] += 1
print(res)


### FIXED CODE ###

from itertools import accumulate
from collections import defaultdict
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = accumulate([0]+ A)
C = [(b-i)%K for i, b in enumerate(B)]
cnt = defaultdict(int)
cnt[C[0]] = 1
res = 0
for i in range(1, N+1):
    if i >= K:
        cnt[C[i-K]] -= 1
    res += cnt[C[i]]
    cnt[C[i]] += 1
print(res)
print(1 - input())

### FIXED CODE ###

print(1 - (int(input())))
n,m,q=map(int,raw_input().split())
lrs=[map(int,raw_input().split()) for _ in range(m)]
a=[[0 for j in range(n)] for i in range(n)]
for l,r in lrs:a[l-1][r-1]+=1
cnt=[[0 for j in range(n)] for i in range(n)]
for y in range(n):
 v = 0
 for x in range(y+1):
  v+=a[x][y]
  cnt[x][y]=cnt[x][y-1]+v
for _ in range(q):
 l,r=map(int,raw_input().split())
 print cnt[l][r] 

### FIXED CODE ###

n,m,q=map(int,raw_input().split())
lrs=[map(int,raw_input().split()) for _ in range(m)]
a=[[0 for j in range(n)] for i in range(n)]
for l,r in lrs:a[l-1][r-1]+=1
cnt=[[0 for j in range(n)] for i in range(n)]
for y in range(n):
 v = 0
 for x in range(y,-1,-1):
  v+=a[x][y]
  cnt[x][y]=cnt[x][y-1]+v
for _ in range(q):
 l,r=map(int,raw_input().split())
 print cnt[l-1][r-1]
h,w,D = map(int,input().split())
a=[]

for _ in range(h):
    b=list(map(int,input().split()))
    a.append(b)

d={}
for i in range(h):
    c=a[i]
    for j in range(w):
        d[c[j]]=(i+1,j+1)


R_min=h*w
R_max=1
query=[]
q=int(input())
for _ in range(q):
    l,r=map(int,input().split())
    query.append([l,r])
    R_min = min(l,R_min)
    R_max = max(r,R_max)


cum=[0]*(h*w)
prev=0
cum[R_min]=0
for k in range(R_min,R_max-D+1):
    prev = cum[k-1]
    cost = abs(d[k+D][0]-d[k][0]) + abs(d[k+D][1]-d[k][1])
    cum[k+D-1]=cost+prev



for j in range(q):
    l,r=query[j][0],query[j][1]

    score = cum[r-1]-cum[l-1]

    if l==r:
        score=0
    

    print(score)

### FIXED CODE ###

h,w,D = map(int,input().split())
a=[]

for _ in range(h):
    b=list(map(int,input().split()))
    a.append(b)

d={}
for i in range(h):
    c=a[i]
    for j in range(w):
        d[c[j]]=(i+1,j+1)


R_min=h*w
R_max=1
query=[]
q=int(input())
for _ in range(q):
    l,r=map(int,input().split())
    query.append([l,r])
    R_min = min(l,R_min)
    R_max = max(r,R_max)


cum=[0]*(h*w+1)
for k in range(R_min,R_max-D+1):
    prev = cum[k-1]
    cost = abs(d[k+D][0]-d[k][0]) + abs(d[k+D][1]-d[k][1])
    cum[k+D-1]=cost+prev



for j in range(q):
    l,r=query[j][0],query[j][1]
    score = cum[r-1]-cum[l-1]
    print(score)
import sys
def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0

    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            #print(dist)
            if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i==num_v-1: 
                	print("inf")
                    sys.exit()

    return dist

n,m=map(int,input().split())
es=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    es.append((a,b,-c))
    
res=BellmanFord(es,n,1)
print(-res[-1])

### FIXED CODE ###

def BellmanFord(s,N,Edge):
    INF=float("inf")
    dist=[INF]*N
    neg=[False]*N
    dist[s]=0
    for i in range(N-1):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=min(dist[t],dist[f]+c)
    for i in range(N):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=dist[f]+c
                neg[t]=True
            if neg[f]:
                neg[t]=True
    return dist,neg

n,m=map(int,input().split())
es=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    es.append((a-1,b-1,-c))
    
res, neg =BellmanFord(0,n,es)
if not neg[-1]:
    print(-res[-1])
else:
    print("inf")
s=input()
a,b,c=s.count("a"),s.count("b"),s.count("c")
print("NO"ifabs(a-b)>1 or abs(a-c)>1 or abs(b-c)>1else"YES")

### FIXED CODE ###

s = list(input())
a, b, c = s.count("a"), s.count("b"), s.count("c")
if abs(a - b) > 1 or abs(a - c) > 1 or abs(b - c) > 1:
    print("NO")
else:
    print("YES")
N = int(input())
A = [int(x) for x in input().split()]

reg = A[0]
flg=True
if 0 in A:
    print(0)
    flg=False
    reg=0
for i in range(1, N):
    reg *= a
    if reg>10**18:
        print(-1)
        flg=False
        break
if flg:
    print(reg)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]

reg = A[0]
flg=True
if 0 in A:
    print(0)
    flg=False
    reg=0
for i in range(1, N):
    reg *= A[i]
    if reg>10**18:
        print(-1)
        flg=False
        break
if flg:
    print(reg)
if S=='Sunny':
	print('Cloudy')
elif S=='Cloudy':
	print('Rainy')
else:
	print('Sunny') 

### FIXED CODE ###

S=input()
if S=='Sunny':
	print('Cloudy')
elif S=='Cloudy':
	print('Rainy')
else:
	print('Sunny')
h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(list(input()))
a=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            a+=1

visited = [[0]*w for _ in range(h)]

def dfs(s,visit,h,w):
    stack=[[0,0,1]]
    visit[0][0]=1
    while stack:
        sh,sw,c=stack.pop(0)
        if sh==h-1 and sw==w-1:
            return c
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = sh+j, sw+k
            if new_h < 0 or new_h >= h or new_w < 0 or new_w >= w:
                continue
            elif s[new_h][new_w] != "#" and visit[new_h][new_w] == 0:
                visit[new_h][new_w] = 1
                stack.append([new_h,new_w,c+1])
    return -1
  
if dfs(s,visited,h,w)==-1:
    print(-1)
else:
    print(h*w-c-a)
    
        

### FIXED CODE ###

h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(list(input()))
a=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            a+=1

visited = [[0]*w for _ in range(h)]

def dfs(s,visit,h,w,a):
    stack=[[0,0,1]]
    visit[0][0]=1
    while stack:
        sh,sw,c=stack.pop(0)
        if sh==h-1 and sw==w-1:
            return h*w-a-c
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = sh+j, sw+k
            if new_h < 0 or new_h >= h or new_w < 0 or new_w >= w:
                continue
            elif s[new_h][new_w] != "#" and visit[new_h][new_w] == 0:
                visit[new_h][new_w] = 1
                stack.append([new_h,new_w,c+1])
    return -1
  
print(dfs(s,visited,h,w,a))
def gcd(a: int, b: int)->int:
    if a < b:
        a, b = b, a
    return gcd(b, a % b) if b else a


def sum_seq1(l: int, r: int)->int:
    if r < l:
        return 0
    return r*(r+1) // 2 - l*(l-1) // 2


def sum_difference(N: int, X: int, D: int)->int:
    if D == 0:
        if X == 0:
            return 1
        return N+1

    # D != 0
    D = abs(D)

    g = gcd(X, D)
    a, b = D // g, -X // g

    if a < 0:
        a *= -1
        b *= -1

    i_range = [(float('inf'), -float('inf'))] * (N+1)

    ans = 0
    for k in range(N+1):
        kl, kr = i_range[k]
        nl = sum_seq1(0, k-1)
        nr = sum_seq1(N-k, N-1)
        # print('k: ({}, {}), n: ({}, {})'.format(kl, kr, nl, nr))

        if k+a <= N:
            i_range[k+a] = (b+min(kl, nl), b+max(kr, nr))

        if kr == -float('inf'):
            ans += nr - nl + 1
        elif kr < nl or nr < kl:
            ans += nr - nl + 1
        elif nl <= kl and kr <= nr:
            ans += (nr-nl+1) - (kr-kl+1)
        elif kl <= nl:
            ans += max(0, nr-kr)
        else:
            ans += kl-nl

    return ans


if __name__ == "__main__":
    N, X, D = map(int, input().split())
    ans = sum_difference(N, X, D)
    print(ans)


### FIXED CODE ###

def gcd(a: int, b: int)->int:
    a, b = abs(a), abs(b)
    if a < b:
        a, b = b, a
    return gcd(b, a % b) if b else a


def sum_seq1(l: int, r: int)->int:
    if r < l:
        return 0
    return r*(r+1) // 2 - l*(l-1) // 2


def sum_difference(N: int, X: int, D: int)->int:
    if D == 0:
        if X == 0:
            return 1
        return N+1

    # D != 0
    g = gcd(X, D)
    a, b = D // g, -X // g

    if a < 0:
        a *= -1
        b *= -1
    i_range = [(float('inf'), -float('inf'))] * (N+1)

    ans = 0
    for k in range(N+1):
        kl, kr = i_range[k]
        nl = sum_seq1(0, k-1)
        nr = sum_seq1(N-k, N-1)
        # print('k: ({}, {}), n: ({}, {})'.format(kl, kr, nl, nr))

        if k+a <= N:
            i_range[k+a] = (b+min(kl, nl), b+max(kr, nr))

        if kr == -float('inf'):
            ans += nr - nl + 1
        elif kr < nl or nr < kl:
            ans += nr - nl + 1
        elif nl <= kl and kr <= nr:
            ans += (nr-nl+1) - (kr-kl+1)
        elif kl <= nl:
            ans += max(0, nr-kr)
        else:
            ans += kl-nl

    return ans


if __name__ == "__main__":
    N, X, D = map(int, input().split())
    ans = sum_difference(N, X, D)
    print(ans)
from math import factorial
def C(a,b):
    return (factorial(a)//factorial(b))//factorial(a-b)
N,K=map(int,input().split())
MOD=10**9+7
for i in range(1,K+1):
    print((C(N-K+1,i)*(C(K-1,i-1)))%MOD)

### FIXED CODE ###

from math import factorial
def C(a,b):
    return (factorial(a)//factorial(b))//factorial(a-b)
N,K=map(int,input().split())
MOD=10**9+7
for i in range(1,K+1):
    if N-K+1>=i:print((C(N-K+1,i)*(C(K-1,i-1)))%MOD)
    else:print(0)
n=0
for i in map(int, input().split()):
    if i==1:
        n+= 300000
    elif i==2:
        n+= 200000
    elif i==3:
        n+= 100000
if n==600000:
    n=1000000
print(n)

### FIXED CODE ###

s = 0
for i in map(int, input().split()):
    if i == 1:
        s+=300000
    elif i ==2 :
        s+= 200000
    elif i ==3 :
        s+= 100000
if s== 600000:
    s = 1000000
print(s)
N = int(input())
s = [[0,0,0]]*(N+1)
t = [0]*(N+1)
x = [0]*(N+1)
y = [0]*(N+1)
for i in range(1,N+1):
  s[i] = input().split()
  t[i] = int(s[i][0])
  x[i] = int(s[i][1])
  y[i] = int(s[i][2])
k = 0
for i in range(N):
  T = t[i+1]-t[i]
  p = 0
  if T%2 == 0:
    for u in range((T/2)+1):
      for l in range(-2*u,2*u+1):
        if x[i]+l == x[i+1] and y[i]+2*u - max(l,-l) == y[i+1]:
          w = l
          k = k + 1
          break
        elif x[i]+l == x[i+1] and y[i]-2*u + max(l,-l) == y[i+1]:
          w = l
          k = k + 1
          break
        else:
          p = p + 1
      if (x[i]+w == x[i+1] and y[i]+2*u - max(w,-w) == y[i+1]) or (x[i]+w == x[i+1] and y[i]-2*u + max(w,-w) == y[i+1]):
        break
    if p == ((T/2)+1)(T+1):
      print('No')
      break
  
  else:
    for u in range(int((T+1)/2)):
      for l in range(-2*u-1,2*u+2):
        if x[i]+l == x[i+1] and y[i]+2*u+1 - max(l,-l) == y[i+1]:
          w = l
          k = k + 1
          break
        elif x[i]+l == x[i+1] and y[i]-2*u-1 + max(l,-l) == y[i+1]:
          w = l
          k = k + 1
          break
        else:
          w = 10000000000
          p = p + 1
      if (x[i]+w == x[i+1] and y[i]+2*u+1 - max(w,-w) == y[i+1]) or (x[i]+w == x[i+1] and y[i]-2*u-1 + max(w,-w) == y[i+1]):
        break
    if p == ((T**2)+(3*T)+2)/2:
      print('No')
      break
    
if k == N:
  print('Yes')

### FIXED CODE ###

N = int(input())
s = [[0,0,0]]*(N+1)
t = [0]*(N+1)
x = [0]*(N+1)
y = [0]*(N+1)
for i in range(1,N+1):
  s[i] = input().split()
  t[i] = int(s[i][0])
  x[i] = int(s[i][1])
  y[i] = int(s[i][2])
k = 0
for i in range(N):
  dt = t[i+1]-t[i]
  d = abs(x[i]-x[i+1]) + abs(y[i]-y[i+1])
  if d <= dt and d%2 == dt%2:
    k = k + 1
  else:
    print('No')
    break
if k == N:
  print('Yes')
X = int(input())
max_num = 1
root = math.floor(math.sqrt(X))
if root >= 2:
    for b in range(2, root+1):
        p = math.floor(math.log(X, b))
        if b**p > max_num:
            max_num = b**p
else:
    print(1)

if root >= 2:
    print(max_num)


### FIXED CODE ###

import math
X = int(input())
max = 0
bRange = math.floor(math.sqrt(X))
pRange = math.floor(math.log(X,2))
for b in range(bRange + 1):
    for p in range(pRange + 1):
        # print(b**p)
        if(max < b**p <= X):
            max = b**p
print(max)
n = int(input())
a = list(map(int,input().split()))
ans = 0
for i in range(n):
  if a[i] < a[i+1] < a[i+2]:
    ans += 1
print(ans)
  

### FIXED CODE ###

n = int(input())
s = list(map(int,input().split()))
ans = 0
for i in range(n-2):
    a,b,c = s[i:i+3]
    if a<b<c or c<b<a:  ans += 1
print(ans)
def pickup(S,ans):
    l = len(S)
    if l<2:
        return ans
    check_dif = False
    #print(S)
    for i in range(l-1):
        if S[i] != S[i+1]:
            S.pop(i)
            S.pop(i)
            #print(S)
            check_dif = True
            ans += pickup(S,ans)
            break
    if check_dif:
        ans+=2
    return ans   
S=input()
l = len(S)
S_list = [S[i] for i in range(l)]
ans =0
print(pickup(S_list,ans))

### FIXED CODE ###

S=input()
num_one=S.count('1')
num_zero=S.count('0')
ans = 2*min(num_one,num_zero)
print(ans)
S = raw_input();
S = S.replace(",", " ");
print(S);

### FIXED CODE ###

S = input();
S = S.replace(",", " ");
print(S);
a=int(input('a '))
b=int(input('b '))
if (a*b)%2 ==1:
	print('Odd')
else:
	print('Even')

### FIXED CODE ###

a,b=map(int,input().split())
if (a*b)%2 ==0:
  print('Even')
else:
  print('Odd')
n=int(input())
data = [input() for i in range(n)]
sum=0
for i in range(n):
  sum = sum + 1/data[i]
print(1/sum)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
sum=0
for i in a:
  sum = sum + 1/i
print(1/sum)
def main():
    n = int(input()) 
	t = [int(input()) for i in range(n)] 
    print(t[1]*2 - t[0])

### FIXED CODE ###

import sys

a = []
for line in sys.stdin:
    a.append(int(line))
print(a[1] * 2 - a[0])
#ABC129C-TypicalStairs.py

#import list
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(100000)

#constant
#N = int(input())
N, M = list(map(int,input().split()))
A = [int(input()) for _ in range(M)]

#variable

#function
@lru_cache(maxsize=1000)
def rootCount(position):
    if position < 0:
        return 0
    elif position == 0:
        return 1
    elif position in A:
        return 0
    else:
        return (rootCount(position-1)+rootCount(position-2)) % 1000000007
#class

#main function
def main():
    print(rootCount(N))

if __name__ == "__main__":
    main()


### FIXED CODE ###

#ABC129C-TypicalStairs.py

#import list
import numpy as np
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(1000)

#constant
#N = int(input())
N, M = list(map(int,input().split()))
A = {int(input()) for _ in range(M)}

#variable
rootList = np.array([1]+[0]*(N))

#function

#class

#main function
def main():
    for i in range(N):
        rootList[i+1] = (rootList[i]+rootList[i-1])%1000000007
        if i+1 in A:
            rootList[i+1] = 0
    print(rootList[N])

if __name__ == "__main__":
    main()
import numpy as np

N = int(input())
x_list = np.repeat(list(map(int, input().split())), N).reshape(N,N)

print(np.sum(np.sum(x_list%x_list[:,0]==0, axis=1)==1))



### FIXED CODE ###

N = int(input())
a_list = sorted(list(map(int, input().split())))
a_max = a_list[-1]

count = [0] * (a_max+1)

for a in a_list:
  for j in range(a, a_max+1, a):
    count[j] += 1
  
ans = 0
for a in a_list:
  if count[a] == 1:
    ans += 1
print(ans)
n = input()

money = 0
if int(n)%1000 == 0:
    print(0)
else:
    money = (int(n[:-3]) + 1)*1000 
    ans = money - int(n)
    print(ans)


### FIXED CODE ###

n = input()

money = 0
if int(n)%1000 == 0:
    print(0)
elif 1000 > int(n):
    ans = 1000 - int(n)
    print(ans)
else:
    money = (int(n[:-3]) + 1)*1000
    ans = money - int(n)
    print(ans)