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

import heapq,sys



def heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap) - 1)


def heappop_max(heap):
    lastelt = heap.pop()
    if heap:
        return_item = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return return_item
    return lastelt

def main():
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    A = sorted([int(i) for i in input().split()], reverse=True)
    B = sorted([int(i) for i in input().split()], reverse=True)
    C = sorted([int(i) for i in input().split()], reverse=True)
    ans = []
    heap_queue = []
    for i in range(X):
        for j in range(Y):
            for k in range(Z):
                heappush_max(heap_queue, A[i] + B[j] + C[k])
    for k in range(K):
        print(heappop_max(heap_queue))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,bisect
input = sys.stdin.readline

x,y,z,k = map(int,input().split())
a = tuple(map(int,input().split()))
b = tuple(map(int,input().split()))
c = list(map(int,input().split()))

ab = []
for e in a:
    for w in b:
        ab.append(e+w)
ab.sort()

ok = -1
ng = 10**12
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    cnt = 0
    for e in c:
        cnt += len(ab)-bisect.bisect_left(ab,mid-e)
    if cnt >= k:
        ok = mid
    else:
        ng = mid

res = []
for e in c:
    ind = bisect.bisect_left(ab,ok-e)
    for i in range(ind,len(ab)):
        res.append(e+ab[i])
res.sort()
for i in range(1,k+1):
    print(res[-i])
### BUGGY CODE ###

from collections import deque

N, M = [int(x) for x in input().split()]

friends_map = {}
remain_user = set()
for m in range(M):
    a, b = [int(x) - 1 for x in input().split()]

    if a in friends_map:
        friends_map[a].add(b)
    else:
        friends_map[a] = {b}

    if b in friends_map:
        friends_map[b].add(a)
    else:
        friends_map[b] = {a}

    remain_user.add(a)
    remain_user.add(b)

stack = deque()
stack.appendleft(0)

max_group = 1
watch = set()
while stack:
    now = stack.popleft()
    remain_user.discard(now)
    watch.add(now)

    if now in friends_map:
        for next_node in friends_map[now]:
            if not next_node in watch:
                stack.appendleft(next_node)
                remain_user.discard(next_node)

    if not stack:
        if len(watch) > max_group:
            max_group = len(watch)

        if remain_user:
            stack.appendleft(remain_user.pop())
            watch = set()

print(max_group)


### FIXED CODE ###

from collections import deque

N, M = [int(x) for x in input().split()]

friends_map = {n : set() for n in range(N)}
remain_user = set()
for m in range(M):
    a, b = [int(x) - 1 for x in input().split()]

    friends_map[a].add(b)
    friends_map[b].add(a)
    remain_user.add(a)
    remain_user.add(b)

stack = deque()
stack.appendleft(0)

max_group = 1
watch = [0] * N
count = 0
while stack:
    now = stack.popleft()

    if watch[now] == 0:
        remain_user.discard(now)
        watch[now] = 1
        count += 1

        for next_node in friends_map[now]:
            if watch[next_node] == 0:
                stack.appendleft(next_node)

    if not stack:
        max_group = max(count, max_group)

        if remain_user:
            stack.appendleft(remain_user.pop())
            count = 0

print(max_group)
### BUGGY CODE ###

n, s = map(int, input().split())
a = tuple(map(int, input().split()))
MOD = 998244353

# dp0 = [[0] * (s + 1) for _ in range(n + 1)]
# dp0[0][0] = 1
# for i in range(n):  # ここをrange(i, n)にすると、f(i, r)の計算ができる
#     for j in range(s + 1):
#         dp0[i + 1][j] += dp0[i][j]  # do NOT use a[i]
#         if j + a[i] <= s:
#             dp0[i + 1][j + a[i]] += dp0[i][j]  # USE a[i]
# # f(1, n) = dp0[n][s]
# # f(1, i) = dp0[i][s] (i = 1, 2, ..., n)
# print('dp0')
# print(*dp0, sep='\n')

dp = [[[0] * 3 for _ in range(s + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(s + 1):
        # i番目の要素は使わない
        dp[i + 1][j][0] += dp[i][j][0]
        dp[i + 1][j][0] %= MOD
        dp[i + 1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i + 1][j][1] %= MOD

        if j + a[i] <= s:
            dp[i + 1][j + a[i]][1] += dp[i][j][0] + dp[i][j][1]
            dp[i + 1][j + a[i]][1] %= MOD
# dp[r][s][1] = \sum_{i=1}^{r} f(i, r)

# print('dp[][][1]')
# for i in range(n + 1):
#     print([dp[i][j][1] for j in range(s + 1)])

ans = 0
for i in range(1, n + 1):
    ans += dp[i][s][1]
    ans %= MOD

print(ans)


### FIXED CODE ###

n, s = map(int, input().split())
a = tuple(map(int, input().split()))
MOD = 998244353

# dp = [[0] * (s + 1) for _ in range(n + 1)]
# dp[0][0] = 1
# for i in range(n):  # ここをrange(i, n)にすると、f(i, r)の計算ができる
#     for j in range(s + 1):
#         dp[i + 1][j] += dp[i][j]  # do NOT use a[i]
#         if j + a[i] <= s:
#             dp[i + 1][j + a[i]] += dp[i][j]  # USE a[i]
# # f(1, n) = dp[n][s]
# # f(1, i) = dp[i][s] (i = 1, 2, ..., n)
# print('dp')
# print(*dp, sep='\n')

dp0 = [[0] * (s + 1) for _ in range(n + 1)]
dp1 = [[0] * (s + 1) for _ in range(n + 1)]
dp0[0][0] = 1
ans = 0
for i in range(n):
    for j in range(s + 1):
        # i番目の要素は使わない
        dp0[i + 1][j] += dp0[i][j]
        dp0[i + 1][j] %= MOD
        dp1[i + 1][j] += dp0[i][j] + dp1[i][j]
        dp1[i + 1][j] %= MOD

        if j + a[i] <= s:
            dp1[i + 1][j + a[i]] += dp0[i][j] + dp1[i][j]
            dp1[i + 1][j + a[i]] %= MOD

    ans += dp1[i + 1][s]
    ans %= MOD
# dp[r][s][1] = \sum_{i=1}^{r} f(i, r)

# print('dp[][][1]')
# for i in range(n + 1):
#     print([dp[i][j][1] for j in range(s + 1)])

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

N = int(input())
s = []
for _ in range(N):
    s.append(input())

c = 0
out = 0
while c < N-1:
    for i in range(c, N-1):
        s_l = set(s[c])
        s_r = set(s[i+1])
        if(s_l != s_r):
            continue
        s_l_li = list(s_l)
        s_r_li = list(s_r)
        for j in range(len(s_l_li)):
            if(s[c].count(s_l_li[j]) != s[i+1].count(s_l_li[j])):
                break
            if j == (len(s_l_li)-1):
                out += 1
    c += 1
print(out)

### FIXED CODE ###

N = int(input())
D = {}
for _ in range(N):
    S = "".join(sorted(input()))
    if S in D:
        D[S] += 1
    else:
        D[S] = 1
 
out = 0
for i in D.values():
    out += i * (i-1) //2
print(out)
### BUGGY CODE ###

n, p = map(int, input().split(' '))
s = input()

if 10 % p == 0:
    ans = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
    print(ans)
else:
    ans = 0
    d = [0 for _ in range(n + 1)]
    ten = 1
    for i in range(n - 1, -1, -1):
        a = int(s[i]) * ten % p
        d[i] = (d[i + 1] + a) % p
        ten *= 10
        # ten %= p
    cnt = [0 for _ in range(p)]
    for i in range(n, -1, -1):
        ans += cnt[d[i]]
        cnt[d[i]] += 1
    print(ans)

### FIXED CODE ###

n, p = map(int, input().split(' '))
s = input()

if 10 % p == 0:
    ans = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
    print(ans)
else:
    ans = 0
    d = [0 for _ in range(n + 1)]
    ten = 1
    for i in range(n - 1, -1, -1):
        a = int(s[i]) * ten % p
        d[i] = (d[i + 1] + a) % p
        ten *= 10
        ten %= p
    cnt = [0 for _ in range(p)]
    for i in range(n, -1, -1):
        ans += cnt[d[i]]
        cnt[d[i]] += 1
    print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

S1,S2 = S[:N],S[N:][::-1]

dic = {}
Ans = 0

for i in range(2**N):
    red,blue = "",""
    bits = bin(2**N+i)[3:]
    for j in range(N):
        if bits[j]=="0":
            red += S1[j]
        else:
            blue += S1[j]
    key = red+"-"+blue[::-1]
    if key not in dic.keys():
        dic[key] = 1
    else:
        dic[key] += 1

for i in range(2**N):
    red,blue = "",""
    bits = bin(2**N+i)[3:]
    for j in range(N):
        if bits[j]=="1":
            red += S2[j]
        else:
            blue += S2[j]
    key = red+"-"+blue[::-1]
    if key in dic.keys():
        Ans += dic[key]
        
print(Ans)

### FIXED CODE ###

N = int(input())
S = input()

S1,S2 = S[:N],S[N:][::-1]

dic = {}
Ans = 0
keys = []

for i in range(2**N):
    red,blue = "",""
    red2,blue2 = "",""
    bits = bin(2**N+i)[3:]
    for j in range(N):
        if bits[j]=="0":
            red   += S1[j]
            red2 += S2[j]
        else:
            blue += S1[j]
            blue2 += S2[j]
    keys.append(red2+"-"+blue2)
    key = red+"-"+blue
    if key not in dic.keys():
        dic[key] = 1
    else:
        dic[key] += 1

for k in keys:
    Ans += dic.get(k,0)

print(Ans)
### BUGGY CODE ###

times=10**100
S=input()
bs=[True if s=="L" else False for s in S]
#print(bs)

start=-1
cycle=-1
list_list=[]

clist=[1]*len(bs)
list_list.append(clist)

dic_list={}
dic_list[str(clist)]=0
for i in range(1,10**100):  
  new_clist=[0]*len(bs)
  for j,b in enumerate(bs):
    if b:
      new_clist[j-1]+=clist[j]
    else:
      new_clist[j+1]+=clist[j]

  clist=new_clist
  list_list.append(clist)
  #print(clist)
  
  if str(clist) in dic_list:
    #print(i,i-dic_list[str(clist)],str(clist))
    start=dic_list[str(clist)]
    cycle=i-dic_list[str(clist)]
    break
  else:
    dic_list[str(clist)]=i
    
#print(start,cycle,list_list[start])
index=((10**100-start)%cycle)+start
ans_list=map(str,list_list[index])
print(" ".join(ans_list))


### FIXED CODE ###

S=input()
ans_list=[0]*len(S)

rmode=True
cnt_R=0
cnt_L=0
border_R=0
border_L=0
for i in range(len(S)):
  if rmode:
    if S[i]=="R":
      cnt_R+=1
    else:
      border_R=i-1
      border_L=i      
      rmode=False
      cnt_L=1
  else:
    if S[i]=="L":
      cnt_L+=1
    else:
      ans_list[border_R]+=(cnt_R+1)//2
      ans_list[border_L]+=cnt_R//2
      ans_list[border_R]+=cnt_L//2
      ans_list[border_L]+=(cnt_L+1)//2
      rmode=True
      cnt_R=1
      cnt_L=0
else:
  ans_list[border_R]+=(cnt_R+1)//2
  ans_list[border_L]+=cnt_R//2
  ans_list[border_R]+=cnt_L//2
  ans_list[border_L]+=(cnt_L+1)//2
  
      
ans_list_str=map(str,ans_list)
print(" ".join(ans_list_str))
### BUGGY CODE ###

def isSquare(x):
  f = 1
  while f * f <= x:
    if f * f == x:
      return True
    else:
      f += 1
  return False

N = int(input())
print(max(x if isSquare(x) else 0 for x in range(1,1+N)))

### FIXED CODE ###

def isSquare(x):
  return x == round(x**(1/2))**2

N = int(input())
f = N
while True:
  if isSquare(f):
    print(f)
    exit()
  else:
    f -= 1
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    d=input()
    a.append(sorted(d))
#print(a)

count=0
for i in range(n):
    temp=a.pop()
    count+=a.count(temp)
print(count)


### FIXED CODE ###

from collections import Counter
n=int(input())
d=Counter()
ans=0
for i in range(n):
    t=str("".join(sorted(input())))
    if t in d:
        ans+=d[t]
    d[t]+=1
print(ans)
### BUGGY CODE ###

def is_like2017(X):
  res = 1
  for x in [X,(X+1)/2]:
    y = int(x**0.5)
    for i in range(2,y+1):
      if x%i==0:
        res=0
        break
    if res==0:
      break
  return res

prime = []
for i in range(10**5+2):
  if i<2 or i%2==0:
    prime.append(0)
  else:
    if is_like2017(i)==1:
      prime.append(1)
    else:
      prime.append(0)

#input
Q = int(input())
ans = []
for i in range(Q):
  l,r = map(int,input().split())
  print(sum(prime[l:r+1]))

### FIXED CODE ###

def is_like2017(X):
  res = 1
  for x in [X,(X+1)/2]:
    y = int(x**0.5)
    for i in range(2,y+1):
      if x%i==0:
        res=0
        break
    if res==0:
      break
  return res

prime_accumulation = []
for i in range(10**5+2):
  if i<2:
    prime_accumulation.append(0)
  elif i%2==0:
    prime_accumulation.append(prime_accumulation[i-1])
  else:
    if is_like2017(i)==1:
      prime_accumulation.append(prime_accumulation[i-1]+1)
    else:
      prime_accumulation.append(prime_accumulation[i-1])

#input
Q = int(input())
ans = []
for i in range(Q):
  l,r = map(int,input().split())
  print(prime_accumulation[r]-prime_accumulation[l-1])
### BUGGY CODE ###

n = int(input())
ls = list(map(int, input().split()))
i = 0
while i < n:
    if ls.count(ls[i]) == 1:
        i += 1
    else:
        print("NO")
        break

if i == n:
    print("YES")

    

### FIXED CODE ###

n = int(input())
ls = list(map(int, input().split()))

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = merge_sort(left)
    right = merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right)


def merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

a = merge_sort(ls)
i = 0
while i < n-1:
    if a[i] == a[i+1]:
        print("NO")
        break
    else:
        i += 1

if i == n-1:
    print("YES")
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
c = 0
while True:
  for i in A:
    if i%2:
      print(c)
      break
    i //= 2
    
  c += 1

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
c = 0
while True:
  for i in range(n):
    if A[i]%2:
      print(c)
      exit()
    A[i] //= 2
    
  c += 1
### BUGGY CODE ###

import pprint
H, W, M = map(int, input().split())
bombs = set()
hCount = [0]*H
vCount = [0]*W

for i in range(M):
    h, w = map(int, input().split())
    h -= 1; w -= 1;
    hCount[h] += 1
    vCount[w] += 1
    bombs.add((h, w))

hMax = max(hCount)
vMax = max(vCount)
hMaxIndex = [i for i, x in enumerate(hCount) if x==max(hCount)]
vMaxIndex = [i for i, x in enumerate(vCount) if x==max(vCount)]

ans = -1
for x in vMaxIndex:
    for y in hMaxIndex:
        if (y, x) in bombs:
            continue
        else:
            print(hMax + vMax)
            exit()
print(hMax + vMax - 1)


### FIXED CODE ###

import pprint
H, W, M = map(int, input().split())
bombs = set()
hCount = [0]*H
vCount = [0]*W

for i in range(M):
    h, w = map(int, input().split())
    h -= 1; w -= 1;
    hCount[h] += 1
    vCount[w] += 1
    bombs.add((h, w))

hMax = max(hCount)
vMax = max(vCount)
hMaxIndex = [i for i, x in enumerate(hCount) if x==hMax]
vMaxIndex = [i for i, x in enumerate(vCount) if x==vMax]

ans = -1
for x in vMaxIndex:
    for y in hMaxIndex:
        if (y, x) in bombs:
            continue
        else:
            print(hMax + vMax)
            exit()
print(hMax + vMax - 1)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
a = sorted(a,reverse=True)
for i in a:
	ans *=i
	if(0 in a):
		print(0)
		exit()
	if(ans>1000000000000000000):
		print(-1)
		exit()
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
a = sorted(a,reverse=True)
if(0 in a):
	print(0)
	exit()
for i in a:
	if(len(str(i)) + len(str(ans)) > 20):
		print(-1)
		exit()
	ans *=i

print(ans if(ans<=pow(10,18)) else -1)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    x, y, z, k = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    AB = []
    for a in A:
        for b in B:
            AB.append(a + b)
    AB = sorted(AB, reverse=True)[:k]

    res = []
    for ab in AB:
        for c in C:
            res.append(ab + c)
    res = sorted(res, reverse=True)[:k]
    print(*res, sep="\n")


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    AB = []
    for i in range(X):
        for j in range(Y):
            AB.append(A[i] + B[j])
    AB.sort(reverse=True)

    res = []
    for i in range(min(K, len(AB))):
        for j in range(Z):
            res.append(AB[i] + C[j])
    res.sort(reverse=True)

    for i in range(K):
        print(res[i])


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

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

ans = ""
n, q = [int(item) for item in input().split()]
for i in range(q):
    v, w = [int(item) - 1 for item in input().split()]
    while v != w:
        if v > w:
            v = (v - 1) // n
        else:
            w = (w - 1) // n
    print(v + 1)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

ans = ""
n, q = [int(item) for item in input().split()]
if n == 1:
    for i in range(q):
        v, w = [int(item) for item in input().split()]
        print(min(v, w))
    exit()

for i in range(q):
    v, w = [int(item) - 1 for item in input().split()]
    while v != w:
        if v > w:
            v = (v - 1) // n
        else:
            w = (w - 1) // n
    print(v + 1)
### BUGGY CODE ###

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
INF = float("inf")
import sys
sys.setrecursionlimit(10000)

a = []
memo = []


def dfs(no, i):
    global memo, a
    if memo[no][i]:
        return memo[no][i]

    ans = abs(a[-1] - a[i])
    for j in range(i + 1, len(a) - 1):
        nex = dfs(1 - no, j + 1)
        # X
        if no == 0:
            ans = max(ans, nex)
        # Y
        else:
            ans = min(ans, nex)

    memo[no][i] = ans
    return ans


def solve2(N, Z, W):
    global a, memo
    a = [Z, W] + a
    memo = [[None] * len(a) for _ in range(2)]
    return dfs(0, 1)


def solve(N, Z, W):
    global a
    ans = abs(a[-1] - W)
    if len(a) > 1:
        ans = max(ans, abs(a[-2] - a[-1]))
    return ans


def main():
    global a
    N, Z, W = map(int, input().split())
    a = list(map(int, input().split()))
    print(solve2(N, Z, W))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
INF = float("inf")
import sys
sys.setrecursionlimit(10000)


def solve(N, Z, W, a):
    ans = abs(a[-1] - W)
    if len(a) > 1:
        ans = max(ans, abs(a[-2] - a[-1]))
    return ans


def main():
    N, Z, W = map(int, input().split())
    a = list(map(int, input().split()))
    print(solve(N, Z, W, a))


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

import sys

# from collections import Counter, deque, defaultdict
# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
# N = int(input())
# A,B,C = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

H, W = [int(x) for x in input().split()]
S = []
for h in range(H):
    S.append(input())

Th = [[0] * W for _ in range(H)]
Tw = [[0] * W for _ in range(H)]

for h in range(H):
    cnt = 0
    st = 0
    for w in range(W):
        if S[h][w] == "#":
            for i in range(st, w):
                Tw[h][i] = cnt
            st = w + 1
            cnt = 0
        else:
            cnt += 1
    for i in range(st, W):
        Tw[h][i] = cnt

for w in range(W):
    cnt = 0
    st = 0
    for h in range(H):
        if S[h][w] == "#":
            for i in range(st, h):
                Th[i][w] = cnt
            st = h + 1
            cnt = 0
        else:
            cnt += 1
    for i in range(st, H):
        Th[i][w] = cnt

ALL = []
for w in range(W):
    for h in range(H):
        ALL.append(Tw[h][w] + Th[h][w])

print(max(ALL) - 1)


### FIXED CODE ###

import sys

# from collections import Counter, deque, defaultdict
# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
# N = int(input())
# A,B,C = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

H, W = [int(x) for x in input().split()]
S = []
for h in range(H):
    S.append(input())

Th = [[0] * W for _ in range(H)]
Tw = [[0] * W for _ in range(H)]

for h in range(H):
    cnt = 0
    st = 0
    for w in range(W):
        if S[h][w] == "#":
            for i in range(st, w):
                Tw[h][i] = cnt
            st = w + 1
            cnt = 0
        else:
            cnt += 1
    for i in range(st, W):
        Tw[h][i] = cnt

for w in range(W):
    cnt = 0
    st = 0
    for h in range(H):
        if S[h][w] == "#":
            for i in range(st, h):
                Th[i][w] = cnt
            st = h + 1
            cnt = 0
        else:
            cnt += 1
    for i in range(st, H):
        Th[i][w] = cnt

ALL = []
for w in range(W):
    for h in range(H):
        ALL.append(Tw[h][w] + Th[h][w])

print(max(ALL) - 1)
### BUGGY CODE ###

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

result = 0

while A != [] and K >= A[0] or B != [] and K >= B[0]:
    a, b = 0, 0
    na, nb = 0, 0
    for i in range(len(A)):
        if a+A[i] <= K:
            a += A[i]
            na += 1
        else:
            break
    for i in range(len(B)):
        if b+B[i] <= K:
            b += B[i]
            nb += 1
        else:
            break
    if na > nb:
        K -= A.pop(0)
        result += 1
    elif na < nb:
        K -= B.pop(0)
        result += 1
    elif na == nb:
        if A[0] <= B[0]:
            K -= A.pop(0)
        else:
            K -= B.pop(0)
        result += 1

print(result)


### FIXED CODE ###

from itertools import accumulate

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0

a_accum = [0] + list(accumulate(a))
b_accum = [0] + list(accumulate(b))

j = m
for i in range(n+1):
  while k < a_accum[i] + b_accum[j] and j >= 1:
    j -= 1
  if k >= a_accum[i] + b_accum[j] and ans < i + j:
    ans = i + j

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

while True:
    n = int(input())
    if n == 0:
        break
    cnt = 1
    for i in range(1, n+1):
        tmp = str(cnt)
        while '4' in tmp or '6' in tmp:
            if '4' in tmp and '6' in tmp:
                l = min(tmp.find('4'), tmp.find('6'))
                r = len(tmp[l+1:])
                cnt += 1*pow(10, r)
            elif '4' in tmp:
                l = tmp.find('4')
                r = len(tmp[l+1:])
                cnt += 1*pow(10, r)
            else:
                l = tmp.find('6')
                r = len(tmp[l+1:])
                cnt += 1*pow(10, r)
            tmp = str(cnt)
        cnt += 1
    print(cnt-1)

### FIXED CODE ###

while True:
    n = int(input())
    if n == 0:
        break
    print(str(oct(n)[2:]).translate(str.maketrans("4567", "5789")))