Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
ab = [tuple(map(int, input().split())) for _ in range(m)]
dic = {}
ban = {}
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    if h[a - 1] < h[b - 1]:
        ban[a] = True
    elif h[a - 1] == h[b - 1]:
        ban[a] = True
        ban[b] = True
    else:
        ban[b] = True

    if dic.get(a):
        dic[a].append(b)
    else:
        dic[a] = [b]

    if dic.get(b):
        dic[b].append(a)
    else:
        dic[b] = [a]
    dic[a] = list(set(dic[a]))
    dic[b] = list(set(dic[b]))
ans = 0
for i in range(n):
    if dic.get(i + 1):
        if ban.get(i + 1):
            if ban[i + 1]:
                continue
        flg = True
        for j in range(len(dic[i + 1])):
            if h[i] <= h[dic[i + 1][j] - 1]:
                flg = False
                break
        if flg:
            ans += 1
    else:
        ans += 1
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
ab = [tuple(map(int, input().split())) for _ in range(m)]
dic = {}
ban = {}
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]

    if dic.get(a):
        dic[a] = max(dic[a], h[b - 1])
    else:
        dic[a] = h[b - 1]

    if dic.get(b):
        dic[b] = max(dic[b], h[a - 1])
    else:
        dic[b] = h[a - 1]
ans = 0
for i in range(n):
    if dic.get(i + 1):
        if dic[i + 1] < h[i]:
            ans += 1
    else:
        ans += 1
print(ans)
### BUGGY CODE ###

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

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

ans = 0
for i in range(n):
    a = A[i]
    ato = i+a
    if i+a > n:
        ato = n
    for j in range(ato,n):
        if j-i == A[i]+A[j]:
            ans += 1

print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
X = dict()
ans = 0
for i in range(N):
    L = i + A[i]
    if L not in X:
        X[L] = 1
    else:
        X[L] += 1

for j in range(N):
    R = j - A[j]
    if R in X:
        ans += X[R]

print(ans)
### BUGGY CODE ###

L, R = map(int, input().split())
min_l = []
ij = [_ % 2019 for _ in range(L, R+1)]
ij_s = list(set(ij))
for i in ij_s:
    for j in ij_s:
        if i < j:
            min_l.append((i*j) % 2019)
print(min(min_l))

### FIXED CODE ###

l, r = map(int, input().split())
if r // 3 > (l - 1) // 3 and r // 673 > (l - 1) // 673:
    print(0)
else:
    print(min(i * j % 2019 for i in range(l, r + 1) for j in range(l, i)))
### BUGGY CODE ###

def isok(t):
    cnt = 0
    for i in range(n):
        cnt += max(a[i] - t // f[i], 0)
    if cnt > k:
        return False
    else:
        return True 

n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort(reverse = 1)
f.sort()
ok = a[0] * f[-1]
ng = -1
bool = True
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if isok(mid):
        ok = mid
    else:
        ng = mid
    #print(ng,mid,ok)
print(ok)


### FIXED CODE ###

def isok(t):
    cnt = 0
    for i in range(n):
        cnt += max(a[i] - t // f[i], 0)
        if cnt > k:
            return False
    return True 

n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort(reverse = 1)
f.sort()
ok = a[0] * f[-1]
ng = -1
bool = True
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if isok(mid):
        ok = mid
    else:
        ng = mid
    #print(ng,mid,ok)
print(ok)
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    change = []
    for _ in range(m):
        b, c = map(int, input().split())
        for _ in range(b):
            change.append(c)
    change.sort(reverse=True)
    answer = 0
    for i in range(n):
        if i < len(change):
            answer += max(a[i], change[i])
        else:
            answer += a[i]
    print(answer)


if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    change = []
    change_n = 0
    for _ in range(m):
        b, c = map(int, input().split())
        change.append((b, c))
        change_n += b
    change.sort(key=lambda x: x[1], reverse=True)
    answer = 0
    added = 0
    index = 0
    for i in range(n):
        if i < change_n:
            if added + change[index][0] == i:
                added = i
                index += 1
            answer += max(a[i], change[index][1])
        else:
            answer += a[i]
    print(answer)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,M=map(int,input().split());D=[0]+[9e9]*(1<<N)
for i in range(M):
 a,_=input().split();s=sum(1<<~-int(c)for c in input().split())
 for j in range(1<<N):t=s|j;D[t]=min(D[t],D[j]+int(a))
print(-1*(D[-2]>8e9)or D[-2])

### FIXED CODE ###

N,M=map(int,input().split());D=[0]+[9**9]*(1<<N)
for i in range(M):
 a=int(input().split()[0]);s=sum(1<<~-int(c)for c in input().split())
 for j in range(1<<N):D[s|j]=min(D[s|j],D[j]+a)
print(D[-2]%(9**9)or-1)
### BUGGY CODE ###

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

N,S, *A = map(int, sys.stdin.buffer.read().split())
mod = 998244353
A = sorted(A)

answer = [0 for _ in range(S+1)]
power2 = 1
total = 0

for a in A:
  if total<S:
    total = min(S,a+total)
  for i in range(total,0,-1):
    if i>a:
      answer[i] = (2*answer[i]+answer[i-a])%mod
    elif i==a:
      answer[i] = (2*answer[i]+power2)%mod
    else:
      answer[i] = (2*answer[i])%mod
  power2 = (2*power2)%mod

print(answer[S])

### FIXED CODE ###

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

N,S, *A = map(int, sys.stdin.buffer.read().split())
mod = 998244353

answer = [0 for _ in range(S+1)]
power2 = 1

for a in A:
  answer_next = [(2*b)%mod for b in answer]
  if a<=S:
    answer_next[a] = (answer_next[a]+power2)%mod
    for i in range(a+1,S+1):
      answer_next[i] = (answer_next[i]+answer[i-a])%mod
  answer = answer_next
  power2 = (2*power2)%mod

print(answer[S])
### BUGGY CODE ###

from collections import deque


h, w = map(int, input().split())
field = [list(input()) for _ in range(h)]
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def check_done():
    for i in range(h):
        for j in range(w):
            if field[i][j] == ".":
                return False
    return True


def check_black_list():
    res = []
    for i in range(h):
        for j in range(w):
            if field[i][j] == "#":
                res.append((i, j))
    return res


que = deque(check_black_list())
ans = -1
done = [[False] * w for _ in range(h)]

while que:
    for i in range(len(que)):
        y, x = que.popleft()
        if y < 0 or y >= h or x < 0 or x >= w or done[y][x] is True:
            continue
        field[y][x] = "#"
        done[y][x] = True
    

        for dy, dx in directions:
            que.append((y+dy, x+dx))

    ans += 1
    if check_done():
        print(ans)
        exit()



### FIXED CODE ###

def main():
    h,w = map(int,input().split())
    a = []
    for i in range(h):
        a.append(input())

    used = [True]*(h*w)

    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                p.append(i*w+j)
                used[i*w+j] = False


    
    res = 0
    while p:
        tank = []
        for e in p:
            if e>w-1 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w > 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e<(h-1)*w and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w<w-1 and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import collections
n = int(input())
ls = [input() for i in range(n)]    
c = collections.Counter(ls)
count = c.most_common()[0][1]
ans = []
for i in range(len(c)):
    if c.most_common()[i][1] == count:
        ans.append(c.most_common()[i][0])
    else:
        break    
ans.sort()
for i in ans:
  print(i)

### FIXED CODE ###

import collections
from collections import Counter

n = int(input())
ls = [input() for i in range(n)]    
c = Counter(ls).most_common()

count = c[0][1]
ans = []

for i in range(len(c)):
    if c[i][1] == count:
        ans.append(c[i][0])
    else:
        break   
ans = sorted(ans)
for i in ans:
    print(i)
### BUGGY CODE ###

# 初期入力
import sys
from collections import defaultdict
input = sys.stdin.readline  #文字列では使わない
H,W,M = map(int, input().split())

bom_H ={i:0 for i in range(1,H+1)}
bom_W ={i:0 for i in range(1,W+1)}
posision =defaultdict(int)
for i in range(M):
    h,w = map(int, input().split())
    bom_H[h] +=1
    bom_W[w] +=1
    posision[(h,w)] =1
max_H = [kv for kv in bom_H.items() if kv[1] == max(bom_H.values())]
max_W = [kv for kv in bom_W.items() if kv[1] == max(bom_W.values())]


ans =0
for p_h,v_h in max_H:
    for p_w,v_w in max_W:
        if posision[(p_h,p_w)] ==1:
            ans =max(ans,v_h +v_w -1)
        else:
            ans =max(ans,v_h +v_w )
            break
print(ans)

### FIXED CODE ###

import sys


H, W, M = map(int, input().split())
bomb = [tuple(map(lambda x: int(x) - 1, s.split())) for s in sys.stdin.readlines()]
X = [0] * H  # X:各行の爆破対象の個数
Y = [0] * W  # Y:各列の爆破対象の個数
for h, w in bomb:
    X[h] += 1
    Y[w] += 1
maxX = max(X)
maxY = max(Y)

R = [h for h, x in enumerate(X) if x == maxX]  # R:爆破対象の数が最大となる行の番号
C = [w for w, y in enumerate(Y) if y == maxY]  # C:爆破対象の数が最大となる列の番号

bomb = set(bomb)
for r in R:
    for c in C:
        # (r, c)に爆破対象が存在しないとき, maxX + maxY が答えとなることが確定するため, 
        # 即座に探索を終了する.
        if (r, c) not in bomb:
            print(maxX + maxY)
            exit()
print(maxX + maxY - 1)
### BUGGY CODE ###

nk = list(map(int,input().split()))
n,k= nk[0],nk[1]
h = list(map(int,input().split()))
dp = [0] * (n)
if n >= k:
    for i in range(k):#初期条件の定義
        dp[i] = abs(h[i] - h[0])
    for l in range(n-k):#漸化式の定義
        lis = []
        for m in range(k):
            lis.append(dp[l+m] + abs(h[l+k]-h[l+m]))
        dp[l+k] = min(lis)
    print(dp[n-1])
else:#n < k
    print(abs(h[n-1]-h[0]))

### FIXED CODE ###

nk = list(map(int,input().split()))
n,k= nk[0],nk[1]
h = list(map(int,input().split()))
dp = [0] * (n)
if n >= k:
    for i in range(k):#初期条件の定義
        dp[i] = abs(h[i] - h[0])
    for l in range(n-k):#漸化式の定義
        lis = []
        for m in range(k):
            lis.append(dp[l+m] + abs(h[l+k]-h[l+m]))
        dp[l+k] = min(lis)
    print(dp[n-1])
else:#n < k
    print(abs(h[n-1]-h[0]))
### BUGGY CODE ###

n = input()
S = list(map(int,input().split()))
n = input()
T = list(map(int,input().split()))
count =  0
for i in T:
    if i in S:
        count+= 1
print(count)

### FIXED CODE ###

input()
S = list(map(int,input().split()))
input()
T = list(map(int,input().split()))

def binarySearch(k,a):
    left = 0
    right = len(a)
    while left < right:
        middle = (left + right) // 2
        if a[middle] == k:
            return 1
        elif a[middle] < k:
            left = middle+1
        elif a[middle] > k:
            right = middle 
    return 0


count = 0
for t in T:
    count += binarySearch(t,S)
print(count)
### BUGGY CODE ###

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

dp = [0] * (1 << n)
dp[0] = 1

# 配るDP
for bit in range((1 << n) - 1):
    i = bin(bit).count('1')
    for j in range(n):
        if a[i][j] and (bit >> j) & 1 ^ 1:
            newbit = bit | (1 << j)
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[(1 << n) - 1])


### FIXED CODE ###

mod = 10**9+7
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
dp = [0]*(1 << n)
dp[0] = 1
for i in range(1, 1 << n):
    k = bin(i).count("1")
    for j in range(n):
        if i >> j & 1 and a[k-1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-1])
### BUGGY CODE ###

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

mae = []
stepsum = 0
for i in A:
  if mae and max(mae) > i:
    stepsum += max(mae)-i
  mae.append(i)

print(stepsum)

### FIXED CODE ###

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

heighest = 0
stepsum = 0
for i in A:
  if heighest < i:
    heighest = i
    continue
  else:
    stepsum += heighest-i

print(stepsum)
### BUGGY CODE ###

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

a = 0
for i in range(len(s)):
    if s.count(s[i]) > 1:
        a = 1
        break

if a == 0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

n = int(input())
s = list(map(int,input().split()))
 
def count(x):
    if len(s) != len(set(x)):
        return "NO"
    else:
        return "YES"
print(count(s))
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

class Node:
    def __init__(self):
        self.size = 1  # 自分以下のノードの数
        self.children = []

def dfs(v):
    V = Node()
    visited[v] = True
    for u in AL[v]:
        if visited[u]: continue
        U = dfs(u)
        V.size += U.size
        V.children.append(U)
    return V

def anaaki(V):
    ret = pow(2, n - 1, p) - 1
    for ch in V.children:
        ret -= pow(2, ch.size) - 1
        ret %= p
    ret -= pow(2, n - V.size) - 1
    ret %= p
    return ret

n = int(input())
AL = [[] for _ in range(n)]
visited = [False] * n
p = 10 ** 9 + 7
for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    AL[a].append(b)
    AL[b].append(a)

# dfs
root = dfs(0)
que = deque([root])
numer = 0
while que:
    next = que.popleft()
    numer += anaaki(next)
    numer %= p
    for ch in next.children:
        que.append(ch)

denom = pow(2, n, p)

print( numer * pow(denom, p - 2, p) % p)


### FIXED CODE ###

# classを使うのをやめてlistで実施する
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
import sys
input = sys.stdin.readline

def dfs(v):
    visited[v] = True
    for i in range(len(AL[v][CHILDREN])):
        u = AL[v][CHILDREN][i]
        if visited[u]:
            AL[v][CHILDREN][i] = None
            continue
        AL[v][SIZE] += dfs(u)
    return AL[v][SIZE]


def anaaki(v):
    ret = powp - 1
    for ch in AL[v][CHILDREN]:
        if ch is None: continue
        ret -= pow(2, AL[ch][SIZE], p) - 1
        ret %= p
    ret -= pow(2, n - AL[v][SIZE], p) - 1
    ret %= p
    return ret

n = int(input())
SIZE = 0
CHILDREN = 1
AL = [[1, []] for _ in range(n)]
visited = [False] * n
p = 10 ** 9 + 7
powp = pow(2, n - 1, p)

for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    AL[a][CHILDREN].append(b)
    AL[b][CHILDREN].append(a)

dfs(0)
numer = 0
for i in range(n):
    numer += anaaki(i)
    numer %= p

denom = pow(2, n, p)
print(numer * pow(denom, p - 2, p) % p)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = input()
ans = set()
for i in range(10):
  for I in range(n-2):
    if s[I] == str(i):
      for j in range(10):
        for J in range(I+1,n-1):
          if s[J] == str(j):
            for l in range(10):
              for L in range(J+1,n):
                if s[L] == str(l):
                  ans.add(i*100+j*10+l)
                  break
                  
            break
print(len(ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = input()
def multi_index(l,x):
  return tuple([i for i,_x in enumerate(l) if _x == x])

ans = 0
for i in range(10):
  e = 0
  if str(i) in s:
    c = multi_index(s,str(i))[0]
    for j in range(10):
      if str(j) in s and i!=j and c<=len(s)-2:
        for q in range(c+1,len(s)-1):
          if str(j) == s[q]:
            d = q
            break
        else:
          d = -1
      elif str(j) in s and i==j and len(multi_index(s,str(i)))>=2:
        d = multi_index(s,str(i))[1]
      else:
        d = -1
      if d > c:
        for l in range(10):
          if str(l) in s and i!=j and j!=l and i!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i!=j and j==l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i==j and j!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i==j and j==l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i==l and j!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 0
for c in S:
    if c == 'A':
        a += 3**q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+3**q, ab*3+a, ans*3+ab, q+1
    #a %= mod
    #ab %= mod
    #ans %= mod
    #q %= mod
    #print(c, a, ab, ans, q)
print(ans%mod)


### FIXED CODE ###

import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 1
for c in S:
    if c == 'A':
        a += q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+q, ab*3+a, ans*3+ab, q*3
    a %= mod
    ab %= mod
    ans %= mod
    q %= mod
print(ans % mod)
### BUGGY CODE ###

N, M = map(int, input().split())
dic = {}
for m in range(M):
  dic[m] = list(map(int, input().split()))
for n in range(N):
  l = sorted([d for d in dic.items() if d[1][0]==n+1], key=lambda x:x[1][1])
  for i in range(len(l)):
    l[i][1].append(i+1)
for d in dic.items():
  print("{:06d}{:06d}".format(d[1][0], d[1][2]))

### FIXED CODE ###

N, M = map(int, input().split())
dic = {}
cnt = [1]*N
for m in range(M):
  dic[m] = list(map(int, input().split()))
l = sorted([d for d in dic.items()], key=lambda x:x[1][1])
for m in range(len(l)):
  l[m][1].append(cnt[l[m][1][0]-1])
  cnt[l[m][1][0]-1] += 1
for d in dic.values():
  print("{:06d}{:06d}".format(d[0], d[2]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n,q=map(int,input().split())
g=[[]for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

lis = [0 for i in range(n)]
for i in range(q):
    p,x=map(int,input().split())
    lis[p-1]+=x

def dfs(i,j,k):
    nex=g[i]
    lis[i]=k
    for d in nex:
        if d==j: continue
        nk=k+lis[d]
        dfs(d,i,nk)

dfs(0,-1,lis[0])
print(*lis)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)
n,q=map(int,input().split())
g=[[]for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

lis = [0 for i in range(n)]
for i in range(q):
    p,x=map(int,input().split())
    lis[p-1]+=x

def dfs(i,j):
    nex=g[i]
    for d in nex:
        if d==j: continue
        #print(d)
        lis[d]+=lis[i]
        dfs(d,i)

dfs(0,-1)
print(*lis)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
sorted_a=list(set(sorted(a)))
for i in range(n):
    y=a[i]
    print(sum([sum(range(a.count(x) - (1 if x==y else 0))) for x in sorted_a]))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
d={}
for x in a:
    if d.get(x) is None:
        d[x]=1
        continue
    d[x]+=1
total=0
for v in d.values():
    total+=(v-1)*v//2
for x in a:
    print(total-d[x]+1)
### BUGGY CODE ###

#coding: utf-8
from collections import deque
N, M = map(int, input().split())
d = [[10^6 for _ in range(N)] for _ in range(N)]
dd = {i:[] for i in range(N)}
for i in range(N):
    d[i][i] = 0
for i in range(M):
    a, b = map(int, input().split())
    dd[a-1].append(b-1)
    dd[b-1].append(a-1)
ans = [0 for _ in range(N)]
visited = [False for _ in range(N)]
queue = []
for i in range(len(dd[0])):
    queue.append([0, dd[0][i]])
queue = deque(queue)
while queue:
    q = queue.popleft()
    if visited[q[1]]:
        continue
    visited[q[1]] = True
    ans[q[1]] = q[0] + 1
    for v in dd[q[1]]:
        if not visited[v]:
            queue.append([q[1], v])
print("Yes")
print(*ans[1:], sep="\n")


### FIXED CODE ###

#coding: utf-8
from collections import deque
N, M = map(int, input().split())
dd = {i:[] for i in range(N)}
for i in range(M):
    a, b = map(int, input().split())
    dd[a-1].append(b-1)
    dd[b-1].append(a-1)
ans = [0 for _ in range(N)]
visited = [False for _ in range(N)]
queue = []
for i in range(len(dd[0])):
    queue.append([0, dd[0][i]])
queue = deque(queue)
while queue:
    q = queue.popleft()
    if visited[q[1]]:
        continue
    visited[q[1]] = True
    ans[q[1]] = q[0] + 1
    for v in dd[q[1]]:
        if not visited[v]:
            queue.append([q[1], v])
print("Yes")
print(*ans[1:], sep="\n")
### BUGGY CODE ###

p = [0, 0, 1, 1, 0, 1]
while True:
    try:
        n = int(input())
        if len(p) < n+1:
            i = len(p)
            while i < n+1:
                j = 2
                flag = True
                while j <= i**0.5:
                    if i % j == 0:
                        p.append(0)
                        flag = False
                        break
                    j += 1
                if flag == True:
                    p.append(1)
                i += 1
        print(sum(p[0:n+1]))
    except:
        break

### FIXED CODE ###

import sys
prime = [0]
isPrime = [1 for i in range(1000000)]
isPrime[0] = 0
isPrime[1] = 0
for i in sys.stdin:
    n = int(i)
    if prime[len(prime)-1] < n:
        for i in range(prime[len(prime)-1]+1,n+1):
            if isPrime[i] == 1:
                prime.append(i)
                for j in range(i*2, 1000000, i):
                    isPrime[j] = 0
    print(sum(isPrime[:n+1]))
### BUGGY CODE ###

import numpy as np
n = int(input())
A = np.array(list(map(int, input().split())))
A = np.sort(A)
c = 0
while len(A) > 0:
    ai = A[0]
    AL = A[1:]
    if not ai in AL:
        c += 1
    mask = AL % ai != 0
    A = AL[mask]
print(c)


### FIXED CODE ###

from collections import Counter
n = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)
A = list(set(A))
ok = [True] * (10**6+1)

for a in A:
    temp = a+a
    while temp < 10**6+1:
        ok[temp] = False
        temp += a

c = 0
for a in A:
    if C[a] == 1 and ok[a] == True:
        c += 1
print(c)
### BUGGY CODE ###

s = input()

cnt = 0
for i in range(len(s)):
	if s[i] == "B":
		cnt += s[i:].count("W")

print(cnt)

### FIXED CODE ###


s = input()
ans = 0
tmp = 0
#saving the number of black
for c in reversed(s):
    if c == 'W':
        tmp += 1
    else:
        ans += tmp
print(ans)
### BUGGY CODE ###

from copy import deepcopy
INF = 10 ** 10
N = int(input())
A = []
for _ in range(N):
    A.append(list(map(int,input().split())))


L = []
for i in range(N-1):
    for j in range(i+1, N):
        L.append((A[i][j], i, j))
L.sort()

B = deepcopy(A)
for k in range(N):
    for i in range(N):
        for j in range(N):
            if B[i][k] != 0 and B[k][j] != 0 and B[i][j] == B[i][k] + B[k][j]:
                B[i][j] = INF

ans = 0
for i in range(N):
    for j in range(N):
        if B[i][j] != INF:
            ans += B[i][j]
ans //= 2

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

if A == B:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

from copy import deepcopy
INF = 10 ** 10
N = int(input())
A = []
for _ in range(N):
    A.append(list(map(int,input().split())))


L = []
for i in range(N-1):
    for j in range(i+1, N):
        L.append((A[i][j], i, j))
L.sort()

B = deepcopy(A)
for k in range(N):
    for i in range(N):
        for j in range(N):
            if B[i][k] != 0 and B[k][j] != 0 and B[i][j] == B[i][k] + B[k][j]:
                B[i][j] = INF

ans = 0
for i in range(N):
    for j in range(N):
        if B[i][j] != INF:
            ans += B[i][j]
ans //= 2

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

if A == B:
    print(ans)
else:
    print(-1)