Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, S):
        self.size = 19
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


N = int(input())
S = [ord(_) - 97 for _ in list(input())]
Q = int(input())
tree = SegmentTree(S)
for q in range(Q):
    t, i, c = input().split()
    if t == '1':
    i = int(i) - 1
    tree.update(i, ord(c) - 97)
    else:
        l, r = int(i) - 1, int(c)
        print(tree.query(l, r))

### FIXED CODE ###

import sys
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, S):
        self.size = 19
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


def main():
    N = int(input())
    S = [ord(_) - 97 for _ in list(input())]
    Q = int(input())
    tree = SegmentTree(S)
    for q in range(Q):
        t, i, c = input().split()
        if t == '1':
            i = int(i) - 1
            tree.update(i, ord(c) - 97)
        else:
            l, r = int(i) - 1, int(c)
            print(tree.query(l, r))


if __name__ == '__main__':
    main()
N, M = map(int, input().split())
a = [int(input())for i in range(M)]
MOD = 10 ** 9 + 7
ans = []
dp = [1] * N

dp[0] = 1 if 1 not in a else 0
dp[1] = (dp[0] + 1) if 2 not in a else 0
for i in range(2, N):
    if (i + 1) in a:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2])

print(dp[N-1] % MOD)


### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input())for i in range(M)]
MOD = 10 ** 9 + 7
ans = []
dp = [1] * (N + 1)

for i in a:
    dp[i] = 0

for i in range(2, N + 1):
    if dp[i] != 0:
        dp[i] = (dp[i - 1] + dp[i - 2])

print(dp[N] % MOD)
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class UnionFind:
    def __init__(self, n):
        self.state = [-1] * n
        self.size_table = [1<<i for i in range(n)]
        # cntはグループ数
        # self.cnt = n

    def root(self, u):
        v = self.state[u]
        if v < 0: return u
        self.state[u] = res = self.root(v)
        return res

    def merge(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru == rv: return
        du = self.state[ru]
        dv = self.state[rv]
        if du > dv: ru, rv = rv, ru
        if du == dv: self.state[ru] -= 1
        self.state[rv] = ru
        # self.cnt -= 1
        self.size_table[ru] |= self.size_table[rv]
        self.size_table[rv]=0
        return

    # グループの要素数
    def size(self, u):
        return self.size_table[self.root(u)]

def popcnt(a):
    res=0
    while a:
        res+=a&1
        a>>=1
    return res

def main():
    n,k,l=MI()
    road=UnionFind(n)
    train=UnionFind(n)
    for _ in range(k):
        u,v=MI1()
        road.merge(u,v)
    for _ in range(l):
        u,v=MI1()
        train.merge(u,v)
    ans=[popcnt(road.size(i)&train.size(i)) for i in range(n)]
    print(*ans)

main()


### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class UnionFind:
    def __init__(self, n):
        self.state = [-1] * n
        #self.size_table = [1<<i for i in range(n)]
        # cntはグループ数
        # self.cnt = n

    def root(self, u):
        v = self.state[u]
        if v < 0: return u
        self.state[u] = res = self.root(v)
        return res

    def merge(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru == rv: return
        du = self.state[ru]
        dv = self.state[rv]
        if du > dv: ru, rv = rv, ru
        if du == dv: self.state[ru] -= 1
        self.state[rv] = ru
        # self.cnt -= 1
        #self.size_table[ru] |= self.size_table[rv]
        #self.size_table[rv]=0
        return

def main():
    n,k,l=MI()
    road=UnionFind(n)
    train=UnionFind(n)
    for _ in range(k):
        u,v=MI1()
        road.merge(u,v)
    for _ in range(l):
        u,v=MI1()
        train.merge(u,v)
    cnt=defaultdict(int)
    for u in range(n):
        cnt[road.root(u),train.root(u)]+=1
    ans=[cnt[road.root(u),train.root(u)] for u in range(n)]
    print(*ans)

main()
import scala.io.StdIn.readInt
import scala.collection.mutable.ArrayBuffer

object Main {

  def factorize(p:Int,d:Int,l:List[Int]):List[Int] = {
    if(d >= Math.sqrt(p)+1) {
      if(p != 1) p::l else l
    } else {
      if(p%d == 0)
        factorize(p,d,d::l)
      else if(d==2)
        factorize(p,d+1,l)
      else
        factorize(p,d+2,l)
    }
  }

  def printList(l:List[Int]):Unit = l match {
    case List() => ()
    case h::tail =>
        print(" " + h)
        printList(tail)
  }

  def main(args: Array[String]) = {
    val n = readInt
    val list = factorize(n,2,List())
    print(n.toString + ":")
    printList(list)
    println()
  }
}

### FIXED CODE ###

import math

def factorize(p):
    l = []
    while p % 2 == 0:
        p //= 2
        l.append(2)

    r = 3
    while r < int(math.sqrt(p)+1):
        if p % r == 0:
            p //= r
            l.append(r)
        else:
            r += 2

    if p != 1:
        l.append(p)

    return l

n = int(input())
l = factorize(n)

print(str(n)+":",*l)
N,A=map(int,input().split())
if (N-1*A)%500==0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

N=int(input())
A=int(input())
if N%500<=A:
    print("Yes")
else:
    print("No")
n=[int(i) for i in input.split()]
print(n[0]+n[1]/2)

### FIXED CODE ###

n=[int(i) for i in input().split()]
print(int(n[0]+n[1]/2))
n, a, b, c, d = list(map(int, input().split()))
s = input()

flag = 0
if s[c-1] == "#" or s[d-1] == "#":
    flag = 1
elif s[a-1] == "#" or s[b-1] == "#":
    flag = 1
elif c == d:
    flag == 1
else:
    for i in range(n-1):
        if s[i] == s[i+1] == "#":
            flag = 1
            break

if flag == 1:
    print("No")
elif c > d:
    ans = 0
    if s[c-2] == "#" or s[c] == "#":
        print("No")
    else:
        for i in range(a-1,n-2):
            if s[i] == s[i+1] == s[i+2] ==".":
                ans = 1
                break
        if ans == 1:
            print("Yes")
        else:
            print("No")
else:
    print("Yes")


### FIXED CODE ###

n, a, b, c, d = list(map(int, input().split()))
s = input()

jump = 0
if c < d:
    for i in range(a, d-1):
        if s[i-1] == s[i] == "#":
            print("No")
            break
    else:
        print("Yes")            
else:
    for i in range(a, c-1):
        if s[i-1] == s[i] == "#":
            print("No")
            break
    else:
        for i in range(b-1, d):
            if s[i-1] == s[i+1] == s[i] ==".":
                print("Yes")
                break
        else:
            print("No")
N = int(input())
tree = [[] for i in range(N)]
color = [-1] * N
for i in range(N-1):
  u, v, w = map(int, input().split())
  tree[u-1].append((v-1, w))
  tree[v-1].append((u-1, w))


def dfs(u):
  for v, w in tree[u]:
    if color[v] == -1:
      color[v] = color[u] ^ (w % 2)
      dfs(v)


color[0] = 0
dfs(0)
print('\n'.join(map(str, color)))





### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N = int(input())
tree = [[] for i in range(N)]
color = [-1] * N
for i in range(N-1):
  u, v, w = map(int, input().split())
  tree[u-1].append((v-1, w))
  tree[v-1].append((u-1, w))


def dfs(u):
  for v, w in tree[u]:
    if color[v] == -1:
      color[v] = color[u] ^ (w % 2)
      dfs(v)


color[0] = 0
dfs(0)
print('\n'.join(map(str, color)))
a, b = map(int, input().split())

c = b - a
y = 0
for i in range(c+1):
    y = y + i

print(y-b)


### FIXED CODE ###

N = int(input())

if (N<=999) :
    print('ABC')
else :
    print('ABD')
digit(num):
    sum = 0
    while(num > 0):
        sum += num % 10
        num = int(num / 10)
    return sum
 
 
for a in range(2,n):
    sum_A =sum_digit(a)
    sum_B =sum_digit(n-a)
    all=min(all,(sum_A + sum_B))

print(all)

### FIXED CODE ###

n = list(map(int, list(input())))
 
if n[0] == 1 and sum(n)  == 1:
    print(10)
else:
    print(sum(n))
import sys
input = sys.stdin.readline
class segtree:
    def __init__(self, nn):
        self.NN = nn
        self.XX = [0] * (2**(nn+1)-1)
    def getmax(self, i):
        j = 2**self.NN + i - 1
        ma = -1
        while j >= 0:
            ma = max(ma, self.XX[j])
            j = (j-1) // 2
        return -1 if ma <= 0 else INF - ma
    def updaterange(self, a, b, x):
        l = a + (1<<self.NN)
        r = b + (1<<self.NN)
        s = 0
        while l < r:
            if l%2:
                self.XX[l-1] = max(self.XX[l-1], x)
                l += 1
            if r%2:
                r -= 1
                self.XX[r-1] = max(self.XX[r-1], x)
            l >>= 1
            r >>= 1

N, Q = map(int, input().split())
st = segtree(18)
INF = 1<<50
for _ in range(N):
    s, t, x = map(int, input().split())
    st.updaterange(s-x, t-x, INF-x)
for _ in range(Q):
    print(st.getmax(int(input())))

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left as bl
class segtree:
    def __init__(self, nn):
        self.NN = nn
        self.XX = [0] * (2**(nn+1)-1)
    def getmax(self, i):
        j = 2**self.NN + i - 1
        ma = -1
        while j >= 0:
            ma = max(ma, self.XX[j])
            j = (j-1) // 2
        return -1 if ma <= 0 else INF - ma
    def updaterange(self, a, b, x):
        l = a + (1<<self.NN)
        r = b + (1<<self.NN)
        s = 0
        while l < r:
            if l%2:
                self.XX[l-1] = max(self.XX[l-1], x)
                l += 1
            if r%2:
                r -= 1
                self.XX[r-1] = max(self.XX[r-1], x)
            l >>= 1
            r >>= 1

N, Q = map(int, input().split())
st = segtree(18)
INF = 1<<50
X = []
D = []
for _ in range(N):
    s, t, x = map(int, input().split())
    X.append((s, t, x))
for _ in range(Q):
    D.append(int(input()))

for s, t, x in X:
    st.updaterange(bl(D, s-x), bl(D, t-x), INF-x)
for i in range(Q):
    print(st.getmax(i))
n,y=map(int,input().split())
y //=1000
for i in range(n+1):
    for j in range(n-i+1):
        if n -(i+j) < 0
            break
        if 9*i+4*j+n == y:
            print(i,j,n-(i+j))
            exit()
print('-1','-1','-1')

### FIXED CODE ###

n,y=map(int,input().split())
y //=1000
for i in range(n+1):
    for j in range(n-i+1):
        if n -(i+j) < 0:
            break
        if 9*i+4*j+n == y:
            print(i,j,n-(i+j))
            exit()
print('-1','-1','-1')
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <map>
#include <list>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <stack>
#pragma GCC optimize(3 , "Ofast" , "inline")
using namespace std ;
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair<int , int> PII ;
const int N = 1e5 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
ll in()
{
  ll x = 0 , f = 1 ;
  char ch = getchar() ;
  while(!isdigit(ch)) {if(ch == '-') f = -1 ; ch = getchar() ;}
  while(isdigit(ch)) x = x * 10 + ch - 48 , ch = getchar() ;
  return x * f ;
}
int main()
{
  ll a = in() , b = in() , n = in() ;
  ll l = 0 , r = n , ans = 0 ;
  while(l < r)
   {
     ll mid = l + r + 1 >> 1 ;
     if((a * mid) / b - a * (mid / b) >= ans) l = mid ;
     else r = mid - 1 ;
   }
  cout << (a * r) / b - a * (r / b) << endl ;
  return 0 ;
}
/*
*/


### FIXED CODE ###

a , b , n = map(int , input().split())
l = 0
r = n
ans = 0
while (l < r) :
    mid = (l + r + 1) // 2
    if  (a * mid) // b - a * (mid // b) >= ans :
         ans =  (a * mid) // b - a * (mid // b)
         l = mid
    else :
        r = mid - 1
print((a * r) // b - a * (r // b))
a = input()
print(a.count(1))

### FIXED CODE ###

print(input().count('1'))
s=input()

op_n=len(s) - 1

ans=0

for i in range(1 << len(s)):
  sign = [""] * op_n
  for j in range(op_n):
    if ((i>>j)==1):
      sign[j] = "+"
  formula = ""
  for k in range(op_n):
    formula += s[k] + sign[k]
  formula += s[op-n] 
  ans += eval(formula)
print(ans)  
    
      
       

### FIXED CODE ###

s = input()

op_n = len(s) - 1

ans = 0

for i in range(1 << op_n):
  sign = [""] * op_n
  for j in range(op_n):
    if ((i>>j)&1):
      sign[j] = "+"
  formula = ""
  for k in range(op_n):
    formula += s[k] + sign[k]
  formula += s[op_n] 
  ans += eval(formula)
print(ans)
# -*- coding: utf-8 -*-

n, q = map(int,input().split())
s = list(input())
l = [0] * q
r = [0] * q
for i in range(q):
    l[i],r[i] = map(int,input().split())

aclist = []

cnt = 0
for i in range(n+1):
    if s[i-1] == "A" and s[i] == "C":
        cnt += 1
        aclist.append(cnt)
    else:
        aclist.append(cnt)

for i in range(q):
    print(aclist[r[i]-1] - aclist[l[i]-1])


### FIXED CODE ###

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

n, q = map(int,input().split())
s = list(input())
l = [0] * q
r = [0] * q
for i in range(q):
    l[i],r[i] = map(int,input().split())

aclist = []

cnt = 0
for i in range(n):
    if s[i-1] == "A" and s[i] == "C":
        cnt += 1
        aclist.append(cnt)
    else:
        aclist.append(cnt)

for i in range(q):
    print(aclist[r[i]-1] - aclist[l[i]-1])
N = int(input())
ans_lis = [[0　for k in range(9)] for i in range(9)]
for i in range(1,N+1):
  t = str(i)
  mae = int(t[0])
  ushiro = int(t[-1])
  if ushiro == 0:
    continue
  ans_lis[mae-1][ushiro-1] += 1
ans = 0
for i in range(9):
  for j in range(9):
    ans += ans_lis[i][j] * ans_lis[j][i]
print(ans)


### FIXED CODE ###

N = int(input())
ans_lis = [[0] * 9 for i in range(9)]
for i in range(1,N+1):
  t = str(i)
  mae = int(t[0])
  ushiro = int(t[-1])
  if ushiro == 0:
    continue
  ans_lis[mae-1][ushiro-1] += 1
ans = 0
for i in range(9):
  for j in range(9):
    ans += ans_lis[i][j] * ans_lis[j][i]
print(ans)
x = input()
print(x**3)

### FIXED CODE ###

import sys

d = int(sys.stdin.readline().rstrip())
print(d**3)
r＝int(input())
print(r**2)

### FIXED CODE ###

r=int(input())
print(r**2)
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

if n == 1:
    print(a[0] + b[0])
    exit()

for i in range(1, n-1):
    candy = []
    candy.append(sum(a[:i]) + sum(b[i-1:]))

print(max(candy))


### FIXED CODE ###

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

ans = a[0] + sum(b)
c = ans

for i in range(n-1) :
    c = c - b[i] + a[i+1]
    ans = max(ans, c)

print(ans)
a,b=[int(i) for i in input().split()]
x=(a+b)/2
prnit(a%1+1)

### FIXED CODE ###

a,b=[int(i) for i in input().split()]
x=a+b+1
print(x//2)
N = input()
a = []
for i in range(N):
    a.append(input())
a= list(set(a))
a.sort()
print len(a)

### FIXED CODE ###

input_line1 = raw_input()
str_list = list(input_line1)
str_list[3]="8"
str_changed = "".join(str_list)
print(str_changed)
import copy
s=0
a=0
H,W,K=map(int,input().split())
L=[[0 for j in range(W)] for i in range(H)]
for i in range(H):
  c=list(input().split())
  L[i]=c
for i in range(2**(H+W)):
  c=bin(i)[2:]
  T=copy.deepcopy(L)
  for k in range(len(c)):
    if c[k] is None:
      print(c,k)
    if c[k]=="1" and k<H:
      T[k]=[0]*W
    if c[k]=="1" and k>=H:
      for n in range(H):
        T[n][k-H]=0
  for j in range(H*W):
    if j%W==0:
      if T[(j//W)-1][-1]=="#":
        a+=1
    else:
      if T[j//W][(j%W)-1]=="#":
        a+=1
  if a==K:
    s+=1
  a=0
print(s)

### FIXED CODE ###

import copy
s=0
a=0
H,W,K=map(int,input().split())
L=[[0 for j in range(W)] for i in range(H)]
for i in range(H):
  c=list(input())
  L[i]=c
for i in range(2**(H+W)):
  c=bin(i)[2:]
  c=str(c)
  if len(c)<H+W:
    c=str((H+W-len(c))*"0"+c)
  T=copy.deepcopy(L)
  for k in range(H+W):
    if c[k]=="1":
      if k<H:
        T[k]=[0]*W
    if c[k]=="1" and k>=H:
      for n in range(H):
        T[n][k-H]=0
  for j in range(1,(H*W)+1):
    if j%W==0:
      if T[(j//W)-1][-1]=="#":
        a+=1
    else:
      if T[j//W][(j%W)-1]=="#":
        a+=1
  if a==K:
    s+=1
  a=0
print(s)
H,W,M = list(map(int,input().split()))

h = [0] * H
w = [0] * W

hw = []

for _ in range(H):
    hw.append([0] * W)

for _ in range(M):
    a,b = list(map(int,input().split()))
    h[a - 1] += 1
    w[b - 1] += 1
    hw[a - 1][b - 1] += 1
    
hm = max(h)
wm = max(w)

hp = [i for i, v in enumerate(h) if v == hm]
wp = [i for i, v in enumerate(w) if v == wm]

for x in hp:
    for y in wp:
        if hw[x][y] == 0:
            print(hm + wm)
            exit()
else:
    print(hm + wm - 1)



### FIXED CODE ###

from collections import defaultdict

h, w, m = map(int, input().split())
HW = [list(map(int, input().split())) for _ in range(m)]
dicHW = defaultdict(set)

for h, w in HW:
  dicHW[h].add(w)

hd = defaultdict(int)
wd = defaultdict(int)

for i, j in HW:
  hd[i] += 1
  wd[j] += 1

hd = list(hd.items())
wd = list(wd.items())

hd.sort(key=lambda x: -x[1])
wd.sort(key=lambda x: -x[1])

kouhoh = []
kouhow = []

for i, j in hd:
  if j < hd[0][1]:
    break
  else:
    kouhoh.append(i)

for i, j in wd:
  if j < wd[0][1]:
    break
  else:
    kouhow.append(i)

for i in kouhoh:
  for j in kouhow:
    if j not in dicHW[i]:
      ans = hd[0][1] + wd[0][1]
      print(ans)
      exit()

ans = hd[0][1] + wd[0][1] - 1  
print(ans)
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[]
for i in range(n):
  ct=0
  score=0
  s=[]
  pos=i
  while ct<k:
    ct+=1
    pos=p[pos]-1
    score+=c[pos]
    s.append(score)
    if pos==i:
      break
  if s[-1]<0:
    ans.append(max(s))
  elif pos!=i:
    ans.append(max(s))
  else:
    ans.append(max(s[-1]*(k//len(s)-1)+max(s),s[-1]*(k//len(s))+max(s[0:k%len(s)])))
print(max(ans))

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[]
for i in range(n):
  ct=0
  score=0
  s=[]
  pos=i
  while ct<k:
    ct+=1
    pos=p[pos]-1
    score+=c[pos]
    s.append(score)
    if pos==i:
      break
  if s[-1]<0:
    ans.append(max(s))
  elif pos!=i:
    ans.append(max(s))
  elif k%len(s)==0:
    ans.append(s[-1]*(k//len(s)-1)+max(s))
  else:
    ans.append(max(s[-1]*(k//len(s)-1)+max(s),s[-1]*(k//len(s))+max(s[0:k%len(s)])))
print(max(ans))
def applpie(apples, pieces):
  x = apples//3
  y = apples + pieces
   return y//2

### FIXED CODE ###

arguments = input()
arguments_as_list = arguments.split(" ")
list_to_integer = list(map(int, arguments_as_list))
apples_pieces = list_to_integer[0]*3
pieces = list_to_integer[1]


print(int((apples_pieces + pieces)//2))
N,D = list(map(int,input().split()))
human = 1
hani = 2*D+1
while hani < N:
    hani = hani + (2*D+1)
    human +=1
    
print(human)


### FIXED CODE ###

r = int(input())

print(3*r*r)
S = input()
T = input()

cnt = 0

for i in range(3)

if S[i] == T[i]:
  cnt += 1
print(cnt)

### FIXED CODE ###

S = input()
T = input()

cnt = 0

for i in range(3):
  if S[i] == T[i]:
    cnt += 1
print(cnt)
s = str(input())
t = str(input())

if s == t[：-1]:
	print("Yes")
else:
  	print("No")

### FIXED CODE ###

s = str(input())
t = str(input())

if s == t[:-1]:
	print("Yes")
else:
  	print("No")
#bit全探索の亜種(4種全探索)
#itertools.product([0,1,2,3],repeat=N)

import itertools
N,A,B,C = map(int,input().split())
l = [int(input()) for i in range(0,N,1)]

ans = 10**10
for ABCD in itertools.product([0,1,2,3],repeat=N):
    tmp = [[] for i in range(4)]
    for i in range(0,N,1):
        tmp[ABCD[i]].append(l[i])
    score = 0
    owaowari = False
    for i in range(3):#Dはくっ付ける必要なし
        if len(tmp[i])==0:
            owaowari = True
            break
        score+=10*max(len(tmp[i])-1,0)
    if owaowari: continue
    score+=abs(A-sum(tmp[0]))
    score+=abs(B-sum(tmp[1]))
    score+=abs(C-sum(tmp[2]))
    ans = min(ans,score)
    if score == 120:

print(ans)


### FIXED CODE ###

#bit全探索の亜種(4種全探索)
#itertools.product([0,1,2,3],repeat=N)

import itertools
N,A,B,C = map(int,input().split())
l = [int(input()) for i in range(0,N,1)]

ans = 10**10
for ABCD in itertools.product([0,1,2,3],repeat=N):
    tmp = [[] for i in range(4)]
    for i in range(0,N,1):
        tmp[ABCD[i]].append(l[i])
    score = 0
    owaowari = False
    for i in range(3):#Dはくっ付ける必要なし
        if len(tmp[i])==0:
            owaowari = True
            break
        score+=10*max(len(tmp[i])-1,0)
    if owaowari: continue
    score+=abs(A-sum(tmp[0]))
    score+=abs(B-sum(tmp[1]))
    score+=abs(C-sum(tmp[2]))
    ans = min(ans,score)


print(ans)
def swap(A, i, j):
    tmp  = A[i]
    A[i] = A[j]
    A[j] = tmp

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 shellSort(A, n):
    global cnt
    cnt = 0
    m = 1
    G = [1]
    while 2 ** m < n:
        G.append(2 ** m)
        m += 1
    G.reverse()
    print(m)
    print(' '.join(map(str, G)))
    for i in range(m):
        insertionSort(A, n, G[i])

n = int(input())
A = []
for i in range(n):
    a = int(input())
    A.append(a)

shellSort(A, n)
print(cnt)
for a in A:
    print(a)



### FIXED CODE ###

from sys import stdin

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 shellSort(A, n):
    global cnt
    cnt = 0
    g = 1
    G = [g]
    while 3 * g + 1 < n:
        g = 3 * g + 1
        G.append(g)
    m = len(G)
    G.reverse()
    print(m)
    print(' '.join(map(str, G)))
    for i in range(m):
        insertionSort(A, n, G[i])

n =  int(stdin.readline())
A = [int(stdin.readline()) for i in range(n)]

shellSort(A, n)
print(cnt)
for a in A:
    print(a)