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

from collections import deque

H, W = map(int, input().split())
A = [list(input()) for i in range(H)]

q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append((i, j))

ans = 0
while q:
    nq = deque()
    while q:
        h, w = q.popleft()
        if h > 0 and A[h - 1][w] == '.':
            A[h - 1][w] = '#'
            nq.append((h - 1, w))
        if h < H - 1 and A[h + 1][w] == '.':
            A[h + 1][w] = '#'
            nq.append((h + 1, w))
        if w > 0 and A[h][w - 1] == '.':
            A[h][w - 1] = '#'
            nq.append((h, w - 1))
        if w < W - 1 and A[h][w + 1] == '.':
            A[h][w + 1] = '#'
            nq.append((h, w + 1))
    if not nq:
        break
    q = nq
    ans += 1
print(ans)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
A = [list(input()) for i in range(H)]

q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append((i, j))

ans = 0
while q:
    nq = deque()
    while q:
        h, w = q.popleft()
        if h > 0 and A[h - 1][w] == '.':
            A[h - 1][w] = '#'
            nq.append((h - 1, w))
        if h < H - 1 and A[h + 1][w] == '.':
            A[h + 1][w] = '#'
            nq.append((h + 1, w))
        if w > 0 and A[h][w - 1] == '.':
            A[h][w - 1] = '#'
            nq.append((h, w - 1))
        if w < W - 1 and A[h][w + 1] == '.':
            A[h][w + 1] = '#'
            nq.append((h, w + 1))
    if not nq:
        break
    q = nq
    ans += 1
print(ans)
### BUGGY CODE ###

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

for i in range(n):
    ans = 0
    for j in range(n):
        if i==j:
            continue
        ans = ans^ali[j]
    
    if i != (n-1):
        print(ans, end=" ")
    else:
        print(ans)

### FIXED CODE ###

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

allxor = 0
for ai in ali:
    allxor = allxor ^ ai

for i in range(n):
    ans = allxor ^ ali[i]
    
    if i != (n-1):
        print(ans, end=" ")
    else:
        print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

X,Y,Z,K=MAP()
A=LIST()
B=LIST()
C=LIST()

AB=[]
for i in range(X):
    for j in range(Y):
        AB.append(A[i]+B[j])
AB.sort(reverse=True)
AB=AB[:3000]

ABC=[]
for i in range(len(AB)):
    for j in range(Z):
        ABC.append(AB[i]+C[j])
ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

X,Y,Z,K=MAP()
A=LIST()
B=LIST()
C=LIST()

AB=[]
for i in range(X):
    for j in range(Y):
        AB.append(A[i]+B[j])
AB.sort(reverse=True)
AB=AB[:3000]

ABC=[]
for i in range(len(AB)):
    for j in range(Z):
        ABC.append(AB[i]+C[j])
ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

N = int(input())
S = str(input())
R = []
G = []
B = []
for i in range(N):
    if S[i] == 'R':
        R.append(i+1)
    elif S[i] == 'G':
        G.append(i+1)
    else:
        B.append(i+1)
ans = 0
count = 0
for k in R:
    for j in G:
        for i in B:
            fr = 0
            ab = [k,j,i]
            ab.sort()
            if ab[2] - ab[1] == ab[1] - ab[0]:
                pass
            else:
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
N -= 1
S = str(input())
count = S.count('R') * S.count('G') * S.count('B')
for i in range(N):
    for j in range(i,N+1):
        k = 2*j - i
        if k > N:
            pass
        elif S[i] == S[j] or S[i] == S[k] or S[j] == S[k]:
            pass
        else:
            count -= 1
print(count)
### BUGGY CODE ###

input()
strs = input().split(' ')
nums = [int(i) for i in strs]

ct = 0
b_flag = False
while(1):
  for num in nums:
    if num % 2 == 0:
      continue
    else:
      b_flag = True
      break
  if b_flag:
    break
  ct += 1
print(ct)

### FIXED CODE ###

input()
strs = input().split(' ')
nums = [int(i) for i in strs]

ct = 0
b_flag = False
while(1):
  for i, num in enumerate(nums):
    if num % 2 == 0:
      nums[i] = num/2
      continue
    else:
      b_flag = True
      break  
  if b_flag:
    break
  ct += 1
print(ct)
### BUGGY CODE ###

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

cards = [x for x in range(N)]

tmp = cards
for i in range(M):
    L,R = map(int,input().split())
    tmp = list(filter(lambda x: L - 1 <= x <= R - 1,tmp))

print(len(tmp))


### FIXED CODE ###

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

cards = [x for x in range(N)]

tmp = cards
Ls = []
Rs = []
for i in range(M):
    L,R = map(int,input().split())
    Ls.append(L - 1)
    Rs.append(R - 1)

print(max(min(Rs) - max(Ls) + 1,0))
### BUGGY CODE ###

# 素因数分解
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table
  
N = int(input())
a = list(map(int,input().split()))

ans = 0

for i in range(N):
    ans += prime_decomposition(a[i]).count(2)
    
print(ans)

### FIXED CODE ###

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

ans = 0

for i in range(N):
    num = a[i]
    while num % 2 == 0:
        num = num // 2
        ans += 1
    
print(ans)
### BUGGY CODE ###

# E - Handshake

import numpy as np

N, M = map(int, input().split())
A = list(int(x) for x in input().split())
A.sort(reverse=True)
A = np.array(A)
Acsum = np.zeros(N+1,dtype=np.int64)
Acsum[0:N] = np.cumsum(A)

left = min(A)*2-1
right = max(A)*2+1

def Check(x):
    X = x-A
    cnt = 0
    happy = 0
    for i in range(N):
        l = -1
        r = N
        while l+1 < r:
            m = (l+r)//2
            if A[m] >= X[i]:
                l = m
            else:
                r = m 
        cnt += l+1
        if l>=0:
            #print(A[i], Acsum[l])
            happy += A[i]*(l+1)+Acsum[l]
    return cnt, happy
    
# 2分探索
while left+1 < right:
    mid = (left+right)//2
    if Check(mid)[0] >= M:
        left = mid
    else:
        right = mid

tmp, ans = Check(right)
ans += (M-tmp)*left
print(ans)




### FIXED CODE ###

# E - Handshake

N, M = map(int, input().split())
A = list(int(x) for x in input().split())

A.sort(reverse=True)

S = []
S.append(A[0])
for i in range(N-1):
    S.append(S[i]+A[i+1])
S.append(0)

# 幸福度がX以上となる握手がM以上になることを考える
# つまり、幸福度がXより大きい(X+1以上)の握手と
# 幸福度がXの握手を足すとM以上

def CheckHappy(x):
    X = list(map(lambda y: x - y, A))
    cnt = 0
    happy = 0
    for i in range(N):
        l = -1
        r = N
        while l+1 < r:
            m = (l+r)//2
            if A[m] >= X[i]:
                l = m
            else:
                r = m 
        cnt += l+1
        if l>=0:
            #print(A[i], S[l])
            happy += A[i]*(l+1)+S[l]
    #print('cnt, happy', cnt, happy)
    return cnt, happy

def isGreaterThanM(x):
    X = list(map(lambda y: x - y, A))
    #print('X',X)
    cnt = 0
    for i in range(N):
        l = -1
        r = N
        #print('l, r', l, r)
        while l+1 < r:
            m = (l+r)//2
            if A[m] >= X[i]:
                l = m
            else:
                r = m 
        cnt += l+1
        #print('cnt',cnt)
        if cnt >= M:
            return True
    return False


# 2分探索
left = min(A)*2-1
right = max(A)*2+1

while left+1 < right:
    mid = (left+right)//2
    if isGreaterThanM(mid):
        left = mid
    else:
        right = mid

#print('left, right', left, right)

tmp, ans = CheckHappy(right)
ans += (M-tmp)*left
print(ans)
### BUGGY CODE ###

def main():
    N , M, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    B_list = list(map(int, input().split()))

    al = [0]
    bl = [0]

    for i in range(N) :
        al.append(al[i] + A_list[i])
    for i in range(M) :
        bl.append(bl[i] + B_list[i])
    #print("al = %s" % al)
    #print("bl = %s" % bl)
    book = 0

    for i in range(N+1) :
        re = M
        if al[i] > K :
            break
        for j in range(M+1) :
            if bl[re] <= K - al[i] :
                break
            else :
                re -= 1

        book = max(book, i + re)

    print(book)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N , M, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    B_list = list(map(int, input().split()))

    al = [0]
    bl = [0]

    for i in range(N) :
        al.append(al[i] + A_list[i])
    for i in range(M) :
        bl.append(bl[i] + B_list[i])
    #print("al = %s" % al)
    #print("bl = %s" % bl)
    book = 0
    re = M

    for i in range(N+1) :
        if al[i] > K :
            break
        #for j in range(M+1) :
        #    if bl[re] <= K - al[i] :
        #        break
        #    else :
        #        re -= 1
        while bl[re] > K - al[i] :
            re -= 1

        book = max(book, i + re)

    print(book)


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

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()

C_list = []
for i in range(M):
  [B, C] = list(map(int, input().split(' ')))
  if len(C_list) >= N and C_list[-N] > C:
    continue
  else:
    for k in range(B):
      C_list.append(C)
      if len(C_list) >= N and C_list[-N] == C:
        break
    C_list.sort()
  
C_list.sort()

ans = 0
count = 0
for i in range(N):
  if card_list[-1] > C_list[-1]:
    ans += card_list.pop()
    count += 1
  else:
    ans += C_list.pop()
    count += 1
    
  if C_list == []:
    for k in range(N - count):
      ans += card_list.pop()
    break
      
print(ans)

### FIXED CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()
compare_list = []

for i in range(M):
  (B, C) = list(map(int, input().split(' ')))
  compare_list.append((C,B))
    
compare_list.sort()

ans = 0
for i in range(N):
  if compare_list == []:
    ans += sum(card_list[i:])
    break
  if card_list[-1] > compare_list[-1][0]:
    ans += card_list.pop()
  elif compare_list[-1][1] > 0:
    ans += compare_list[-1][0]
    tmp = compare_list.pop()
    a = tmp[0]
    b = tmp[1]
    if b != 1:
      compare_list.append((a,b-1)) 
      
print(ans)
### BUGGY CODE ###

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

cnt = 0
for i in range(N-1):
    height_A = A[i]
    start = i + height_A
    if start < N - 1:
        for j in range(start,N):
            height_B = A[j]
            if j - i == height_A + height_B:
                cnt += 1

print(cnt)


### FIXED CODE ###

import collections

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

P = [i+A[i] for i in range(N)]
Q = [j-A[j] for j in range(N)]

Q_dict = collections.Counter(Q)

cnt = 0
for i in range(N-1):
    Q_dict[Q[i]] -= 1
    cnt += Q_dict[P[i]]

print(cnt)
### BUGGY CODE ###

k,q=map(int,input().split())
D=list(map(int,input().split()))
A=[]
for i in range(q):
    n,x,m=map(int,input().split())
    mD=list(map(lambda i: i%m, D)) #元の列のmodを取る
    ans=0
    ans+=mD.count(0)*((n-1)//k)+mD[:((n-1)%k)].count(0) #0の数
    cnt=x%m+sum(mD)*((n-1)//k)+sum(mD[:((n-1)%k)]) #増えた量
    ans+=cnt//m
    A.append(n-1-ans)
for a in A:
    print(a)

### FIXED CODE ###

import sys
input = sys.stdin.readline

k,q=map(int,input().split())
D=list(map(int,input().split()))
A=[]
for i in range(q):
    n,x,m=map(int,input().split())
    mD=list(map(lambda i: i%m, D)) #元の列のmodを取る
    ans=0
    cnt=x%m
    a=(n-1)//k
    b=(n-1)%k
    for d in mD[:b]: #mod kで余る部分
        if d==0:
            ans+=a+1
        cnt+=d*(a+1)
    for d in mD[b:]: #余らない部分
        if d==0:
            ans+=a
        cnt+=d*a
    ans+=cnt//m
    print(n-1-ans)
### BUGGY CODE ###

A,B,K=map(int,input().split())
for num in range(K):
    if A>=1:
        A-=1
    elif B>=1:
        B-=1
    else:
        pass
print("{} {}".format(A,B))

### FIXED CODE ###

A,B,K=map(int,input().split())
if A-K>=0:
    print("{} {}".format(A-K,B))
elif A+B-K>=0:
    print("0 {}".format(A+B-K))
else:
    print("0 0")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Feb 12 16:01:34 2020

@author: matsui
"""

N=int(input())
A=input().split()

ans='YES'
maxa=int(A[0])
mina=int(A[0])
for i in range(1,N):
    ai=int(A[i])
    if ai<mina:mina=ai
    if ai>maxa:maxa=ai
    if ai>=mina and ai<=maxa:
        if A[i] in A[:i]:
            ans='NO'
            break
    
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Feb 12 16:01:34 2020

@author: matsui
"""

N=int(input())
A=input().split()
A=[int(a) for a in A]
A.sort()

ans='YES'
for i in range(1,N):
    if A[i]==A[i-1]:
        ans='NO'
        break
    
print(ans)
### BUGGY CODE ###

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

for _ in range(M):
    i = max(range(len(A)), key=A.__getitem__)
    A[i] /= 2
A = list(map(int, A))
print(sum(A))


### FIXED CODE ###

import heapq

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

heap = [-Ai for Ai in A]
heapq.heapify(heap)
for _ in range(M):
    heapq.heapreplace(heap, heap[0]/2)
A = [int(-p) for p in heap]
print(sum(A))
### BUGGY CODE ###

n = int(input())
ia = [int(input()) for _ in range(n)]
a = ia

for i in range(n):
  temp = a.pop(i)
  print(max(a))
  a.insert(i,temp)

### FIXED CODE ###

import numpy as np
n = int(input())
a = [int(input()) for _ in range(n)]

# 最大値のインデックス
i1 = np.argmax(a)
temp = a[i1]
a[i1] = 0
# ２番目の最大値のインデックス
i2 = np.argmax(a)
a[i1] = temp


for i in range(n):
  if i == i1:
    print(a[i2])
  else:
    print(a[i1])
### BUGGY CODE ###

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

adj = [{} for i in range(N)]
for i in range(N):
    for j in range(i + 1, N):
        adj[i][j] = A[i][j]
        adj[j][i] = A[j][i]

import heapq

def Dijkstra(numV, v_st):

    cost = [float('inf') for i in range(numV)]
    cost[v_st] = 0
    num = [0 for i in range(numV)]

    pq = []
    heapq.heappush(pq, (0, v_st))

    while pq:
        c_min, v_now = heapq.heappop(pq)

        if cost[v_now] < c_min:
            continue

        for v, c in adj[v_now].items():
            if cost[v_now] + c < cost[v]:
                cost[v] = cost[v_now] + c
                num[v] = num[v_now] + 1
                heapq.heappush(pq, (cost[v], v))
            elif cost[v_now] + c == cost[v]:
                if num[v] == 1:
                    del adj[v_st][v]
                    del adj[v][v_st]
                elif num[v_now] + 1 == 1:
                    del adj[v_now][v]
                    del adj[v][v_now]
                num[v] = max(num[v], num[v_now] + 1)

    return cost

dist = [[] for i in range(N)]
for i in range(N):
    dist[i] = Dijkstra(N, i)

ans = sum(sum(adj[i].values()) for i in range(N)) // 2
for i in range(N):
    for j in range(N):
        if dist[i][j] < A[i][j]:
            ans = -1
            break
    if ans == -1:
        break

print(ans)


### FIXED CODE ###

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

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    Ai = A[i]
    for j in range(i):
        d = min(map(sum, zip(Ai, A[j])))

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

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

MOD = 10**9 + 7


def comb(n,k,p):
    """power_funcを用いて(nCk) mod p を求める"""
    from math import factorial
    if n<0 or k<0 or n<k:
        return 0
    if n==0 or k==0:
        return 1
    a=factorial(n) %p
    b=factorial(k) %p
    c=factorial(n-k) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p


def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0:
        return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p


N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
A.sort()
A_rev = list(reversed(A))


ans = 0
for i, j in zip(A, A_rev):
    if N < K:
        break
    C = comb(N - 1, K - 1, MOD)
    ans += C * j
    ans -= C * i
    ans %= MOD
    N -= 1
print(int(ans % MOD))


### FIXED CODE ###

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
A.sort()
MOD = 10 ** 9 + 7


def combination(mod=MOD):
    fact = [1] * (N + 1)
    inv_fact = [1] * (N + 1)
    r = 1
    for i in range(1, N + 1):
        fact[i] = r = r * i % mod
    inv_fact[N] = r = pow(fact[N], mod - 2, mod)
    for i in range(N, 0, -1):
        inv_fact[i - 1] = r = r * i % mod

    def _wrapper(n, k):
        nonlocal fact, inv_fact, mod
        if n == 0 or k == 0:
            return 1
        return fact[n] * inv_fact[k] * inv_fact[n - k] % mod

    return _wrapper


def main():
    if K == 1:
        print(0)
        exit()
    comb = combination()
    sum_max = 0
    sum_min = 0
    for i, A_i in enumerate(A):
        if i >= K - 1:
            sum_max += comb(i, K - 1) * A_i % MOD
        if N - i >= K:
            sum_min += comb(N - i - 1, K - 1) * A_i % MOD
    ans = (sum_max - sum_min) % MOD
    print(ans)


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

n=int(input())
s=input()
cnt=0
if n<=2:
    print(0)
    quit()
import itertools           
for i,j,k in itertools.combinations_with_replacement(range(0,n), 3):
    if j-i!=k-j and s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
        cnt+=1
print(cnt)


### FIXED CODE ###

n = int(input())
s =     input()
if n < 3:
  print(0)
  exit

result = s.count('R') * s.count('G') * s.count('B')
for i in range(n):
  for j in range(i+1, n):
    k = 2*j - i
    if k < n and s[k] != s[i] and s[k] != s[j] and s[j] != s[i]:
      result -= 1

print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
def f(n):
  dp = [0]*(n+1)
  for i in range(n+1):
    for a, b in zip(A, B):
      if i-a >= 0:
        dp[i] = max(dp[i], dp[i-a]+b)
  return max(dp[i]+n-i for i in range(n+1))
m = f(n)
A, B = B, A
ans = f(m)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
def f(n):
  dp = list(range(n+1))
  for a, b in zip(A, B):
    for i in range(n+1):
      if i-a >= 0:
        dp[i] = max(dp[i], dp[i-a]+b)
  return max(dp)
m = f(n)
A, B = B, A
ans = f(m)
print(ans)
### BUGGY CODE ###

n = int(input())
a = []
a_sorted = []
tmp = 0

for i in range(n):
    a.append(int(input()))

for i in range(n):
    
    tmp = a[i]
    a[i] = 0

    a_sorted = sorted(a, reverse=True)

    a[i] = tmp
    
    print(a_sorted[0])


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

sorted_a = sorted(a)

max_a = sorted_a[-1]
max_a_r = sorted_a[-2]

for i in range(n):
    if a[i] == max_a:
        print(max_a_r)
    else:
        print(max_a)
### BUGGY CODE ###

def f(n, m, A):
    w = {i: {j for j in A if j[0]<= i < j[1]} for i in range(n, m)}
    # print(w)
    max_n = max(w.items(), key=lambda x:len(x[1]))[0]
    # print("w", A, w[max_n], A- w[max_n])
    return max_n, A - w[max_n]

def ff(n, m, A):
    # print(n ,m ,A)

    i, A_ = f(n, m, A)
    A_1 = set(j for j in A_ if j[1] <= i)
    A_2 = A_ - A_1

    # print(" ", i, A_1, A_2)

    a1 = ff(n, i, A_1) if A_1 else 0
    a2 = ff(i+1, m, A_2) if A_2 else 0

    return a1 + a2 + 1

w = [int(i) for i in input().split()]
N = w[0]
M = w[1]
A = {tuple([int(j) for j in input().split()]) for i in range(M)}

print(ff(1, N, A))


### FIXED CODE ###

w = [int(i) for i in input().split()]
N = w[0]
M = w[1]
A = {tuple([int(j) for j in input().split()]) for i in range(M)}

A_ = sorted(A, key=lambda x: x[1])
bridge = 0
c = 0
for i in A_:
    if i[0] > bridge:
        bridge = i[1]-1
        c += 1
print(c)
### BUGGY CODE ###

import bisect

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

count = 0
for a in A:
  for i in range(bisect.bisect_right(B, a), len(B)):
    count += len(C) - bisect.bisect_right(C, B[i])
print(count)


### FIXED CODE ###

import bisect

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
count = 0
lenA = len(A)
lenB = len(B)
lenC = len(C)
for b in B:
  count += (bisect.bisect_left(A, b))*(lenC-bisect.bisect_right(C, b))
print(count)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np
import math


def solve(A: int, B: int, N: int):
    ans = 0
    for x in range(N+1):
        ans = max(ans, math.floor(A*x/B)-A*math.floor(x/B))

    print(ans)
    
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    solve(A, B, N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np
import math

def solve(A: int, B: int, N: int):
    x = min(B-1, N)
    print(math.floor(A*x/B)-A*math.floor(x/B))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    solve(A, B, N)

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

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

ans = "IMPOSSIBLE"

ls = [[] for m in range(M)]
for m in range(M):
    a,b = map(int,(input().split()))
    ls[m].append(a-1)
    ls[m].append(b-1)
    
    if a-1 == 0 and b-1 == N-1:
        ans = "POSSIBLE"
    if a-1 == 0:
        ls[m].append("P")
    else:
        ls[m].append("I")

for m in range(M):
    if ls[m][2] == "P":
        for i in range(M):
            if ls[m][1] == ls[i][0] and ls[i][1] == N-1:
                ans = "POSSIBLE"

print(ans)

### FIXED CODE ###

from sys import stdin
input = stdin.readline

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

ans = "IMPOSSIBLE"

seta,setb = set(),set()
af,bf = [False]*M,[False]*M

for m in range(M):
    a,b = map(int,(input().split()))
    if a-1 == 0:
        af[m] = True
        seta.add(b-1)
    if b-1 == N-1:
        bf[m] = True
        setb.add(a-1)
    if af[m] and bf[m]:
        ans = "POSSIBLE"
        break
    
for a in seta:
    if ans == "POSSIBLE":
        break
    if a in setb:
        ans = "POSSIBLE"
        break

print(ans)