Harryxun/stf_run huggingface dataset:
def dfs():
  while len(q) > 0:
  	p = q.pop()
  	for e in g[p]:
      if d[e] < 0 or d[e] > d[p] + 1:
        d[e] = d[p] + 1
        q.append(e)
  
  
n, m = map(int, input().split())
g = [[] for i in range(3 * (n+1))]
for i in range(m):
  u, v = map(int, input().split())
  g[3*u].append(3*v+1)
  g[3*u+1].append(3*v+2)
  g[3*u+2].append(3*v)

s, t = map(int, input().split())

d = [-1] * (3 * (n+1))
d[3*s] = 0

q = [3*s]
dfs()
print(d[3*t])



### FIXED CODE ###

from collections import deque
def bfs():
  while len(q) > 0:
    p = q.popleft()
    for e in g[p]:
      if d[e] < 0:
        q.append(e)
        d[e] = d[p] + 1
        f[e] = p
      elif d[e] > d[p] + 1:
        d[e] = d[p] + 1
        f[e] = p       

  
  
n, m = map(int, input().split())
g = [[] for i in range(3 * (n+1))]
for i in range(m):
  u, v = map(int, input().split())
  g[3*u].append(3*v+1)
  g[3*u+1].append(3*v+2)
  g[3*u+2].append(3*v)

s, t = map(int, input().split())

d = [-1] * (3 * (n+1))
f = [-1] * (3 * (n+1))
d[3*s] = 0
f[3*s] = 0
q = deque([3*s])
bfs()
c = 0
if f[3*t] == -1:
  print(-1)
  exit()

t = 3 * t
while f[t] > 0:
  c += 1
  t = f[t]
  
print(c // 3)
N = int(input())
for i in range(6):
  if 2**(i+1)<=N:
    a=2**(i+1)
print(a)

### FIXED CODE ###

N = int(input())
a=1
for i in range(6):
  if 2**(i+1)<=N:
    a=2**(i+1)
print(a)
def p_a():
    H, W, A, B = map(int, input().split())

    if H % A != 0 or W % B != 0:

        if H < A * 2 or W < B * 2:
            print("No")
            exit()

        if H > A * 3 or W > B * 3:
            print("No")
            exit()

    S = [[0] * W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if j // B == 1 and i // A == 1:
                S[i][j] = 1

            if j // B == 1:
                continue

            if i // A == 1:
                continue

            S[i][j] = 1

    for i in range(H):
        print(*S[i], sep="")


if __name__ == '__main__':
    p_a()


### FIXED CODE ###

def p_a():
    H, W, A, B = map(int, input().split())

    S = [[0] * W for _ in range(H)]

    if A == 0 and B == 0:
        for i in range(H):
            print(*S[i], sep="")
        exit()

    for i in range(H):
        for j in range(W):
            if A == 0:
                if i < B:
                    S[i][j] = 1
                continue
            elif B == 0:
                if j < A:
                    S[i][j] = 1
                continue

            if i // B == 1 and j // A == 1:
                S[i][j] = 1

            if i // B == 1:
                continue

            if j // A == 1:
                continue

            S[i][j] = 1

    for i in range(H):
        print(*S[i], sep="")


if __name__ == '__main__':
    p_a()
s=input()
flag=True
for i in range(0,len(s),2):
  if "hi"=ar[i:i+2]:
    continue
  else:
    flag=False
    break
if flag==True:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s=input()
flag=True
for i in range(0,len(s),2):
  if "hi"==s[i:i+2]:
    continue
  else:
    flag=False
    break
if flag==True:
  print("Yes")
else:
  print("No")
import math
NK = input().split()
N = int(NK[0])
K = int(NK[1])
if N==1 or K==1:
    print(0)
    exit()
elif N==0:
    print(K)
else:
    print(math.gcd(N,K))


### FIXED CODE ###

NK = input().split()
N = int(NK[0])
K = int(NK[1])
if N%K<K-N%K:
    print(N%K)
else:
    print(K-N%K)
a,b,c = map(int, raw_input().split)

count=0
for x in range(a,b+1):
    if  c%x == 0:
     print(str(count+=1) + x)
       
  

### FIXED CODE ###

a,b,c = map(int, raw_input().split())

count=0
for x in range(a,b+1):
    if  c%x == 0:
       count += 1
print(count)
n=int(input())
x=list(map(int,input().split()))

x.sort()
ans=0

for i range(n):
  ans+=x[i*2]
    
print(ans)


### FIXED CODE ###

N = int(input())

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

L.sort()

ans = 0

for i in range(N):
    ans = ans + L[i*2]
    
print(ans)
def main():
	N, K = map(int,input().split())
	A = list(map(int,input().split()))
	A.sort()
	l, r = 0, N-1
	while l < r:
		m = (l+r)>>1
		p = True
		if solve(N, K, A[:m]+A[m+1:], A[m]):
			l = m+1
		else:
			r = m
	if l == N-1 and solve(N, K, A[:N-1], A[N-1]):
		l = N
	print(l)


def solve(n, k, a, ai):
	dp = [[False for _ in range(k+1)] for _ in range(n)]
	dp[0][0] = True
	if a[0] > k:
		dp[0][k] = True
	else:
		dp[0][a[0]] = True
	for i in range(1, n-1):
		for j in range(k-1):
			if not dp[i-1][j]:
				continue
			dp[i][j] = True
			if j + a[i] > k:
				dp[i][k] = True
			else:
				dp[i][j+a[i]] = True
	return not any(map(lambda j: dp[n-2][j], range(k-ai, k)))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
	N, K = map(int,input().split())
	A = list(map(int,input().split()))
	A.sort(reverse=True)
	no_need = 0
	sub = 0
	for ai in A:
		if sub+ai < K:
			sub += ai
			no_need += 1
		else:
			no_need = 0

	print(no_need)


if __name__ == '__main__':
    main()
N, K = map(int, input().split())
S = input()

ans = S[:K-1] + S[K-1].lower() + S[K:]
print(ans3 1) 

### FIXED CODE ###

N, K = map(int, input().split())
S = input()
 
ans = S[:K-1] + S[K-1].lower() + S[K:]
print(ans)
l = raw_input().split()
N = l[0]
M = l[1]
ans = 1                                                                                                                                                                                                                                                               

if N == (M + 1) or N == (M - 1):
    for n in range(1, N+1):
        ans *= n
        ans %= 1e9 + 7
    for m in range(1, M+1):
        ans *= m
        ans %= 1e9 + 7
elif N == M:
    for n in range(1, N+1):
        ans *= n
        ans %= 1e9 + 7
    for m in range(1, M+1):
        ans *= m
        ans %= 1e9 + 7
    ans *= 2
    ans %= 1e9 + 7
else:
    ans = 0

print int(ans)

### FIXED CODE ###

import sys

N, M = (int(i) for i in raw_input().split())
ans = 1                                                                                                                                                                                                                                                                     

if __name__ == '__main__':
    if N == (M + 1) or N == (M - 1):
        for n in range(1, N+1):
            ans *= n
            ans %= 1e9 + 7
        for m in range(1, M+1):
            ans *= m
            ans %= 1e9 + 7
    elif N == M:
        for n in range(1, N+1):
            ans *= n
            ans %= 1e9 + 7
        for m in range(1, M+1):
            ans *= m
            ans %= 1e9 + 7
        ans *= 2
        ans %= 1e9 + 7
    else:
        ans = 0

    print int(ans)
nm=list(map(int,input().split()))
n=nm[0]
m=nm[1]
py=[]
y=[]
for i in range(m):
    py.append([])
for i in range (n):
    y.append([])
for i in range(m):
    py[i]=list(map(int,input().split()))
    y[py[i][0]-1].append(py[i][1])
for i in range(n):
    y[i].sort()
#print(py)
#print(y)
for i in range(m):
    if py[i][0]<10:
        print("00000"+str(py[i][0]*10**6+y[py[i][0]-1].index(py[i][1])+1))
    elif  py[i][0]<100:
        print("0000"+str(py[i][0]*10**6+y[py[i][0]-1].index(py[i][1])+1))
    elif py[i][0]<1000:
        print("000"+str(py[i][0]*10**6+y[py[i][0]-1].index(py[i][1])+1))
    elif py[i][0]<10000:
        print("00"+str(py[i][0]*10**6+y[py[i][0]-1].index(py[i][1])+1))
    elif py[i][0]<100000:
        print("0"+str(py[i][0]*10**6+y[py[i][0]-1].index(py[i][1])+1))
    else:
        print(str(py[i][0]*10**6+y[py[i][0]-1].index(py[i][1])+1))

### FIXED CODE ###

l=list(map(int,input().split()))
x=l[0]
y=l[1]
print(int(x+y/2))
#!/usr/bin/env python
import math

n = int(input())
m = int(math.sqrt(n))+1
x = y = z = 0 

def p(x, y, z): 
    return x*x + y*y + z*z + x*y + y*z + z*x 

anss = [0 for _ in range(n)]
visited = []

def dfs(x, y, z): 
    if x+y+z > m or (x, y, z) in visited:
        return
    anss[p(x, y, z)-1] += 1
    visited.append((x, y, z)) 
    dfs(x+1, y, z)
    dfs(x, y+1, z)
    dfs(x, y, z+1)

# output
dfs(1,1,1)
for i in range(n):
    print(anss[i])


### FIXED CODE ###

#!/usr/bin/env python
import math

n = int(input())
m = int(math.sqrt(n))+1
x = y = z = 0 

def p(x, y, z): 
    return x*x + y*y + z*z + x*y + y*z + z*x 

anss = [0 for _ in range(n)]

for x in range(1, m): 
    for y in range(1, m): 
        for z in range(1, m): 
            if p(x, y, z)-1 <= n-1:
                anss[p(x, y, z)-1] += 1

for i in range(n):
    print(anss[i])
import math
import functools
N = int(input())
T = []
for i in range(N):
  T.append(int(input()))
def gcd(A, B):
  while(True):
    if A and B:
      if A > B:
        A = A % B
      else:
        B = B % A
    else:
      return max(A, B)

def mcm(A, B):
  return int(A * B / gcd(A, B))

print(functools.reduce(mcm, sorted(T, reverse=True)))

### FIXED CODE ###

import functools
N = int(input())
T = []
for i in range(N):
  T.append(int(input()))
def gcd(A, B):
  while(True):
    if A and B:
      if A > B:
        A = A % B
      else:
        B = B % A
    else:
      return max(A, B)
 
def lcm(A, B):
  return (A // gcd(A, B)) * B
 
print(functools.reduce(lcm, sorted(T, reverse=True)))
#!/usr/bin/env python3
A, B = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
dp = [[0] * (B + 1) for _ in range(A + 1)]

for i in range(A)[::-1]:
    dp[i][B] = dp[i + 1][B] + a[i] if (i + B) % 2 == 0 else dp[i + 1][B]
for j in range(B)[::-1]:
    dp[A][j] = dp[A][j + 1] + b[j] if (A + j) % 2 == 0 else dp[A][j + 1]

for i in range(A)[::-1]:
    for j in range(B)[::-1]:
        dp[i][j] = \
        max(dp[i + 1][j] + a[i], dp[i][j + 1] + b[j]) if (i + j) % 2 == 0 else \
        min(dp[i + 1][j], dp[i][j + 1])

print(dp[0][0])


### FIXED CODE ###

#!/usr/bin/env python3
S = input()
n = [S.count('a'), S.count('b'), S.count('c')]

ans = False
if len(S) == 1:
    ans = True
elif len(S) == 2 and len([x for x in n if x != 0]) == 2:
    ans = True
else:
    n.sort()
    if n[0] != 0 and n[2] - n[0] <= 1:
        ans = True
print(('NO', 'YES')[ans])
temp = r
print(temp * 2)

### FIXED CODE ###

r = int(input())
print(r * r)
n=int(input())
string=""

if n==0:
    string="0"
while n!=0:
    if n%2==1:
        string="1"+string
        n=n-1
    else:
        string="0"+string
    n=n/(-2)
    
print(string)

### FIXED CODE ###

n,k=(int(i) for i in input().split())
if n%k==0:
    print(0)
else:
    print(1)
number_1 = int(input())
number_2 = int(input())
if number_1>9 or number_2>9:
  print("-1")
else:
  print(str(number_1*number_2))

### FIXED CODE ###

S = input()
li = S.split(" ")
A = int(li[0])
B = int(li[1])
if A>9 or B>9:
    print(-1)
else:
    print(A*B)
N = int(input())

def prime_factorize(n):
    a = []
    time = 0
    while n % 2 == 0:
        a.append(2)
        n //= 2
    ff = 3
    while ff * ff <= n:
        if n % ff == 0:
            a.append(ff)
            n //= ff
        else:
            ff += 2
    if n != 1:
        a.append(n)
        a.append(1)
    return a


f = []
serch_mini = []


for i in range(len(prime_factorize(N))):
    f = prime_factorize(N)
    b = f[0:i+1]
    c = f[i+1:]
    bb = 1
    cc = 1
    for j in range(len(b)):
        bb *= b[j]
    for k in range(len(c)):
        cc *= c[k]
    serch_mini.append(bb+cc)

serch_mini.remove(bb+cc)

print(min(serch_mini)-2)


### FIXED CODE ###

N = int(input())
n = int((N ** 0.5)//1 + 1)

ans = 1000000
ans_list = []

for i in range(1, n):
    if N % i == 0:
        ans = N / i
        ans_list.append(i + ans)

print(int(min(ans_list)-2))
N = int(input())
L0 = 2
L1 = 1
for i in range(N-1):
    L = L0 + L1
    L0,L1 = L1,L
print(L)

### FIXED CODE ###

N = int(input())
L0 = 2
L1 = 1
for i in range(N-1):
    L = L0 + L1
    L0,L1 = L1,L
if N == 1:
    print(1)
else:
    print(L)
coin = int(input())
Max = int(input())
total = coin*500
if total >= Max:
    print("Yes")
else:
    print("No")
 

### FIXED CODE ###

inp = input()
arr = [int(i) for i in inp.split() if i.isdigit()]
total = arr[0]*500
if total >= arr[1]:
    print("Yes")
else:
    print("No")
w=list(input())
ans=sorted(w)

print(ans)
while ans[-1]==ans[-2]:
  del ans[-2:]
  if ans==[]:
    break
  print(ans)

if ans==[]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

w=list(input())
ans=sorted(w)

if len(ans)>1:
  while ans[-1]==ans[-2]:
    del ans[-2:]
    if len(ans)==0 or len(ans)==1:
      break

if len(ans)==0:
  print('Yes')
else:
  print('No')
import sys,math
input=sys.stdin.readline
N=int(input())
num = list(map(int,input().split()))
left=[0]*(N+1)
right=[0]*(N+1)
for i in range(N):
  j = N-i-1#初期値=4
  left[i+1] = math.gcd(left[i],num[i])
  right[j] = math.gcd(right[j+1],num[j])
ans=0
for k in range(N):
  ans = max(ans,math.gcd(left[k],right[k+1]))
print(ans)

### FIXED CODE ###

import sys,fractions
input=sys.stdin.readline
N=int(input())
num = list(map(int,input().split()))
g = fractions.gcd
left=[0]*(N+1)
right=[0]*(N+1)
for i in range(N):
  j = N-i-1#初期値=4
  left[i+1] = g(left[i],num[i])
  right[j] = g(right[j+1],num[j])
ans=0
for k in range(N):
  ans = max(ans,g(left[k],right[k+1]))
print(ans)
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
s=input()
t=input()
dp=[["" for i in range(len(s)+1)] for j in range(len(t)+1)]
for i,sele in enumerate(s):
  for j ,tele in enumerate(t):
    if sele==tele:
      dp[i+1][j+1]=dp[i][j] +sele
    else :
      dp[i+1][j+1]=dp[i+1][j] if dp[i+1][j]>=dp[i][j+1] else dp[i][j+1]     
print(dp[len(s)][len(t)])
    

### FIXED CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
s=input()
t=input()
dp=[[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i,sele in enumerate(s):
  for j ,tele in enumerate(t):
    if sele==tele:
      dp[i+1][j+1]=dp[i][j] +1
    else :
      dp[i+1][j+1]=dp[i+1][j] if dp[i+1][j]>=dp[i][j+1] else dp[i][j+1]     
res=""
i=len(s)
j=len(t)
#print(dp)
while True:
#for k in range(9):
  #rint(i,j,dp[i][j])
  if i-1>=0:
    if dp[i-1][j]==dp[i][j]:
      i=i-1
      continue
  if j-1>=0:
    if dp[i][j-1]==dp[i][j]:
      j=j-1
      continue
  if i-1>=0 and j-1>=0:
    if dp[i-1][j-1]==dp[i][j]-1:
      j=j-1
      i=i-1
      res=s[i]+res
      #print(i,res)
      if dp[i][j]==0:
        break
      continue
  break
print(res)
a=int(input())
b=int(input())

c=a*b

if c%2==0:
  print("Even")
  else:
    print("Odd")
    

### FIXED CODE ###

a, b = map(int, input().split())
print("Even" if a*b % 2 == 0 else "Odd")
N = int(input())
T = [int(i) for i in input().split()]
M = int(input())

PX = []

for i in range(M):
    # 0-indexed
    PX.append([int(j) for j in input().split()])
    PX[i][0] -= 1

ans = sum(T)

for i in range(M):
    print(ans - T[PX[i][0]] + T[PX[i][1]])


### FIXED CODE ###

N = int(input())
T = [int(i) for i in input().split()]
M = int(input())

PX = []

for i in range(M):
    # 0-indexed
    PX.append([int(j) for j in input().split()])
    PX[i][0] -= 1

ans = sum(T)

for i in range(M):
    print(ans - T[PX[i][0]] + PX[i][1])
w = ['Sunny', 'Cloudy', 'Rainy']
s = input()
i = w.index(s) +1
if i==3:
  i=0
print(w(i))

### FIXED CODE ###

w = ['Sunny', 'Cloudy', 'Rainy']
s = input()
i = w.index(s) +1
if i==3:
  i=0
print(w[i])
N,X = map(int,input().split(" "))
l_list = input().split()

count = 1
d = 0
for i in range(N):
        da = d + int(l_list[i])
        d = da
        if da <= X:
                count +=1
        else:
                print(count)
                break


### FIXED CODE ###

lists = []
lists = input().split(" ")
if int(lists[0])<int(lists[1]):
  print(0)
else:
  print(10)
from sys import stdin
import math
a,b,c,d = [int(x) for x in stdin.readline().rstrip().split()]
kouyaku = math.gcd(c, d)
koubai = (c * d // kouyaku)
b_s = (b - b//c - b//d + b//koubai)
a_s = (a-1 - (a-1)//c - (a-1)//d + (a-1)//koubai)
print(b_s - a_s)

### FIXED CODE ###

from sys import stdin
import fractions
a,b,c,d = [int(x) for x in stdin.readline().rstrip().split()]
kouyaku = fractions.gcd(c, d)
koubai = c * d // fractions.gcd(c, d)
b_s = b - b//c - b//d + b//koubai
a_s = a-1 - (a-1)//c - (a-1)//d + (a-1)//koubai
print(b_s - a_s)
# coding: utf-8
# Here your code !
n = int(input())
output = []
for i in range(n):
    order,data =input().split() 
    if order == "insert":
        output.append(int(data))
    elif order == "deleteFirst":
        output.pop()
    elif order == "deleteLast":
        output.popleft()
    elif order == "delete":
        try:
            output.remove(int(data))
        except:
            pass
output.reverse()
print(" ".join(map(str,output)))

### FIXED CODE ###

import sys
from collections import deque
n = int(sys.stdin.readline())
lines = sys.stdin.readlines()
 
Q = deque()
for i in range(n):
    command = lines[i].split()
    if command[0] == "insert":
        Q.appendleft(command[1])
    elif command[0] == "deleteFirst":
        Q.popleft()
    elif command[0] == "deleteLast":
        Q.pop()
    elif command[0] == "delete":
        try:
            Q.remove(command[1])
        except:
            pass
print(" ".join(Q))
data = list(input())
tera = []
ans = 999
for i in len(data) - 3:
  x = int(data[i] + data[i + 1] + data[i + 2])
  ans = min(ans, abs(ans - x))
print(ans)
  

      

### FIXED CODE ###

data = [int(i) for i in input()]
ans = 999
 
for i in range(len(data) - 2):
  x = (data[i] * 100) + (data[i + 1] * 10) + (data[i + 2])
  ans = min(ans, abs(753 - x))
  
print(ans)
import itertools

N, Y = (int(x) for x in input().split())
for x, y in itertools.product(range(N+1), range(N+1)):
  z = N - x - y
  if 0 <= z and 10000*x + 5000*y + 1000*z == Y:
    print('{} {} {}'.format(x, y, z))
    break
if not(x + y + z == N and 10000*x + 5000*y + 1000*z == Y):      
  print('-1 -1 -1')

### FIXED CODE ###

S = input()
print('2018'+S[4:])
N = int(input())
c = 0
for  i in rrange(1,N+1):
  li = []
  if i < 10:
    continue
  else:
    k = i
    for j in range(2,int(i**(0.5)+1)):
      while k % j == 0:
        k = k/j
        li.append(j)
    if len(li) == 8:
      c += 1
print(c)

### FIXED CODE ###

N = int(input())
c = 0
for  i in range(1,N+1):
  if i % 2 == 0:
    continue
  li = []
  if i < 10:
    continue
  else:
    k = i
    for j in range(2,int(i**(0.5)+3)):
      d = 1
      while k % j == 0:
        k = k/j
        d += 1
      if d != 1:
        li.append(d)
    ss = 1
    for x in li:
      ss *= x
    if ss == 8:
      #print(i)
      c += 1
    
print(c)
def insertionSort(_list, _length):
    for i in range(1, _length):
        ll = [str(_l) for _l in _list]
        print(' '.join(ll))
        val = _list[i]
        j = i - 1
        while j >= 0 and _list[j] > val:
            _list[j+1] = _list[j]
            j -= 1
        _list[j+1] = val
    ll = [str(_l) for _l in _list]
    print(' '.join(ll))


import sys
 
length = input()
eles = map(int, sys.stdin.readlines().rstrip().split(' '))

insertionSort(eles, length)

### FIXED CODE ###

length = int(input())
eles = [int(i) for i in input().split()]

for i in range(length):
    val = eles[i]
    j = i - 1
    while j >= 0 and eles[j] > val:
        eles[j+1] = eles[j]
        j -= 1
    eles[j+1] = val
    print(*eles)
N, M = map(int, input().strip().split())

i=1
while i*i < M:
  if M % i == 0:
    maxg = M // N
  i += 1

print(maxg)

### FIXED CODE ###

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

i=1
while i <= M//N: 
  if M % i == 0:
    maxg = i
    if M//i <= M//N:
      maxg = M // i
      break
  i += 1

print(maxg)
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [None] * N

def solve(idx):
    if dp[idx] is not None:
        return dp[idx]

    if idx == N - 1:
        dp[idx] = 0
    elif idx == N - 2:
        dp[idx] = abs(h[idx] - h[idx + 1])
    else:
        temp = 10**10
        for k in range(1, K + 1):
            if idx + k == N:
                break
            temp = min(temp, solve(idx + k) + abs(h[idx] - h[idx + k]))
        dp[idx] = temp
    return dp[idx]

print(solve(0))


### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n

for i in range(n):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        costs = []
        for j in range(1, k+1):
            if j > i:
                break
            if abs(h[i-j]-h[i]) == 0:
                costs.append(dp[i-j])
                break
            costs.append(dp[i-j] + abs(h[i-j]-h[i]))

        # if i == 3:
        #     print(costs)
        dp[i] = min(costs)

#print(dp)
print(dp[n-1])
n = int(input())
P =[]
s = 0
for i in range(n):P.append([int(i) for i in input().split()])
P.append(P[0])
for i in range(n):
    a = P[i][0] ; b = P[i][1]; c = P[i+1][0] ; P[i+1][1]
    s += a * d - b * c
print(abs(s)*0.5)

### FIXED CODE ###

x=range(int(input())-1,-1,-1)
P=[]
for _ in x:P+=[[int(i) for i in input().split()]]
P+=[P[0]]
for j in x:_+=P[j+1][1]*P[j][0]-P[j][1]*P[j+1][0]
print(_*0.5)
n = int(input())
for i in range(n):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(float, input().split())
    x2 -= x1
    y2 -= y1
    x4 -= x3
    y4 -= y3
    if x2 == 0 or x4 == 0:
        print("YES" if x2 == x4 == 0 else "NO")
    else:
        print("YES" if x2 / y2 == x4 / y4 else "NO")

### FIXED CODE ###

n = int(input())
for i in range(n):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(float, input().split())
    print("YES" if abs((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))
          < 1e-10 else 'NO')
# -*- coding: utf-8 -*-
import math
import copy

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

B = copy.copy(A)

gcd_array = []
for i in range(N):
    B.pop(i)
    C = copy.copy(B[1:])
    C.append(B[0])
    gcd = 100000000000000000000
    for b, c in zip(B, C):
        tmp = math.gcd(b, c)
        if tmp < gcd:
            gcd = tmp
    gcd_array.append(gcd)

    B = copy.copy(A)
print(max(gcd_array))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import fractions

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


gcd = fractions.gcd


left = [0] * N
right = [0] * N
for i in range(N):
    if i == 0:
        left[0] = A[0]
        right[N-1] = A[-1]
        continue

    left[i] = gcd(left[i-1], A[i])
    right[N-i-1] = gcd(right[N-i], A[N-i-1])

max_gcd = right[1]
for i in range(N):
    if i == 0:
        continue
    elif i == N - 1:
        if max_gcd < left[-2]:
            max_gcd = left[-2]
    else:
        target = gcd(left[i-1], right[i+1])
        if max_gcd < target:
            max_gcd = target

print(max_gcd)
if x == 0:
 print(1)
else:
 print(0)

### FIXED CODE ###

n=int(input())
if(n==1):
  print(0)
else:
  print(1)