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

# 2020/02/09
# AtCoder Beginner Contest 154 - D

# Input
n, k = map(int,input().split())
p = list(map(int,input().split()))

acm = [0] * n

# Calc
for i in range(k-1, n):
    for j in range(i-k+1, i+1):
        acm[i] = acm[i] + p[j] + 1

ans = max(acm) / 2

# Output
print(ans)


### FIXED CODE ###

# 2020/02/09
# AtCoder Beginner Contest 154 - D

# Input
n, k = map(int,input().split())
p = list(map(int,input().split()))

acm = [0] * n

# Calc
for i in range(n):
    if i-k < 0:
        minu = 0
    else:
        minu = p[i-k]
    acm[i] = acm[i-1] + p[i] - minu

ans = (max(acm) + k) / 2

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

#!/usr/bin/env python3
import sys
from fractions import gcd

def solve(N: int, M: int, a: "List[int]"):
    koubaisu = 1
    for i in a:

        koubaisu = koubaisu * (i // 2) // gcd(koubaisu, i//2)

    for i in a:
        if koubaisu // (i//2) % 2 == 0:
            print(0)
            exit()

    print(M // koubaisu - M // (2*koubaisu))


    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from fractions import gcd

def solve(N: int, M: int, a: "List[int]"):
    koubaisu = a[0]
    for i in range(1, N):

        koubaisu = koubaisu * a[i] // gcd(koubaisu, a[i])

    for i in a:
        if koubaisu // i % 2 == 0:
            print(0)
            exit()

    print(M // koubaisu - M // (2*koubaisu))


    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) // 2 for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)

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

x, y, z, k = map(int, input().split())
A = list(sorted(list(map(int, input().split())), reverse=True))
B = list(sorted(list(map(int, input().split())), reverse=True))
C = list(sorted(list(map(int, input().split())), reverse=True))
D = [A[a] + B[b] + C[c] for a in range(x) for b in range(y) for c in range(z) if (a + 1) * (b + 1) * (c + 1) <= k]
D.sort(reverse=True)
for i in range(k):
    print(D[i])

### FIXED CODE ###

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()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
AB = [x + y for x in A for y in B]
AB.sort(reverse=True)
ABC = [x + y for x in AB[:min(len(AB), k)] for y in C[:min(len(C), k)]]
ABC.sort(reverse=True)
for i in range(k):
    print(ABC[i])
### BUGGY CODE ###

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

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n = int(input())
    a = input_to_int_tuple()

    import itertools

    ret = 0
    for comb in itertools.combinations(range(1, n + 1), 2):
        if abs(comb[0] - comb[1]) == (a[comb[0] - 1] + a[comb[1] - 1]):
            ret += 1

    return ret


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

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

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n = int(input())
    a = input_to_int_tuple()

    from collections import defaultdict
    l = defaultdict(int)
    r = defaultdict(int)
    for i, h in enumerate(a):
        no = i + 1
        l[no + h] += 1
        r[no - h] += 1

    ret = 0
    for i in range(1, n + 1):
        ret += (l.get(i, 0) * r.get(i, 0))

    return ret


if __name__ == "__main__":
    print(main())
### BUGGY CODE ###

from bisect import bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ng, pz = [], []
z = 0
for x in a:
    if x > 0:
        pz.append(x)
    elif x < 0:
        ng.append(-x)
    else:
        z += 1
ra = list(reversed(list(map(lambda x: -x, a))))
l, r = -10 ** 19, 10 ** 19
while r - l > 1:
    if r - l < 100:
        r
    m = (l + r) // 2
    res = 0
    if m >= 0:
        res += z * (n - 1)
    for x in ng:
        idx = bisect_right(ra, m // x)
        if idx > 0 and ra[idx - 1] >= x:
            idx -= 1
        res += idx
    for x in pz:
        idx = bisect_right(a, m // x)
        if idx > 0 and a[idx - 1] >= x:
            idx -= 1
        res += idx
    if k <= res // 2:
        r = m
    else:
        l = m
print(r)


### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
a.sort()
pz = a[a > 0]
ng = a[a < 0]
z = np.count_nonzero(a == 0)


def count(x):
    res = 0
    if x >= 0:
        res += z * n
    res += np.searchsorted(a, x // pz, side="right").sum()
    res += n * len(ng) - np.searchsorted(a, -(-x // ng), side="left").sum()
    res -= np.count_nonzero(a * a <= x)
    return res // 2


l, r = -10 ** 19, 10 ** 19
while r - l > 1:
    m = (l + r) // 2
    if count(m) >= k:
        r = m
    else:
        l = m
print(r)
### BUGGY CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    ans = []
    for i in range(N):
        ans.append(A.index(i+1)+1)
    print(*ans)
resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    ans = []
    for _ in range(N):
        ans.append("0")
    for i in range(N):
        ans[A[i]-1] = i+1
    print(*ans)
resolve()
### BUGGY CODE ###

n=int(input())

battle=[]

def mainasu(x):
    return int(x)-1

front=[]

for _ in range(n):
    tmp=list(map(mainasu,input().split()))[::-1]
    front.append(tmp.pop())
    battle.append(tmp)

def pri():
    global front,battle,day
    print(day,front,battle)

day=0

#pri()

while 1:
    flag=0
    for i in range(n):
        if front[i]<n and i==front[front[i]]:
            flag=1
            front[front[i]]=n
            front[i]=n

    for i in range(n):
        if front[i]==n:
            if len(battle[i])>0:
                front[i]=battle[i].pop()
    
    if flag==0:
        break
    
    day+=1

flag=0
for item in front:
    if item!=n:
        flag=1
        break

if flag==0:
    print(day)
else:
    print(-1)            

    




### FIXED CODE ###

n=int(input())

battle=[]

def mainasu(x):
    return int(x)-1

front=[]

for _ in range(n):
    tmp=list(map(mainasu,input().split()))[::-1]
    front.append(tmp.pop())
    battle.append(tmp)

def pri():
    global front,battle,day,checkday
    print(day,front,battle,checkday)

day=0

checkday=[-1]*n

#pri()
cnt=0
while 1:
    flag=0
    for i in range(n):
        if i<n and front[i]<n and i==front[front[i]] and checkday[i]<day and checkday[front[i]]<day:
            flag=1
            if len(battle[front[i]])>0:
                front[front[i]]=battle[front[i]].pop()
                checkday[front[i]]=day
            else:
                front[front[i]]=n
                cnt+=1
            
            if len(battle[i])>0:
                front[i]=battle[i].pop()
                checkday[i]=day
            else:
                front[i]=n
                cnt+=1
    #pri()
    if flag==0:
        break
    
    day+=1


if cnt==n:
    print(day)
else:
    print(-1)
### BUGGY CODE ###

import collections
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
val = list(c.values())
key = list(c.keys())
for i in range(n):
    ind = key.index(a[i])
    val[ind] -= 1
    count = 0
    for j in val:
        if j < 2:
            pass
        else:   
            count += combinations_count(j,2)
    print(count)
    val[ind] += 1

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]*n
for i in range(n):
    b[a[i]-1] += 1
c = sum([(i*(i-1))//2 for i in b])
for i in a:
    print(c-(b[i-1]-1))
### BUGGY CODE ###

from sys import exit
n, m = map(int, input().split())
s = input()

one_sequence = 0
for i in range(1, n):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos != 0:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos -= i
            break
print(ans)


### FIXED CODE ###

from sys import exit
n, m = map(int, input().split())
s = input()

one_sequence = 0
for i in range(1, n):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos != 0:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos -= i
            break
print(ans)
### BUGGY CODE ###

import bisect
def find_ge(a, x):
    i = bisect.bisect_right(a,x)
    return i
    
def solve(n, a, b, c):

    b_count = [0]*len(b)
    for i, x in enumerate(b):
        b_count[i] = len(c) - find_ge(c, x)

    ans = 0
    for i in a:
        x = find_ge(b, i)
        ans += sum(b_count[x:])
        
    return ans

if __name__ == "__main__":
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    b = sorted([int(i) for i in input().split()])
    c = sorted([int(i) for i in input().split()])
    print(solve(n, a, b, c))


### FIXED CODE ###

import bisect
import itertools
def find_ge(a, x):
    i = bisect.bisect_right(a,x)
    return i

def solve(n, a, b, c):

    tmp = len(c)
    b_count =list(itertools.accumulate([tmp - find_ge(c, x) for x in b]))
    ans = 0
    for i in a:
        min_index = find_ge(b, i)
        
        ans += b_count[-1] -(0 if min_index == 0 else b_count[min_index-1])
    
    return ans

if __name__ == "__main__":
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    b = sorted([int(i) for i in input().split()])
    c = sorted([int(i) for i in input().split()])
    print(solve(n, a, b, c))
### BUGGY CODE ###

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

flag = True

for b in a:
    if a.count(b) >= 2:
        flag = False


if flag:
    print('YES')
else:
    print('NO')


### FIXED CODE ###

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

if len(set(a)) == n:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    N=int(input())
    A=list(map(int,input().split()))
    cnt=[0]*N
    for i in range(N):
        for j in range(N):
            if abs(A[i]-A[j])<=1:
                cnt[i]+=1
    print(max(cnt))




resolve()

### FIXED CODE ###

from collections import Counter, deque
# from copy import copy, deepcopy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    N=int(input())
    A=list(map(int,input().split()))
    AA=Counter(A)
    maxval=0
    for i in AA.keys():
        maxval=max(AA[i-1]+AA[i]+AA[i+1],maxval)

    print(maxval)



resolve()
### BUGGY CODE ###

from collections import deque

class MyClass():    
    def load(self):
        self.n = input()
        self.A = map(int,raw_input().split())
        self.q = input()
        self.M = map(int,raw_input().split())

    def main(self):
        self.load()
        W = map(self.solve,self.M)
        for w in W:
            print w

    def solve(self,m):
        qA = deque(self.A)
        for j in range(self.n):
            w = self.rec(m,list(qA))
            if w:
                break
            qA.popleft()
        if w:
            return "yes"
        else:
            return "no"

    def rec(self,m,A):
        if len(A) == 0:
            return False
        else:
            r1 = self.rec(m,A[1:])
            m_new = m - A[0]
            if m_new < 0:
                r2 = False
            elif m_new == 0:
                r2 = True
            else:
                r2 = self.rec(m_new,A[1:])
            
            if r1 or r2:
                return True
            else:
                return False

if __name__ == "__main__":
    MC = MyClass()
    MC.main()

### FIXED CODE ###

from collections import deque

def main():
    n = input()
    A = deque(map(int,raw_input().split()))
    q = input()
    M = map(int,raw_input().split())

    p = rec([0],A)

    for m in M:
        if m in p:
            print "yes"
        else:
            print "no"

def rec(a,A):
    if len(A) == 0:
        return a
    else:
        y = A.popleft()
        a = a+[x+y for x in a]
        return rec(a,A)

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

n=int(input())
a=list(map(int,input().split()))
sa=set(a)
a2=[]
for ii in sa:
  ca=a.count(ii)
  a2.append([ii,ca])
  for jj in range(ca):
    a.remove(ii)
#import numpy as np
#a2=np.array(a2)
#print(a2)

def func(a2):
  r=0
  for jj in range(len(a2)):
     r+= a2[jj][0]*a2[jj][1]
  return r

r=func(a2)
q=int(input())
for ii in range(q):
  b,c=map(int,input().split())
  for jj in range(len(a2)):
    if a2[jj][0]==b:
      r+=(c-b)*a2[jj][1]
      a2[jj][0]=c
  print(r)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ma=10**5
a2=[0]*ma
for ii in a:
  a2[ii-1]+=1

def func(a2):
  r=0
  for jj in range(len(a2)):
     r+= a2[jj]*(jj+1)
  return r

r=func(a2)
q=int(input())
for ii in range(q):
  b,c=map(int,input().split())
  r+=(c-b)*a2[b-1]
  a2[c-1]+=a2[b-1]
  a2[b-1]=0
  print(r)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns()) #int
na = lambda: list(map(int, stdin.readline().split())) #int,list
ns = lambda: stdin.readline().rstrip()  # str

n,m=na()
a=na()
for i in range(m):
	b,c=na()
	a.extend([c]*b)

print(sum(sorted(a)[-n:]))

### FIXED CODE ###

import sys
#import time
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import heapq
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n,m = rl()
a = rl()

li=dict(Counter(a))
for _ in range(m):
    b, c = rl()
    if c in li:
        li[c]+=b
    else:
        li[c]=b
li=sorted(li.items(),key=lambda x: -x[0])
ans=0
res=n
for pair in li:
    if res<=0:
        continue
    if res>=pair[1]:
        ans+=pair[0]*pair[1]
        res-=pair[1]
    else:
        ans+=pair[0]*res
        res=0
print(ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    N = int(input())
    A = []
    C = defaultdict(int)
    for i in map(int, input().split()):
        if C[i] == 0:
            A.append(i)
        C[i] += 1
    A.sort()
    X = []
    ans = 0
    if C[1] > 1:
        print(0)
        sys.exit()
    elif C[1] == 1:
        print(1)
        sys.exit()
    for a in A:
        for x in X:
            if a % x == 0:
                break
            if 2 * x > a:
                if C[a] == 1:
                    ans += 1
                X.append(a)
                break
        else:
            if C[a] == 1:
                ans += 1
            X.append(a)
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    N = int(input())
    A = sorted(list(map(int, input().split())))
    C = Counter(A)
    dp = [False] * 1100000
    ans = 0
    for a, cnt in C.items():
        if dp[a]:
            continue
        for i in range(2*a, 1100000, a):
            dp[i] = True
        if cnt == 1:
            ans += 1
    print(ans)

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

n = int(input())
a = [int(i) for i in input().split()]
sum1 = []
sum2 = []
s = sum(a)
ls = []
for i in range(1,n):
    sum1.append(sum(a[:i]))
    sum2.append(s - sum(a[:i]))

for i in range(n-1):
    ls.append(abs(sum1[i] - sum2[i]))

print(min(ls))


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
sum1 = [a[0]]
sum2 = [sum(a)-a[0]]
s = sum(a)
ls = []
for i in range(1,n):
    sum1.append(sum1[i-1]+a[i])
    sum2.append(s - sum1[i])

for i in range(n-1):
    ls.append(abs(sum1[i] - sum2[i]))

print(min(ls))
### BUGGY CODE ###

n=int(input())
s=input()

ans=[]
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            tmp=str(s[i])+str(s[j])+str(s[k])

            if tmp not in ans:
                ans.append(tmp)

print(len(ans))

### FIXED CODE ###

n=int(input())
s=input()

s=list(map(int,list(s)))

password=[str(i).zfill(3) for i in range(1000)]

cnt=0
can=[]
for word in password:
    w1=int(word[0])
    w2=int(word[1])
    w3=int(word[2])

    i=0
    while i<n-2:
        if s[i]==w1:
            i_1=i
            break
        else:
            i+=1

        if i==n-3 and s[i]!=w1:
            i_1=-1
            break
    
    if i_1==-1:
        continue

    j=i+1
    while j<n-1:
        if s[j]==w2:
            i_2=j
            break
        else:
            j+=1

        if j==n-2 and s[j]!=w2:
            i_2=-1
            break
    
    if i_2==-1:
        continue

    k=j+1
    while k<n:
        if s[k]==w3:
            i_3=k
            break
        else:
            k+=1
        
        if k>=n-1 and s[n-1]!=w3:
            i_3=-1
            break

    if i_3==-1:
        continue
    elif i_1<i_2 and i_2<i_3:
        cnt+=1
        can.append(word)


print(cnt)
### BUGGY CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
import bisect

N = INT()
A = LIST()
B = LIST()
C = LIST()

A.sort()
B.sort()
C.sort()

ans = 0
for ai in A:
    i = bisect.bisect_right(B, ai)
    for bi in B[i:]:
        j = bisect.bisect_right(C, bi)
        ans += len(C[j:])

print(ans)

### FIXED CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
# import bisect

N = INT()
A = LIST()
B = LIST()
C = LIST()

A.sort()
B.sort()
C.sort()

def binsearch(lst, th, ud="up"):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if ud == "up":
            if lst[mid] > th:
                right = mid
            else:
                left = mid
        else:
            if lst[mid] >= th:
                right = mid
            else:
                left = mid
        
    return right if ud == "up" else left


ans = 0
# for ai in A:
#     i = bisect.bisect_right(B, ai)
#     for bi in B[i:]:
#         j = bisect.bisect_right(C, bi)
#         ans += len(C[j:])

for bi in B:
    i = binsearch(A, bi, "down")
    j = binsearch(C, bi, "up")
    ans += (i+1) * (N-j)


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

N = int(input())
A = list(map(int,input().split()))
S = [0 for i in range(60)]
for i in range(N):
    a = A[i]
    for j in range(60):
        if (a>>j)&1:
            S[j] += 1
mod = 10**9 + 7
ans = 0
for i in range(60):
    s = S[i]
    t = N - s
    r = (s*t*(2**i))%mod
    ans = (ans + r)%mod
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
S = [0 for i in range(60)]
for i in range(N):
    a = A[i]
    for j in range(60):
        if (a>>j)&1:
            S[j] += 1
mod = 10**9 + 7
ans = 0
for i in range(60):
    s = S[i]
    t = N - s
    r = (s*t*(2**i))%mod
    ans = (ans + r)%mod
print(ans)
### BUGGY CODE ###

import numpy as np
H,W,D = map(int,input().split())
a = [input().split() for l in range(H)]
Q = int(input())
b = [input().split() for l in range(Q)]
a = np.array(a)
b = np.array(b)
a = np.int64(a)
b = np.int64(b)
ans = []
memo = [0] * (H*W+1)
for i in range(D):
  while i < H*W:
    c = np.where(a == i+1)
    i += D
    if i >= H*W:
      break
    d = np.where(a == i+1)
    memo[i] = memo[i-D]  + abs(c[0][0] - d[0][0]) + abs(c[1][0] - d[1][0])
for i in range(Q):
  syo = b[i,0]
  go = b[i,1]
  print(memo[go-1] - memo[syo-1])

### FIXED CODE ###

import numpy as np
H,W,D = map(int,input().split())
a = [input().split() for l in range(H)]
basyo = [[0,0] for i in range(H*W)]
for i in range(W):
  for j in range(H):
    basyo[int(a[j][i])-1] = [j,i]
Q = int(input())
b = [input().split() for l in range(Q)]
ans = []
memo = [0] * (H*W+1)
for i in range(D):
  while i < H*W:
    i += D
    if i >= H*W:
      break
    memo[i] = memo[i-D]  + abs(basyo[i][0] - basyo[i-D][0]) + abs(basyo[i-D][1] - basyo[i][1])
b = np.array(b)
b = np.int64(b)
for i in range(Q):
  syo = b[i,0]
  go = b[i,1]
  print(memo[go-1] - memo[syo-1])
### BUGGY CODE ###

import math
N = int(input())

def minus_2(n):
    ans = ''
    if n == 1:
        ans += '1'
    else:
        while n != 1:
            if n % 2 == 0:
                ans += '0'
            else:
                ans += '1'
            n = math.ceil(n/-2)
        ans += '1'
        ans = ans[::-1]
        
    return ans

print(minus_2(N))

### FIXED CODE ###

import math
N = int(input())
 
def minus_2(n):
    ans = ''
    if n == 1:
        ans += '1'
    elif n == 0:
        ans += '0'
    else:
        while n != 1:
            if n % 2 == 0:
                ans += '0'
            else:
                ans += '1'
            n = math.ceil(n/-2)
        ans += '1'
        ans = ans[::-1]
        
    return ans
 
print(minus_2(N))