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

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
e = 10**-9

for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(e)
data = []
rs = []
cs = []
for pu in range(n):
    ux,uy = divmod(pu,w)
    if ss[ux][uy]=="#":
        continue
    for xx,yy,vv in zip(dx,dy,vvs):
        x,y = ux+xx, uy+yy
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
        u = x*w + y
        data.append(vv)
        rs.append(pu)
        cs.append(u)
        
import scipy.sparse
m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(n, n))
ans = scipy.sparse.csgraph.dijkstra(m, indices=start, directed=False) # startからの最短路木を求める
if ans[goal]>10**9:
    print(-1)
else:
    print(int(ans[goal]))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = hpp(q)
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            hp(q, (num, u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)
### BUGGY CODE ###

res = input()
r = False
for _ in range(int(input())):
    q = input().split()
    if q[0] == "1":
        r = not r
    else:
        if q[1] == "1":
            if r:
                res += q[2]
            else:
                res = q[2] + res
        else:
            if r:
                res = q[2] + res
            else:
                res += q[2]

if r:
    print(res[::-1])
else:
    print(res)

### FIXED CODE ###

S = input()
r = False
L = []
R = []
for _ in range(int(input())):
    q = input().split()
    if q[0] == "1":
        r = not r
    else:
        if q[1] == "1":
            if r:
                R.append(q[2])
            else:
                L.append(q[2])
        else:
            if r:
                L.append(q[2])
            else:
                R.append(q[2])


if r:
    R.reverse()
    print("".join(R + list(S[::-1]) + L))
else:
    L.reverse()
    print("".join(L + [S] + R))
### BUGGY CODE ###

N,M=map(int,input().split())
a=[]
b=[]
c=[]
flag=0
for i in range(M):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)
    if x==1:
        c.append(y)
for i in range(M):
    if b[i]==N:
        if a[i] in c:
            flag+=1
if flag==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")



### FIXED CODE ###

N,M=[int(i) for i in input().split()]
a=[]
b=[]
c=[]
for i in range(M):
    x,y=[int(i) for i in input().split()]
    if x==1 :
        c.append(y)
    if y==N:
        c.append(x)
if len(c)==len(set(c)):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
### BUGGY CODE ###



def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[i][j] - number of pairs for first i man, with mask j=0011..01

    OPT[i+1][j|k] += OPT[i][j] k has exactly one bit set j|k != j and i+1 is compatible with k-th woman

    """
    N = read_int()
    modulo = 10**9+7
    A = []
    for _ in range(N):
        A.append(read_ints())
    OPT = [
        [0]*(2**N) for _ in range(1+N)
    ]
    OPT[0][0] = 1
    S = set([0])
    for i in range(N):
        new_S = set()
        for j in S:
            for k in range(N):
                if j & (1 << k) == 0 and A[i][k] == 1:
                    OPT[i+1][j|(1 << k)] = (OPT[i+1][j|(1 << k)]+OPT[i][j])%modulo
                    new_S.add(j|(1 << k))
        S = new_S
    return OPT[-1][-1]


if __name__ == '__main__':
    print(solve())


### FIXED CODE ###



def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def count_bits(N):
    T = 0
    while N != 0:
        T += N & 1
        N >>= 1
    return T


def solve():
    """
    OPT[i][j] - number of pairs for first i man, with mask j=0011..01

    OPT[i+1][j|k] += OPT[i][j] k has exactly one bit set j|k != j and i+1 is compatible with k-th woman

    """
    N = read_int()
    modulo = 10**9+7
    A = []
    for _ in range(N):
        A.append(read_ints())
    dp = [0]*(2**N)
    dp[0] = 1
    for mask in range(2**N-1):
        a = count_bits(mask)
        for b in range(N):
            if A[a][b] and mask&(1<<b) == 0:
                dp[mask|(1<<b)] = (dp[mask|(1<<b)]+dp[mask])%modulo
    return dp[-1]


if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

#B
N = int(input())
A = list(map(int, input().split()))
result = 1
for a in A:
    result *= a
if result >10**18:
    print(-1)
else:
    print(result)

### FIXED CODE ###

#B
def main ():
    N = int(input())
    A = list(map(int,input(). split ()))
    if 0 in A:
        print(0)
        return
    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod)
main ()
### BUGGY CODE ###

from collections import deque


def main():
    h, w = map(int, input().split())
    cs = list(map(int, input().split()))
    ds = list(map(int, input().split()))
    S = [[s for s in input()] for _ in range(h)]

    curq = deque()
    nexq = deque([(cs[0] - 1, cs[1] - 1)])
    l = 0
    while len(nexq) > 0:
        curq, nexq = nexq, deque()
        while len(curq) > 0:
            y, x = curq.popleft()
            if S[y][x] != ".":
                continue

            S[y][x] = l
            for dy in range(-2, 3):
                for dx in range(-2, 3):
                    if 0 <= y + dy < h and 0 <= x + dx < w and S[y + dy][x + dx] == ".":
                        if abs(dx) + abs(dy) < 2:
                            curq.append((y + dy, x + dx))
                        else:
                            nexq.append((y + dy, x + dx))
        l += 1

    ans = S[ds[0] - 1][ds[1] - 1]
    print(ans if ans != "." else -1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque


def main():
    h, w = map(int, input().split())
    cs = list(map(int, input().split()))
    ds = list(map(int, input().split()))
    S = [[s for s in input()] for _ in range(h)]

    curq = deque()
    nexq = deque([(cs[0] - 1, cs[1] - 1)])
    l = 0
    while len(nexq) > 0:
        curq, nexq = nexq, deque()
        while len(curq) > 0:
            y, x = curq.popleft()
            if S[y][x] != ".":
                continue

            S[y][x] = l
            for dy in range(-2, 3):
                for dx in range(-2, 3):
                    if 0 <= y + dy < h and 0 <= x + dx < w and S[y + dy][x + dx] == ".":
                        if abs(dx) + abs(dy) < 2:
                            curq.append((y + dy, x + dx))
                        else:
                            nexq.append((y + dy, x + dx))
        l += 1

    ans = S[ds[0] - 1][ds[1] - 1]
    print(ans if ans != "." else -1)


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

from math import ceil
n, k = map(int, input().split())
A = sorted(map(int, input().split()))
F = sorted(map(int, input().split()))
A.reverse()
ok = A[0] * F[-1]
ng = -1
while ok - ng != 1:
    x = (ok + ng) // 2
    cnt = 0
    for a, f in zip(A, F):
        if a * f > x:
            cnt += ceil(a - x / f)
        if cnt > k:
            ng = x
            break
    else:
        ok = x

print(ok)


### FIXED CODE ###

def main():
    from math import ceil
    n, k = map(int, input().split())
    A = sorted(map(int, input().split()))
    F = sorted(map(int, input().split()))
    A.reverse()
    ok = max(a * f for a, f in zip(A, F))
    ng = -1
    while ok - ng != 1:
        x = (ok + ng) // 2
        cnt = 0
        for a, f in zip(A, F):
            if a * f > x:
                cnt += ceil(a - x / f)
            if cnt > k:
                ng = x
                break
        else:
            ok = x

    print(ok)

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

s = input()
q = int(input())
ud = False
ud_count = 0
for i in range(q):
    query = list(input().split())
    if int(query[0]) == 1:
        ud = not(ud)
        ud_count += 1
    else:
        if (int(query[1])==1 and ud==False) or (int(query[1])==2 and ud==True):
            s = query[2] + s
        else:
            s += query[2]
if ud_count%2:
    print(s[::-1])
else:
    print(s)


### FIXED CODE ###

s = input()
q = int(input())
ud = False
ud_count = 0
sub_s = ""
for i in range(q):
    query = list(input().split())
    if int(query[0]) == 1:
        ud = not(ud)
        ud_count += 1
    else:
        if (int(query[1])==1 and ud==False) or (int(query[1])==2 and ud==True):
            sub_s += query[2]
        else:
            s += query[2]
s = sub_s[::-1] + s
if ud_count%2:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    s = [0]*n
    l, r = -1*10**18, 10**18
    while l+1 < r:
        p = (l+r)//2
        for i, v in enumerate(a):
            if v < 0:
                target = p // v
                index = bisect_right(a, target)
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif v > 0:
                target = (p+a[i]-1) // v
                index = bisect_left(a, target)
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                if 0 < p:
                    s[i] = n - 1
                else:
                    s[i] = 0
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    if k <= num_neg_pair:
        neg_a = np.array(neg_a)
        pos_a = np.array(pos_a)
        l = -1*10**18
        r = 0
        while l+1 < r:
            p = (l+r)//2
            cnt = np.searchsorted(pos_a, p//neg_a, side="riget").sum()
            result = n*cnt_neg - (cnt + (cnt_neg + cnt_zro)*cnt_neg)
            if result < k:
                l = p
            else:
                r = p
        print(l)
    elif k <= num_neg_pair + num_zro_pair:
        print("0")
    else:
        k -= num_neg_pair + num_zro_pair
        for i in range(len(neg_a)):
            neg_a[i] = -neg_a[i]
        neg_a = np.array(neg_a)
        neg_a = np.sort(neg_a)
        pos_a = np.array(pos_a)
        l = 1
        r = 10**18+1
        while l+1 < r:
            p = (l+r)//2
            cnt_1 = np.searchsorted(neg_a, (p+neg_a-1)//neg_a, side="left").sum()
            cnt_2 = np.searchsorted(pos_a, (p+pos_a-1)//pos_a, side="left").sum()
            cnt_1 -= np.count_nonzero(neg_a < (p+neg_a-1)//neg_a)
            cnt_2 -= np.count_nonzero(pos_a < (p+pos_a-1)//pos_a)
            result = (cnt_1 + cnt_2)//2
            if result < k:
                l = p
            else:
                r = p
        print(l)

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

import itertools

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

for i, j in itertools.combinations(N, 2):
    if j - i == A[i] + A[j]:
        count += 1
        
print(count)

### FIXED CODE ###

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

A1 = []
A2 = []

for i in range(N):
    A1.append(i + A[i])
    A2.append(i - A[i])

C_A1 = collections.Counter(A1)
C_A2 = collections.Counter(A2)
ans = 0
for i in range(N):
    ans += C_A1[i]*C_A2[i]
    
print (ans)
### BUGGY CODE ###

import bisect

N, Q = map(int, input().rstrip().split(' '))

construction = [list(map(int, input().rstrip().split(' '))) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
construction = sorted(construction, key=lambda x: x[2])

dist = [-1] * Q
jump = [-1] * Q
indices = list(range(Q))
for c in construction:
    i1 = bisect.bisect_left(D, c[0] - c[2])
    i2 = bisect.bisect_left(D, c[1] - c[2])
    i = i1
    while i < i2:
        if jump[i] != -1:
            i = jump[i]
            continue
        else:
            jump[i] = i2
            dist[i] = c[2]
            i += 1
    
for d in dist:
    print(d)
    

### FIXED CODE ###

import sys
import bisect
input=sys.stdin.readline

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

construction = [list(map(int, input().split(' '))) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
construction = sorted(construction, key=lambda x: x[2])

dist = [-1] * Q
jump = [-1] * Q
indices = list(range(Q))
for s, t, x in construction:
    i1 = bisect.bisect_left(D, s-x)
    i2 = bisect.bisect_left(D, t-x)
    i = i1
    while i < i2:
        k = jump[i]
        if k != -1:
            i = k
        else:
            jump[i] = i2
            dist[i] = x
            i += 1
    
for d in dist:
    print(d)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
#
import math
import sys
import itertools
import numpy as np


# なんこか入力
x,y,z,k = map(int, input().split())

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
d = []
e = []
s = 0
for i in range(x):
    for j in range(y):
        d.append(a[i]+b[j])

d.sort(reverse=True)
p = min(k,len(d))

for i in range(p):
    for j in range(z):
        e.append(d[i]+c[j])

e.sort(reverse=True)
#print(e)
for i in range(k):
    print(e[i])


### FIXED CODE ###

# -*- coding: utf-8 -*-
# ヒープキューを使う

import math
import sys
import itertools
import numpy as np
import heapq
 
# なんこか入力
x,y,z,k = map(int, input().split())
 
# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

a.sort()
b.sort()
c.sort()

h = [] # heap
g = set() #使用済み

heapq.heappush(h,(-(a[x-1]+b[y-1]+c[z-1]),x-1,y-1,z-1))
g.add((x-1,y-1,z-1))

#print(h)

for i in range(k):
#    heapq.heapify(h)
    temp =[]
    temp = heapq.heappop(h)
    print(-temp[0])
    for j in range(3):
        if temp[j+1]==0:
            continue
        if j == 0:
            temp2 = (-(a[temp[1]-1]+b[temp[2]]+c[temp[3]]),temp[1]-1,temp[2],temp[3])
        elif j == 1:
            temp2 = (-(a[temp[1]]+b[temp[2]-1]+c[temp[3]]),temp[1],temp[2]-1,temp[3])
        else:
            temp2 = (-(a[temp[1]]+b[temp[2]]+c[temp[3]-1]),temp[1],temp[2],temp[3]-1)
        if (temp2[1],temp2[2],temp2[3]) in g:
            continue
        heapq.heappush(h,temp2)
        g.add((temp2[1],temp2[2],temp2[3]))
### BUGGY CODE ###

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    ret = 0
    while M >= 2:
        if N >= 1 and M >= 2:
            ret += 1
            M -= 2
            N -= 1
        if N == 0 and M >= 2:
            N += 1
            M -= 2
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()

    ret = 0
    if N * 2 <= M:
        ret += N
        ret += (M - N * 2) // 4
    else:
        ret += M // 2
    print(ret)


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

# -*- coding: utf-8 -*-
def PoAP_fnct(MOD):
    #MOD:素数
    fact_mod = [1,1]
    inv_mod = [0,1]
    inv_fact_mod = [1,1]
    i = len(fact_mod)
    i_ = len(inv_fact_mod)

    def PoAP(x,d,n):
        nonlocal i, i_
        if d == 0:
            return pow(x,n,MOD)

        while d >= i_:
            inv_mod[i_:i_] = [(-inv_mod[MOD%i_]*(MOD//i_))%MOD]
            inv_fact_mod[i_:i_] = [(inv_fact_mod[i_-1]*inv_mod[i_])%MOD]
            i_ += 1

        j = (-x*inv_mod[d])%MOD
        if j < n:
            return 0

        x = (x*inv_mod[d])%MOD

        while (x+n-1)%MOD >= i:
            fact_mod[i:i] = [(fact_mod[i-1]*i)%MOD]
            i += 1

        while x-1 >= i_:
            inv_mod[i_:i_] = [(-inv_mod[MOD%i_]*(MOD//i_))%MOD]
            inv_fact_mod[i_:i_] = [(inv_fact_mod[i_-1]*inv_mod[i_])%MOD]
            i_ += 1

        return fact_mod[(x+n-1)%MOD] * inv_fact_mod[x-1] * pow(d,n,MOD) % MOD
    return PoAP

def solve():
    Q = int(input())
    PoAP = PoAP_fnct(1000003)
    res = '\n'.join([str(PoAP(*map(int, input().split()))) for _ in range(Q)])
    return str(res)

if __name__ == '__main__':
    print(solve())



### FIXED CODE ###

# -*- coding: utf-8 -*-
def PoAP_fnct(MOD):
    #MOD:素数
    fact_mod = [1,1]
    inv_mod = [0,1]
    inv_fact_mod = [1,1]
    i = len(fact_mod)
    i_ = len(inv_fact_mod)

    def PoAP(x,d,n):
        nonlocal i, i_
        if d == 0:
            return pow(x,n%(MOD-1),MOD)

        while d >= i_:
            inv_mod[i_:i_] = [(-inv_mod[MOD%i_]*(MOD//i_))%MOD]
            inv_fact_mod[i_:i_] = [(inv_fact_mod[i_-1]*inv_mod[i_])%MOD]
            i_ += 1

        j = (-x*inv_mod[d])%MOD
        if j < n:
            return 0

        x = (x*inv_mod[d])%MOD

        while (x+n-1)%MOD >= i:
            fact_mod[i:i] = [(fact_mod[i-1]*i)%MOD]
            i += 1

        while x-1 >= i_:
            inv_mod[i_:i_] = [(-inv_mod[MOD%i_]*(MOD//i_))%MOD]
            inv_fact_mod[i_:i_] = [(inv_fact_mod[i_-1]*inv_mod[i_])%MOD]
            i_ += 1

        return fact_mod[(x+n-1)%MOD] * inv_fact_mod[x-1] * pow(d,n%(MOD-1),MOD) % MOD
    return PoAP

def solve():
    Q = int(input())
    PoAP = PoAP_fnct(1000003)
    res = '\n'.join([str(PoAP(*map(int, input().split()))) for _ in range(Q)])
    return str(res)

if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

n, k = map(int, input().split())
p = [int(x) for x in input().split()]

l = 0
r = k

result = 0.0
m = 0
pp = []
while r != len(p)+1:
  tmp_pp = p[l:r]
  s = sum(tmp_pp)
  l += 1
  r += 1
  if s <= m:
    continue
  m = s
  pp = tmp_pp

for pi in pp:
  result += pi / 2 + 1 / 2
print(result)

### FIXED CODE ###

from itertools import accumulate
n, k = map(int, input().split())
p = list(map(int, input().split()))

pp = [0] + list(accumulate(p))

m = 0
for i in range(n - k + 1):
  m = max(m,pp[i + k] - pp[i])
print((m+k)/2)
### BUGGY CODE ###

def resolve():
    (n, m) = list(map(int, input().split(" ")))
    results = [0] * n
    for i in range(m):
        o = list(map(int, input().split(" ")))
        if i == 0:
            results[o[0]:o[1]+1] = [1] * (o[1]+1-o[0])
            continue
        for j in range(n):
            if not results[j]:
                continue
            if not (o[0] <= j and j <= o[1]):
                results[j] = 0
                if o[1] < j:
                    break
            if results.count(1) == 0:
                print(0)
                return

    print(results.count(1))


if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    (n, m) = list(map(int, input().split(" ")))
    
    for i in range(m):
        o = list(map(int, input().split(" ")))
        if i == 0:
            lmax = o[0]
            rmin = o[1]
        else:
            lmax = max(lmax, o[0])
            rmin = min(rmin, o[1])

    print(rmin-lmax+1 if lmax <= rmin else 0)


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

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(n):
  if a[i] != 0:
    if i == n-1:
      ans +=1
    else: 
      if a[i] == a[i+1]:
        for j in range(i+1, n):
          if a[j]%a[i]==0:
            a[j]=0
      else:
        ans += 1
        for j in range(i+1, n):
          if a[j]%a[i]==0:
            a[j]=0
        
    
print(ans)

### FIXED CODE ###

n = int(input())
a  = list(map(int, input().split()))
a.sort()
dp = [0]*a[n-1]
ans = 0
temp2 = 0
for i in range(n):
  if temp2 == a[i]:
    ans -= 1
    temp2=0
  if dp[a[i]-1] == 0:
    ans += 1
    temp = a[i]
    temp2 = a[i]
    while temp <= a[n-1]:
      dp[temp-1] = 1
      temp = temp+a[i]
  #print(dp)    
print(ans)