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

import math
import sys
sys.setrecursionlimit(int(10**9))

mod = 10**9 + 7

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def fact(n):
    if n == 1: 
        return 1
    else:
        return (fact(n-1)*n)%mod

def comb(n, k):
    ans = 1
    for i in range(k):
        ans *= (n-i)
        ans //= i+1
    return ans % mod

n, a, b = map(int, input().split())
cnk = []
now = 1
for i in range(b+2):
    cnk.append(now)
    now = (now*(n-i)*power(i+1,mod-2))%mod

ans = power(2, n)%mod - cnk[a] - cnk[b] - 1
print(ans % mod)

### FIXED CODE ###

import math
import sys
sys.setrecursionlimit(int(10**9))

mod = 10**9 + 7

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def fact(n):
    if n == 1: 
        return 1
    else:
        return (fact(n-1)*n)%mod

def comb(n, k):
    ans = 1
    for i in range(k):
        ans *= (n-i)
        ans //= i+1
    return ans % mod

n, a, b = map(int, input().split())
now = 1
for i in range(a):
    now = (now*(n-i))%mod
cnka = (now * power(math.factorial(a),mod-2) )% mod
for i in range(a,b):
    now = (now*(n-i))%mod
cnkb = (now * power(math.factorial(b),mod-2) )% mod

ans = power(2, n)%mod - cnka - cnkb - 1
print(ans % mod)
### BUGGY CODE ###

import sys
import itertools
input = sys.stdin.readline
inf = 200000000
n, m, r = map(int, input().split())
rs = list(map(int, input().split()))
n1 = n + 1
d = [inf] * (n1 * n1)
for i in range(n1):
    d[i * n1 + i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a * n1 + b] = d[b * n1 + a] = c


def update(i, j, k):
    d[i * n1 + j] = d[j * n1 +
                      i] = min(d[i * n1 + j], d[i * n1 + k] + d[k * n1 + j])


[update(i, j, k) for k in range(1, n+1)
 for i in range(1, n+1) for j in range(i+1, n+1)]
p = list(itertools.permutations(range(r)))
s = inf
for q in p:
    t = 0
    for i in range(r-1):
        t += d[rs[q[i]] * n1 + rs[q[i+1]]]
    if s > t:
        s = t
print(s)


### FIXED CODE ###

from itertools import product, permutations


def warshall_floyd(d):
    # d        : nxn adjacent matrix
    for k, i, j in product(range(n), repeat=3):
        if d[i][j] > d[i][k] + d[k][j]:
            d[i][j] = d[i][k] + d[k][j]


INF = float("inf")
n, m, r = map(int, input().split())
r_list = list(map(lambda x: int(x) - 1, input().split()))
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    d[a][b] = d[b][a] = c
warshall_floyd(d)

ans = float("inf")
for np in permutations(r_list):
    cand = sum([d[np[i]][np[i + 1]] for i in range(r - 1)])
    ans = min(ans, cand)

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

import itertools

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

ans = 0
for vi in itertools.permutations(v):
    point = vi[0]
    for j in range(1,n):
        point = (point+vi[j])/2
    ans = max(point, ans)
    
print(ans)

### FIXED CODE ###

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

v.sort()

tmp = v[0]
for i in range(n-1):
    tmp = (tmp+v[i+1]) / 2
print(tmp)
### BUGGY CODE ###

#from scipy.special import comb
#from math import factorial
import collections

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

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

#a = cmb(n,r)
c = collections.Counter(A)
l1 = []
l2 = []
l3 = []
for i in c.keys():
  l1.append(i)
  if c[i] == 1:
    l2.append(0)
    l3.append(0)
  if c[i] == 2:
    l2.append(1)
    l3.append(0)
  if c[i] >= 3:
    l2.append(cmb(c[i], 2))
    l3.append(cmb(c[i]-1, 2))    

#print(l1)
#print(l2)
#print(l3)
l4 = []
for i in c.keys():
  sum = 0
  for j in c.keys():
    var_index = l1.index(j)
    if i == j:
      sum += l3[var_index]
    else:
      sum += l2[var_index]
  l4.append(sum)
#print(l4)
for i in range(N):
  var_index = l1.index(A[i])
  print(l4[var_index])

### FIXED CODE ###

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

from collections import Counter
C=Counter(A)
ANS=0
for i in C.values():
    ANS+=i*(i-1)//2

for a in A:
    k=C[a]

    print(ANS-(k*(k-1)//2)+((k-1)*(k-2)//2))
### BUGGY CODE ###

N,M=map(int,input().split())
X=[[] for x in range(N+1)]
city=[]
for i in range(M):
    P,Y=map(int,input().split())
    city.append((P,Y))
    X[P].append(Y)
X=[sorted(i) for i in X]
for p,y in city:
    num=X[p].index(y)+1
    print("%06d"%p+"%06d"%num)

### FIXED CODE ###

# ABC113 D 

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

P=[[] for _ in [0]*(N+1)]

for i in range(M):
    p,y=map(int,input().split())
    P[p].append((y,i))
    
from bisect import bisect_left as bl

res=[]
for p in range(N+1):
    Y=P[p][:]
    if not Y:
        continue
    
    sortY=sorted(list(set(Y)))
        
    zatY=[]
    for t_y in Y:
        zatY.append(bl(sortY,t_y))
    
    for index in zatY:
        y,i=sortY[index]
        num=10**12+p*10**6+index+1
        res.append((str(num)[1:],i))

res=[y for y,i in sorted(res,key=lambda x:x[1])]
print(*res,sep='\n')
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

def unset_nth_bit(num, n):
    return num & ~(1 << n)

def bit(S, j):
    # Sの右からj bit目(0-indexed)
    return (S>>j)&1

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

a = []
c = []
for i in range(M):
    p, q = map(int, input().split())
    a.append(p)
    c.append(list(map(int, input().split())))

dp = [[INF for j in range(1<<N)] for i in range(M+1)]
dp[0][0] = 0


for i in range(M):
    for S in range(1<<N):
        for T in range(1<<len(c[i])):
            SS = S
            for k in range(len(c[i])):
                if bit(T, k):
                    SS = unset_nth_bit(SS, c[i][k]-1)
            dp[i+1][S] = min(dp[i+1][S], dp[i][SS] + a[i])
        dp[i+1][S] = min(dp[i+1][S], dp[i][S])


if dp[M][(1<<N)-1] == INF:
    print(-1)
else:
    print(dp[M][(1<<N)-1])

### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

def unset_nth_bit(S, j):
    # Sの右からj bit目を0にする
    return S & ~(1 << j)

def set_nth_bit(S, j):
    # Sの右からj bit目を1にする
    return S | (1 << j)

def bit(S, j):
    # Sの右からj bit目(0-indexed)
    return (S>>j)&1

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

a = []
c = []
for i in range(M):
    p, q = map(int, input().split())
    a.append(p)
    c.append(list(map(int, input().split())))

dp = [[INF for j in range(1<<N)] for i in range(M+1)]
dp[0][0] = 0

for i in range(M):
    for S in range(1<<N):
        SS = S
        for cc in c[i]:
            SS = set_nth_bit(SS, cc-1)
        dp[i+1][SS] = min(dp[i+1][SS], dp[i][S] + a[i])
        dp[i+1][S] = min(dp[i+1][S], dp[i][S])

if dp[M][(1<<N)-1] == INF:
    print(-1)
else:
    print(dp[M][(1<<N)-1])
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort(reverse=True)
f.sort()
ok = max(x*y for x,y in zip(a,f))
ng = -1

def judge(v):
  tot = 0
  for x,y in zip(a,f):
    if x*y > v:
      tot += x - v//y
  return tot <= k

while ok-ng>1:
  mid = (ok+ng)//2
  if judge(mid):
    ok = mid
  else:
    ng = mid
print(ok)

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort(reverse=True)
f.sort()
z = list(zip(a,f))
ok = max(x*y for x,y in z)
ng = -1
while ok-ng>1:
  mid = (ok+ng)//2
  if sum(x-mid//y for x,y in z if x*y > mid) <= k:
    ok = mid
  else:
    ng = mid
print(ok)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def main():
    N = int(input())
    A = inpl()
    lx = 30
    tmp = [0] * lx

    for a in A:
        for i in range(lx):
            if (a >> i) % 2 == 1:
                tmp[i] = (tmp[i] + 1) % 2

    ans = []
    for a in A:
        b = 0
        for i in range(lx):
            if tmp[i] == 0 and (a >> i) % 2 == 1:
                b += 2**i
            elif tmp[i] == 1 and (a >> i) % 2 == 0:
                b += 2**i
        ans.append(b)
    print(*ans)

    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def main():
    N = int(input())
    A = inpl()
    lx = 30
    tmp = [0] * lx

    for a in A:
        for i in range(lx):
            if (a >> i) % 2 == 1:
                tmp[i] = (tmp[i] + 1) % 2

    ans = []
    for a in A:
        b = 0
        for i in range(lx):
            if tmp[i] == 0 and (a >> i) % 2 == 1:
                b += 2**i
            elif tmp[i] == 1 and (a >> i) % 2 == 0:
                b += 2**i
        ans.append(b)
    print(*ans)

    return


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

import collections
N, Q = map(int, input().split())
C = list(map(int, input().split()))
L = [0] * Q
R = [0] * Q
for i in range(Q):
    l,r = map(int, input().split())
    L[i] = l
    R[i] = r
D = {}
E = [{0:0}] * N
for i in range(N):
    if D.get(C[i], -1) == -1:
        D[C[i]] = 1
        D_other = dict(D)
        E[i] = D_other
    else:
        D[C[i]] += 1
        D_other = dict(D)
        E[i] = D_other

for i in range(Q):
    if L[i] == 1:
        E_dif = E[R[i] - 1]
    else:
        E_dif = dict(E[R[i] - 1].items() - E[L[i] - 2].items())
    e_dif = collections.Counter(E_dif)
    values, counts = zip(*e_dif.most_common())
    ans = len(values)
    print(ans)


### FIXED CODE ###

from collections import defaultdict
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = defaultdict(list)

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E[D_i].append((D_i, i))
        D[C[i]] = i

    F = defaultdict(list)
    for i in range(Q):
        l, r = map(int, input().split())
        F[l-1].append((r - 1, i))



    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for x in range(N - 1, -1, -1):
        for e in E[x]:
            d.add(e[1], 1)
        for f in F[x]:
            ANS[f[1]] = f[0] - x + 1 - d.sum(f[0])

    for i in range(Q):
        print(ANS[i])

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

n = int(input())

a = []
b = []

for i in range(n):
    aa, bb = map(int, input().split(' '))
    a.append(aa)
    b.append(bb)

order = list(range(n))
tmp_b = b[:]

while(True):
    ok = False
    for i in range(n - 1):
        ok = False
        if tmp_b[i] > tmp_b[i + 1]:
            tmp = tmp_b[i]
            tmp_b[i] = tmp_b[i + 1]
            tmp_b[i + 1] = tmp

            tmp = order[i]
            order[i] = order[i + 1]
            order[i + 1] = tmp
            break
        ok = True
    if ok:
        break

available = False

for i in range(1000):

    margin = [0 for i in range(n)]
    now_time = 0
    for i in range(n):
        j = order[i]
        margin[j] = b[j] - (now_time + a[j])
        now_time += a[j]
    
    if min(margin) >= 0:
        available = True
        break
    else:
        min_index = margin.index(min(margin))
        max_index = margin.index(max(margin))

        tmp = order[min_index]
        order[min_index] = order[max_index]
        order[max_index] = tmp


if available:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = int(input())

a = []
b = []

for i in range(n):
    aa, bb = map(int, input().split(' '))
    a.append(aa)
    b.append(bb)

order = sorted(range(len(b)), key=lambda k: b[k])

available = False


margin = [0 for i in range(n)]
now_time = 0
for i in range(n):
    j = order[i]
    margin[j] = b[j] - (now_time + a[j])
    now_time += a[j]

if min(margin) >= 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N, M = map(int, input().split())
friend = [1 for i in range(N)]
k = []

for i in range(M):
    A, B = map(int, input().split())
    if [A, B] not in k:
        friend[A-1] += 1
        friend[B-1] += 1
        k.append([A, B])
        k.append([B, A])

print(max(friend))


### FIXED CODE ###

def find(n):
    if parent[n] < 0:
        return n
    else:
        parent[n] = find(parent[n])
        return parent[n]


def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x == root_y:
        return
    if parent[root_x] > parent[root_y]:
        root_x, root_y = root_y, root_x
    parent[root_x] += parent[root_y]
    parent[root_y] = root_x


def get_size(x):
    return -parent[find(x)]


n, m = map(int, input().split())
parent = [-1 for _ in range(n)]

for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    union(a, b)
ans = 0
for i in range(n):
    ans = max(ans, get_size(i))
print(ans)
### BUGGY CODE ###

n = int(input())
lst = list(map(int,input().split()))
res = 1
for i in lst:
    res *= i
if res > 1000000000000000000:
    print(-1)
else:
    print(res)


### FIXED CODE ###

def cal():
    n = int(input())
    lst = list(map(int,input().split()))
    if 0 in lst:
    	return 0
    else:
        prod = 1
        for a in lst:
            prod *= a
            if prod > 1000000000000000000:
                return -1
    return prod
print(cal())
### BUGGY CODE ###

from sys import stdin

def solve() :
    X,Y = [int(x) for x in stdin.readline().rstrip().split()]

    if X == Y :
        print("-1")
        return
    
    ans = X * 2
    while True:
        if ans % Y != 0 :
            print(ans)
            return
        elif ans >= 1e18:
            print(-1)
            return
        else:
            ans += X

solve();

### FIXED CODE ###

from sys import stdin

def solve() :
    X,Y = [int(x) for x in stdin.readline().rstrip().split()]

    if(X % Y != 0):
        print(X)
    else :
        print(-1)

solve();
### BUGGY CODE ###

import numpy as np
s = input()
t = input()
dp = np.zeros((len(s)+1, len(t)+1))

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i][j] = dp[i-1][j-1]+1
        else :
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

l = int(dp[len(s)-1][len(t)-1])
i = len(s)-1
j = len(t)-1
ans = []

while l>0:
    if s[i] == t[j]:
        ans.append(s[i])
        i -= 1
        j -= 1
        l -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else :
        j -= 1
print(''.join(ans[::-1]))


### FIXED CODE ###

import numpy as np
s = np.array(list(input()))
t = np.array(list(input()))
dp = np.zeros((len(s)+1, len(t)+1), dtype=int)

equal = s[:, None] == t[None, :]

for i in range(len(s)):
    dp[i+1, 1:] = np.maximum(dp[i, :-1]+equal[i], dp[i, 1:])
    dp[i+1] = np.maximum.accumulate(dp[i+1])

i = len(s)
j = len(t)
ans = []

while i>0 and j>0:
    if s[i-1] == t[j-1]:
        ans.append(s[i-1])
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else :
        j -= 1

print(''.join(ans[::-1]))
### BUGGY CODE ###

S = input()
K = int(input())
S_len = len(S)
ans = set()
for i in range(0, S_len+1):
    for j in range(0, S_len):
        if j + i <= S_len:
            t = S[j:j + i]
            if t != '':
                ans.add(t)
ans = list(ans)
ans.sort()
print(ans[K-1])


### FIXED CODE ###

S = input()
K = int(input())
S_len = len(S)
ans = set()
for i in range(0, K+1):
    for j in range(0, S_len):
        if j + i <= S_len:
            t = S[j:j + i]
            if t != '':
                ans.add(t)
ans = list(ans)
ans.sort()
print(ans[K-1])
### BUGGY CODE ###

def main():
    S = input()
    N = len(S)

    MOD = 10**9 + 7
    dp = [[0 for _ in range(13)] for _ in range(N)]  # dp[i][j]: S[i]までみて13で割ってjあまるものの個数

    # 初期値
    if S[0] == "?":
        for j in range(10):
            dp[0][j] = 1
    else:
        dp[0][int(S[0])] = 1

    # dpテーブル更新式
    for i in range(1, N):
        if S[i] == "?":
            for si in range(10):
                for j in range(13):
                    dp[i][(j*10 + si)%13] += dp[i-1][j] % MOD
        else:
            si = int(S[i])
            for j in range(13):
                dp[i][(j*10 + si)%13] += dp[i-1][j] % MOD

    print(dp[N-1][5] % MOD)

if __name__ == '__main__':
    main()


### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13

print(dp[len(S)][5])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = [[0] * (N-1)]+[list(map(int,input().split())) for _ in range(N)]

idx = [0] * (N+1)
cnt = 0
day = 0
flag_max = [False] * (N+1)
while cnt != N:
    
    error = True
    flag =[False] * (N+1)
    looplist = [i for i in range(1,N+1) if not(flag_max[i])]
    
    for i in looplist:
        if (flag[i]):continue
        tmp = A[i][idx[i]]
        if (flag[tmp]):continue
    
        if A[tmp][idx[tmp]] == i:
            idx[tmp] = idx[tmp] + 1
            idx[i] = idx[i] + 1
            if idx[tmp] == N-1:
                flag_max[tmp] = True
                cnt += 1
            if idx[i] == N-1:
                flag_max[i] = True
                cnt += 1
            flag[i] = True
            flag[tmp] = True
            error = False
    if error:
        print(-1)
        sys.exit()
    
    day += 1
            

    if day > 10000:
        print(N*(N-1)//2)
    
    
print(day)
    
    


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = [[0] * (N-1)]+[list(map(int,input().split())) for _ in range(N)]

idx = [0] * (N+1)
cnt = 0
day = 0
flag_max = [False] * (N+1)
while cnt != N:
    
    error = True
    flag =[False] * (N+1)
    looplist = [i for i in range(1,N+1) if not(flag_max[i])]
    
    for i in looplist:
        if (flag[i]):continue
        tmp = A[i][idx[i]]
        if (flag[tmp]):continue
    
        if A[tmp][idx[tmp]] == i:
            idx[tmp] = idx[tmp] + 1
            idx[i] = idx[i] + 1
            if idx[tmp] == N-1:
                flag_max[tmp] = True
                cnt += 1
            if idx[i] == N-1:
                flag_max[i] = True
                cnt += 1
            flag[i] = True
            flag[tmp] = True
            error = False
    if error:
        print(-1)
        sys.exit()
    
    day += 1
            

    if day > 10000:
        print(N*(N-1)//2)
        sys.exit()
    
    
print(day)
### BUGGY CODE ###

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a = [0]
b = [0]
ans = 0
max_num = 0
j = 0
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])
for i in range(N+1):
    if a[i] > K:
        break
    else:
        j = M
        while b[j] > K - a[i]:
            j -=1
            if j <0:
                break
    ans = max(ans,i + j)
print(ans)

### FIXED CODE ###

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a = [0]
b = [0]
ans = 0
max_num = 0
j = M
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])
for i in range(N+1):
    if a[i] > K:
        break
    else:
        while b[j] > K - a[i]:
            j -=1
            if j <0:
                break
    if K>= a[i] + b[j]:
        ans = max(ans,i + j)
print(ans)
### BUGGY CODE ###

import numpy as np
n = int(input())
A = [[ord(i) for i in input()] for j in range(n)]
count = 0
for a in range(n):
    arr = np.roll(A, a, axis=0)
    arrT = arr.T
    for i in range(n):
        if list(arr[i][i+1:]) != list(arrT[i][i+1:]):
            break
    else:
        count += n
print(count)

### FIXED CODE ###

n = int(input())
A = [input() for _ in range(n)]
# AT = list(map(''.join,zip(*A)))
count = 0
for a in range(n):
    arr = A[a:][:] + A[:a][:]
    arrT = list(map(''.join, zip(*arr)))
    for i in range(n):
        if arr[i][i+1:] != arrT[i][i+1:]:
            break
    else:
        count += n
print(count)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())

    MAP = [[0]*N for n in range(N)]

    for m in range(M):
        a, b = map(int, input().split())
        MAP[a-1][b-1] = 1
        MAP[b-1][a-1] = 1

    for first in range(N):
        if MAP[0][first]==1 and MAP[first][N-1] == 1:
            print('POSSIBLE')
            return

    print('IMPOSSIBLE')
        

if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()

### FIXED CODE ###

from collections import defaultdict as dd
def main():
    N, M = map(int, input().split())

    D = dd(list)

    for m in range(M):
        a, b = map(int, input().split())
        D[a-1].append(b-1)

    for d in D[0]:
        if N-1 in D[d]:
            print('POSSIBLE')
            return

    print('IMPOSSIBLE')
        

if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()
### BUGGY CODE ###

def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v

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

cnt = 0
G = []
for i in range(100):
    if n < 1 + 3*i:
        break
    G.append(1 + 3*i)
m = len(G)
G.reverse()
for i in range(m):
    insertionSort(A, n, G[i])

print(m)
print(*G)
print(cnt)
print(*A, sep='\n')

### FIXED CODE ###

def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v

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

cnt = 0
G = [1]
for i in range(99):
    if n < 1 + 3*G[-1]:
        break
    G.append(1 + 3*G[-1])
m = len(G)
G.reverse()
for i in range(m):
    insertionSort(A, n, G[i])

print(m)
print(*G)
print(cnt)
print(*A, sep='\n')