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

from itertools import combinations_with_replacement

n = int(input())

for i in range(1, n+1):
    ans = 0
    for v in combinations_with_replacement(range(1, 40), 3):        
        x, y, z = v

        if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
            if x == y == z:
                ans = 1
            else:
                ans = 3
            break

    print(ans)

### FIXED CODE ###

n = int(input())
ans = [0] * (n+1)

for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            s = x*x + y*y + z*z
            s += x*y + y*z + z*x
            if (s > n):
                continue
            else:
                ans[s] += 1

for i in range(1, n+1):
    print(ans[i])
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for i in range(int(N/R) + 1):
    for j in range(int(N/G) + 1):
        tmp = int((R * i) + (G * j))
        if N >= tmp and (N - tmp) % B == 0:
            ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for i in range(int(N/R) + 1):
    for j in range(int(N/G) + 1):
        tmp = int((R * i) + (G * j))
        if N >= tmp and (N - tmp) % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

MOD = 10**9 + 7
MAX = 7 * 10**5
fact = [1] * (MAX + 1)
finv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    finv[i] = pow(fact[i], MOD - 2, MOD)


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


x, y = map(int, input().split())
a = 2 * y - x
b = 2 * x - y

if a < 0 or b < 0:
    ans = 0
elif a % 3 != 0 or b % 3 != 0:
    ans = 0
else:
    a //= 3
    b //= 3
    print(a, b)
    ans = comb(a + b, a)

print(ans)


### FIXED CODE ###

MOD = 10**9 + 7


def comb(n, k):
    if k > n - k:
        k = n - k
    ans = 1
    for i in range(1, k + 1):
        ans *= n + 1 - i
        ans *= pow(i, MOD - 2, MOD)
        ans %= MOD
    return ans


x, y = map(int, input().split())
a = 2 * y - x
b = 2 * x - y

if a < 0 or b < 0:
    ans = 0
elif a % 3 != 0 or b % 3 != 0:
    ans = 0
else:
    a //= 3
    b //= 3
    # print(a, b)
    ans = comb(a + b, a)

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

n,w = map(int, input().split())
wv = []
for _ in range(n):
    data = list(map(int,input().split()))
    wv.append(data)
 
dct={}
 
def solve(i,j):
    if i>=n:
        return 0
 
    ky = str(i)+"_"+str(j)
    if ky in dct:
        return dct[ky]
 
 
    weight=wv[i][0]
    value =wv[i][1]
 
    if j<weight: # can't push this item
        val = solve(i+1,j)
    else:# push or not push
        val =  max(solve(i+1,j-weight)+value, solve(i+1,j))
 
    dct[ky] = val
 
    return val
 
print(solve(0,w))

### FIXED CODE ###

n,w = map(int, input().split())
wv = []
for _ in range(n):
    data = list(map(int,input().split()))
    wv.append(data)

dp = [[0 for i in range(w+1)] for j in range(n+1)]

for item in range(n):
    now_w=wv[item][0]
    now_v=wv[item][1]

    for weight in range(w+1):
        ans1=dp[item][weight]
        ans2=-1
        if weight - now_w >= 0:
            ans2=dp[item][weight-now_w]+now_v
        dp[item+1][weight] = max(ans1,ans2)

print(dp[n][w])
### BUGGY CODE ###

N, M = map(int, input().split())
list_num = list(map(int, input().split()))
# list_num_ar = np.array(list_num)
# print(list_num)
for i in range(M):
	a, b = map(int, input().split())
	res = [b]*a
	# print(res)
	list_num = list_num + res

list_num_ar = sorted(list_num, reverse=True) 
# print(list_num_ar[0:N])
print(sum(list_num_ar[0:N]))

### FIXED CODE ###

from sys import stdin
 
def main():
    n,m = [int(x) for x in stdin.readline().split()]
    cards = [int(x) for x in stdin.readline().split()]
    cards.sort()
 
    bcs = [tuple(map(int,x.split())) for x in stdin.readlines()]
    bcs.sort(key=lambda x:x[1], reverse=True)
 
    ans = 0
    minIndex = 0
    isFinished = False
 
    for b,c in bcs:
 
        for _ in range(b):
            if minIndex < n and cards[minIndex] < c:
                ans += c
                minIndex += 1
            else:
                isFinished = True
                break
        
        if isFinished:
            break
 
    if minIndex < n:
        ans += sum(cards[minIndex:])
 
    print(ans)
    
if __name__=='__main__':
    main()
### BUGGY CODE ###

s = list(str(input()))
a = [0]
b = [0]*2019
b[0] += 1
for num,i in enumerate(reversed(s)):
  a.append(a[num]+int(i)*10**num)
  b[(a[num+1])%2019] += 1
ans = 0
for i in b:
  ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

s = input()
MOD = 2019
a =[0]*MOD
a[0] = 1
c_ = 0
ans = 0
t = 1
for i in reversed(s):
  c = (c_+int(i)*t)%MOD
  a[c] += 1
  t *= 10
  t %= MOD
  c_ = c
for i in a:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

from hashlib import md5

th, tw = map(int, input().split())
t = [input().strip() for _ in range(th)]
ph, pw = map(int, input().split())

t = [[md5(t[i][j:j + pw].encode('utf-8')).digest() for j in range(tw - pw + 1)] for i in range(th)]
p = [md5(input().strip().encode('utf-8')).digest() for _ in range(ph)]

for i in range(th - ph + 1):
    for j in range(tw - pw + 1):
        for k in range(ph):
            if t[i + k][j] != p[k]:
                break
        else:
            print(i, j)

### FIXED CODE ###

base1 = 127
base2 = 1009
mask = (1 << 32) - 1


def calc_hash(f, r, c):
    global ph, pw, h
    tmp = [[0] * c for _ in range(r)]
    dr, dc = r - ph, c - pw

    t1 = 1
    for _ in range(pw):
        t1 = (t1 * base1) & mask
    for i in range(r):
        e = 0
        for j in range(pw):
            e = e * base1 + f[i][j]
        for j in range(dc):
            tmp[i][j] = e
            e = (e * base1 - t1 * f[i][j] + f[i][j + pw]) & mask
        tmp[i][dc] = e

    t2 = 1
    for _ in range(ph):
        t2 = (t2 * base2) & mask
    for j in range(dc + 1):
        e = 0
        for i in range(ph):
            e = e * base2 + tmp[i][j]
        for i in range(dr):
            h[i][j] = e
            e = (e * base2 - t2 * tmp[i][j] + tmp[i + ph][j]) & mask
        h[dr][j] = e


th, tw = map(int, input().split())
t = [[ord(c) for c in input().strip()] for _ in range(th)]
ph, pw = map(int, input().split())
p = [[ord(c) for c in input().strip()] for _ in range(ph)]

if th >= ph and tw >= pw:
    h = [[0] * tw for _ in range(th)]
    calc_hash(p, ph, pw)
    key = h[0][0] & mask
    calc_hash(t, th, tw)
    for i in range(th - ph + 1):
        for j in range(tw - pw + 1):
            if h[i][j] & mask == key:
                print(i, j)
### BUGGY CODE ###

S = input()
Q = int(input())
QUERY = []
for i in range(Q):
    QUERY.append(input().split(' '))


def main(s, q, query):
    for i in range(q):
        if query[i][0] == '1':
            s = ''.join(reversed(list(s)))
        elif query[i][0] == '2':
            if query[i][1] == '1':
                s = query[i][2] + s
            elif query[i][1] == '2':
                s = s + query[i][2]

    return s


print(main(S, Q, QUERY))


### FIXED CODE ###

S = input()
Q = int(input())
QUERY = []
for i in range(Q):
    QUERY.append(input().split(' '))


def main(s, q, query):
    addflag = 'front'

    s_front = ''
    s_back = ''

    for i in range(q):
        if query[i][0] == '1':
            if addflag == 'front':
                addflag = 'back'
            elif addflag == 'back':
                addflag = 'front'
        elif query[i][0] == '2':
            if addflag == 'front' and query[i][1] == '1':
                s_front = query[i][2] + s_front
                # s = query[i][2] + s
            elif addflag == 'front' and query[i][1] == '2':
                s_back = s_back + query[i][2]
                # s = s + query[i][2]
            elif addflag == 'back' and query[i][1] == '1':
                s_back = s_back + query[i][2]
                # s = s + query[i][2]
            elif addflag == 'back' and query[i][1] == '2':
                s_front = query[i][2] + s_front
                # s = query[i][2] + s

    if addflag == 'back':
        s = ''.join(reversed(list(s)))
        s_tmp = ''.join(reversed(list(s_front)))
        s_front = ''.join(reversed(list(s_back)))
        s_back = s_tmp

    return s_front + s + s_back


print(main(S, Q, QUERY))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
ac_numbers = 0 
for i in range(Q):
    l, r = map(int, input().split())
    for j in range(r-l): 
        if S[l-1+j:l+j+1] == 'AC':
            ac_numbers += 1
    print(ac_numbers)
    ac_numbers = 0


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
L = [0]*Q 
R = [0]*Q
for q in range(Q):
    l, r = map(int, input().split())
    L[q] = l
    R[q] = r
ans = [0]*Q 
accumulative_count = [0]*(N) 
accumulative_count[0] = 0 
for i in range(1, N, 1): 
    accumulative_count[i] = accumulative_count[i-1]
    if (S[i-1:i] == 'A') & (S[i:i+1] == 'C'):
        accumulative_count[i] = accumulative_count[i-1] + 1
for q in range(Q):
    print(accumulative_count[R[q]-1] - accumulative_count[L[q]-1])
### BUGGY CODE ###

#-*-coding:utf8;-*-
#qpy:3
#qpy:console
n = int(input())
hp = list(map(int, input().split()))
while len(hp) != 1:
    minhp = min(hp)
    hp = [i % minhp if not i == minhp else i for i in hp]
    hp = [i for i in hp if not i == 0]
    if min(hp) == 1:
        minhp = min(hp)
        break
print(minhp)


### FIXED CODE ###

#-*-coding:utf8;-*-
#qpy:3
#qpy:console
n = int(input())
hp = list(map(int, input().split()))
while len(hp) != 1:
    minhp = min(hp)
    hp = [i % minhp if not i == minhp else i for i in hp]
    hp = [i for i in hp if not i == 0]
    if min(hp) == 1:
        minhp = min(hp)
        break
    elif hp == [minhp for i in hp]:
        break
print(minhp)
### BUGGY CODE ###

def main():
  s=int(input())
  #while s%10==0:
  #    s//=10
  #s=9**800000
  s=str(s)
  lens=len(s)

  d=int(s[0])
  p=11-int(s[0])

  for c in s[1:]:
      j=int(c)
      a=min(d+j,p+j)
      b=min(d+11-j,p+9-j)
      d,p=a,b

  print(min(d,p))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
  s=input()
  #while s%10==0:
  #    s//=10
  #s=9**100
  #s=str(s)
  lens=len(s)

  d=int(s[0])
  p=11-int(s[0])

  for c in s[1:]:
      j=int(c)
      a=min(d+j,p+j)
      b=min(d+11-j,p+9-j)
      d,p=a,b

  print(min(d,p))

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

import itertools
import sys

input = sys.stdin.readline

n, m, q = map(int, input().split())
ls = [[0] * n for _ in range(n)]
for _ in range(m):
    l, r = map(int, input().split())
    ls[l - 1][r - l] += 1
for i in range(n):
    ls[i] = list(itertools.accumulate(ls[i]))
for _ in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    res = 0
    for i in range(min(r - l + 1, n - l)):
        res += ls[l + i][r - l - i]
    print(res)

### FIXED CODE ###

import itertools
import sys

input = sys.stdin.readline

n, m, q = map(int, input().split())
ls = [[0] * n for _ in range(n)]
for _ in range(m):
    l, r = map(int, input().split())
    ls[l - 1][r - l] += 1
for i in range(n):
    ls[i] = list(itertools.accumulate(ls[i]))
for _ in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    res = 0
    for i in range(r - l + 1):
        res += ls[l + i][r - l - i]
    print(res)
### BUGGY CODE ###

import math

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

def pf(x):
  x2=x
  y=int(x/2)
  l=[1]
  sq_x=math.sqrt(x)
  if x%2==0:
    l.append(2)
    while x%2==0:
      x=x//2
  for i in range(3,y,2):
    if x%i==0:
      l.append(i)
    while x%i==0:
      x=x//i
    if x==1:
      break
  if x==x2:
    if x!=1:
      l.append(x)
  return(l)

count=0
if b>a:
  a,b=b,a

l=pf(b)
len=len(l)
for i in range(len):
  if  a%l[i]==0:
        count+=1
print(count)


### FIXED CODE ###

import math
from fractions import gcd

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

def pf(x):
  x2=x
  y = int(math.sqrt(x))+1
  l=[1]
  if x%2==0:
    l.append(2)
    while x%2==0:
      x=x//2
  for i in range(3,y,2):
    if x%i==0:
      l.append(i)
    while x%i==0:
      x=x//i
    if x==1:
      break
  if x>=y:
    if x!=1:
      l.append(x)
  return(l)

count=0
n=gcd(a,b)

l=pf(n)

len=len(l)
for i in range(len):
  if  a%l[i]==0:
        count+=1
print(count)
### BUGGY CODE ###

S = input()
Q = int(input())

for i in range(Q) :
    query = input()
    if query == "1" :
        S = "".join(list(reversed(S)))
    else :
        a, F, C = query.split()
        if F == "1" :
            S = C + S
        else :
            S = S + C

print(S)


### FIXED CODE ###

S = input()
Q = int(input())

rev = 0
head = ""
foot = ""
for i in range(Q) :
    query = input()
    if query == "1" :
        rev += 1
    else :
        a, F, C = query.split()
        if F == "1" and rev%2 == 0:
            head = C + head
        elif F == "1" and rev%2 == 1:
            foot = foot + C
        elif F == "2" and rev%2 == 0:
            foot = foot + C
        else :
            head = C + head

if rev%2 == 0 :
    print("".join(list(head + S + foot)))
else :
    print("".join(list(reversed(head + S + foot))))
### BUGGY CODE ###

s = input()
t = input()
schr = [0]*26
tchr = [0]*26
for i in range(len(s)):
    schr[ord(s[i])-97] = 1
for i in range(len(t)):
    tchr[ord(t[i])-97] = 1
for i in range(26):
    if tchr[i] and not schr[i]:
        print(-1)
        break
else:
    i = 0
    j = 0
    while True:
        if s[i%len(s)] == t[j]:
            if j==len(t)-1:
                break
            j += 1
        i += 1
    print(i+1)

### FIXED CODE ###

import bisect

s = input()
t = input()

ss = s+s

char = [[] for _ in range(26)]

for i in range(len(ss)):
    char[ord(ss[i])-97].append(i+1)

ans = 0
tmp = 0

for i in range(len(t)):
    if not char[ord(t[i])-97]:
        print(-1)
        break
    
    k = bisect.bisect_right(char[ord(t[i])-97],tmp)
    ans += char[ord(t[i])-97][k]-tmp
    tmp = char[ord(t[i])-97][k]
    if tmp-len(s)>0:
        tmp -= len(s)
    
else:
    print(ans)
### BUGGY CODE ###

from numpy import zeros

N, K, *A = map(int, open(0).read().split())

for _ in range(min(K, 41)):
    B = zeros(N, dtype=int)
    for x, d in enumerate(A):
        B[x - d if x > d else 0] += 1
        if (x := x + d + 1) < N:
            B[x] -= 1
    A = B.cumsum()

print(*A)

### FIXED CODE ###

from itertools import accumulate

N, K, *A = map(int, open(0).read().split())

for _ in range(min(K, 41)):
    B = [0] * (N + 1)
    for x, d in enumerate(A):
        B[max(0, x - d)] += 1
        B[min(N, x + d + 1)] -= 1
    A = list(accumulate(B))

print(*A[:-1])
### BUGGY CODE ###

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

INF = 10 ** 10

n = int(input())
# 貰うDPだと0へのアクセスが、配るDPだとn+1へのアクセスが必要になる
h = [INF] + list(map(int, input().split())) + [INF]
dp = [INF] + [INF] * n + [INF]
dp[1] = 0

def chmin(dp_table, index, value):
    if dp_table[index] > value:
        dp_table[index] = value

# 貰うDP(dp[i-1], dp[i-2]が計算済み)
#for i in range(2, n+1):
#    chmin(dp, i, dp[i-1] + abs(h[i] - h[i-1]))
#    chmin(dp, i, dp[i-2] + abs(h[i] - h[i-2]))

# 配るDB(dp[i]が計算済み)
#for i in range(1, (n-1)+1):
#    chmin(dp, i+1, dp[i] + abs(h[i] - h[i+1]))
#    chmin(dp, i+2, dp[i] + abs(h[i] - h[i+2]))
#
#print(dp[n])

# 再帰(DFS) (メモ化なし)
def dfs(i):
    if i == 0:
        return INF
    if i == 1:
        return 0

    ans = INF
    prev_cost = dfs(i-1)
    if ans > prev_cost + abs(h[i] - h[i-1]):
        ans = prev_cost + abs(h[i] - h[i-1])
    prev_cost = dfs(i-2)
    if ans > prev_cost + abs(h[i] - h[i-2]):
        ans = prev_cost + abs(h[i] - h[i-2])

    return ans

# 再帰(DFS) (メモ化ありfunctools.lru_cache使用)
import functools
dfs = functools.lru_cache(maxsize=None)(dfs)

print(dfs(n))  


### FIXED CODE ###

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

INF = 10 ** 10

n = int(input())
h = [0] + list(map(int, input().split()))
dp = [INF] + [INF] * n
dp[1] = 0

def chmin(dp_table, index, value):
    if dp_table[index] > value:
        dp_table[index] = value

for i in range(2, n+1):
    chmin(dp, i, dp[i-1] + abs(h[i] - h[i-1]))
    chmin(dp, i, dp[i-2] + abs(h[i] - h[i-2]))

print(dp[n])
### BUGGY CODE ###

import math
n,a,b = map(int,input().split())
if n == 2 :
    print(0)
else:
    ans = 2**n -1
    numa = 1
    for i in range(1,a+1):
        numa = numa *(n - i + 1) // i
    numb = numa
    for i in range(a+1,b+1):
        numb = numb * (n - i + 1) //i
    ans = ans -(numa+numb)
    print(ans%(10**9+7))

### FIXED CODE ###

#TRE
#pow(m,n)のnが大きい時は繰り返し2乗法を使う

#繰り返し2乗法のアルゴリズム
def modPow (a,n,p):
    if n==1:
        return a % p
    if n%2 == 1:
        return (a * modPow(a,n-1,p)) % p
    else:
        t = modPow(a,n/2,p)
        return t * t


#main
n,a,b = map(int,input().split())
p = 10**9+7
if n == 2 :
    print(0)
else:
#繰り返し2乗法により計算時間を短縮
    ans = modPow(2,n,p)-1#組み合わせのシグマは2のn乗
#組み合わせはn*...*(n-a+1)/(a*...*1)
    child_a = 1
    mother_a = 1
    for i in range(a):
        child_a = (child_a*(n-i))%p
        mother_a = (mother_a*(i+1))%p
    com_a = (child_a * modPow(mother_a,p-2,p)) % p
    child_b = 1
    mother_b = 1
    for i in range(b):
        child_b = (child_b*(n-i))%p
        mother_b = (mother_b*(i+1))%p
    com_b = (child_b * modPow(mother_b,p-2,p)) % p
    ans = (ans -(com_a+com_b))%p
    print(ans%p)
### BUGGY CODE ###

import io
import os

from collections import Counter, defaultdict, deque


def solve(N, K, A):
    window = deque()
    val = 1
    grades = []
    for x in A:
        window.append(x)
        val *= x

        if len(window) > K:
            val //= window.popleft()
        if len(window) == K:
            grades.append(val)
    ans = []
    for x, y in zip(grades, grades[1:]):
        if x < y:
            ans.append("Yes")
        else:
            ans.append("No")

    return "\n".join(ans)


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    ans = solve(N, K, A)
    print(ans)



### FIXED CODE ###

import io
import os

from collections import Counter, defaultdict, deque


def solve(N, K, A):
    window = deque()
    ans = []
    for x in A:
        window.append(x)

        if len(window) > K:
            if window.popleft() < x:
                ans.append("Yes")
            else:
                ans.append("No")
    return "\n".join(ans)


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    ans = solve(N, K, A)
    print(ans)
### BUGGY CODE ###

MOD = 998244353
n, s = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 1
for i, a in enumerate(A):
    for j in range(s+1):
        if j >= a:
            dp[i+1][j] = dp[i][j]*2 + dp[i][j-a]
        else:
            dp[i+1][j] = dp[i][j]*2
        dp[i+1][j] %= MOD
ans = dp[n][s]
print(ans)

### FIXED CODE ###

MOD = 998244353
n, s = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 1
for i, a in enumerate(A):
    for j in range(s+1):
        if j >= a:
            dp[i+1][j] = dp[i][j]*2 + dp[i][j-a]
        else:
            dp[i+1][j] = dp[i][j]*2
        dp[i+1][j] %= MOD
ans = dp[n][s]
print(ans)
### BUGGY CODE ###

n,m =map(int, input().split())  #複数数値入力
x=list(map(int, input().split()))  #リスト入力

x.sort()
x_d = list()

if n > m:
    print(0)
else:
    if m == 1:
        print(0)
    else:
        for i in range(m-1):
            x_d.append(x[i+1] - x[i])   

        for i in range(n-1):
            
            x_d.remove(max(x_d))
            

        sumd = sum(x_d)  
        print(sumd)


### FIXED CODE ###

import numpy as np
n,m =map(int, input().split())  #複数数値入力
x=list(map(int, input().split()))  #リスト入力

x.sort()
x_d = list()

if n > m:
    print(0)
else:
    if m == 1:
        print(0)
    else:
#         for i in range(m-1):
#             x_d.append(x[i+1] - x[i])   
        x_d = list(np.diff(x))

#         for i in range(n-1):
            
#             x_d.remove(max(x_d))
            
        x_d.sort(reverse=True)
#         sumd = sum(x_d)  
        sumd = sum(x_d[n-1:])
        print(sumd)
### BUGGY CODE ###

def main():
    s = input()
    q = int(input())

    hanten = 0 # 偶数なら正常、 奇数なら反転状態

    front = ""
    back = ""

    for _ in range(q):
        tmp = input()
        if len(tmp) == 1:
            hanten ^= 1
        else:
            if hanten: # 反対ver
                if tmp[2] == '1':
                    back += tmp[4]
                else:
                    front += tmp[4]
            else: # 正常
                if tmp[2] == '1':
                    front += tmp[4]
                else:
                    back += tmp[4]

    if hanten == 0:
        print(front[::-1] + s + back)
    else:
        print((front[::-1] + s + back)[::-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
    s = input()
    q = int(input())

    hanten = 0 # 偶数なら正常、 奇数なら反転状態

    front = "" # リストの前に追加するのは、O(n)なので避ける
    back = ""

    for _ in range(q):
        tmp = readline().split()
        if len(tmp) == 1:
            hanten ^= 1
        else:
            if hanten: # 反対ver
                if tmp[1] == '1':
                    back += tmp[2]
                else:
                    front += tmp[2]
            else: # 正常
                if tmp[1] == '1':
                    front += tmp[2]
                else:
                    back += tmp[2]

    if hanten == 0:
        print(front[::-1] + s + back)
    else:
        print((front[::-1] + s + back)[::-1])

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

def f(i):
    return (i + 1) / 2


n, k = [int(i) for i in input().split()]
p = [f(int(i)) for i in input().split()]
ans = sum(p[0:k])
for i in range(1, n - 2):
    ans = max(ans, sum(p[i : i + k]))
print(ans)


### FIXED CODE ###

def f(x):
    return (x + 1) / 2


n, k = [int(i) for i in input().split()]
p = [f(int(i)) for i in input().split()]
ans = sum(p[:k])
a = ans
for i in range(k, n):
    a = a + p[i] - p[i - k]
    ans = max(ans, a)
print(ans)
### BUGGY CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    n,*a=map(int,open(0).read().split())
#    print(a)
    while 1:
        flag=0
        for i in range(n-2):
            if a[i]>a[i+2]:
                a[i],a[i+2]=a[i+2],a[i]
                flag=1
        if not flag:
            break
#    print(a)
    ans=0
    while 1:
        flag=0
        for i in range(n-1):
            if a[i]>a[i+1]:
                a[i],a[i+1]=a[i+1],a[i]
                flag=1
                ans+=1
        if not flag:
            break
#    print(a)
    print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    n,*a=map(int,open(0).read().split())
    b=set(a[::2])
    c=set(sorted(a)[::2])
    print(len(b^c)//2)
if __name__ == '__main__':
    main()