Harryxun/stf_run huggingface dataset:
h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 移動Aで探索する方向
d_a = [(-1,0), (0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = [ (i, j) for j in range(-2, 3) for i in range(-2, 3)]

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+2, w+2), INF)
dist = [[INF for j in range(w+2)] for i in range(h+2)]

# マップ境界と壁を距離0にして探索させない
for i in range(h+2):
    dist[i, 0] = 0
    dist[i, -1] = 0
for j in range(w+2):
    dist[0, j] = 0
    dist[-1, j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+1][j+1] = 0
#dist = [[INF for j in range(w)] for i in range(h)]

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        # マップ境界で2以上移動したときに、反対の境界に向かうように剰余を取る
        di, dj = (d_b[v][0]+i)%(h+2), (d_b[v][1]+j)%(w+2)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)


### FIXED CODE ###

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 移動Aで探索する方向
d_a = [(-1,0), (0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = [ (i, j) for j in range(-2, 3) for i in range(-2, 3)]

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+2, w+2), INF)
dist = [[INF for j in range(w+2)] for i in range(h+2)]

# マップ境界と壁を距離0にして探索させない
for i in range(h+2):
    dist[i][0] = 0
    dist[i][-1] = 0
for j in range(w+2):
    dist[0][j] = 0
    dist[-1][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+1][j+1] = 0
#dist = [[INF for j in range(w)] for i in range(h)]

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        # マップ境界で2以上移動したときに、反対の境界に向かうように剰余を取る
        di, dj = (d_b[v][0]+i)%(h+2), (d_b[v][1]+j)%(w+2)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

dd={}
def get_f(v):
	global dd
	if v == 0:
		return 0
		
	if v in dd:
		return dd[v]
	
	pn = bin(v).count('1')
	ret = 1+get_f(v % pn)
	dd[v] = ret
	return ret
	
def bb(n, s):
	saigo = int(s[-1])
	for i, c in enumerate(s[:-1]):
		if c == '0':
			print(get_f(saigo)+1)
		else:
			print(0)
	if saigo == '0':
		print(get_f(1)+1)
	else:
		print(0)
		

def main():
	n = int(input())
	#b , c = tin()
	s = input()
	sa=s[::-1]
	n_one=s.count('1')
	if n_one == 1:
		bb(n,s)
		return 
	#pa(n_one)
	#pa(s)
	amari_p = 0
	amari_n = 0
	for i, c in enumerate(sa):
		if c == '1':
			amari_p += pow(2,i,n_one+1)
			amari_n += pow(2,i,n_one-1)
			amari_p %= n_one+1
			amari_n %= n_one-1
		
	#pa(amari_p)
	#pa(amari_n)
	for i, c in enumerate(s):
		keta = n - i - 1
		if c == '1':
			ta = amari_n
			ta -= pow(2,keta,n_one-1)
			ta %= n_one-1
		else:
			ta = amari_p
			ta += pow(2, keta, n_one+1)
			#pa(('q',ta))
			ta %= n_one+1
		#pa((keta,pow(2,keta),ta))
		print(get_f(ta)+1)
		
		
	
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	l, r , d= tin()
	#s = input()
	ret = r // d - (l-1) // d
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
# 2019-11-23 21:00:35(JST)
import sys

def main():
    m = int(sys.stdin.readline().rstrip())

    s = ''
    for i in range(m):
        d, c = sys.stdin.readline().split()
        c = int(c)
        s += d * c

    count = 0
    while len(s) >= 2:
        s = str(int(s[0]) + int(s[1])) + s[2:]
        count += 1
    
    print(count)




if __name__ == '__main__':
    main()


### FIXED CODE ###

# 2019-11-23 21:00:35(JST)
import sys
import collections
import math

def main():
    m = int(sys.stdin.readline().rstrip())

    a = collections.defaultdict(int)
    for _ in range(m):
        d, c = map(int, sys.stdin.readline().split())
        a[d] += c
    

    b = 0
    for i in range(10):
        b += (i + 9) * a[i]
    
    ans = math.ceil((b - 9)/ 9) - 1
    print(ans)
    
if __name__ == '__main__':
    main()
def d():
    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        ai, bi, ci = map(int, input().split())
        edges[ai].append((bi, ci))
        edges[bi].append((ai, ci))
    Q, K = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    weighted_nodes = [0]*(N+1)
    def add_weight(k):
        for v in edges[k]:
            d, w = v
            if (weighted_nodes[d] != 0) or (d == K):
                continue
            weighted_nodes[d] = w + weighted_nodes[k]
            add_weight(d)
    add_weight(K)

    for q in queries:
        s, e = q
        print(weighted_nodes[s] + weighted_nodes[e])

d()

### FIXED CODE ###

from collections import deque

N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    ai, bi, ci = map(int, input().split())
    edges[ai].append((bi, ci))
    edges[bi].append((ai, ci))
Q, K = map(int, input().split())

distance = [-1]*(N+1)
# def add_weight(k, pre):
#     for v in edges[k]:
#         d, w = v
#         if d != pre:
#             distance[d] = w + distance[k]
#             add_weight(d, k)
# add_weight(K, -1)
que = deque()
que.append(K); distance[K] = 0
while len(que):
    a = que.popleft()
    for b, c in edges[a]:
        if distance[b] == -1:
            distance[b] = c + distance[a]
            que.append(b)

# print(distance)

for _ in range(Q):
    s, e = map(int, input().split())
    print(distance[s] + distance[e])
n = int(input())
e = [[] for _ in range(n)]
for j in range(n - 1):
    a, b = [int(i)-1 for i in input().split()]
    e[a].append((b, j))
    e[b].append((a, j))

co = [0]*(n-1)
def dfs(i=0, r=-1, dis=-1):
    global co
    c = 1
    for j in e[i]:
        if j[0] == r:
            continue
        if c == dis:
            c += 1
        co[j[1]] = c
        dfs(j[0], i, c)
        c += 1

dfs()

print(max(co))
for i in co:
    print(i)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n = int(input())
ab = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = [int(i)-1 for i in input().split()]
    ab[a].append([b, i])
    ab[b].append([a, i])
re = [False] * n
ed = [0]*(n-1)


def c(i=0, used=-1):
    global re, ed
    if re[i]:
        return 0
    re[i] = True
    k = 1
    for j in ab[i]:
        if re[j[0]]:
            continue
        if k == used:
            k += 1
        ed[j[1]] = k
        c(j[0], k)
        k += 1


c()
print(max(ed))
print(" ".join([str(i) for i in ed]))
s=input()
count=0
count_1=0
for i in range((len(s)-1)//2):
    if s[i]==s[-(i+1)]:
        count+=1
for j in range(len(s[:(len(s)+1)//2])//2):
    if s[:(len(s)+1)//2][j]==s[:(len(s)+1)//2][-(j+1)]:
    count_1+=1
if count==(len(s)-1)//2 and count_1==len(s[:(len(s)+1)//2])//2:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s=input()
a=s[:len(s)//2+1//2]
b=s[len(s)//2+1:]
if s==s[::-1] and a==a[::-1] and b==b[::-1]:
    print("Yes")
else:
    print("No")
S=input()
T=input()
SL=list(S)
N=len(S)
M=len(T)

for i in range(N-M+1):
    cond=True
    temp=S[N-M-i:N-i]
    for s in range(M):
        if temp[s]!="?" and temp[s]!=T[s]:
            cond=False
    if cond:
        SL[N-M-i:N-i]=list(T)
        break
if not cond:
    print("UNRESTORABLE")
else:
    for j in range(N):
        if SL[j]=="?":
            SL[j]="a"

    for a in SL:
        print(a,end="")

### FIXED CODE ###

S=input()
T=input()
SL=list(S)
N=len(S)
M=len(T)

if len(S)<len(T):
    print("UNRESTORABLE")
    
else:
    for i in range(N-M+1):
        cond=True
        temp=S[N-M-i:N-i]
        for s in range(M):
            if temp[s]!="?" and temp[s]!=T[s]:
                cond=False
        if cond:
            SL[N-M-i:N-i]=list(T)
            break
    if not cond:
        print("UNRESTORABLE")
    else:
        for j in range(N):
            if SL[j]=="?":
                SL[j]="a"
    
        for a in SL:
            print(a,end="")
operand = []
for x in raw_input().split():
  if  x.isdigit():
    operand.append(int(x))
  else:
    a1 = operand[len(operand)-1]
    operand.pop()
    a2 = operand[len(operand)-1]
    operand.pop()
      if  x == '+' :
        operand.append(a2 + a1)
      elif  x == '-':
        operand.append(a2 - a1)
      elif  x == '*':
        operand.append(a2 * a1)


print operand[0]
  

### FIXED CODE ###

operand = []
for x in raw_input().split():
  if x.isdigit():
    operand.append(int(x))
  else:
    a1 = operand.pop()
    a2 = operand.pop()
    if  x == '+' :
      operand.append(a2 + a1)
    elif  x == '-':
      operand.append(a2 - a1)
    elif  x == '*':
      operand.append(a2 * a1)

print operand.pop()
m_Coin500 = int(input())
num_Coin100 = int(input())
num_Coin50 = int(input())
total = int(input())

count = 0

for i_Coin500 in range(num_Coin500 + 1):
    for i_Coin100 in range(num_Coin100 + 1):
        for i_Coin50 in range(num_Coin50 + 1):
            sum = 500*i_Coin500 + 100*i_Coin100 + 50*i_Coin50
            if total == sum:
                count += 1

print(count)

### FIXED CODE ###

num_Coin500 = int(input())
num_Coin100 = int(input())
num_Coin50 = int(input())
total = int(input())

count = 0

for i_Coin500 in range(num_Coin500 + 1):
    for i_Coin100 in range(num_Coin100 + 1):
        for i_Coin50 in range(num_Coin50 + 1):
            sum = 500*i_Coin500 + 100*i_Coin100 + 50*i_Coin50
            if total == sum:
                count += 1

print(count)
import bisect
n = int(input())
a = sorted(list(map(int, input().split())))
l, r = 0, 0
l = max(a)
a.remove(l)
j = bisect.bisect_left(a, l/2)
if abs((l/2) - a[j-1]) < abs((l/2) - a[j]):
    j -= 1
print(l, a[min(j, len(a)-1)])

### FIXED CODE ###

import bisect
n = int(input())
a = sorted(list(map(int, input().split())))
l, r = 0, 0
l = max(a)
a.remove(l)
j = bisect.bisect_left(a, l/2)
try:
    if abs((l/2) - a[j-1]) < abs((l/2) - a[j]):
        j -= 1
except:
    pass
print(l, a[min(j, len(a)-1)])
import math
import sys

n = int(input())

l = []
if n == 2:
    print(1)
    sys.exit()
else:
    for i in range(2, int(math.sqrt(n) + 1)):
        if n % i == 0:
            for i in range(1, int(math.sqrt(n)) + 1):
                if n % i == 0:
                    j = n // i
                    l.append(i + j)
            print(min(l) - 2)
            sys.exit()
print(n -1)

### FIXED CODE ###

a, b = map(int, input().split())
 
n = -1
if (a < 10) and (b < 10):
  n = a * b
else:
  pass
print(n)
#include <iostream>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	int a = 0;
	int b = n;
	for (int i = 0; i < m; i++){
		int l, r;
		cin >> l >> r;
		a = max(a, l);
		b = min(b, r);
	}

	cout << (a <= b ? b-a+1 : 0) << endl;
}


### FIXED CODE ###

n, m = map(int, input().split())
a, b = 0, n;
for i in range(m):
	l, r = map(int, input().split())
	a, b = max(a, l), min(b, r)

print(b-a+1 if a <= b else 0)
S=int(input())

if S<10**18:
    X1,Y1=0,0

    mod=10**9

    X2=mod
    Y3=S//mod + 1

    Y2=1
    X3=mod-S%mod
else:
    X1,Y1,X2,Y3=0,0,0,0
    Y2=10**9
    Y3=10**9

print(X1,Y1,X2,Y2,X3,Y3)


### FIXED CODE ###

S=int(input())

if S<10**18:
    X1,Y1=0,0

    mod=10**9

    X2=mod
    Y3=S//mod + 1

    Y2=1
    X3=mod-S%mod
else:
    X1,Y1,X2,Y3=0,0,0,0
    Y2=10**9
    X3=10**9

print(X1,Y1,X2,Y2,X3,Y3)
#coding : utf-8　

import os
import sys

N, K = map(lambda x: int(x), input().split(" "))
S = input()

S = S[0:K] + S[K].lower() + S[K+1:len(S)]

print(S)




### FIXED CODE ###

#coding : utf-8　

import os
import sys

N, K = map(lambda x: int(x), input().split(" "))
S = input()

S = S[0:K-1] + S[K-1].lower() + S[K:len(S)]

print(S)
4 3
CABA

### FIXED CODE ###

a,b=map(int,input().split())
b=b-1
s=input()
print(s[0:b].upper()+s[b].lower()+s[b+1:].upper())
animals= input()
legs= input()

for i in range (len(animals)):

    if int(legs) % 2 ==0: #to check if it's even then there is a possibility of combination
        print ("yes")
    elif int(legs) % 4 ==0:
        print ("yes")
    elif int(legs) % 2 !=0:
        print ("no")
    elif int(legs) % 4 !=0:
        print ("no")

### FIXED CODE ###

#getting input from user
#cranes and turtle already give the information
#condition yes or no 
X,Y= map(int,input().split())
cranes= 2 # assign 2 to cranes
turtles= 4 # assign 4 to turtle
ans="No"
for i in range(X+1): 
    b=X-i
    if cranes*i + turtles*b == Y:
        ans = "Yes"
print(ans)

# Time complixity O(X)
n = int(input())
a = list(map(int, input().split()))
count = 0
for el in a:
    count += a.count(el)-1
count //= 2
for el in a:
    print(count - a.count(el)+1)

### FIXED CODE ###

n, m = map(int, input().split())
result = (n+m)*(n+m-1)//2 - n*m
print(result)
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

C_B = []
for _ in range(M):
    B, C = map(int, input().split())
    C_B.append([C, B])
C_B.sort(reverse = True)

sums = 0
now = 0
for j in range(M):
    #temp = A[now:now+C_B[j][1]]
    #print(temp)
    X=min(now+C_B[j][1], N-1)
    if C_B[j][0]>=A[X]: #すべて置き換え
        sums += C_B[j][0]*C_B[j][1]
        now += C_B[j][1]
        if now>=N:
            break
    elif C_B[j][0]<=A[now]: #置き換えない
        break
    else:
        sm = now
        la = now+C_B[j][1]-1
        md = now+C_B[j][1]//2
        p = C_B[j][0]
        while la-sm>1:
            
            if A[md]<p:
                sm=md
                md=(la-sm)//2
            elif A[md]==p:
                la=md
            else:
                la=md-1
                md=(la-sm)//2
        sums += (la-now)*p
        now = la
        break
#print(sums, now)
#残りを加算
if now<=N:
    for i in range(now, N):
        sums += A[i]
print(sums)

### FIXED CODE ###

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

CB = []
for i in range(M):
    b, c = map(int, input().split())
    CB.append([c, b])
CB.sort(reverse=True)
CBCB = [CB[0]]
for i in range(1, M):
    if CB[i][0]==CB[i-1][0]:
        CBCB[-1][1]+= CB[i][1]
    else:
        CBCB.append(CB[i])

ind = 0
ans=0
for l in CBCB:
    if A[ind]>l[0]: # 打ち切り
        break
    elif A[min(ind+l[1]-1, N-1)]<l[0]: #すべて置き換え
        if ind+l[1]>N-1:
            ans+=l[0]*(N-ind)
            ind = N
            break
        else:
            ans+=l[0]*l[1]
            ind+=l[1]
    else:
        sm = ind-1
        la = min(ind + l[1] -1 , N-1)
        while sm+1<la:
            md = (sm+la)//2
            if A[md]>=l[0]:
                la = md
            else:
                sm = md
        ans += l[0]*(sm-ind+1)
        ind = sm+1
        break
        
for i in range(ind, N):
    ans+=A[i]
print(ans)
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


N = I()
s = S()

inf = 10**9+7

from math import factorial
def c(n, r):
    a = factorial(n) / factorial(r) / factorial(n - r)
    return a

result = 0
counts = collections.Counter(s)
red = [i for i in counts.values() if i != 1]
tmp = 1
for i in red:
    tmp *= i
#  print('tmp', tmp)
for i in range(1, len(s)+1):
    #  print(i)
    #  import pdb
    #  pdb.set_trace()
    #  combis = list(itertools.combinations(counts, i))
    #  print('combis' ,combis)
    result += c(len(s), i)
    #  for combi in combis:
    #      #  print('combi', combi)
    #      tmp = 1
    #      for c in combi:
    #          #  print('c', c)
    #          tmp *= counts[c]
    #      #  print('tmp', tmp)
    #      result += tmp
for i in range(1, tmp):
    result -= c(tmp, i)
print(int(result)%inf)


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


N = I()
s = S()

inf = 10**9+7

counts = collections.Counter(s)
result = 1
for i in counts.values():
    result *= i+1
result -= 1
print(result%inf)
exit()
if x == 0:
    print(1)
else:
    print(0)

### FIXED CODE ###

x = int(input())

if x == 1:
    print(0)
else:
    print(1)
n, m = map(int, input().split())
if n == 1 or m == 1:
    print(1)
else:
    r = (n * m) // 2
    if (n * m) % 2 == 0:
        print(r)
    else:
        print(r+1)


### FIXED CODE ###

t = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(t[int(input()) - 1])
import sys
n = int(input())
A=[int(e)for e in sys.stdin]
cnt = 0
G = [797161,265720,88573,29524,9841,3280,1093,364,121,40,13,4,1]
G = [v for v in G if v <= n]
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
for g in G:
    insertionSort(A, n, g)
print(len(G))
print(*G)
print(cnt)
print("\n".join(A))


### FIXED CODE ###

import sys
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
def solve():
    n = int(input())
    A = list(map(int, sys.stdin))
    G = [int((2.25**i - 1) / 1.25)for i in range(17, 0, -1)]
    G = [v for v in G if v <= n]
    for g in G:
        insertionSort(A, n, g)
    print(len(G))
    print(*G)
    print(cnt)
    print('\n'.join(map(str, A)))
if __name__ == '__main__':
    cnt = 0
    solve()
import sys
import math
n = map(int,input().split())
T,A = 1,1
for i in range(n):
    t,a = map(int,input().split())
    coef = max((T+t-1)//t,(A+a-1)//a)
    T,A = coef * t, coef * a 
print(T+A)     

    


### FIXED CODE ###

import sys
import math
n = int(input())
T,A = 1,1
for i in range(n):
    t,a = map(int,input().split(" "))
    coef = max((T+t-1)//t,(A+a-1)//a)
    T,A = coef * t, coef * a 
print(T+A)
list1 = [int(e) for e in input().split()]
sum = 0
for num in list1:
    sum += num

if sum >= 22:
    print 'bust'
else:
    print 'win'

### FIXED CODE ###

list1 = [int(e) for e in input().split()]
sum = 0
for num in list1:
    sum += num

if sum >= 22:
    print ('bust')
else:
    print ('win')
# 052

# 1.値を正しく取得
A = int(input())
B = int(input())
C = int(input())
D = int(input())

# 2.正しく処理

menseki1 = A * B
print(menseki1)
menseki2 = C * D
print(menseki2)

if menseki1 > menseki2:
    print(menseki1)

elif menseki1 < menseki2:
    print(menseki2)

else :
    print(menseki1)

### FIXED CODE ###

# 052

# 1.値を正しく取得
a,b,c,d=(int(x) for x in input().split())

# 2.正しく処理

menseki1 = a * b
menseki2 = c * d

if menseki1 > menseki2:
    print(menseki1)

elif menseki1 < menseki2:
    print(menseki2)

else :
    print(menseki1)
n=int(input());e=[[]for _ in[0]*-~n];q=[(1,0)];f=[-1]*n
while n>1:v,w,c=map(int,input().split());e[v]+=(w,c),;e[w]+=(v,c),;n-=1
while q:
 v,c=q.pop();f[v-1]=c%2
 for w,d in e[v]:q+=(w,c+d),*(f[w-1]<0)
print(*f)

### FIXED CODE ###

from collections import*
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for v,w,c in zip(t[::3],t[1::3],t[2::3]):
  e[v-1].append((w-1,c))
  e[w-1].append((v-1,c))
q=deque([(0,0)])
f=[0]+[-1]*~-n
while q:
  v,c=q.pop()
  for w,d in e[v]:
    if-1<f[w]:continue
    d=(c+d)%2
    f[w]=d
    q.append((w,d))
print(*f)
n, q = map(int, input().split())
s = input()
cnt = 0
for i in range(n):
    if s[i] == 'A' and s[i + 1] == 'C':
        cnt += 1

data = [0] * cnt
j = 0
ans = [0] * q
for i in range(n - 1):
    if s[i] == 'A' and s[i + 1] == 'C':
        data[j] = i + 1
        j += 1
        
for i in range(q):
    l, r = map(int, input().split())
    cnt = 0
    for j in range(len(data)):
        if data[j] <= r - 1 and data[j] >= l:
            cnt += 1
        elif data[j] >= r:
            break
    ans[i] = cnt

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

### FIXED CODE ###


n, q = map(int, input().split())
s = input()
cnt = 0
data = [0] * (n + 1)
ans = [0] * q
for i in range(n - 1):
    if s[i] == 'A' and s[i + 1] == 'C':
        cnt += 1
    data[i + 1] = cnt

data[n - 1] = cnt

for i in range(q):
    l, r = map(int, input().split())

    ans[i] = data[r - 1] - data[l - 1]

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