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

from collections import deque

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
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()


### FIXED CODE ###

from collections import deque

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
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

import itertools
def myAnswer(N:int,S:str) -> int:
   counter = 0
   for i in range(1,N+1):
      for p in itertools.combinations(S,i):
         if (len(set(p)) == i):
            counter += 1

   return counter

def modelAnswer():
   return
def main():
   N = int(input())
   S = input()
   print(myAnswer(N,S))
if __name__ == '__main__':
   main()

### FIXED CODE ###

from collections import Counter
def myAnswer(N:int,S:list) -> int:
   counter = Counter(S)
   ans = 1
   for s in list(set(S)):
      ans *= counter[s] + 1

   return (ans - 1) % (10 ** 9 + 7)
def modelAnswer():
   return
def main():
   N = int(input())
   S = list(input())
   print(myAnswer(N,S))
if __name__ == '__main__':
   main()
### BUGGY CODE ###

h,w = map(int,input().split())
g = []
for i in range(h):
    s = list(input())
    g.append(s)


#left
left = [[0]*w for i in range(h)]
for i in range(h):
    cnt = 0
    for j in range(w):
        if g[i][j] == ".":
            cnt += 1
            left[i][j] =cnt
        else:
            cnt = 0

#right
right = [[0]*w for i in range(h)]
for i in range(h-1,-1,-1):
    cnt = 0
    for j in range(w-1,-1,-1):
        if g[i][j] == ".":
            cnt += 1
            right[i][j] =cnt
        else:
            cnt = 0
#top
top = [[0]*w for i in range(h)]
for j in range(w):
    cnt = 0
    for i in range(h):
        if g[i][j] == ".":
            cnt += 1
            top[i][j] =cnt
        else:
            cnt = 0
#down
down = [[0]*w for i in range(h)]
for j in range(w-1,-1,-1):
    cnt = 0
    for i in range(h-1,-1,-1):
        if g[i][j] == ".":
            cnt += 1
            down[i][j] =cnt
        else:
            cnt = 0

maxans = -1
for i in range(h):
  for j in range(w):
    if g[i][j] =="#":
      continue
    ans = left[i][j]+right[i][j]+top[i][j]+down[i][j]-3
    maxans = max(ans,maxans)
    
print(maxans)


### FIXED CODE ###

h,w = map(int,input().split())
g = []
for i in range(h):
    s = list(input())
    g.append(s)


#left
left = [[0]*w for i in range(h)]
for i in range(h):
    cnt = 0
    for j in range(w):
        if g[i][j] == ".":
            cnt += 1
            left[i][j] =cnt
        else:
            cnt = 0

#right
right = [[0]*w for i in range(h)]
for i in range(h-1,-1,-1):
    cnt = 0
    for j in range(w-1,-1,-1):
        if g[i][j] == ".":
            cnt += 1
            right[i][j] =cnt
        else:
            cnt = 0
#top
top = [[0]*w for i in range(h)]
for j in range(w):
    cnt = 0
    for i in range(h):
        if g[i][j] == ".":
            cnt += 1
            top[i][j] =cnt
        else:
            cnt = 0
#down
down = [[0]*w for i in range(h)]
for j in range(w-1,-1,-1):
    cnt = 0
    for i in range(h-1,-1,-1):
        if g[i][j] == ".":
            cnt += 1
            down[i][j] =cnt
        else:
            cnt = 0

maxans = -1
for i in range(h):
  for j in range(w):
    if g[i][j] =="#":
      continue
    ans = left[i][j]+right[i][j]+top[i][j]+down[i][j]-3
    maxans = max(ans,maxans)
    
print(maxans)
### BUGGY CODE ###

H,W=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]
import numpy as np
d=np.zeros((H+1,W+1,80*(H+W)),dtype=bool)
d[1][1][A[0][0]-B[0][0]]=d[1][1][B[0][0]-A[0][0]]=1
for h in range(H):
    for w in range(W):
        x=A[h][w]-B[h][w]
        d[h+1][w+1]|=(np.roll(d[h][w+1],x))|(np.roll(d[h][w+1],-x))|(np.roll(d[h+1][w],x))|(np.roll(d[h+1][w],-x))
for i in range(99):
    if d[H][W][i] or d[H][W][-i]:
        print(i)
        exit()

### FIXED CODE ###

H,W=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]
d=[[0]*W for j in range(H)]
m=80*(H+W)
d[0][0]=1<<m
for h in range(H):
    for w in range(W):
        x=abs(A[h][w]-B[h][w])
        if h>0:
            d[h][w]|=d[h-1][w]
        if w>0:
            d[h][w]|=d[h][w-1]
        d[h][w]=d[h][w]<<x|d[h][w]>>x
x,y=1<<m,1<<m
for i in range(99):
    if d[H-1][W-1]&x or d[H-1][W-1]&y:
        print(i)
        exit()
    x<<=1
    y>>=1
### BUGGY CODE ###

from collections import deque
 
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
 
que = deque()
INF = float('inf')
dx = [1, 0, -1, 0]
dy = [0, 1, 0 , -1]            
D = [[INF] * W for i in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            que.append([i, j])
            D[i][j] = 0
                       
def bfs():
    while len(que) != 0:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and A[nx][ny] != '#' and D[nx][ny] == INF:
                que.append([nx, ny])
                D[nx][ny] = D[p[0]][p[1]] + 1
    
bfs()

ans = 0
for i in range(H):
    for j in range(W):
        tmp = D[i][j]
        ans = max(ans, tmp)
        
print(ans)

### FIXED CODE ###

from collections import deque
 
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
 
que = deque()
INF = float('inf')
dx = [1, 0, -1, 0]
dy = [0, 1, 0 , -1]            
D = [[INF] * W for i in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            que.append([i, j])
            D[i][j] = 0
                       
def bfs():
    while len(que) != 0:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and A[nx][ny] != '#' and D[nx][ny] == INF:
                que.append([nx, ny])
                D[nx][ny] = D[p[0]][p[1]] + 1
    
bfs()

ans = 0
for i in range(H):
    for j in range(W):
        tmp = D[i][j]
        ans = max(ans, tmp)
        
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline
 
S = input().strip()
l = len(S)
dp = np.zeros((l, 2019), dtype=int)
for i in range(l):
    s = int(S[i])
    for j in range(2019):
        k = (10 * j + s) % 2019
        dp[i][k] = dp[i-1][j]
    dp[i][s] += 1
 
print(dp[:, 0].sum())

### FIXED CODE ###

import sys
input = sys.stdin.readline

S = input().strip()
l = len(S)
dic = {0:[-1]}
ans = 0
base = 1
mod = 0
for i in range(0, l):
    base = (10 * base) % 2019
    s = base * int(S[l-1-i]) + mod
    mod = s % 2019
    if mod in dic:
        dic[mod].append(i)
    else:
        dic[mod] = [i]

for key, val in dic.items():
    v_len = len(val)
    ans += (v_len * (v_len -1))// 2

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

N = int(input())

for i in range(1,N+1):
  ans = 0
  if i < 6:
    print(ans)
  else:
    for a in range(2,int((2*i)**0.5+1)):
      for b in range(2,int((2*i-a**2)**0.5+1)):
        for c in range(2,int((2*i-a**2-b**2)**0.5+1)):
          #print(a,b,c)
          if a**2 + b**2 + c**2 == 2*i:
            if max(a,b,c) < a+b+c-max(a,b,c):
              ans += 1
              #print(a,b,c)
    print(ans)



### FIXED CODE ###

import numpy as np

N = int(input())

#print(1e+5)
ans = np.zeros(int(1e+5),dtype = int)
for x in range(1,int(N**0.5+1)):
  for y in range(x,int((N-x**2)**0.5+1)):
    for z in range(y,int((N-x**2-y**2)**0.5+1)):
      n = x**2 + y**2 + z**2 +x*y+y*z+z*x
      num = len({x,y,z})
      if num == 1:
        ans[n] += 1
      elif num == 2:
        ans[n] += 3
      elif num == 3:
        ans[n] += 6

for i in range(1,N+1):
  print(ans[i])
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
c=0
for i in range(n):
  for j in range(i+1,n+1):
    s=l[i:j]
    if sum(s)==0:
      c+=1
print(c)

### FIXED CODE ###

def main():
    import sys
    from itertools import accumulate
    from collections import Counter

    n = int(input())
    a = list(map(int, sys.stdin.readline().split()))
    b = [0] + list(accumulate(a))
    c = Counter(b)

    ans = 0
    for v in c.values():
        ans += v * (v - 1) // 2

    print(ans)


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

S = input()
p = 10**9 + 7

N = len(S)
# dp = [[0 for _ in range(13)] for _ in range(N + 1)]
# dp[N][0] = 1 # i = N - 1のケースでうまくいくための処置

dp = [[0 for _ in range(13)] for _ in range(2)]
dp[0][0] = 1 # i = N - 1のケースでうまくいくための処置
r = 0

for i in range(N - 1,  -1,  -1):  # 小さい桁から順に
    w = 1 if i == N - 1 else (w * 10) % 13 # 各桁の重み
    r = 1 - r  # dpの0行目と1行目を交互に使う
    if S[i] == '?':
        for j in range(13):
            for k in range(10): # ?の値が0, 1, ..., 9のとき
                dp[r][(j + w * k) % 13] += dp[1 - r][j]
                if dp[r][(j + w * k) % 13] >= p:
                    dp[r][(j + w * k) % 13] -= p
    else:
        k = int(S[i])
        for j in range(13):
            dp[r][(j + w * k) % 13] = dp[1 - r][j]

    dp[1 - r] = [0] * 13

print(dp[r][5])


### FIXED CODE ###

p = 10**9 + 7
S = input()
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(2)]
dp[0][0] = 1 # i = N - 1のケースでうまくいくための処置
r = 0

for i in range(N - 1,  -1,  -1):  # 小さい桁から順に
    w = 1 if i == N - 1 else (w * 10) % 13 # 各桁の重み
    r = 1 - r  # dpの0行目と1行目を交互に使う
    if S[i] == '?':
        for j in range(13):
            for k in range(10): # ?の値が0, 1, ..., 9のとき
                dp[r][(j + w * k) % 13] += dp[1 - r][j]
                if dp[r][(j + w * k) % 13] >= p:
                    dp[r][(j + w * k) % 13] -= p
    else:
        k = int(S[i])
        for j in range(13):
            dp[r][(j + w * k) % 13] = dp[1 - r][j]

    dp[1 - r] = [0] * 13

print(dp[r][5])
### BUGGY CODE ###

import sys
def li():
    return list(map(int,input().split()))
n=int(input())
p=li()
s=1
for i in range(n):
    s*=p[i]
if s>=10**18+1:
    print(-1)
    sys.exit()
print(s)

### FIXED CODE ###

import sys
def main():

    n=int(input())
    p=list(map(int,input().split()))
    s=1
    p=sorted(p)
    for i in p:
        s*=i
        if i==0:
            print(0)
            sys.exit()
        elif s>=10**18+1:
            print(-1)
            sys.exit()
    print(s)

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

import math


def main():
    N = int(input())
    table = [''.join(sorted(list(input()))) for _ in range(N)]
    sort_table = list(set(list(table)))
    ans = 0
    for i in sort_table:
        n = table.count(i)
        if n <= 1:
            continue
        x = math.factorial(n) / (2 * math.factorial(n - 2))
        ans += x

    print(int(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections


def main():
    N = int(input())
    table = [''.join(sorted(list(input()))) for _ in range(N)]
    sort_table = set(table)
    cnt_table = collections.Counter(table)
    ans = 0
    for i in sort_table:
        num_of_i = cnt_table[i]
        if num_of_i <= 1:
            continue
        x = (num_of_i * (num_of_i - 1)) // 2
        ans += x

    print(ans)


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

s = list(input())
p = 0
flg = True
while flg:
    flg = False
    for i in range(len(s)-1):
        if s[i] == 'B' and s[i+1] == 'W':
            s[i] = 'W'
            s[i+1] = 'B'
            p += 1
            flg = True

print(p)

### FIXED CODE ###

s = list(input())
n = len(s)
m = s.count('B')
p = 0
for i in range(n-1):
    if s[i] == 'B':
        p += (n-m) - (i)
        m -= 1

print(p)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc175/submissions/15965930

def main():
    import sys
    input = sys.stdin.readline

    H, W, K = map(int, input().split())

    G = [[0] * W for _ in range(H)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        G[r - 1][c - 1] = v

    dp0 = [0] * (W + 1)
    dp1 = [0] * (W + 1)
    dp2 = [0] * (W + 1)
    dp3 = [0] * (W + 1)
    # dpx:=行内取得x個以下の最大値
    # <cは更新済の同じ行の値
    # c<=は前の行の値

    for r in range(H):
        for c in range(W):
            v = G[r][c]

            dp0[c] = max(dp0[c], dp3[c])  # 垂直移動
            vertical_take = dp0[c] + v  # 垂直移動+(r,c)取得

            dp3[c] = max(dp3[c - 1], dp2[c - 1] + v, vertical_take)
            dp2[c] = max(dp2[c - 1], dp1[c - 1] + v, vertical_take)
            dp1[c] = max(dp1[c - 1], dp0[c - 1] + v, vertical_take)
            # 水平移動（左）から来て取らない
            # 水平移動（左）から来て取る
            # 垂直移動で来て取らない:=dp0
            # 垂直移動で来て取る:=dpx(x>0)

            # print(f'{dp0=}')
            # print(f'{dp1=}')
            # print(f'{dp2=}')
            # print(f'{dp3=}')
            # print('*******************')

    print(dp3[-2])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    H, W, K = map(int, input().split())

    G = [[0] * W for _ in range(H)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        G[r - 1][c - 1] = v

    pdp = [[0] * 4 for _ in range(W)]
    for r in range(H):
        dp = [[0] * 4 for _ in range(W)]
        left = [0] * 4
        for c in range(W):
            cell = dp[c]

            for k in range(4):
                cell[k] = left[k]

            up = max(pdp[c])
            if cell[0] < up:
                cell[0] = up

            for k in range(2, -1, -1):
                cell[k + 1] = max(
                    cell[k + 1],
                    cell[k] + G[r][c])
            left = cell
        pdp = dp

    # for k in range(4):
    #     for row in range(H):
    #         for col in range(W):
    #             print(dp[row][col][k], end=' ')
    #         print()
    #     print()

    # print(*G, sep='\n')

    ans = max(dp[-1])
    print(ans)


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

import sys
input = sys.stdin.readline

N=int(input())
B=[list(map(int,input().split())) for i in range(N)]

B.sort(key=lambda x:x[0]+x[1])
#W+Sの順にソートすると無駄がない。

DP=[0]*(10**4+2)
#重さの合計がWのときの価値。
#W=10**4+1ならそれ以上更新されないので、W>=10**4+1以上のものはそこに置く

for w,s,v in B:
    for i in range(s,-1,-1):
        if i+w<=10**4:
            if DP[i+w]<DP[i]+v:
                DP[i+w]=DP[i]+v

        else:
            if DP[-1]<DP[i]+v:
                DP[-1]=DP[i]+v

print(max(DP))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
B=[list(map(int,input().split())) for i in range(N)]

B.sort(key=lambda x:x[0]+x[1])
#W+Sの順にソートすると無駄がない。

DP=[0]*(10**4+2)
#重さの合計がWのときの価値。
#W=10**4+1ならそれ以上更新されないので、W>=10**4+1以上のものはそこに置く

for w,s,v in B:
    for i in range(s,-1,-1):
        if i+w<=10**4:
            if DP[i+w]<DP[i]+v:
                DP[i+w]=DP[i]+v

        else:
            if DP[-1]<DP[i]+v:
                DP[-1]=DP[i]+v

print(max(DP))
### BUGGY CODE ###

mod=998244353
n,s=map(int,input().split())
arr=list(map(int,input().split()))
dp=[[[0]*(s+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
  val=arr[i-1]
  for j in range(i,-1,-1):
    for k in range(s,-1,-1):
      dp[i][j][k]=dp[i-1][j][k]
      if k-val>=0 and dp[i-1][j-1][k-val]!=0:
        dp[i][j][k]+=dp[i-1][j-1][k-val]
ans=0
for i in range(1,n+1):
  ans+=dp[n][i][s]*pow(2,n-i,mod)
  ans%=mod
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

def calc():
  mod=998244353
  n,s=map(int,input().split())
  arr=list(map(int,input().split()))
  dp=[0]*(s+1)
  dp[0]=1
  ans=0
  for i in range(1,n+1):
    val=arr[i-1]
    for k in range(s,-1,-1):
      dp[k]*=2
      dp[k]%=mod
      if k>=val and dp[k-val]!=0:
        dp[k]+=dp[k-val]
        dp[k]%=mod
  print(dp[s]%mod)
calc()
### BUGGY CODE ###

N=int(input())
A=[]
I=[]
for n in range(N):
    a=int(input())
    A.append(a)
I.append(1)
def t(I):
    #while 2 not in I:
    while 1:
        a=A[I[-1]-1]
        if a in I:
            return print(-1)
        if a==2:
            return print(len(I))
        I.append(a)
t(I)


### FIXED CODE ###

N=int(input())
A=[int(input()) for n in range(N)]
def t(N,A):
    i=1
    for n in range(1,N+1):
        a=A[i-1]
        if a==2:
            return print(n)
        i=a
    return print(-1)
t(N,A)
### BUGGY CODE ###

import math

N = int(input())
S = []

for _ in range(N):
    S.append(input())

def create_hash(_str):
    hash = ""
    for i, a in enumerate(["a", "b", "c", "d", "e",
     "f", "g", "h", "i", "j",
     "k", "l", "m", "n", "o",
     "p", "q", "r", "s", "t",
     "u", "v", "w", "x", "y", "z"]):
        count = 0
        for s in _str:
            if s == a:
                count += 1
        hash += str(count)
    return hash

def combinations(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

hist = {}
for s in S:
    hash = create_hash(s)
    hist[hash] = hist.get(hash, 0) + 1

pairs = 0
for k, v in hist.items():
    if v > 1:
        pairs += combinations(v, 2)
print(pairs)


### FIXED CODE ###

import math

N = int(input())
S = []

for _ in range(N):
    S.append(input())

def create_hash(_str):
    hash = ""
    for i, a in enumerate(["a", "b", "c", "d", "e",
     "f", "g", "h", "i", "j",
     "k", "l", "m", "n", "o",
     "p", "q", "r", "s", "t",
     "u", "v", "w", "x", "y", "z"]):
        count = 0
        for s in _str:
            if s == a:
                count += 1
        hash += str(count)
    return hash

def combinations(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

hist = {}
for s in S:
    hash = create_hash(s)
    hist[hash] = hist.get(hash, 0) + 1

pairs = 0
for k, v in hist.items():
    if v > 1:
        pairs += combinations(v, 2)
print(pairs)
### BUGGY CODE ###

import math
import copy

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


dp=[0 for _ in range(1000000+1)]

sosuu = [2]
A = 1000
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    for L2 in sosuu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosuu.append(L)
        
V=0  

VV=0
if V>1000:
  VV+=1
  

else:
  ch1=0
  ch3=0
  for w in sosuu:
    ch2=0
    for q in range(n):
      if B[q]%w==0:
        ch2+=1
        S=B[q]
        while S%w==0:
          S=S//w
        B[q]=S
    if ch2>1:
      ch3+=1
  d={}
  ch4=0
  for u in B:
      if u>1000:
        if u not in d:
          d[u]=0
        else:
          ch4+=1
  if ch3==0 and ch4==0:
    print('pairwise coprime')
    
      
  
  
    
  else:
    g=a[0]
    for h in range(1,n):
      g=math.gcd(g,a[h])
    
    if g==1:
      print('setwise coprime')
    
    else:
      print('not coprime')
      
     

### FIXED CODE ###

import math

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

dp=[0 for _ in range(1000001)]

for d in a:
  dp[d]+=1
  
ch1=0
for i in  range(2,1000001):
  ch=0
  x=i
  while x<=1000000:
    ch+=dp[x]
    x+=i
  if ch>1:
    ch1+=1
    
if ch1==0:
  print('pairwise coprime')
  
else:
  g=a[0]
  for h in range(1,n):
    g=math.gcd(g,a[h])
    
  if g==1:
    print('setwise coprime')
    
  else:
    print('not coprime')
### BUGGY CODE ###

# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
mod = 10**9+7

# dp[i][j] : Sの左からi文字目までと Tの左からj文字目まででの 共通部分文字列の数
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
dp[0][0] = 1

for i in range(N+1):
    for j in range(M+1):
        if 0<=i-1 and 0<=j-1 and S[i-1]==T[j-1]:
            dp[i][j] += dp[i-1][j-1]
        if 0<=i-1:
            dp[i][j] += dp[i-1][j]
        if 0<=j-1:
            dp[i][j] += dp[i][j-1]
        # 重複カウント部分を減算する
        if 0<=i-1 and 0<=j-1:
            dp[i][j] -= dp[i-1][j-1]
        dp[i][j] %= mod

print(dp[N][M])


### FIXED CODE ###

# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
mod = 10**9+7

# dp[i][j] : Sの左からi文字目までと Tの左からj文字目まででの 共通部分文字列の数
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
dp[0][0] = 1

for i in range(N+1):
    for j in range(M+1):
        if 0<=i-1 and 0<=j-1 and S[i-1]==T[j-1]:
            dp[i][j] += dp[i-1][j-1]
        if 0<=i-1:
            dp[i][j] += dp[i-1][j]
        if 0<=j-1:
            dp[i][j] += dp[i][j-1]
        # 重複カウント部分を減算する
        if 0<=i-1 and 0<=j-1:
            dp[i][j] -= dp[i-1][j-1]
        dp[i][j] %= mod

print(dp[N][M])
### BUGGY CODE ###

# coding: utf-8
import math
N = int(input())
a_list = [int(x) for x in input().split()]
b_list = [int(x) for x in input().split()]
c_list = [int(x) for x in input().split()]
a_list.sort()
b_list.sort()
c_list.sort()

a_lt_b_index = [N] * N
i = j = 0
while (i < N and j < N):
    if (a_list[i] < b_list[j]):
        a_lt_b_index[i] = j
        i += 1
    else:
        j += 1

b_lt_c_count = [0] * (N+1)
i = j = 0
while (i < N and j < N):
    if (b_list[i] < c_list[j]):
        b_lt_c_count[i] = N-j
        i += 1
    else:
        j += 1

sum_of_b_lt_c = [sum(b_lt_c_count[i:]) for i in range(N+1)]

print(sum([sum_of_b_lt_c[a_lt_b_index[i]] for i in range(N)]))


### FIXED CODE ###

N = int(input())
A_list = [int(a) for a in input().split()]
B_list = [int(b) for b in input().split()]
C_list = [int(c) for c in input().split()]
A_list.sort()
B_list.sort()
C_list.sort()

i = j = N-1
count_B_gt_A = [0] * N
while i >= 0 and j >= 0:
    if B_list[i] > A_list[j]:
        count_B_gt_A[i] = j+1
        i -= 1
    else:
        j -= 1

i = j = 0
count_B_lt_C = [0] * N
while i < N and j < N:
    if B_list[i] < C_list[j]:
        count_B_lt_C[i] = N - j
        i += 1
    else:
        j += 1
    
result = sum([B_gt_A * B_lt_C for B_gt_A, B_lt_C in zip(count_B_gt_A, count_B_lt_C)])
print(result)