Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter

from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#l=deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

#mod = 10**9+7
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え
#start 4:00
N = int(input())
#N, K = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [list(map(int, input().split())) for i in range(N)]



A = list(map(int, input().split()))
edge = [[] for i in range(N)]
for i in range(N-1):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)


#始点sから各頂点への最短距離
inf=10**10
dp = [inf]*N
visited=[False]*N
q=[]
q=deque(q)
ans=[0]*N

def dfs(e):
    visited[e]=True
    a=A[e]
    ci=bisect_left(dp,a)
    q.append((ci,dp[ci]))
    dp[ci]=a
    ans[e]=bisect_left(dp,inf)
    #print(edge[e])
    for ne in edge[e]:
        if not visited[ne]:
            dfs(ne)
            pi,px=q.pop()
            dp[pi]=px


dfs(0)
    #print(d)
    
for x in ans:
    print(x)
#print(d[4])



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter

from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

#mod = 10**9+7
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

K = int(input())
A,B = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [list(map(int, input().split())) for i in range(N)]


if A%K==0 or B%K==0:
    print('OK')
    exit()

elif A//K<B//K:
    print('OK')
    exit()
print('NG')
n=int(input())
p=list(map(int,input().split()))
count=0
for i in range:
    if p[i]==i+1:
        count+=1

if count==2 or count==0:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
count=0
for i in range(n):
    if p[i]!=i+1:
        count+=1

if count==2 or count==0:
    print("YES")
else:
    print("NO")
import sys

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

array = [-1] * (n+1)
array[1] = 0

li = []
li.append(1)

tmp = -1
i = 1
index = 0
while True:
  if array[a[index]] != -1:
    tmp = array[a[index]]
    break
    
  if i == k:
    print(a[index])
    sys.exit(0)
    
  li.append(a[index])
  array[index] = i
  index = a[index] -1
  i += 1
  
  

k -= tmp
d = len(li)

k %= d

print(li[k+tmp])

### FIXED CODE ###

import sys

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

array = [-1] * (n+1)
array[1] = 0

li = []
li.append(1)

tmp = -1
index = 0
for i in range(2 * (10**5)):
  if array[a[index]] != -1:
    tmp = array[a[index]]
    break
    
  if i == k:
    print(index+1)
    sys.exit(0)
    
  li.append(a[index])
  array[a[index]] = i+1
  index = a[index] -1
  
k -= tmp
d = len(li) - tmp

k %= d

print(li[k+tmp])
l=[]
while True:
    try:
        l.append(input())
    except SyntaxError:
        break
l.sort(reverse = True)
for i in range(3):
    print l[i]

### FIXED CODE ###

l=[]
while True:
    try:
        l.append(input())
    except EOFError:
        break
l.sort(reverse = True)
for i in range(3):
    print l[i]
def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[inf for i in range(W+1)] for j in range(N+1)]
  dp[0][0]= 0
  #DP
  for i in range(N):
    for w in range(W+1):
      if 0 <= w-weight[i]: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=min(dp[i+1][w-weight[i]]+value[i], dp[i][w],dp[i+1][w-1]+value[i])
      else:
        dp[i+1][w]=dp[i][w]
  return dp[N][W]
 
H,N = map(int,input().split())
 
weight=[]
value=[]
for i in range(N):
    n,a=input().split()
    weight.append(int(n))
    value.append(int(a))
a = knapsack(N,H,weight,value)
 
print(int(a))

### FIXED CODE ###

def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[inf for i in range(W+1)] for j in range(N+1)]
  dp[0][0]= 0
  #DP
  for i in range(N):
    for w in range(W+1):
      if 0 <= w-weight[i]: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=min(dp[i+1][w-weight[i]]+value[i], dp[i][w])
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
H,N = map(int,input().split())
 
weight=[]
value=[]
for i in range(N):
    n,a=input().split()
    weight.append(int(n))
    value.append(int(a))
MAX = max(weight)
dp = knapsack(N,H+MAX,weight,value)
 
print(min(dp[N][H:H+MAX]))
def main():
    n = int(input())
    s = input()
    res = 0
    r = []
    g = []
    b = []
    for i, c in enumerate(s):
        if c == 'R':
            r.append(i)
        elif c == 'G':
            g.append(i)
        else:
            b.append(i)
    
    cnt = 0
    for i in r:
        for j in g:
            diff = abs(j-i)
            for k in b:
                if abs(i-k) != diff and abs(j-k) != diff and abs(j-k) != abs(i-k):
                    cnt += 1
    print(cnt)
                    


if __name__ == '__main__':
    main()



### FIXED CODE ###

import numpy as np
from itertools import combinations

def main():
    k = int(input())
    res = 0
    memo = np.zeros((k+1, k+1), int)
    for i in range(1, k+1):
        for j in range(i, k+1):
            tmp = np.gcd(i,j)
            memo[i][j] = tmp
            memo[j][i] = tmp

    for i in range(1, k+1):
        res += i 

    for c in combinations(range(1,k+1),2):
        ab = memo[c[0], c[1]]
        res += ab * 6

    for c in combinations(range(1,k+1), 3):
        ab = memo[c[0], c[1]]
        abc = memo[ab, c[2]]
        res += abc * 6
    print(res)


if __name__ == '__main__':
    main()
n = input()
nl = [int(i) for i in n]
ns = sum(nl)
print(["No", "Yes"][n % ns == 0])

### FIXED CODE ###

n = input()
nl = [int(i) for i in n]
ns = sum(nl)
print(["No", "Yes"][int(n) % ns == 0])
s = input()
print(s[:(len(s)-8)]

### FIXED CODE ###

s = input()
print(s[:(len(s)-8)])
from sys import stdin
n,m = map(int,stdin.readline().rstrip().split())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
li = make_divisors(m)
for i in range(1,len(li)):
    if m//li[i] < n:
        point = li[i-1]
        break
print(point)

### FIXED CODE ###

from sys import stdin
n,m = map(int,stdin.readline().rstrip().split())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
li = make_divisors(m)
point = 1
if n == 1:
    print(m)
    exit()
for i in range(1,len(li)):
    if m//li[i] < n:
        point = li[i-1]
        break
print(point)
N = int(input())

colors = [0] * (N+1)
vertices = defaultdict(bool)
edges = defaultdict(dict)
for i in range(1, N):
    u, v, w = map(int, input().split())
    edges[u][v] = w % 2 == 0
    edges[v][u] = w % 2 == 0
    vertices[u] = False
    vertices[v] = False

queue = [(u, v)]
while len(queue) > 0:
    u, v = queue.pop(0)
    vertices[u] = True
    if vertices[v]:
        continue
    vertices[v] = True
    if colors[u] == colors[v] and not edges[u][v]:
        colors[v] = 1 - colors[u]

    for nv in edges[v].keys():
        if not vertices[nv]:
            queue.append((v, nv))

for i in range(1, N+1):
    print(colors[i])

### FIXED CODE ###

from collections import defaultdict

N = int(input())

colors = [0] * (N+1)
vertices = defaultdict(bool)
edges = defaultdict(dict)
for i in range(1, N):
    u, v, w = map(int, input().split())
    edges[u][v] = w % 2 == 0
    edges[v][u] = w % 2 == 0
    vertices[u] = False
    vertices[v] = False

queue = []
for v in edges[u].keys():
    queue.append((u, v))
vertices[u] = True

while len(queue) > 0:
    u, v = queue.pop(0)
    if vertices[v]:
        continue
    vertices[v] = True
    if colors[u] == colors[v]:
        if not edges[u][v]:
            colors[v] = 1 - colors[u]
    else:
        if edges[u][v]:
            colors[v] = colors[u]

    for nv in edges[v].keys():
        if not vertices[nv]:
            queue.append((v, nv))

for i in range(1, N+1):
    print(colors[i])
N,L=map(int,input().split())
a=list(range(N,N+L))
print(sum(a)-min(a,key=abs))

### FIXED CODE ###

N,L=map(int,input().split())
a=list(range(L,N+L))
print(sum(a)-min(a,key=abs))
<?php
//https://stackoverflow.com/questions/5506888/permutations-all-possible-sets-of-numbers

function pc_permute($items, $perms = array( )) {
    if (empty($items)) {
        // もう取り出すものがなければその時点の$permsが順列の一つなのでそのまま返却 
        $return = array($perms);
    } else {
        $return = array();
        // 並んでる数字を順番にみてく
        for ($i =  0; $i < count($items); $i++) {
            // 処理対象の配列と、組み合わせを保持してる変数を別変数にコピー
            // array_spliceなどは破壊的なメソッドなので退避しないと元配列が変更される
            $newitems = $items;
            $newperms = $perms;
            // インデックスが$iの値を$fooにとる。($newitemsからは削除される)
            list($foo) = array_splice($newitems, $i, 1);
            // 取り除いた値（$foo)を組み合わせの候補の先頭に持ってくる
            array_unshift($newperms, $foo);
            // 最終的に呼び出し元に返却する配列に追加する
            // 追加する配列は、一文字削ったあとの$newitems,
            // 現段階での組み合わせの$newpermsを引数に、再帰的に自分を呼び出した結果
            $return = array_merge($return, pc_permute($newitems, $newperms));
        }
    }
    return $return;
}


// ----------------------------------------------------
// こっから実際に解く
// ----------------------------------------------------

// 入力値の取得（int変換)
$N = intval(trim(fgets(STDIN)));
// 入力値の取得（配列化）
$P = explode(" ",fgets(STDIN));
$Q = explode(" ",fgets(STDIN));

// 順列の生成
$a = range(1,$N);
$perms = pc_permute($a);
sort($perms);

$p_index = -1;
$q_index = -1;

// 列挙した順列をfor文で確認していき、PとQの位置を確認する
for ($i=0; $i < count($perms); $i++){
  if ($perms[$i] == $P){
    $p_index = $i;
  }
  if ($perms[$i] == $Q){
    $q_index = $i;
  }
}

// 答えの計算
$ans = abs($p_index - $q_index);
echo $ans;


### FIXED CODE ###

import itertools

def main():
    N = int(input())
    
    P = list(map(int, input().split()))
    Q = list(map(int, input().split()))
    
    combi = list(itertools.permutations(range(1, N+1)))
    
    pi = 0
    qi = 0
    for i in range(len(combi)):
        if list(combi[i]) == P:
            pi = i + 1
        if list(combi[i]) == Q:
            qi = i + 1
            
            
    print(abs(qi - pi))
    
main()
"""
Match Matching
提出 #4299735 を参考に作成
"""


def solve():
    # 初期値の設定
    num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    # 丁度n本で作成できる最大桁数を格納する.
    # 初期値は -inf (丁度使い切ることは不可能) としておく
    dp = [-1 * float("inf")] * (N + 1)

    # 動的計画法で丁度n本のマッチを使うときに作れる最大桁数を計算する
    dp[0] = 0
    for a in A:
        if num[a] <= N:
            dp[num[a]] = 1
    
    for n in range(1, N + 1):
        for a in A:
            if n - num[a] >= 0:
                # マッチがnum[a]本あるときにaが作れるなら,
                # n - num[a]本の時よりも1桁多く作れるはず.
                # これをすべてのAに対して行い、その中で最大となった桁数を求める.
                dp[n] = max(dp[n], dp[n - num[a]] + 1)
    # print('各本数丁度で作れる最大桁数')
    # print(dp)

    # 回答となる数値を算出
    ans = ''
    for i in range(dp[N]):  # dp[N]桁の数を上位の桁から決定していく
        for a in A:
            # num[a]本使って数を作ったとき,
            # N - num[a] 本で作れる桁数よりも N 本で作れる桁数のほうが1多い場合,
            # numを作っても最終的に作れる数の桁数は変わらない.
            # そのため dp[N] - 1 == dp[N - num[a]] を満たすような最大のAを作り,
            # 作成する数の上位桁に使用すればよい.
            # 同じ本数のマッチを使用する場合はより大きい数を採用する.
            # そのためAはあらかじめ降順にソートしておく.
            if dp[N] - 1 == dp[N - num[a]]:
                ans += str(a)
                N -= num[a]
                break
        # print('現在の残本数', N, '採用された数', a)

    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

"""
Match Matching
提出 #4299735 を参考に作成
"""


def solve():
    # 初期値の設定
    num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    # 丁度n本で作成できる最大桁数を格納する.
    # 初期値は -inf (丁度使い切ることは不可能) としておく
    dp = [-1 * float("inf")] * (N + 1)

    # 動的計画法で丁度n本のマッチを使うときに作れる最大桁数を計算する
    dp[0] = 0
    for n in range(1, N + 1):
        for a in A:
            if n - num[a] >= 0:
                # マッチがnum[a]本あるときにaが作れるなら,
                # n - num[a]本の時よりも1桁多く作れるはず.
                # これをすべてのAに対して行い、その中で最大となった桁数を求める.
                dp[n] = max(dp[n], dp[n - num[a]] + 1)
    # print('各本数丁度で作れる最大桁数')
    # print(dp)

    # 回答となる数値を算出
    ans = ''
    for i in range(dp[N]):  # dp[N]桁の数を上位の桁から決定していく
        for a in A:
            # num[a]本使って数を作ったとき,
            # N - num[a] 本で作れる桁数よりも N 本で作れる桁数のほうが1多い場合,
            # numを作っても最終的に作れる数の桁数は変わらない.
            # そのため dp[N] - 1 == dp[N - num[a]] を満たすような最大のAを作り,
            # 作成する数の上位桁に使用すればよい.
            # 同じ本数のマッチを使用する場合はより大きい数を採用する.
            # そのためAはあらかじめ降順にソートしておく.
            # 最初の条件で配列外アクセスを防ぐ
            if N - num[a] > -1 and dp[N] - 1 == dp[N - num[a]]:
                ans += str(a)
                N -= num[a]
                break
        # print('現在の残本数', N, '採用された数', a)

    print(ans)


if __name__ == '__main__':
    solve()
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
#  = int(input())
n, k = map(int, input().split())
a = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

homon = [-1] * n

current = 0
st_loop = -1
for i in range(n): 
    if homon[current] == -1:
        homon[current] = i
        current = a[current] - 1
    else:
        #print(current)
        break

#print(homon)
nitta = len([t for t in homon if t != -1])
nltn = current
nlty = nitta - nltn

k -= nltn
print(homon.index(k%nlty) + 1)



### FIXED CODE ###

#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
#  = int(input())
n, k = map(int, input().split())
a = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

ord_ = [-1] * (n + 1)
s = []
v = 1
while ord_[v] == -1:
    ord_[v] = len(s)
    s.append(v)
    v = a[v-1]
c = len(s) - ord_[v]
l = ord_[v]

if k < l:
    print(s[k])
else:
    k -= l
    k %= c
    print(s[l+k])
def dfs(tree, n, ans):
    for i in tree[n]:
        ans[i] += ans[n]
        tree[i].remove(n)
        dfs(tree, i, ans)

n, q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n-1)]
px = [list(map(int,input().split())) for _ in range(q)]
 
g = [[] for _ in range(n)]

for i in range(n-1):
    g[ab[i][0]-1].append(ab[i][1]-1)
    g[ab[i][1]-1].append(ab[i][0]-1)

ans = [0]*n
for i in range(q):
    ans[px[i-1][0]-1] += px[i-1][1]
dfs(g, 0, ans)

print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
def dfs(tree, n, ans):
    for i in tree[n]:
        ans[i] += ans[n]
        tree[i].remove(n)
        dfs(tree, i, ans)
 
n, q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n-1)]
px = [list(map(int,input().split())) for _ in range(q)]
 
g = [[] for _ in range(n)]
for i in range(n-1):
    g[ab[i][0]-1].append(ab[i][1]-1)
    g[ab[i][1]-1].append(ab[i][0]-1)
 
ans = [0]*n
for i in range(q):
    ans[px[i-1][0]-1] += px[i-1][1]
dfs(g, 0, ans)
 
print(*ans)
n=int(input())
dat = list(map(int, input().split()))
dan = []
for e in dat:
    e = list(str(bin(e)))
    e.reverse()

re = 0
for e in dat:
     w=e.index('1')
     re=w
     
print(re)
     

 
      
      
             


    
    
     
                

         
           




### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
a = set([I() for _ in range(M)])
dp = [0]*(N+1) #1_indexed
dp[1] = 0 if 1 in a else 1
dp[2] = 0 if 2 in a else (1+dp[1])
for i in range(3,N+1):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = (dp[i-2]+dp[i-1])%1000000007
print(dp[-1])


### FIXED CODE ###

def main(N,M,a):
    dp = [-1]*N
    dp[0] = 1
    if N != 1:
        dp[1] = 2
    for i in a:
        if i == 1:
            dp[0] = 0
            dp[1] = 1
        else:
            dp[i-1] = 0
    for i in range(2,N):
        if dp[i] != 0:
            dp[i] = dp[i-1] + dp[i-2]
    return dp[-1]
N,M = map(int, input().split())
a = list(int(input()) for i in range(M))

print(main(N,M,a) % 1000000007)
import numpy as np

def sol():
    A,B,C,D,E,F = map(int, input().split(' '))
    na, nb, nc, nd = int(F/A/100),int(F/A/100),int(E*F/E/100),int(E*F/D/100) 
    sug = np.arange(0,nc).reshape(1,1,nc,1)*C+np.arange(0,nd).reshape(1,1,1,nd)*D
    wat = np.arange(0,na).reshape(na,1,1,1)*A*100+np.arange(0,nb).reshape(1,nb,1,1)*B*100
    tot =  wat + sug
    tot[0,0,0,0]=1
    dense = sug/tot*100
    maxi = np.argmax(dense[tot<F][dense[tot<F]<E])
    swat = (wat + np.ndarray((na,nb,nc,nd))*0)[tot<F][dense[tot<F]<E]
    ssug = (sug + np.ndarray((na,nb,nc,nd))*0)[tot<F][dense[tot<F]<E]
    print(swat[maxi],ssug[maxi])
    
sol()

### FIXED CODE ###

import numpy as np

def ceil(a):
    return int(np.ceil(a))

def sol2():
    A,B,C,D,E,F = map(int, input().split(' '))
    na, nb, nc, nd = ceil(F/A/100),ceil(F/B/100),ceil(E*F/C/100),ceil(E*F/D/100) 
    sug = np.arange(0,nc).reshape(1,1,nc,1)*C+np.arange(0,nd).reshape(1,1,1,nd)*D
    wat = np.arange(0,na).reshape(na,1,1,1)*A*100+np.arange(0,nb).reshape(1,nb,1,1)*B*100
    sug2=np.unique(sug[sug<=F*F/100])
    wat2=np.unique(wat[wat<=F])
    
    if len(wat2)==1:
        print(0,0)
        return
    elif E==0:
        print(wat2[1],0)
        return
    
    tot =  wat2[1:].reshape(len(wat2[1:]),1) + sug2
    e2 = E/(100+E)
    dense = (sug2/tot)[tot<=F]
    
    maxi = np.argmax(dense[dense<=e2])
    stot = tot[tot<=F][dense<=e2]
    ssug = (sug2 + tot*0)[tot<=F][dense<=e2]
    
    if dense[maxi] ==0:
        print(wat2[1],0)
    else:
        print(int(stot[maxi]),int(ssug[maxi]))
sol2()
N = int(input())
S, T = map(int,input().split())
for i in N:
    print(S + T)
    print(S[i] + T[i])

### FIXED CODE ###

N = int(input())
S, T = map(str,input().split())
for i in range(N):
     print(S[i] + T[i],end="")
a=int(input())
b=[]
if(a==0)print(0)
while a:
	b.append(a&1)
	a=int((a-(a&1))/(-2))
print(''.join(map(str,b)))

### FIXED CODE ###

a=int(input())
b=[]
if a==0:
	print(0)
while a:
	b.append(a&1)
	a-=a&1
	a=int(a/-2)

print(''.join(map(str,b[::-1])))
N = int(input())
A = [int(k) for k in input().split(' ')]

from collections import Counter 
import math 

res = [] # solution for each key in A
res_list = {} # solution for each value in A

# counter ver
A_c = Counter(A)
l = len(A_c)

def ncr(j):
  return math.factorial(j) // math.factorial(2) // math.factorial(j - 2) if j >= 2 else 0

# store ncr for each value 
combs = {k: ncr(v) for k, v in A_c.items()}

s = sum(combs.values())
  
for m in A_c.keys():
  res_list[m] = s - combs[m] + ncr(A_c[m] - 1)

for k in range(N):
  res.append(res_list[A[k]])
print('\n'.join([str(s) for s in res]))

### FIXED CODE ###

M, N = [int(k) for k in input().split(' ')]
import math 
res = 0

if N >= 2:
  res += (math.factorial(N) // math.factorial(2) // math.factorial(N - 2))

if M >= 2:
  res += (math.factorial(M) // math.factorial(2) // math.factorial(M - 2))

print(res)
n=int(input())
h=[]
for i in range(n):
     h.append(int(input()))
count=flag=0 
for i in range(n-1): 
      if(h[i]>=h[i+1]):
        flag+=1
      else :
        count=flag if(flag>count) else count
        flag=0
print(count)

### FIXED CODE ###

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

count = 0
count_list = [0]

for i in range(n-1):
	if(h[i+1] <= h[i]):
		count += 1
		count_list.append(count)
	else:
		count = 0

print(max(count_list))
s=sorted;print(['No','Yes'][s(input())<s(input(),reverse=1)])

### FIXED CODE ###

import math;a,b=map(int,input().split());print(math.ceil((a+b)/2))
from scipy.special import comb


def solve(string):
    n, k = map(int, string.split())
    ans = []
    for i in range(1, k + 1):
        base = comb(n - k + 1, i, exact=True)
        var = comb(k - 1, i - 1, exact=True)
        ans.append(str(base * var % (10**9 + 7)))
    return "\n".join(ans)


if __name__ == '__main__':
    print(solve(input()))


### FIXED CODE ###

from scipy.misc import comb


def solve(string):
    n, k = map(int, string.split())
    ans = []
    for i in range(1, k + 1):
        base = comb(n - k + 1, i, exact=True)
        var = comb(k - 1, i - 1, exact=True)
        ans.append(str(base * var % (10**9 + 7)))
    return "\n".join(ans)


if __name__ == '__main__':
    print(solve(input()))
w, h, x, y = list(map(int, input().split(" ")))

if w == 0 and y == 0:
	print(0,"0")
else:
	S = w*h/2.0
	if w%x == 0 and h%y == 0:
		print(S, "1")
	else:
		print(S, "0")

### FIXED CODE ###

w, h, x, y = list(map(int, input().split(" ")))

if x*2 == w  and y*2 == h:
	print(w*h/2.0, "1")
else:
	print(w*h/2.0, "0")