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

#!/usr/local/bin/python3

'''
Author: andyli
Time: 2020-06-24 21:10:25
'''

mod = 10**9 + 7

m = int(input())
n = len(input())
t = n+m

fac = [0]*(t+1)
ifac = [0]*(t+1)
pw = [0] * (t+1)
fac[0] = 1
for i in range(1, t+1):
    fac[i] = fac[i-1] * i % mod
ifac[t] = pow(fac[t], mod-2, mod)

for i in range(t-1, -1, -1):
    ifac[i] = ifac[i+1] * (i+1) % mod

pw[0] = 1
for i in range(1, t+1):
    pw[i] = pw[i-1] * 25 % mod

def C(n, m):
    return fac[n]*ifac[m]*ifac[n-m]%mod

ans=0
for i in range(n, t+1):
    ans = (ans + pw[t-i] * C(t, i)) % mod

print(ans)

### FIXED CODE ###

#!/usr/local/bin/python3

'''
Author: andyli
Time: 2020-06-24 21:10:25
'''

mod = 10**9 + 7

m = int(input())
n = len(input())
t = n+m

fac = [0]*(t+1)
ifac = [0]*(t+1)
pw = [0] * (t+1)
fac[0] = 1
for i in range(1, t+1):
    fac[i] = fac[i-1] * i % mod
ifac[t] = pow(fac[t], mod-2, mod)

for i in range(t-1, -1, -1):
    ifac[i] = ifac[i+1] * (i+1) % mod

pw[0] = 1
for i in range(1, t+1):
    pw[i] = pw[i-1] * 25 % mod

def C(n, m):
    return fac[n]*ifac[m]*ifac[n-m]%mod

ans=0
for i in range(n, t+1):
    ans = (ans + pw[t-i] * C(t, i)) % mod

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

import sys
input = sys.stdin.readline
if __name__ == "__main__":
    N,M,Q = map(int,input().split())
    acc = [[0]*(N+1) for _ in range(N+1)]
    for _ in range(M):
        l,r = map(int,input().split())
        acc[l][r] += 1
    for i in range(N):
        for j in range(1, N+1):
            acc[i][j] += acc[i][j-1]
    for _ in range(Q):
        p,q = map(int,input().split())
        ans = 0
        for i in range(p,q+1):
            ans += acc[i][q]-acc[i][p-1]
        print(ans)

### FIXED CODE ###

N,M,Q = map(int,input().split())
plane = [[0]*N for _ in range(N)]
for i in range(M):
    l,r = map(int,input().split())
    plane[l-1][r-1] += 1
acc = [[0]*(N+1) for _ in range(N)]

for i in range(N):
    for j in range(N):
        acc[i][j+1] = acc[i][j]+plane[i][j]

for i in range(Q):
    p,q = map(int,input().split())
    tmp = 0
    for j in range(p,q+1):
        tmp += acc[j-1][q]-acc[j-1][p-1]
    print(tmp)
### BUGGY CODE ###

a,b,x = map(int,input().split())
 
d =0
 
for c in range(a,b+1):
  if c%x == 0:
    d+=1
print(d)

### FIXED CODE ###

a,b,x = map(int,input().split())
 
print(b//x-(a-1)//x)
### BUGGY CODE ###

import numpy as np
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = [0] + A
stack = [A[1]]
idx_list = [1]
while True:
    last = A[stack[-1]]
    if last in stack:
        ind = stack.index(last)
        if ind == stack[-1]:
            break
    idx_list.append(stack[-1])
    stack.append(last)
    if len(stack) == K:
        print(stack[-1])
        exit(0)
mod = len(stack[ind:])
idx = ind + (K-ind-1)%mod
print(stack[idx])

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    A = list(map(lambda x: int(x)-1, input().split()))
    now = 0
    dict_ = {}
    stack = []
    for i in range(N):
        if now not in dict_:
            dict_[now] = A[now]
            stack.append(now)
            now = A[now]
        else:
            idx = stack.index(now)
            mod = i - idx
            break
    idx = idx + (K-idx) % mod
    idx = min(K, idx)
    print(stack[idx]+1)


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

import numpy as np
H,W,A,B=np.array(list(map(int, input().split())))

for row in range(H):
    L1=np.zeros(W)
    if (B-row-1)>=0:
        L1[0:W-A]=1
    else:
        L1[W-A:]=1
    L2=np.array(L1, dtype='int64')
    print(''.join(list(map(str, L2))))

### FIXED CODE ###

import numpy as np
H,W,A,B=np.array(list(map(int, input().split())))

for row in range(H):
    if  row<=B-1:
        print(''.join(list(map(str, [1 if i<=A-1 else 0 for i in range(W)]))))
    else:
        print(''.join(list(map(str, [0 if i<=A-1 else 1 for i in range(W)]))))
### BUGGY CODE ###

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

    # 一点更新・一点取得の加法BIT
    class BIT():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        # 位置iに値vを足す
        def add(self, i):
            x, n, bit = i+1, self.n, self.bit
            while x < n+1:
                bit[x] += 1
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret, x, bit = 0, i, self.bit
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            return ret

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a, int(b)-1) for a, b in ab]

    f_B = [[0]*(n+1) for _ in [0]*n]  # f_B[i][j] = Bがi個、Wがj個あるときのBを置く手数
    f_W = [[0]*(n+1) for _ in [0]*n]  # f_W[i][j] = Bがi個、Wがj個あるときのWを置く手数
    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    # まずf_Bから出す
    for i in range(n+1):
        bit = BIT(n)
        cnt = 0
        for a, b in ab:
            if a == "B":
                f_B[b][i] = bit.sum(n-b-1)+cnt
                bit.add(n-b-1)
            else:
                if b >= i:
                    cnt += 1
    # f_Wも同様
    for i in range(n+1):
        bit = BIT(n)
        cnt = 0
        for a, b in ab:
            if a == "W":
                f_W[b][i] = bit.sum(n-b-1)+cnt
                bit.add(n-b-1)
            else:
                if b >= i:
                    cnt += 1
    for i in range(n+1):
        for j in range(n+1):
            d = dp[i][j]
            try:
                dp[i+1][j] = min(dp[i+1][j], d+f_B[i][j])
            except:
                pass
            try:
                dp[i][j+1] = min(dp[i][j+1], d+f_W[j][i])
            except:
                pass
    print(dp[n][n])


main()


### FIXED CODE ###

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

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a == "B", int(b)-1) for a, b in ab]
    dct_b = [0]*n
    dct_w = [0]*n
    for i, (a, b) in enumerate(ab):
        if a:
            dct_b[b] = i
        else:
            dct_w[b] = i

    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    # 左i個にあるj以上のボールの数
    lb = [[0]*(n+1) for _ in [0]*(2*n)]
    lw = [[0]*(n+1) for _ in [0]*(2*n)]

    for j in range(n):
        cnt1, cnt2 = 0, 0
        for i, (a, b) in enumerate(ab):
            lb[i][j] = cnt1
            lw[i][j] = cnt2
            if a:
                if b >= j:
                    cnt1 += 1
            else:
                if b >= j:
                    cnt2 += 1

    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    for i in range(n+1):
        dp1 = dp[i]
        if i < n:
            dp2 = dp[i+1]
            t = dct_b[i]
        for j in range(n+1):
            d = dp1[j]
            if i < n:
                dp2[j] = min(dp2[j], d+lb[t][i]+lw[t][j])
            if j < n:
                t2 = dct_w[j]
                dp1[j+1] = min(dp1[j+1], d+lb[t2][i]+lw[t2][j])
    print(dp[n][n])


main()
### BUGGY CODE ###

import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K, *A = map(int, read().split())
K = min(50,K)
B = [0]*N
for _ in range(K):
  for i in range(N):
    a = max(0,i-A[i])
    b = min(N-1,i+A[i])
    B[a] += 1
    if b+1 <= N-1:
      B[b+1] -= 1
  B = np.cumsum(B)
  A=B
  B = [0]*N
print(*A)

### FIXED CODE ###

import sys
import numpy as np
from numba import jit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K, *A = map(int, read().split())
K = min(50,K)

@jit
def imos(A):
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    a = max(0,i-x)
    b = min(N-1,i+x)
    B[a] += 1
    if b+1 <= N-1:
      B[b+1] -= 1
  B = np.cumsum(B)
  return B

for i in range(K):
  if i >= 50:
    break
  A = imos(A)
print(*A)
### BUGGY CODE ###

n = int(input())
for a in range(1,3501):
    for b in range(1,3501):
        if 4*a*b-n*a-n*b == 0:
            continue
        if 1 <= n*a*b//(4*a*b-n*(a+b)) <= 3500 and (n*a*b)%(4*a*b-n*a-n*b) == 0:
            print(a,b,n*a*b//(4*a*b-n*(a+b)))
            exit()

### FIXED CODE ###

n = int(input())
for a in range(1,3501):
    for b in range(1,3501):
        if 4*a*b-n*a-n*b == 0:
            continue
        if 1 <= n*a*b//(4*a*b-n*(a+b)) <= 3500 and (n*a*b)%(4*a*b-n*a-n*b) == 0:
            print(a,b,n*a*b//(4*a*b-n*(a+b)))
            exit()
### BUGGY CODE ###

d = int(input())
c = list(map(int,input().split()))
ans = []
fin = [1]*d
pen = [0]*26
sattemp = 0
sat = 0
sl = [list(map(int,input().split())) for i in range(d)]
for k in range(400):
    for l in range(28):
        for i in range(d):
            s = sl[i]
            sp = sum(pen)
            temp = -(10**9)
            for j in range(26):
                if s[j]*l*0.1-(sp-pen[j])*(k*0.01) > temp:
                    temp = s[j]*l*0.1-(sp-pen[j])*(k*0.01)
                    tempans = j+1
            ans += [tempans]
            sattemp += s[tempans-1]-sp+pen[tempans-1]
            for j in range(26):
                pen[j] += c[j]
                pen[tempans-1] = 0
        if sattemp > sat:
            sat = sattemp
            fin = ans
        ans = []
        pen = [0]*26
        # print(k,sattemp)
        sattemp = 0
for i in fin:
    print(i)

### FIXED CODE ###

d = int(input())
c = list(map(int,input().split()))
for i in range(d):
    s = list(map(int,input().split()))
    print(s.index(max(s))+1)
### BUGGY CODE ###

from collections import deque
b = deque(list())
n = int(input())
alist = list(map(int,input().split()))
for a in alist:
    b.append(a)
    b.reverse()
for i in b:
    print(i, end=' ')

### FIXED CODE ###

from collections import deque
b = deque(list())
n = int(input())
alist = list(map(int,input().split()))
num = len(alist)

if num % 2 == 0:
    for i in range(num):
        if i % 2 == 0:
            b.append(alist[i])
        elif i % 2 == 1:
            b.appendleft(alist[i])

elif num % 2 == 1:
    for i in range(num):
        if i % 2 == 1:
            b.append(alist[i])
        elif i % 2 == 0:
            b.appendleft(alist[i])

for i in b:
    print(i, end=' ')
### BUGGY CODE ###

m = input()
N = list(map(int, input().split(' ')))
# m = int(input())
# k = int(input())
c = 0
N.sort()
for i in N:
    
    if N.count(i) > 1:
        c = 1
        break
if c == 0:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

m = input()
N = list(map(int, input().split(' ')))
# m = int(input())
# k = int(input())
c = 0
N.sort()
for i in range(len(N)-1):
    if N[i] == N[i+1]:
        print('NO')
        exit()

print('YES')
### BUGGY CODE ###

s=input()
n=int(input())
for i in range(n):
    e=list(map(str,input().split()))
    q=int(e[0])
    if len(e)!=1:
        f=int(e[1])
        c=e[2]
    if q==2:
        if f==1:
            s=c+s
        else:
            s=s+c
    else:
        x=list(reversed(s))
        y=''.join(x)
        s=y
print(s)

### FIXED CODE ###

s=input()
n=int(input())
cnt=0
l=[]
r=[]
for i in range(n):
    e=list(map(str,input().split()))
    q=int(e[0])
    if len(e)!=1:
        f=int(e[1])
        c=e[2]
    if q==2:
        if (f==1 and cnt%2==0) or (f==2 and cnt%2!=0):
            l.append(c)
        else:
            r.append(c)
    else:
        cnt+=1
if cnt%2==0:
    print(''.join(l[::-1])+s+''.join(r))
else:
    print(''.join(r[::-1])+s[::-1]+''.join(l))
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort(reverse=True)
ans = 0
 
for i in range(n-2):
    for j in reversed(range(i+2,n)):
        gap = l[i]-l[j]
        if l[j-1] > gap:
            ans += (j-i)*(j-i-1)//2
            break
        elif l[i+1] < gap:
            break
        else:
            for k in reversed(range(i+1,j)):
                if l[k] > gap:
                    ans += k-i
                    break
 
print(ans) 

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        ind = bisect.bisect_left(l,l[i]+l[j])
        ans += ind-j-1

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

t = int(input())
ans = []

for tt in range(t):
    n = int(input())

    redk = {}
    bluek = {}
    asum = 0
    for i in range(n):
        k,l,r = list(map(int,input().split()))
        asum += min(l,r)
        if l >= r:
            if k in redk:
                redk[k].append(l-r)
            else:
                redk[k] = [l-r]
        else:
            if k in bluek:
                bluek[k].append(r-l)
            else:
                bluek[k] = [r-l]
    reds = []
    for i in range(1,n+1):
        if i in redk:
            reds += redk[i]
        while len(reds) > i:
            reds.remove(min(reds))
    blues = []
    for i in range(n,0,-1):
        if i in bluek:
            blues += bluek[i]
        while len(blues) >= n + 1 - i:
            blues.remove(min(blues))
    ans.append(asum + sum(reds) + sum(blues))

for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

t = int(input())
ans = []

for tt in range(t):
    n = int(input())

    redk = {}
    bluek = {}
    asum = 0
    for i in range(n):
        k,l,r = list(map(int,input().split()))
        asum += min(l,r)
        if l >= r:
            if k in redk:
                redk[k].append(l-r)
            else:
                redk[k] = [l-r]
        else:
            if k in bluek:
                bluek[k].append(r-l)
            else:
                bluek[k] = [r-l]
    reds = []
    for i in range(1,n+1):
        if i in redk:
            reds += redk[i]
        while len(reds) > i:
            reds.remove(min(reds))
    blues = []
    for i in range(n,0,-1):
        if i in bluek:
            blues += bluek[i]
        while len(blues) >= n + 1 - i:
            blues.remove(min(blues))
    ans.append(asum + sum(reds) + sum(blues))

for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n, k = map(int, input().split())
P = [[-1]*(k+1) for _ in range(n+1)]
MOD = 10**9+7

def product(l, k):
  if P[l][k] != -1:
    return P[l][k]
  if k==1:
    return l
  c = 0
  for i in range(1, l+1):
    c += product(n//i, k-1)
    c %= MOD
  P[l][k] = c
  return c

print(product(n, k))

### FIXED CODE ###

import sys
input = sys.stdin.readline
from itertools import accumulate
MOD = 10**9+7
  
n, k = map(int, input().split())
S = set()
i = 1
while i * i <= n:
  S.add(i)
  S.add(n//i)
  i += 1
L = [0] + sorted(S)
l = len(L) - 1
num = [0]*l
for i in range(l):
  num[i] = L[i+1] - L[i]
dp = [0]*l
dp[0] = 1
for _ in range(k):
  A = list(accumulate(dp))
  for i in range(l):
    dp[i] = A[l-1-i] * num[i]
    dp[i] %= MOD
ans = sum(dp) % MOD
print(ans)
### BUGGY CODE ###

def main():
    import heapq as h
    n,q = map(int, input().split())
    tl = []
    que = []
    d = dict()
    for _ in range(n):
        s,t,x = map(int, input().split())
        h.heappush(tl,[s-x,1,x])
        h.heappush(tl,[t-x,0,x])
    for _ in range(q):
        t = int(input())
        que.append(t)
        h.heappush(tl,[t,2])
    wor = dict()
    wcur = 0
    cur = -1
    for _ in range(n*2+q):
        x = h.heappop(tl)
        if x[1] == 1:
            wcur += 1
            wor[x[2]] = 1
            if cur < 0 or x[2] < cur:
                cur = x[2]
        elif x[1] == 0:
            wcur -= 1 
            wor[x[2]] = 0
            if cur == x[2]:
                if wcur:
                    cur = min([x for x in wor if wor[x]])
                else:
                    cur = -1
        else:
            d[x[0]] = cur
    for i in que:
        print(d[i])
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n,q = map(int, input().split())
    tl = []
    que = []
    d = dict()
    for _ in range(n):
        s,t,x = map(int, input().split())
        tl.append((s-x,1,x))
        tl.append((t-x,0,x))
    for _ in range(q):
        t = int(input())
        tl.append((t,2))
    tl.sort()
    wor = set()
    wcur = 0
    cur = -1
    flg = 0
    for x in tl:
        if x[1] == 1:
            wcur += 1
            wor.add(x[2])
            if cur < 0 or x[2] < cur:
                cur = x[2]
                flg = 0
        elif x[1] == 0:
            wcur -= 1 
            wor.remove(x[2])
            if x[2] == cur:
                flg = 1
            if not wcur:
                cur = -1
                flg = 0
        else:
            if flg:
                cur = min(wor)
                flg = 0
            print(cur)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math
 
K = int(input());
gcd = 0;

for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      gcd += math.gcd(math.gcd(a,b),c);

print(gcd)


### FIXED CODE ###

from math import gcd
 
K = int(input());
sum = 0;

for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      sum += gcd(gcd(a,b),c);

print(sum)
### BUGGY CODE ###

def check(i):
    num=int(i**0.5)
    if i==1:return 0
    if i==2:return 1
    for j in range(2,num+1):
        if i%j==0:break

    else:return 1
    return 0
q=int(input())
lr=[list(map(int,input().split())) for i in range(q)]

L=[0]*(10**5)#1~100000
for i in range(1,10**5):
    L[i]=check(i+1)

for l,r in lr:
    cnt=0
    for i in range(l,r+1,2):
        if L[i-1]==0:continue
        if L[(i+1)//2-1]==0:continue
        cnt+=1

    print(cnt)

### FIXED CODE ###

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

def jud(i):
    #iの素数判定
    num=int(i**0.5)+1
    for k in range(2,num):
        if i%k==0:
            return 0
    return 1

s=[0]*(10**5+1)
for i in range(2,10**5+1):
    if i%2==0:
        s[i]=s[i-1]
    else:
        if jud(i)*jud((i+1)//2)==1:
            s[i]=s[i-1]+1
        else:
            s[i]=s[i-1]

for k,v in l:
    ans=s[v]-s[k-1]
    print(ans)
### BUGGY CODE ###

def main():
    s = input()
    t = input()
    S = len(s)
    T = len(t)
    dp = [[[0, ""] for j in range(T+1)] for _ in range(S+1)]
    for i in range(S):
        for j in range(T):
            if s[i] == t[j]:
                dp[i+1][j+1][0] = dp[i][j][0]+1
                dp[i+1][j+1][1] = dp[i][j][1]+s[i]
            else:
                if dp[i+1][j][0] >= dp[i][j+1][0]:
                    dp[i+1][j+1][0] = dp[i+1][j][0]
                    dp[i+1][j+1][1] = dp[i+1][j][1]
                else:
                    dp[i+1][j+1][0] = dp[i][j+1][0]
                    dp[i+1][j+1][1] = dp[i][j+1][1]
    print(dp[S][T][1])


main()


### FIXED CODE ###

def main():
    s = input()
    t = input()
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for _ in range(S+1)]
    for i in range(S):
        for j in range(T):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    res = ""
    i = S
    j = T
    while i > 0 and j > 0:
        if dp[i][j] == dp[i][j-1]:
            j -= 1
        elif dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            res = s[i-1]+res
            i -= 1
            j -= 1
    print(res)


main()
### BUGGY CODE ###

N = int(input())
P_list = [int(i) for i in input().split()]
c = 0
for j in range(N):
  if P_list[j] == min(P_list[0:j+1]):
    c += 1
  else:
    pass
print(c)

### FIXED CODE ###

N = int(input())
P = [int(x) for x in input().split()]
R = 1000000
c = 0
for i in range(N):
  if min(R, P[i])==P[i]:
    c += 1
    R = P[i]
  else:
    pass
print(c)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
for _ in range(q):
    l,r = map(int,input().split())
    print (s[l-1:r].count('AC'))


### FIXED CODE ###

n,q = map(int,input().split())
s = input()

t = [0] * (n+1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2] == 'AC' else 0)

#print (t)

for _ in range(q):
    l,r = map(int,input().split())
    print (t[r-1]-t[l-1])
### BUGGY CODE ###

a, b = map(int, input().split())
c = input()
for i in range(b):
    d, e = map(int, input().split())
    f = c[d-1:e]
    print((len(f)-len(f.replace("AC", "")))//2)

### FIXED CODE ###

a, b = map(int, input().split())
c = input()
d = [0] * a
e = 0
for i in range(1, a):
    if c[i] == "C" and c[i-1] == "A":
        e += 1
    d[i] = e
for i in range(b):
    f, g = map(int, input().split())
    print(d[g-1]-d[f-1])
### BUGGY CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    base = [0] * n
    midway = [0] * (n//1000 + 1)

    for _ in xrange(q):
        a, v = (int(s) for s in readline().split())

        a -= 1
        base[a] += v

        b = a - a % 1000
        index = b
        value = base[b]
        end = b + 1000 if b + 1000 < n else n
        for i in xrange(b, end):
            if value < base[i]:
                value = base[i]
                index = i
        midway[b//1000] = index

        index = midway[0]
        value = base[index]
        for i in midway:
            if value < base[i]:
                value = base[i]
                index = i

        print(index+1, value)
    exit()


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    base = [0] * n
    midway = [0] * (n//100 + 1)
    last = [0] * (n//10000 + 1)

    for _ in range(q):
        a, v = (int(s) for s in readline().split())

        a -= 1
        base[a] += v

        b = a - a % 100

        index = b
        value = base[b]
        end = b + 100 if b + 100 < n else n
        for i in range(b, end):
            if value < base[i]:
                value = base[i]
                index = i
        midway[b//100] = index

        c = a - a % 10000
        cc = c // 100

        index = c
        value = base[c]
        for i in midway[cc:cc+100]:
            if value < base[i]:
                value = base[i]
                index = i
        last[c//10000] = index

        index = last[0]
        value = base[index]
        for i in last:
            if value < base[i]:
                value = base[i]
                index = i

        print(index+1, value)
    exit()


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

def insertionSort(a,n,g):
    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
            global cnt
            cnt+=1
        a[j+g]=v

def shellsort(a,n):
    global cnt
    cnt=0
    g=[(3**i-1)//2  for i in range(n,0,-1) if (3**i-1)//2<n or (3**i-1)//2==1]
    m=len(g)
    #print(g,m)
    for i in range(m):
        insertionSort(a,n,g[i])
    return a,m,g

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

a,m,g=shellsort(a,n)

print(m)
print(*g)
print(cnt)
for i in a:
    print(i)

### FIXED CODE ###

def insertionSort(a,n,g):
    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
            global cnt
            cnt+=1
        a[j+g]=v

def shellsort(a,n):
    global cnt
    cnt=0
    g=[i for i in [262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1] if i <= n]
    m=len(g)
    #print(g,m)
    for i in range(m):
        insertionSort(a,n,g[i])
    return a,m,g

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

a,m,g=shellsort(a,n)

print(m)
print(*g)
print(cnt)
for i in a:
    print(i)