Harryxun/stf_run huggingface dataset:
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(w)]
    G = [[10**7]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx:
                    break
                if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
    ans = G[gy][gx]
    print(ans if ans < 10**7 else -1)
    return

solve()


### FIXED CODE ###

import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(h)]
    G = [[10**7]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx:
                    break
                if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
    ans = G[gy][gx]
    print(ans if ans < 10**7 else -1)
    return

solve()
from collections import deque
count = 0

def merge(A,left,mid,right):
    L = deque(A[left:mid])
    R = deque(A[mid:right])
    L.append(10**9)
    R.append(10**9)
    
    global count
    
    for k in range(left,right):
        count +=1
        if L[0] <= R[0]:
            A[k] = L.popleft()
 
        else:
            A[k] = R.popleft()

            
def mergeSort(A,left,right):
    if left + 1 < right:
        middle = (left + right) //2
        mergeSort(A,left,middle)
        mergeSort(A,middle,right)
        merge(A,left,middle,right)
        
input()
l = list(map(int,input().split()))
mergeSort(l,0,len(l))
print(" ".join(l))
print(count)            
        

### FIXED CODE ###

from collections import deque
SENIAL = 10**9
count = 0

def merge(A,left,mid,right):
    L = deque(A[left:mid])
    R = deque(A[mid:right])
    L.append(SENIAL)
    R.append(SENIAL)
    
    global count
    
    for k in range(left,right):
        count +=1
        if L[0] <= R[0]:
            A[k] = L.popleft()
 
        else:
            A[k] = R.popleft()

            
def mergeSort(A,left,right):
    if left + 1 < right:
        middle = (left + right) //2
        mergeSort(A,left,middle)
        mergeSort(A,middle,right)
        merge(A,left,middle,right)
        
input()
l = list(map(int,input().split()))
mergeSort(l,0,len(l))
print(" ".join(map(str,l)))
print(count)
A,B,N=map(int,input().split())
#print(math.floor(A/B))
c=[0]*N
for i in range(1,N+1):
  c[i-1]=(A*i)//B-A*(i//B)

print(max(c))

### FIXED CODE ###

A,B,N=map(int,input().split())
if B==1:print(0);exit()
if N<=B:
  print(max((A*(N-1))//B-A*((N-1)//B),(A*N)//B-A*(N//B)))
else:print(A-1)
import numpy as np

tmp = np.array(list(map(int, input().split())))
N = tmp[0]
A = tmp[2:]

Needed = np.sum(A)

if Needed > N:
    print(-1)
else:
    print(N - Needed)

### FIXED CODE ###

import numpy as np

N = int(input().split()[0])
A = np.array(list(map(int, input().split())))
Needed = np.sum(A)
if Needed > N:
    print(-1)
else:
    print(N - Needed)
n = int(input())
s = list(input())
ing_total = 0

while i < n - 2
    if s[i] == "A":
        if s[i + 1] == "B":
            if s[i+2] == "C":
                ing_total+= 1
print(ing_total)


### FIXED CODE ###

n = int(input())
s = input()
print(s.count("ABC"))
N,H = list(map(int, input().split()))
A=0
B=[]
for _ in range(N):
    a,b = list(map(int, input().split()))
    A = max(A, a)
    B.append(b)

B = sorted([b for b in B if b>A], reverse=True)
from itertools import accumulate
B = list(accumulate(B))
HP_after_throw = H - B[-1]
if HP_after_throw <= 0:
    for i,b in enumerate(B,1):
        if H<=b:
            print(i)
            exit()
    raise AssertionError('error')
else:
    q,r = divmod(HP_after_throw, A)
    print(len(B)+q+min(1, r))


### FIXED CODE ###

N,H = list(map(int, input().split()))
A=0
B=[]
for _ in range(N):
    a,b = list(map(int, input().split()))
    A = max(A, a)
    B.append(b)

B = sorted([b for b in B if b>A], reverse=True)
from itertools import accumulate
B = list(accumulate(B))
total_throw_damage = (B[-1] if len(B)>0 else 0)

HP_after_throw = H - total_throw_damage
if HP_after_throw <= 0:
    for i,b in enumerate(B,1):
        if H<=b:
            print(i)
            exit()
    raise AssertionError('error')
else:
    q,r = divmod(HP_after_throw, A)
    print(len(B)+q+min(1, r))
n,m = map(int,input().split())
ab_list = [list(map(int, input().split())) for _ in range(m)]
tmp_list = sorted(list(chain(*ab_list)))
tmp_dic = {}
for i in range(1,n+1):
    tmp_dic[i]=0
for val in tmp_list:
    tmp_dic[val] += 1
for k,v in tmp_dic.items():
    print(v)


### FIXED CODE ###

from itertools import chain
n,m = map(int,input().split())
ab_list = [list(map(int, input().split())) for _ in range(m)]
tmp_list = sorted(list(chain(*ab_list)))
tmp_dic = {}
for i in range(1,n+1):
    tmp_dic[i]=0
for val in tmp_list:
    tmp_dic[val] += 1
for k,v in tmp_dic.items():
    print(v)
n, k=map(int, input().split())

ans=k*((k-1)**(n-1))

print(ans)

### FIXED CODE ###


def penki(a, b, c):
  if a==b and b==c:
    return 1
  elif a!=b and b!=c and c!=a:
    return 3
  else:
    return 2

a,b,c=map(int, input().split())
print(penki(a, b, c))
a = int(input())
b = int(input())
c = b * (b-1) ** (a-1)
print(c)

### FIXED CODE ###

a, b = map(int, input().split())
c = b * (b-1) ** (a-1)
print(c)
if n%k==0:
    print(0)
else:
    print(1)

### FIXED CODE ###

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

if n%k==0:
    print(0)
else:
    print(1)
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    X = []
    Y = []
    for _ in range(N):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)

    cnt = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j:
                continue

            dx = X[j] - X[i]
            dy = Y[j] - Y[i]
            cnt[(dx, dy)] += 1

    cnt = sorted(cnt.items(), key=lambda x: x[1], reverse=True)
    ans = N - cnt[0][1]
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    if N == 1:
        print(1)
        return
    xy = []
    for _ in range(N):
        x, y = map(int, input().split())
        xy.append((x, y))

    d = {}
    for i in range(N):
        tmp = set()
        for j in range(N):
            if i == j:
                continue
            dx = xy[i][0] - xy[j][0]
            dy = xy[i][1] - xy[j][1]

            if (dx, dy) in tmp:
                continue
            if (dx, dy) not in d:
                d[(dx, dy)] = 1
            else:
                d[(dx, dy)] += 1
            tmp.add((dx, dy))

    d = sorted(d.items(), key=lambda x: x[1], reverse=True)
    cnt = d[0][1]
    print(N - cnt)

main()
from math import factorial

def comb(n, r):
    return factorial(n) // (factorial(n-r) * factorial(r))


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


for i in range(1, k+1):
    print(comb(n-k+1, i) * comb(k-1, i-1) % (10**9+7))





### FIXED CODE ###

from math import factorial

def comb(n, r):
    if n < r:
        return 0
    return factorial(n) // (factorial(n-r) * factorial(r))

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

for i in range(1, K+1):
    print(comb(N-K+1, i) * comb(K-1, i-1) % (10**9+7))
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])
#print(td)
ans=0
kinds=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kinds:
        kinds[td[i][0]].append(td[i][1])
    else:
        kinds[td[i][0]]=[td[i][1]]
ans+=(len(kinds)**2)
#kindsの中はソートされている状況
#print(kinds)
ans_=[ans]
for i in range(k,n):
    if td[i][0] not in kinds:
        mi=[1000000000,1000000000]
        for j in kinds:
            if len(kinds[j])>1:
                if mi[1]>kinds[j][-1]:
                    mi=[j,kinds[j][-1]]
        if mi==[-1,-1]:
            break
        else:
            ans=ans-len(kinds)**2+(len(kinds)+1)**2-mi[1]+td[i][1]
            kinds[mi[0]].pop(-1)
            kinds[td[i][0]]=[td[i][1]]
            ans_.append(ans)
#print(kinds)
print(max(ans_))

### FIXED CODE ###

n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[mi[0]]-=1
                now-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)
n,m=map(int, input().split())
pl=[0]*m
yl=[0]*m
cl=[0]*(m+1)
ol=[[] for i in range(n+1)]
for i in range(m):
    pl[i],yl[i] = map(int, input().split())
    ol[pl[i]].append((pl[i], yl[i], i))
for i in range(n):
    cnt = 1
    for o in sorted(ol[pl[i]]):
        cl[o[2]] = cnt
        cnt+=1
for i in range(m):
    print("%06d%06d" % (pl[i], cl[i]))


### FIXED CODE ###

import bisect
n,m=map(int, input().split())
pl=[0]*100000
yl=[0]*100000
ol=[[] for i in range(100001)]
for i in range(m):
    pl[i],yl[i] = map(int, input().split())
    ol[pl[i]].append(yl[i])
for i in range(1,n+1):
    ol[i].sort()
for i in range(m):
    print("%06d%06d" % (pl[i], bisect.bisect_right(ol[pl[i]], yl[i])))
def inpl(): return [int(i) for i in input().split()]
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
        self.dist = [0 for _ in range(num)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            self.par[ry] = rx
            self.dist[ry] = d + self.dist[x] - self.dist[y]
        elif self.dist[ry] != d + self.dist[x] - self.dist[y]:
            return False
        return True 
    

N, M = inpl()
X = UnionFind(N)
for _ in range(M):
    l, r, d = inpl()
    if not X.union(l-1, r-1, d):
        ans = 'No'
else:
    ans = 'Yes'
print(ans)

### FIXED CODE ###

def inpl(): return [int(i) for i in input().split()]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x],dist[x] = find(par[x]),dist[x]+dist[par[x]]
        return par[x]
N, M = inpl()
par = list(range(N+1))
dist = [0 for _ in range(N+1)]

for _ in range(M):
    l, r, d = inpl()
    fl = find(l)
    fr = find(r)
    if fl == fr and d + dist[l] - dist[r] != 0:
        print('No')
        break
    else: 
        par[fr] = fl
        dist[fr] = d + dist[l] - dist[r]
else:
    print('Yes')
n=int(input())
s=[int(input()) for i in range(n)]
S=list(set(s))
print(len(S))

### FIXED CODE ###

n=int(input())
s=[input() for i in range(n)]
S=list(set(s))
print(len(S))
import math

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

ans = a[0]
for i in range(1, n):
    ans = math.gcd(ans, a[i])

print(ans)

### FIXED CODE ###

from fractions import gcd

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

ans = a[0]
for i in range(1, n):
    ans = gcd(ans, a[i])

print(ans)
import sys

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [[int(a) for a in input().split()] for _ in range(H)]
    Ans = []
    for n in range(H * W - 1):
        h, w = n // W, n % W
        if A[h][w] % 2 == 1:
            if w < W - 1:
                Ans.append((h+1, w+1, h+1 w+2))
                A[h][w] -= 1
                A[h][w+1] += 1
            else:
                Ans.append((h+1, w+1, h+2, w+1))
                A[h][w] -= 1
                A[h+1][w] += 1
    print(len(Ans))
    for move in Ans:
        print(" ".join(map(str, move)))
   
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

H, W = map(int, input().split())
A = [[int(_) for _ in input().split()] for _ in range(H)]
N = 0
move = []
for i in range(H):
    for j in range(W):
        if A[i][j] % 2 == 1 and j <= W-2:
            A[i][j+1] += 1
            N += 1
            move.append([i+1, j+1, i+1, j+2])
        elif A[i][j]%2 == 1 and j == W-1 and i!=H-1:
            A[i+1][j] += 1
            N += 1
            move.append([i+1, j+1, i+2, j+1])

print(N)
for i in range(N):
    print(move[i][0], move[i][1], move[i][2], move[i][3])
n, m = map(int, input().split())
A = list(map(int, input().split()))
borderline = sum(A) / (4 * m)

print('Yes' if sorted(A, reverse=True)[m-1] >= borderline else 'No')


### FIXED CODE ###

x, y, z = map(int, input().split())

print(z, x, y)
import math

(a, b) = tuple([int(s) for s in input().split()])

if a==b:
    print(a)
    return

min = a if a < b else b
divisor = 1

i = 2
while i < math.sqrt(min):
    if a % i == 0 and b % i == 0:
        a = a / i
        b = b / i
        divisor = divisor * i
    else:
        i = i + 1

print(divisor)

### FIXED CODE ###

# 1_1_B

def gcd(x, y):
    while x%y != 0:
        x, y = y, x%y
    return y

x, y = map(int, input().split())
print(gcd(x, y))
a,s  = map(int,input().split())

sum = 0
for i in range(0,a+1):
    for j in range(0,a+1):
        if s-i-j <= a:
            sum + = 1
print(sum)



### FIXED CODE ###

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

sum = 0
for i in range(0,a+1):
    for j in range(0,a+1):
        if 0 <= s-i-j <= a:
            sum += 1
print(sum)
S = input()
n = len(S)
flag = 0
for i in range(0,n):
  if i%2==0 and (not (S[1]=='L' or S[1]=='U' or S[1]=='D')):
      flag = 1
  elif (i+1)%2!=0 and (not (S[1]=='R' or S[1]=='U' or S[1]=='D')):
      flag = 1
      
if flag==1:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

S=input()
flag = 0
for i in range(0,len(S)):
  if (i+1)%2==0 and not (S[i]=='L' or S[i]=='U' or S[i]=='D'):
    flag = 1
  elif (i+1)%2!=0 and not (S[i]=='R' or S[i]=='U' or S[i]=='D'):
    flag = 1
    
if flag==1:
  print("No")
else:
  print("Yes")
a=[[] for _ in range(3)]
for i in range(3):
  a[i]=list(map(int,input().split()))
l=[]
N=int(input())
for i in range(N):
  n=int(input())
  for i in range(3):
    for j in range(3):
      if a[i][j]==n:
        l.append([i,j])

def judge(l):
  if len(l)<=2:
    return 'No'
  else:
    if [0,0] in l and [1,1] in l and [2,2] in l:
      return 'Yes'
    else:
      dic1={}
      dic2={}
      for ij in l:
        i,j=l[0],l[1]
        if i not in dic1.keys():
          dic1[i]=1
        else:
          dic1[i]+=1
          if dci1[i]==3:
            return 'Yes'
        if j not in dic2.keys():
          dic2[j]=1
        else:
          dic2[j]+=1
          if dic2[j]==3:
            return 'Yes'
      return 'No'
print(judge(l))
      

### FIXED CODE ###

a=[[] for _ in range(3)]
for i in range(3):
  a[i]=list(map(int,input().split()))
l=[]
N=int(input())
for i in range(N):
  n=int(input())
  for i in range(3):
    for j in range(3):
      if a[i][j]==n:
        l.append([i,j])

def judge(l):
  if len(l)<=2:
    return 'No'
  else:
    if [0,0] in l and [1,1] in l and [2,2] in l:
      return 'Yes'
    elif [0,2] in l and [1,1] in l and [2,0] in l:
      return 'Yes'
    else:
      dic1={}
      dic2={}
      for ij in l:
        i,j=ij[0],ij[1]
        if i not in dic1.keys():
          dic1[i]=1
        else:
          dic1[i]+=1
          if dic1[i]==3:
            return 'Yes'
        if j not in dic2.keys():
          dic2[j]=1
        else:
          dic2[j]+=1
          if dic2[j]==3:
            return 'Yes'
      return 'No'
print(judge(l))
import sys
input = sys.stdin.readline
 
#input
N = int(input())
A = list(map(int, input().split()))

#output
from collections import Counter
import numpy as np

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
O = l[0]

number_of_operation = [0] * O
maximum_operation = [0] * N
operation_matrix = np.zeros((O, M), int)

for m in range(M):
    operation_matrix[0:l[m], m] += 1

for o in range(O):
    number_of_operation[o] = sum(operation_matrix[o])

for K in range(N):
    temp_number_of_operation = list(number_of_operation)
    for o in range(O-1):
        p, q = divmod(temp_number_of_operation[o], K+1)
        if p > 0:
            temp_number_of_operation[o+1] += q
        maximum_operation[K] += p
    maximum_operation[K] += number_of_operation[O-1]//(K+1)

for m in maximum_operation:
    print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)
nums = list(map(int, input().split()))
ans = 0
for i in nums:
  if i == sum(nums.remove(i)):
    ans += 1
    break
if ans > 0:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

lst = list(map(int, input().split()))
lst.sort()
if lst[0] + lst[1] == lst[2]:
  print("Yes")
else:
  print("No")
# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 01/08/2020

from sys import stdin,stdout
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007

n, m = iia()
dp = [-1] * (n + 1)
d = {}
for i in range(m):
    a, b = iia()
    d.setdefault(a, []).append(b)

def dfs(cur):
    if dp[cur] != -1:
        return dp[cur]
    t = 0
    for i in d.get(cur, []):
        t = max(1 + dfs(i), t)
    dp[cur] = t
    return dp[cur]

res = 0
for i in range(1, n + 1):
    res = max(res, dfs(i))
print(res)

### FIXED CODE ###

# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 01/08/2020

from sys import stdin, stdout
import sys
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007
sys.setrecursionlimit(100000)
n, m = iia()
dp = [-1] * (n + 1)
d = {}
for i in range(m):
    a, b = iia()
    d.setdefault(a, []).append(b)

def dfs(cur):
    if dp[cur] != -1:
        return dp[cur]
    t = 0
    for i in d.get(cur, []):
        t = max(1 + dfs(i), t)
    dp[cur] = t
    return dp[cur]

res = 0
for i in range(1, n + 1):
    res = max(res, dfs(i))
print(res)
N = input()
nlen = len(N)
cnt = 0
for i in range(1, nlen):
  if i % 2:
    cnt += (10 ** i) - (10 ** (i - 1))
N = int(N)
if nlen % 2:
  cnt += N - 10 ** (nlen - 1) + 1
print(cnt)

### FIXED CODE ###

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

res = c -(a - b)
print(res if res > 0 else 0)
n = int(input())
ans = [0]
for i in range(1, 105):
	for j in range(1, 105):
		for k in range(1, 105):
			v = i*i+j*j+k*k+i*j+j*k+k*i;
			if v < 10050:
				#個数を数える
				ans[v] += 1
for i in range(n):
	print(ans[i+1])

### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
	for j in range(1,105):
		for k in range(1,105):
			v = i*i+j*j+k*k+i*j+j*k+k*i;
			if v<10050:
				ans[v]+=1
for i in range(n):
	print(ans[i+1])
s = raw_input()

print 700 + s.count(o)*100

### FIXED CODE ###

s = raw_input()
 
print 700 + s.count('o')*100
n = int(input())

a = list(map(int,input().split()))
a = sorted(a)

aMax = a[-1]
l = len(a)
count = 0

while 1:
    aMin = a.pop(0)
    if aMin == a[0]:
        count -= 1
    count += 1
    l -= 1
    delList = []
    if l == 0:
        break
    for k in a:
        if k % aMin == 0:
            delList.append(k)
    for k in delList:
        a.remove(k)
        l -= 1
    if aMin ** 2 > aMax:
        count += l
        break

print(count)

### FIXED CODE ###

n = int(input())

a = list(map(int,input().split()))
a = sorted(a)

aMax = a[-1]
l = len(a)
count = 0
k = 0
kSet = set()

for i in range(n):
    value = a[i]
    if not(value in kSet):
        if i != 0 and a[i-1] == value:
            count -= 1
            kSet.add(value)
            continue
        count += 1
        j = 2
        k = 0
        while k < aMax:
            k = a[i] * j
            kSet.add(k)
            j += 1
    #if value ** 2 > aMax:
    #    break

print(count)
M = int(M)
N = int(N)
ans = ['0' for i in range (N)]
fl = True

for i in range (M) :
    s , c = input().split()
    s = int(s) - 1
    if (s == 0 and c == '0') :
        fl = False
    if (ans[s] != '0') :
        if (ans[s] != c) :
            fl = False
    else :
        ans[s] = c

res = ''

if (ans[0] == '0' and N != 1) :
    ans[0] = '1'

for i in ans :
    res += i

print (res if fl else -1)


### FIXED CODE ###

n, m = list (map (int, input ().split ()))
d = [-1 for i in range (n + 1)]
flg = True

for i in range (m) :
    s, c = list (map (int, input ().split ()))
    if (flg) :
        if (d[s] != -1 and d[s] != c) :
            flg = False
            continue
        d[s] = c

if (d[1] == 0 and n > 1) :
    flg = False

if (flg and n > 1) :
    for i in range (1, n + 1) :
        if (d[i] == -1) :
            if (i == 1) :
                d[i] = 1
            else :
                d[i] = 0

if (n == 1 and d[1] == -1) :
    d[1] = 0

print (''.join (list (map (str, d[1:]))) if flg else "-1")
def is_cross(la, lb, x1, x2):
    ya1 = la[0] * x1 + la[1]
    ya2 = la[0] * x2 + la[1]
    yb1 = lb[0] * x1 + lb[1]
    yb2 = lb[0] * x2 + lb[1]
    if ya1 == yb1:
        return False
    return (ya1 - yb1) * (ya2 - yb2) <= 0

def get_line(c, x, y):
    return [c, y - c * x]

t = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
xa = sum([ti * ai for ti, ai in zip(t, a)])
xb = sum([ti * bi for ti, bi in zip(t, b)])
if xa / sum(t) == xb / sum(t):
    print('infinity')
else:
    ans = 0
    t_pre = 0
    da = 0
    db = 0
    while(True):
        ans_t = 0
        for ti, ai, bi in zip(t, a, b):
            t_post = t_pre + ti
            la = get_line(ai, t_pre, da)
            lb = get_line(bi, t_pre, db)
            ans_t += is_cross(la, lb, t_pre, t_post)
            t_pre = t_post
            da += ti * ai
            db += ti * bi

        if ans_t == 0:
            break
        ans += ans_t
    print(ans)


### FIXED CODE ###

m1, d1 = map(int, input().split())
m2, d2 = map(int, input().split())

print(int(m2 == m1 + 1 and d2 == 1))