CodeEff/ECCO huggingface dataset:
# Original solution
# -*- coding: utf-8 -*-
x,y,z,k = list(map(int, input().split()))

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

v = []


d = [e1+e2 for e1 in a for e2 in b]
d.sort(reverse=True)
d = d[:k]

e = [e1+e2 for e1 in d for e2 in c]
e.sort(reverse=True)


for i in range(k):
    print((e[i]))



# Optimized solution
# -*- coding: utf-8 -*-
x,y,z,k = list(map(int, input().split()))

a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)


d = [e1+e2 for e1 in a for e2 in b]
d.sort(reverse=True)
d = d[:k]

e = [e1+e2 for e1 in d for e2 in c]
e.sort(reverse=True)


for i in range(k):
    print((e[i]))
# Original solution
from collections import*
from heapq import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
t=[-1]*n
def r(x):
 while t[x]>=0:x=t[x]
 return x
def u(x,y):
 x,y=r(x),r(y)
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
d=defaultdict(list)
for x,y in q:u(x,y)
i=0
for v in a:d[r(i)]+=v,;i+=1
if len(d)<2:exit(print(0))
c,b,k=0,[],(n-m-1)*2
for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1
print(k>len(b)and'Impossible'or c+sum(sorted(b)[:k]))


# Optimized solution
from collections import*
from heapq import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
t=[-1]*n
def r(x):
 while t[x]>=0:x=t[x]
 return x
def u(x,y):
 x,y=r(x),r(y)
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
d=defaultdict(list)
for x,y in q:u(x,y)
i=c=0;b=[];k=(n+~m)*2
for v in a:d[r(i)]+=v,;i+=1
if k<1:exit(print(0))
for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1
print(k>len(b)and'Impossible'or c+sum(sorted(b)[:k]))
# Original solution
import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
import heapq

def main():
    N,M = list(map(int,input().split()))
    a = list(map(int,input().split()))
    d = defaultdict(list)
        
    I = [i for i in range(N)]
    rank = [1 for _ in range(N)]
    def root(a):
        if I[a] == a:
            return a
        else:
            I[a] = root(I[a])
            return I[a]
            
    def unite(a,b):
        pa,pb = root(a),root(b)
        ra,rb = rank[a],rank[b]
        if ra > rb:
            I[pb] = pa
        else:
            I[pa] = pb
            if ra == rb:
                rank[pb] += 1
    
    for _ in range(M):
        x,y = list(map(int,input().split()))
        unite(x,y)
        parent = root(x)
    
    for i,num in enumerate(I):
        parent = root(num)
        heapq.heappush(d[parent],a[i])
        
    if M == N-1:
        print((0))
        exit()
    elif N < 2*(N-M-1):
        print("Impossible")
        exit()

    l = len(list(d.keys()))
    ans = 0
    rest = []
    for use in list(d.values()):
        ans += heapq.heappop(use)
        rest.extend(use)

    remain = 2*(N-M-1)-l
    rest.sort()
    ans += sum(rest[:remain])
    
    print(ans)
    
if __name__ == "__main__":
    main()


# Optimized solution
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)

from collections import defaultdict
N,M,*L = list(map(int, open(0).read().split()))
A = L[:N]
U = UnionFind(N)
for x,y in zip(*[iter(L[N:])]*2):
  U.unit(x,y)
ans = 0
rest = []
dic = defaultdict(list)
for i in range(N):
  dic[U.find(i)].append(A[i])
for k in list(dic.keys()):
  dic[k].sort()
  ans += dic[k][0]
  rest.extend(dic[k][1:])
if N-1==M:
  print((0))
  exit()
if N<2*(N-M-1):
  print('Impossible')
  exit()

rest.sort()
remain = 2*(N-M-1)-len(list(dic.keys()))
ans += sum(rest[:remain])
print(ans)
# Original solution
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
 
def read():
  return int(eval(input()))
 
def reads():
  return [int(x) for x in input().split()]

def main():
  N, M = reads()
  A = reads()

  d = Counter(A)
  uf = union_find(N)
  edges = [[] for _ in range(N)]
  for _ in range(M):
    x, y = reads()
    uf.unite(x, y)

  INF = 1 << 30
  mins = defaultdict(lambda: INF)
  for i in range(N):
    k = uf.root(i)
    mins[k] = min(mins[k], A[i])
  g = len(mins)

  if g == 1:
    print((0)); exit()
  if (g - 1) * 2 > N:
    print("Impossible"); exit()

  ans = 0
  for k, v in list(mins.items()):
    ans += v
    d[v] -= 1
  ans += sum(sorted(d.elements())[:g-2])
  print(ans)
  

class union_find:
  def __init__(self, n):
    self.par = [-1] * n
  def __repr__(self):
    return "union_find({0})".format(self.par)
  def unite(self, x, y):
    if self.root(x) != self.root(y):
      self.par[self.root(x)] = y
  def root(self, x):
    if self.par[x] == -1:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  def same(self, x, y):
    return self.root(x) == self.root(y)

main()

# Optimized solution
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
 
def read():
  return int(eval(input()))
 
def reads():
  return [int(x) for x in input().split()]

def main():
  N, M = reads()
  A = reads()
  if M == N-1:
    print((0)); exit()

  d = Counter(A)
  uf = union_find(N)
  edges = [[] for _ in range(N)]
  for _ in range(M):
    x, y = reads()
    uf.unite(x, y)

  INF = 1 << 30
  mins = defaultdict(lambda: INF)
  for i in range(N):
    k = uf.root(i)
    mins[k] = min(mins[k], A[i])
  g = len(mins)

  if (g - 1) * 2 > N:
    print("Impossible"); exit()

  ans = 0
  for k, v in list(mins.items()):
    ans += v
    d[v] -= 1
  ans += sum(sorted(d.elements())[:g-2])
  print(ans)

class union_find:
  def __init__(self, n): self.par = [-1] * n; self.rank = [0] * n
  def __repr__(self): return "union_find({0})".format([self.root(i) for i in range(n)])
  def unite(self, x, y):
    x = self.root(x); y = self.root(y)
    if x == y: return
    if self.rank[x] < self.rank[y]: self.par[x] = y
    else:
      self.par[y] = x
      if self.rank[x] == self.rank[y]: self.rank[x] += 1
  def root(self, x):
    if self.par[x] == -1: return x
    else: self.par[x] = self.root(self.par[x]); return self.par[x]
  def same(self, x, y): return self.root(x) == self.root(y)

main()
# Original solution
from collections import deque
from collections import defaultdict
import heapq

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

if M==N-1:
	print(0)
	quit()

nl=[ [] for i in range(N) ]

for i in range(M):
	x,y=list(map(int,input().split()))
	nl[x].append(y)
	nl[y].append(x)


d=[ None for i in range(N) ]
V=[ None for i in range(N) ]

group_cost=defaultdict(lambda: [])

def dfs(start):
	q = deque([]) 
	V[start]=start
	d[start]=0
	heapq.heappush(group_cost[start],cost[start])
	q.append(start)

	while len(q)!=0:
		v=q.pop()
		for i in nl[v]:
			if V[i] is None:
				V[i]=start
				q.append(i)
				heapq.heappush(group_cost[start],cost[i])

for i in range(N):
	if V[i] is None:
		dfs(i)


H = []

ans=0
for v in list(group_cost.values()):
	v=sorted(v)
	ans+=v[0]
	H.append(v[1:])

nokori_cost=list(heapq.merge(*H))


if N < 2*(N-M-1):
	print("Impossible")
elif M == N-1:
	print(0)
else:
	ans += sum(nokori_cost[:2*(N-M-1) - len(list(group_cost.keys()))])
	print(ans)





# Optimized solution
from collections import deque
from collections import defaultdict
import heapq

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

par=[i for i in range(N)]

def root(x):
	if par[x]==x:
		return x
	else:
		r=root(par[x])
		par[x]=r
		return r

def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y: return
	par[x]=y


for i in range(M):
	x,y=list(map(int,input().split()))
	unite(x,y)


group_cost=defaultdict(lambda: [])

for i in range(N):
	root(i)
	group_cost[par[i]].append(cost[i])


H = []

ans=0
for v in list(group_cost.values()):
	v=sorted(v)
	ans+=v[0]
	H.append(v[1:])

nokori_cost=list(heapq.merge(*H))


if N < 2*(N-M-1):
	print("Impossible")
elif M == N-1:
	print(0)
else:
	ans += sum(nokori_cost[:2*(N-M-1) - len(list(group_cost.keys()))])
	print(ans)
# Original solution
(n,m),a,*q=[map(int,t.split())for t in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(x):
 x,y=map(r,x)
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
[*map(u,q)]
i=c=0
k,*b=n+~m<<1,
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
print(k<1and'0'or(k>n)*'Impossible'or exec('for p in d:x,*y=sorted(p)+[0];c+=x;b+=y[:-1];k-=p>[]')or c+sum(sorted(b)[:k]))


# Optimized solution
(n,m,*b),a,*q=[list(map(int,t.split()))for t in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(x):
 x,y=list(map(r,x))
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
[*list(map(u,q))]
i=c=0
k=j=n+~m<<1
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
for p in d:x,*y=sorted(p)+[0];c+=x;b+=y[:-1];j-=p>[]
print((k<1and'0'or(k>n)*'Impossible'or c+sum(sorted(b)[:j])))
# Original solution
(n,m,*b),a,*q=[list(map(int,t.split()))for t in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(x):
 x,y=list(map(r,x))
 if x-y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
[*list(map(u,q))]
i=c=0
k=j=n+~m<<1
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
for p in d:x,*y=sorted(p)+[0];c+=x;b+=y[:-1];j-=p>[]
print(((c+sum(sorted(b)[:j]),'Impossible')[k>n]*(k>0)))

# Optimized solution
(n,m,*b),a,*q=[list(map(int,t.split()))for t in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(x):
 x,y=list(map(r,x))
 if x-y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
[*list(map(u,q))]
i=c=0
k=j=n+~m<<1
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
for p in d:
 if p:x,*y=sorted(p);c+=x;b+=y;j-=1
print(((c+sum(sorted(b)[:j]),'Impossible')[k>n]*(k>0)))
# Original solution
s=sorted
(n,m,*b),a,*q=[list(map(int,t.split()))for t in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(x):
 x,y=list(map(r,x))
 if x-y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
[*list(map(u,q))]
i=c=0
k=j=n+~m<<1
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
for p in d:
 if p:x,*y=s(p);c+=x;b+=y;j-=1
print(((c+sum(s(b)[:j]),'Impossible')[k>n]*(k>0)))

# Optimized solution
s=sorted
(n,m,*b),a,*q=[list(map(int,t.split()))for t in open(0)]
t=[-1]*n
r=lambda x:r(t[x])if-1<t[x]else x
def u(x):
 x,y=list(map(r,x))
 if x-y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
*list(map(u,q)),
i=c=0
k=j=n+~m<<1
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
for p in d:
 if p:x,*y=s(p);c+=x;b+=y;j-=1
print(((c+sum(s(b)[:j]),'Impossible')[k>n]*(k>0)))
# Original solution
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group(self):
        return [self.members(r) for r in self.roots()]
      
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

import sys
input = sys.stdin.readline
import heapq

n, m = list(map(int, input().split()))
if m == n-1:
  print((0))
  exit()
if n < 2*(n-m-1):
  print("Impossible")
  exit()
A = tuple(map(int, input().split()))
uf = UnionFind(n)
for _ in range(m):
  x, y = list(map(int, input().split()))
  uf.unite(x, y)
ans = 0
L = []
for l in uf.all_group():
  K = sorted((A[i] for i in l), reverse=True)
  ans += K.pop()
  for k in K:
    heapq.heappush(L, k)
for _ in range(n-m-2):
  ans += heapq.heappop(L)
print(ans)

# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
import heapq

n, m = list(map(int, input().split()))
if m == n-1:
  print((0))
  exit()
if n < 2*(n-m-1):
  print("Impossible")
  exit()
A = tuple(map(int, input().split()))
G = [[] for _ in range(n)]
for _ in range(m):
  x, y = list(map(int, input().split()))
  G[x].append(y)
  G[y].append(x)
ans = 0
L = []
seen = [False]*n
def dfs(v):
  global ans
  K = []
  stack = [v]
  while stack:
    v = stack.pop()
    heapq.heappush(K, A[v])
    seen[v] = True
    for nv in G[v]:
      if seen[nv]:
        continue
      stack.append(nv)
  ans += heapq.heappop(K)
  for k in K:
    heapq.heappush(L, k)
for i in range(n):
  if not seen[i]:
    dfs(i)
for _ in range(n-m-2):
  ans += heapq.heappop(L)
print(ans)
# Original solution
N,M = list(map(int,input().split()))
src = list(map(int,input().split()))
es = [tuple(map(int,input().split())) for i in range(M)]

if M == N-1:
    print((0))
    exit()
if M + N//2 < N-1:
    print('Impossible')
    exit()

parent = [i for i in range(N)]
rank = [0] * N
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    if rank[ra] < rank[rb]:
        parent[ra] = rb
    else:
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1

for a,b in es:
    unite(a,b)
trees = {}
for i in range(N):
    root(i)
for i in range(N):
    trees[root(i)] = False

costs = []
for i,c in enumerate(src):
    costs.append((c,i))
costs.sort()

used = [False] * N
ans = used_n = 0
for c,v in costs:
    t = root(v)
    if trees[t]:
        continue
    else:
        trees[t] = used[v] = True
        used_n += 1
        ans += c

for c,v in costs:
    if used_n == 2*(N-M-1): break
    if used[v]: continue
    used_n += 1
    ans += c
print(ans)


# Optimized solution
N,M = list(map(int,input().split()))
src = list(map(int,input().split()))
es = [tuple(map(int,input().split())) for i in range(M)]

if M == N-1:
    print((0))
    exit()
if M + N//2 < N-1:
    print('Impossible')
    exit()

parent = [i for i in range(N)]
rank = [0] * N
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    if rank[ra] < rank[rb]:
        parent[ra] = rb
    else:
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1

for a,b in es:
    unite(a,b)
trees = {}
for i in range(N):
    trees[root(i)] = False

costs = []
for i,c in enumerate(src):
    costs.append((c,i))
costs.sort()

used = [False] * N
ans = used_n = 0
for c,v in costs:
    t = root(v)
    if trees[t]:
        continue
    else:
        trees[t] = used[v] = True
        used_n += 1
        ans += c

for c,v in costs:
    if used_n == 2*(N-M-1): break
    if used[v]: continue
    used_n += 1
    ans += c
print(ans)
# Original solution
N = int(eval(input()))
print(((N + 1) // 2))
#sjdjsdajkjkafffjfjfjfjfjjfjf

# Optimized solution
n = int(eval(input()))
if n % 2 == 0:
    print((n//2))
else:
    print((n//2 + 1))
# Original solution
import math
n = int(eval(input()))
print((math.ceil(n/2)))

# Optimized solution
n = int(eval(input()))
print((int((n+1)/2)))
# Original solution
N = int(eval(input()))

print(((N+1)>>1))

# Optimized solution
print(((int(eval(input()))+1)//2))
# Original solution
import math
print((math.ceil(int(eval(input()))/2)))

# Optimized solution
print(((int(eval(input()))+1)//2))
# Original solution
n=int(eval(input()))
if n%2==1:
    print((n//2+1))
else:
    print((n//2))

# Optimized solution
n=int(eval(input()))

print(((n+1)//2))
# Original solution
from math import ceil
print((ceil(int(eval(input()))/2)))

# Optimized solution
print((-~int(eval(input()))//2))
# Original solution
import math
N=int(eval(input()))
print((math.ceil(N/2)))

# Optimized solution
print(((int(eval(input()))+1)//2))
# Original solution
import math
print((math.ceil(int(eval(input()))/2)))

# Optimized solution
print(((-int(eval(input()))//2)*-1))
# Original solution
import math
N=int(eval(input()))
print((math.ceil(N/2)))

# Optimized solution
N=int(eval(input()))
print((N//2+N%2))
# Original solution
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
answer = (N+1) // 2
print(answer)


# Optimized solution
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
answer = (N+1) // 2
print(answer)
# Original solution
S = int(eval(input()))
A = 0
if S % 2 == 1:
    A = S // 2 + 1
else:
    A = S // 2
print(A)

# Optimized solution
N = int(eval(input()))  #数字
print((N // 2 if N % 2 == 0 else N // 2 + 1))
# Original solution
import itertools
import math
import fractions
import functools
n = int(eval(input()))
if n % 2 == 1:
    print((n//2+1))
else: print((n//2))

# Optimized solution
n = int(eval(input()))
print(((n+1)//2))
# Original solution
N = int(eval(input()))
if N%2==0:
    print((N//2))
else:
    print((N//2 + 1))

# Optimized solution
N = int(eval(input()))
print(((N+1)//2))
# Original solution
a = int(eval(input()))
if a%2 == 0:
    print((a//2))
else:
    print((a//2+1))

# Optimized solution
n = int(eval(input()))
if n % 2 == 0:
  print((n//2))
else:
    print(((n+1)//2))
# Original solution
import math

n = int(eval(input()))

print((math.floor((n+1)/2)))


# Optimized solution
import math

N = int(eval(input()))
print((math.ceil(N/2)))
# Original solution
def main():
    N = int(eval(input()))
    print(((N + 1) // 2))
    return


main()


# Optimized solution
def main():
    N = int(eval(input()))
    print((-(-N // 2)))
    return


main()
# Original solution
print((int((int(eval(input()))+1)/2)))

# Optimized solution
print(((int(eval(input()))+1)//2))
# Original solution
N = int(eval(input()))

ans = N // 2 + N % 2

print(ans)


# Optimized solution
N = int(eval(input()))

ans = (N + 1) // 2

print(ans)
# Original solution
import math
N = int(eval(input()))
print((math.ceil(N/2)))

# Optimized solution
n = int(eval(input()))
if n % 2 <= 0 :
    print((n//2))
elif n % 2 >= 1 :
    print((n//2 +1))
# Original solution
N = int(eval(input()))

if N % 2 == 0:
    print((N//2))
else:
    print((N//2+1))

# Optimized solution
N = int(eval(input()))
output = 0

for i in range(1, N+1, 2):
    output += 1

print(output)
# Original solution
n = int(eval(input()))
def stairs(n):
    if (n == 1):
        return 1
    elif(n == 2):
        return 2
    elif(n == 3):
        return 4
    return stairs(n-1) + stairs(n-2) + stairs(n-3)
while (n != 0):
    pn = stairs(n)
    if (pn%10 == 0):
        pn //= 10
    else:
        pn = pn//10 + 1

    if (pn%365 == 0):
        pn //= 365
    else:
        pn = pn//365 + 1
    print(pn)
    n = int(eval(input()))


# Optimized solution
n = int(eval(input()))
st = [1,2,4]
for i in range(n-3):
    s = st[-1] + st[-2] + st[-3]
    st.append(s)
while (n != 0):
    pn = st[n-1]
    if (pn%10 == 0):
        pn //= 10
    else:
        pn = pn//10 + 1

    if (pn%365 == 0):
        pn //= 365
    else:
        pn = pn//365 + 1
    print(pn)
    n = int(eval(input()))
    st = [1,2,4]
    for i in range(n-3):
        s = st[-1] + st[-2] + st[-3]
        st.append(s)
# Original solution
import functools


#@functools.lru_cache(maxsize=None)
def rec(i):
    if i <= 0:
        return i == 0
    return rec(i-1) + rec(i-2) + rec(i-3)

while True:
    N = int(eval(input()))
    if not N:
        break
    print((((rec(N)-1)//10)//365+1))

# Optimized solution
import functools


@functools.lru_cache(maxsize=None)
def rec(i):
    if i <= 0:
        return i == 0
    return rec(i-1) + rec(i-2) + rec(i-3)

while True:
    N = int(eval(input()))
    if not N:
        break
    print((rec(N)//3650+1))
# Original solution
def up(n):
	if n == 0: return 1
	if n < 0: return 0
	return up(n-1)+up(n-2)+up(n-3)
	
while True:
	n = int(input())
	if n == 0: break
	print((up(n)//10+1)//365+1)

# Optimized solution
def up(n):
	goal = [0 for i in range(n)]
	goal[:3] = [1,2,4]
	for i in range(3,n):
		goal[i] = sum(goal[i-3:i])
	return goal[-1]
	
while True:
	n = int(input())
	if n == 0: break
	print((up(n)//10+1)//365+1)
# Original solution
from math import ceil
dp = [1] + [0 for i in range(30)]
for i in range(1,31):
	for step in [1,2,3]:
		if step <= i:
			dp[i] += dp[i-step]
unit = 3650.
while 1:
	n = int(input())
	if n == 0:
		break
	print(int(ceil(dp[n] / unit)))

# Optimized solution
from math import ceil
dp = [1] + [0 for i in range(33)]
for i in range(0,30):
	for step in [1,2,3]:
		dp[i+step] += dp[i]
unit = 3650.
while 1:
	n = int(input())
	if n == 0:
		break
	print(int(ceil(dp[n] / unit)))