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

import math
from functools import reduce
 
def gcd_lis(lis):
    return reduce(math.gcd, lis)

def osa_k(max_num):
  lis = [i for i in range(max_num+1)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True
c2 = True

d_lis = osa_k(max(num_lis))
tmp = set()
for i in num_lis:
  num = i
  new_tmp = set()
  while num > 1:
    d = d_lis[num]
    new_tmp.add(d)
    num //= d
  #print(new_tmp)
  if len(tmp)+len(new_tmp) == len(tmp | new_tmp):
    tmp |= new_tmp
    continue
  else:
    c1 = False
    break
  
if gcd_lis(num_lis) != 1:
  c2 = False

if c1:
  print("pairwise coprime")
elif not c1 and c2:
  print("setwise coprime")
else:
  print("not coprime")

### FIXED CODE ###

from math import gcd
N = int(input())
A = list(map(int,input().split()))

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

MAXN = 10**6+10
sieve = [i for i in range(MAXN+1)]
p = 2
while p*p <= MAXN:
    if sieve[p] == p:
        for q in range(2*p,MAXN+1,p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1

st = set()
for a in A:
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
    for p in tmp:
        if p in st:
            print('setwise coprime')
            exit()
        st.add(p)
print('pairwise coprime')
### BUGGY CODE ###

n, y = list(map(int, input().split(' ')))
for ten_th in range(int(y / 10000), -1, -1):
    if y < ten_th * 10000 or n < ten_th:
        continue
    for five_th in range(int((y - ten_th * 10000) / 5000), -1, -1):
        if y < ten_th * 10000 + five_th * 5000 or n < ten_th + five_th:
            continue
        for th in range(int((y - ten_th * 10000 - five_th * 5000) / 1000), -1, -1):
            if y == ten_th * 10000 + five_th * 5000 + th * 1000 and n == ten_th + five_th + th:
                print(' '.join(str(s) for s in [ten_th, five_th, th]))
                exit()
print('-1 -1 -1')
            

### FIXED CODE ###

n, y = list(map(int, input().split(' ')))
if y % 1000 != 0:
    print('-1 -1 -1')
    exit()
for ten_th in range(min(n, int(y / 10000)), -1, -1):
    if y < ten_th * 10000 or n < ten_th:
        continue
    for five_th in range(min(n - ten_th, int((y - ten_th * 10000) / 5000)), -1, -1):
        if y < ten_th * 10000 + five_th * 5000 or n < ten_th + five_th:
            continue
        if (y - ten_th * 10000 - five_th * 5000) % 1000 == 0:
            th = int((y - ten_th * 10000 - five_th * 5000) / 1000)
            if n == ten_th + five_th + th:
                print('{} {} {}'.format(ten_th, five_th, th))
                exit()
print('-1 -1 -1')
### BUGGY CODE ###

import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = np.array(list(map(int, input().split())))
    B = np.zeros(N, dtype='int32')
    count = 0
    i = 0
    for j in range(i+1, N):
        B[j] = A[i] + A[j] - (j - i)
    count += np.count_nonzero(B[i+1:] == 0)
    for i in range(1, N-1):
        B += A[i] - A[i-1] # 身長
        B += 1 # 番号
        count += np.count_nonzero(B[i+1:] == 0)
    print(count)
main()


### FIXED CODE ###

#import numpy as np
#import math
#from decimal import *
#from numba import njit
from collections import Counter

#@njit
def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = 0
    r = []
    l = []
    for i in range(N):
        r += i - A[i],
        l += i + A[i],

    c = Counter(l)
    for i in r:
        count += c[i]

    print(count)
main()
### BUGGY CODE ###

from collections import defaultdict, deque


N = int(input())
d = defaultdict(int)
for i in range(N):
    d[i+1] = int(input())

#print(d)

q = deque()
q.append(1)

point = 1
count = 1

while True:
    if d[point] in q:
        print(-1)
        break
    elif d[point] == 2:
        print(count)
        break
        
    q.append(d[point])
    point = d[point]
    count += 1

### FIXED CODE ###

from collections import defaultdict, deque
import sys

N = int(input())
d = defaultdict(int)
for i in range(N):
    d[i+1] = int(input())

#print(d)

q = deque()
q.append(1)

point = 1
count = 1

while N > 0:
    if d[point] == 2:
        print(count)
        sys.exit()
        
    q.append(d[point])
    point = d[point]
    count += 1
    N -= 1

print(-1)
### BUGGY CODE ###

def main():
    import sys

    input = sys.stdin.readline
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    dp = [10 ** 9] * n
    dp[0] = 0
    for i in tuple(range(n)):
        for j in tuple(range(1, k + 1)):
            i_j = i + j
            if i_j < n:
                x = dp[i] + abs(h[i] - h[i_j])
                if dp[i_j] > x:
                    dp[i_j] = x
    print(dp[-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            i_j = i + j
            if i_j < n:
                x = dp[i] + abs(h[i] - h[i_j])
                if dp[i_j] > x:
                    dp[i_j] = x
    print(dp[-1])


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

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

def dp(cost):
    for x in range(1,N):
        cost[x] =  min( [ cost[x-k-1] + abs( h[x] - h[x-k-1] ) for k in range(0,min(x,K)) ] ) 
    return 0

def solve():
    cost = [float('inf')] * N
    cost[0] = 0
    dp(cost)
    print(cost[N-1])
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

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

def dp(cost):
    for x in range(1,N):
        for k in range(max(x-K,0),x):
            cost[x] = min(cost[x] , cost[k] + abs( h[x] - h[k] ) )
        # cost[x] =  min( [ cost[k] + abs( h[x] - h[k] ) for k in range(max(x-K,0),x) ] ) 
    return 0

def solve():
    cost = [float('inf')] * N
    cost[0] = 0
    dp(cost)
    print(cost[N-1])
    return 0

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

n = int(input())
s = input()
ans = 0 
for i in range(0,n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k] and j-i != k-j:
                ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
count = 0
r = s.count('R')
g = s.count('G')
b = s.count('B')
for i in range(0,n-2):
    for j in range(i+1,n-1):
        if j < 2*j -i <= n-1 and sorted([s[i],s[j],s[2*j-i]]) == ['B','G','R']:
            count += 1
print(r*g*b - count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import Counter, defaultdict


import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap



def f(c1, c2, c3):
    if min(c1, c2, c3) < 0:
        return 0
    if memo[c1][c2][c3] != -1:
        return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    p1 = c1 / N
    p2 = c2 / N
    p3 = c3 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    ret += f(c1-1, c2, c3) * p1 / ip0
    ret += f(c1+1, c2-1, c3) * p2 / ip0
    ret += f(c1, c2+1, c3-1) * p3 / ip0
    memo[c1][c2][c3] = ret
    return ret

@mt
def slv(N, A):
    ca = Counter(A)


    return f(ca[1], ca[2], ca[3])



N = read_int()
A = read_int_n()
memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
memo[0][0][0] = 0

print(slv(N, A))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def f(c1, c2, c3):
    if memo[c1][c2][c3] != -1:
        return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    if c1 > 0:
        p1 = c1 / N
        ret += f(c1-1, c2, c3) * p1 / ip0
    if c2 > 0:
        p2 = c2 / N
        ret += f(c1+1, c2-1, c3) * p2 / ip0
    if c3 > 0:
        p3 = c3 / N
        ret += f(c1, c2+1, c3-1) * p3 / ip0
    memo[c1][c2][c3] = ret
    return ret


N = read_int()
A = read_int_n()
memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
memo[0][0][0] = 0
print(f(A.count(1), A.count(2), A.count(3)))
### BUGGY CODE ###

# ContestName
# URL
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    H, W = i2nn()
    A = ii2ss(H)
    B = [[[2000] * 4 for j in range(W)] for i in range(H)]
    for i in range(H):
        c = 2000
        for j in range(W):
            if A[i][j] == '#':
                c = 0
                for k, i2 in enumerate(range(i+1, H)):
                    B[i2][j][0] = k + 1
            else:
                c = min(B[i][j][0], c + 1)
            B[i][j][0] = c
    for i in range(H):
        c = 2000
        for j in range(W-1, -1, -1):
            if A[i][j] == '#':
                c = 0
                for k, i2 in enumerate(range(i+1, H)):
                    B[i2][j][1] = k + 1
            else:
                c = min(B[i][j][1], c + 1)
            B[i][j][1] = c
    for i in range(H-1, -1, -1):
        c = 2000
        for j in range(W):
            if A[i][j] == '#':
                c = 0
                for k, i2 in enumerate(range(i-1, -1, -1)):
                    B[i2][j][2] = k + 1
            else:
                c = min(B[i][j][2], c + 1)
            B[i][j][2] = c
    for i in range(H-1, -1, -1):
        c = 2000
        for j in range(W-1, -1, -1):
            if A[i][j] == '#':
                c = 0
                for k, i2 in enumerate(range(i-1, -1, -1)):
                    B[i2][j][3] = k + 1
            else:
                c = min(B[i][j][3], c + 1)
            B[i][j][3] = c
    ans = 0
    for i in range(H):
        for j in range(W):
            t = min(B[i][j])
            if ans < t:
                ans = t
    print(ans)

main()


### FIXED CODE ###

# AtCoder Grand Contest 033
# https://atcoder.jp/contests/agc033
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

import datetime

def main():
    H, W = i2nn()
    HW = H * W
    A = ii2ss(H)
    A = [[0 if s == '#' else HW for s in line] for line in A]
    for i in range(H):
        for j in range(1, W):
            if A[i][j-1]+1 < A[i][j]:
                A[i][j] = A[i][j-1]+1
        for j in range(W-2, -1, -1):
            if A[i][j+1]+1 < A[i][j]:
                A[i][j] = A[i][j+1]+1
    for j in range(W):
        for i in range(1, H):
            if A[i-1][j]+1 < A[i][j]:
                A[i][j] = A[i-1][j]+1
        for i in range(H-2, -1, -1):
            if A[i+1][j]+1 < A[i][j]:
                A[i][j] = A[i+1][j]+1
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] > ans:
                ans = A[i][j]
    print(ans)

main()
### BUGGY CODE ###

import sys
from collections import deque

#import numpy

readline = sys.stdin.readline
inf = float('inf')

def dfs(i, j, n):
    global grid, bfsque
    if grid[i][j] == '#':
        grid[i][j] = n
    if grid[i+1][j] == '#':
        dfs(i+1, j, n)
    if grid[i][j+1] == '#':
        dfs(i, j+1, n)
    if grid[i+1][j] == '.':
        bfsque.append([i+1, j])
    if grid[i][j+1] == '.':
        bfsque.append([i, j+1])


def main():
    global grid, bfsque
    H, W = map(int, readline().split())
    grid = []
    grid.append(['*'] * (W+2))
    for _ in range(H):
        grid.append(['*'] + list(readline()[:-1]) + ['*'])
    grid.append(['*']*(W+2))

    sbfs = True; sdfs = False
    bfsque = deque([[1,1]]); dfsque = deque()
    bfscnt = 0
    while True:
        while sbfs:
            fr = bfsque.popleft()
            if grid[fr[0]][fr[1]] == '.':
                grid[fr[0]][fr[1]] = bfscnt
            if grid[fr[0]][fr[1]] == '#':
                dfsque.append(fr)
                sbfs = False
                sdfs = True
                break
            tor = [fr[0], fr[1]+1]
            tod = [fr[0]+1, fr[1]]
            if grid[tor[0]][tor[1]] == '.':
                bfsque.append(tor)
            if grid[tor[0]][tor[1]] == '#':
                dfsque.append(tor)
            if grid[tod[0]][tod[1]] == '.':
                bfsque.append(tod)
            if grid[tod[0]][tod[1]] == '#':
                dfsque.append(tod)
            if len(bfsque) == 0:
                sbfs = False
                sdfs = True
        bfscnt += 1

        while sdfs:
            if len(dfsque) > 0:
                fr = dfsque.popleft()
                dfs(fr[0], fr[1], bfscnt)
            if len(dfsque) == 0:
                sbfs = True
                sdfs = False
        
        if not (grid[H][W] == '.' or grid[H][W] == '#'):
            break
    
    ans = grid[H][W]
    #print(numpy.array(grid))
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
inf = float('inf')

def main():
    H, W = map(int, readline().split())
    grid = []
    grid.append(['*'] * (W+2))
    for _ in range(H):
        grid.append(['*'] + list(readline()[:-1]) + ['*'])
    grid.append(['*']*(W+2))

    DP = [[inf] * (W+2) for _ in range(H+2)]
    DP[1][1] = (grid[1][1] == '#')*1

    for i in range(1, H+1):
        for j in range(1, W+1): 
            if i == 1 and j == 1:
                continue
            k = i
            gridkj = grid[k][j]
            if gridkj == '.':
                DP[k][j] = min(DP[k][j-1], DP[k-1][j])
            if gridkj == '#':
                DP[k][j] = min(DP[k][j-1]+(grid[k][j-1] in ['.', '*']), DP[k-1][j] + (grid[k-1][j] in ['.', '*']))
    ans = DP[H][W]
    print(ans)

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

import sys
import numpy as np
def input():
    return sys.stdin.readline()[:-1]

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

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

for _ in range(M):
    max_index = np.argmax(A)
    A[max_index] = int(A[max_index] / 2)

print(sum(A))

### FIXED CODE ###

import sys
import numpy as np
import math
import heapq
def input():
    return sys.stdin.readline()[:-1]

N, M = map(int, input().split())
A = list(map(lambda a: int(a)*(-1), input().split()))
heapq.heapify(A)

for _ in range(M):
    heapq.heappush(A, math.trunc(heapq.heappop(A) / 2))

print(sum(A)*(-1))
### BUGGY CODE ###

# 正解ではない

from queue import PriorityQueue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = PriorityQueue(H * W)
    q.put((0, (Ch - 1, Cw - 1)))

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q, S, D, H, W):
    while not q.empty():
        worp_count, (x, y) = q.get()
        S[x][y] = '/'

        if (x, y) == D:
            return worp_count

        for i, j in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
            if 0 <= i < H and 0 <= j < W and S[i][j] in ('.', '1'):
                q.put((worp_count, (i, j)))
                S[i][j] = '0'

        for i, j in ((x + a, y + b) for a in range(-2, 3) for b in range(-2, 3)):
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count + 1, (i, j)))
                S[i][j] = '1'

    return -1


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


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

import collections
import math

# 組み合わせ算出
def combinations_count(n, r):
    if n == 1:
        return 0
    if n == 0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if __name__ == '__main__':

    N= int(input())

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

    for i in range(N):
        total = 0

        b = a[:i] + a[i+1:]

        c = collections.Counter(b)

        for j in set(a):

            total = total + combinations_count(c[j], 2)

        print(total)

### FIXED CODE ###

import collections
import math


if __name__ == '__main__':
    N= int(input())
    a = list(map(int, input().split()))
    c = collections.Counter(a)
    result = 0
    for i in set(a):
        # c[i]の中から2個選ぶ
        result += (c[i]*(c[i]-1))/2

    for i in a:
        d = c[i]
        print(int(result - (d*(d-1))/2 + ((d-1)*(d-2))/2))
### BUGGY CODE ###

N = int(input())
for a in range(1,3501):
    for b in range(1,3501):
        if (4*a*b) - N*(a+b) != 0:
            r = (N*a*b) % ( (4*a*b) - N*(a+b) )
            if r == 0:
                c = (N*a*b) // ( (4*a*b) - N*(a+b) )
                if c > 0:
                    break
    else:
        continue
    break
print(a,b,c)

### FIXED CODE ###

N = int(input())
for a in range(1,3501):
    for b in range(1,3501):
        if (4*a*b) - N*(a+b) != 0:
            r = (N*a*b) % ( (4*a*b) - N*(a+b) )
            if r == 0:
                c = (N*a*b) // ( (4*a*b) - N*(a+b) )
                if c > 0:
                    break
    else:
        continue
    break
print(a,b,c)
### BUGGY CODE ###

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

for j in range(len(n)):
    if n.index(n[j])<x or abs(len(n)-x)<=n.index(n[j]):
        print(n[j])

### FIXED CODE ###

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

if b-a+1<=2*k:
    for i in range(a,b+1):
        print(i)
    exit()

else:
    for i in range(a,a+k):
        print(i)
    for j in range(b-k+1,b+1):
        print(j)
### BUGGY CODE ###

S=input()
q=int(input())
rev=False
pre=''
for i in range(q):
    inp=input()
    if inp[0]=="1":
        rev=not rev
    else:
        t,f,c=inp.split()
        if (f=='1' and rev) or (f=='2' and not rev):
            S+=c
        else:
            pre+=c
if not rev:
    print(''.join(list(reversed(pre)))+S)
else:
    print(''.join(list(reversed(S)))+pre)

### FIXED CODE ###

S=input()
q=int(input())
RV=0
A="A"
for i in range(q):
    IN=input()
    if IN=="1":
        RV+=1
    else:
        t,f,c=IN.split()
        if RV%2==0:
            if f=="1":
                A=c+A               
            else:
                A=A+c
        else:
            if f=="1":
                A=A+c
            else:
                A=c+A
if RV%2==0:
    for i in range(len(A)):
        if A[i]=="A":
            print(A[:i]+S+A[i+1:])
else:
    A=A[::-1]
    for i in range(len(A)):
        if A[i]=="A":
            print(A[:i]+S[::-1]+A[i+1:])
### BUGGY CODE ###

n = int(input())
nums = [int(input()) for i in range(n)]
count = 0
prevMaxs = []
for i in range(n):
    num = nums[i]
    if len(prevMaxs) == 0 :
        prevMaxs.append(num)
    else:
        maxIndex = -1
        maxNum = -1
        for j in range((len(prevMaxs))):
            if prevMaxs[j] < num and maxNum < prevMaxs[j]:
                maxIndex = j
                maxNum = prevMaxs[j]
        if maxIndex == -1:
            prevMaxs.append(num)
        else:
            prevMaxs[maxIndex] = num
print(len(prevMaxs))

### FIXED CODE ###

import sys
import bisect

n = int(input())
a = [int(sys.stdin.readline().rstrip()) for _ in range(n)][::-1]

bottoms = [a[0]]

for i in range(1, n):
    pos = bisect.bisect_right(bottoms, a[i])
    if pos == len(bottoms):
        bottoms.append(a[i])
    else:
        bottoms[pos] = a[i]

print(len(bottoms))
### BUGGY CODE ###

# coding: utf-8
# 整数の入力
#a = int(raw_input())
# スペース区切りの整数の入力
N = int(input())

Rmax = 0
Rmin = 1000000001
Bmax = 0
Bmin = 1000000001

data = sorted([sorted(list(map(int, input().split()))) for i in range(N)],key=lambda x:x[0])

def target(data):
    tempBlues = sorted([d[0] for d in data])
    tempReds = sorted([d[1] for d in data])
    return (max(tempBlues) - min(tempBlues))*(max(tempReds) - min(tempReds))


minValue = target(data)

for i in range(N):
    data[i] = [data[i][1],data[i][0]]
    tempValue = target(data)
    if tempValue < minValue:
        minValue = tempValue
    
print(minValue)

### FIXED CODE ###

# coding: utf-8
# 整数の入力
#a = int(raw_input())
# スペース区切りの整数の入力
import heapq
N = int(input())

Rmax = 0
Rmin = 1000000001
Bmax = 0
Bmin = 1000000001

data = sorted([sorted(list(map(int, input().split()))) for i in range(N)],key=lambda x:x[0])

tempBlues = sorted([d[1] for d in data])
tempReds = [d[0] for d in data]
heapq.heapify(tempReds)

Rmin = data[0][0]
Rmax = data[N-1][0]
Bmax = max(tempBlues)
Bmin = min(tempBlues)

minValue = (Rmax - Rmin)*(Bmax - Bmin)
Bmin = Rmin

for i in range(N):
    heapMin = heapq.heappop(tempReds)
    if heapMin == data[i][0]:
        heapq.heappush(tempReds, data[i][1])
        if  data[i][1] > Rmax:
            Rmax = data[i][1]
        if (Rmax - tempReds[0])*(Bmax - Bmin) < minValue:
            minValue = (Rmax - tempReds[0])*(Bmax - Bmin)
    else:
        break

print(minValue)
### BUGGY CODE ###

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

ans = 1
for a in A:
    ans *= a

print(ans if ans <= 10 ** 18 else - 1)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
if 0 in A:
    print(0)
    exit()
ans = 1
for a in A:
    ans *= a
    if ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

import numpy as np
N, Q = map(int, input().split())
S = list(input())

start_pair = []
for j in range(N-1):
    if S[j] == 'A' and S[j+1] == 'C':
        start_pair.append(j)

length = len(start_pair)
start_pair = np.asarray(start_pair)
for i in range(Q):
    if length == 0:
        print(0)
    else:
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        right = np.searchsorted(start_pair, r)
        left = np.searchsorted(start_pair, l)
        print(right-left)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
T = [0]*N
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        T[i] = T[i-1] + 1
    else:
        T[i] = T[i-1]
for j in range(Q):
    left, right = map(int, input().split())
    print(T[right-1]-T[left-1])