Harryxun/stf_run huggingface dataset:
def gost(lis,ky):
    
    lens=len(lis)
    
    if lens <= 5:
        print("key = "+str(ky)
        print(lis)
        if ky in lis:
            return True
        else:
            return False
    
    if ky <= lis[(lens//2)-1]:
        return gost(lis[:(lens//2)],ky)
    else:
        return gost(lis[(lens//2):],ky)
    

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

q = int(input())
a = input()
t=list(map(int,a.split()))


i = 0
for it in t:
    if gost(s,it):
        i = i+1
print(i)

### FIXED CODE ###

def gost(lis,ky,r,l):
    
    lens=l-r+1
    
    if lens <= 5:
        if ky in lis[r:l+1]:
            return True
        else:
            return False
    
    if ky <= lis[r+(lens//2)-1]:
        return gost(lis,ky,r,r+(lens//2)-1)
    else:
        return gost(lis,ky,r+(lens//2),l)
    

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

q = int(input())
a = input()
t=list(map(int,a.split()))


i = 0
for it in t:
    if gost(s,it,0,n-1):
        i = i+1
print(i)
n = int(input())
xy = [list(map(int,input())) for _ in range(n)]
max = 0
for xy1 in xy:
  for xy2 in xy:
    dis = abs(xy1[0]-xy2[0]) + abs(xy1[1]-xy2[1])
    if dis > max:
      max = dis
print(max)

### FIXED CODE ###

n = int(input())
xy = []
for _ in range(n):
    xy.append(list(map(int,input().split())))
a,b=xy[0]
m1=a+b
p1=xy[0]
m2=a-b
p2=xy[0]
p3=xy[0]
p4=xy[0]
m3=-a-b
m4=-a+b

for x,y in xy:
    if x+y > m1:
        m1=x+y
        p1 = [x,y]
    if x-y > m2:
        m2=x-y
        p2 = [x,y]
    if -x-y > m3:
        m3 = -x-y
        p3 = [x,y]
    if -x+y > m4:
        m4 = -x+y
        p4 = [x,y]
m = 0
for x0,y0 in [p1,p2,p3,p4]:
    for x1,y1 in [p1,p2,p3,p4]:
        dis=abs(x0-x1) + abs(y0-y1)
        if dis > m:
            m = dis
print(m)
MOD = 10**9 + 7
MAX = 5*10**5 + 1

fact = [0 for _ in range(MAX)]
factinv = [0 for _ in range(MAX)]

fact[0] = 1
for k in range(1, MAX):
    fact[k] = fact[k - 1]*k
    fact[k] %= MOD

factinv[MAX - 1] = pow(fact[MAX - 1], MOD - 2, MOD)
for k in range(MAX - 1, 0, -1):
    factinv[k - 1] = factinv[k]*k
    factinv[k - 1] %= MOD

def nCk(n, k):
    return fact[n]*factinv[k]*factinv[n - k] % MOD

def nPk(n, k):
    return fact[n]*factinv[n - k] % MOD

K = int(input())
S = input()
N = len(S)

ans = 0
for k in range(K + 1): ans += nCk(N + K - k - 1, N - 1)*pow(26, k, MOD)*pow(25, K - k, MOD) % MOD

print(ans)

### FIXED CODE ###

MOD = 10**9 + 7
MAX = 5*10**6 + 1

fact = [0 for _ in range(MAX)]
factinv = [0 for _ in range(MAX)]

fact[0] = 1
for k in range(1, MAX):
    fact[k] = fact[k - 1]*k
    fact[k] %= MOD

factinv[MAX - 1] = pow(fact[MAX - 1], MOD - 2, MOD)
for k in range(MAX - 1, 0, -1):
    factinv[k - 1] = factinv[k]*k
    factinv[k - 1] %= MOD

def nCk(n, k):
    return fact[n]*factinv[k]*factinv[n - k] % MOD

def nPk(n, k):
    return fact[n]*factinv[n - k] % MOD

K = int(input())
S = input()
N = len(S)

ans = 0
for k in range(K + 1):
    ans += nCk(N + K - k - 1, N - 1)*pow(26, k, MOD)*pow(25, K - k, MOD) % MOD
    ans %= MOD

print(ans)
def gcd(a, b):
    if (b == 0):
        return a
    return gcd(b, a % b)

input1 = list(map(int,input("").split(" ")))
A = list(map(int,input("").split(" ")))
N = input1[0]
K = input1[1]

temp = A[0]
for i in range(1,N):
	temp = gcd(temp,A[i])

if K <= max(A) and K % G == 0:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

### FIXED CODE ###

def gcd(a, b):
    if (b == 0):
        return a
    return gcd(b, a % b)

input1 = list(map(int,input("").split(" ")))
A = list(map(int,input("").split(" ")))
N = input1[0]
K = input1[1]

temp = A[0]
for i in range(1,N):
	temp = gcd(temp,A[i])

if K <= max(A) and K % temp == 0:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')
_ = input().strip()
kind_set = {}
colors = list(map(int, input().strip().split(' ')))

def whatcolor(rate):
  if rate < 400:
    return 0
  elif rate < 800:
    return 1
  elif rate < 1200:
    return 2
  elif rate < 1600:
    return 3
  elif rate < 2000:
    return 4
  elif rate < 2400:
    return 5
  elif rate < 2800:
    return 6
  elif rate < 3200:
    return 7
  else:
    return 'red'
  
for r in rates:
  color = whatcolor(r)
  if color == 'red':
    continue
  else:
    kind_set.add(color)

print(max(1, len(kind_set)))


### FIXED CODE ###

_ = input().strip()
kind_set = set()
rates = list(map(int, input().strip().split(' ')))

def whatcolor(rate):
  if rate < 400:
    return 0
  elif rate < 800:
    return 1
  elif rate < 1200:
    return 2
  elif rate < 1600:
    return 3
  elif rate < 2000:
    return 4
  elif rate < 2400:
    return 5
  elif rate < 2800:
    return 6
  elif rate < 3200:
    return 7
  else:
    return 'free'
  
free_n = 0
for r in rates:
  color = whatcolor(r)
  if color == 'free':
    free_n += 1
  else:
    kind_set.add(color)

ans_min = max(1, len(kind_set))
ans_max = len(kind_set) + free_n
print(ans_min, ans_max)
import math
import numpy

n , k = map(int, input().split())
a = list(map(int,input().split()))
a1=[0]*(n+1)
k = min(k,int(math.log2(n)*2.5))
for i in range(k):
    for j in range(n):
        st=j-a[j]
        gl=j+a[j]
        if st<0:
            st=0
        if gl>=n:
            gl=n-1
        a1[st]+=1
        a1[gl+1]-=1
    a1=numpy.cumsum(a1)
    a=a1[:n]
    a1=[0]*(n+1)
print(' '.join([str(n) for n in a]))


### FIXED CODE ###

import math
n , k = map(int, input().split())
a = list(map(int,input().split()))
a1=[0]*(n+1)
k = min(k,int(math.log2(n)*2.5))
for i in range(k):
    for j in range(n):
        st=j-a[j]
        gl=j+a[j]
        if st<0:
            st=0
        if gl>=n:
            gl=n-1
        a1[st]+=1
        a1[gl+1]-=1
    for k in range(1,n):
        a1[k]=a1[k-1]+a1[k]
    a=a1[:n]
    a1=[0]*(n+1)
print(' '.join([str(n) for n in a]))
N, M = map(int, input().split())
number = [0 for i in range(N)]
judge = []


for i in range(M):
    keta, num = map(int, input().split())
    keta -= 1
    judge.append(keta)

    if (len(judge) != len(set(judge))):
        ans = -1
    else:
        number[keta] = num

if (number[0] == 0):
    ans = -1
else:
    ans = str(number[0]) + str(number[1]) + str(number[2])
    ans=int(ans)

print(ans)

### FIXED CODE ###

N_keta, M_ko = map(int, input().split())
conditions = [list(map(int, input().split())) for i in range(M_ko)]

answers = []

for num in range(0, 10 ** N_keta):

    judge = True
    str_num = str(num)
    
    if (len(str_num) != N_keta):
        judge = False
        continue

    
    for i in range(M_ko):
        keta, n = conditions[i]
        keta -= 1

        if (keta + 1 > len(str_num)):
            judge = False
            break

        elif (str_num[keta] != str(n)):
            judge = False
            break
    
    if (judge):
        answers.append(num)

print(-1 if (len(answers) == 0) else min(answers))
s=input()
n=int(input())
rev=1

for i in range(n):
  q=input().split()
  if q[0]=='1':
    rev+=1
  elif (rev+int(q[1]))%2==0:
    s=q[2]+s
  else:
    s=s+q[2]
    
if rev%2==0:
  s.reverse()

print(s)

### FIXED CODE ###

s=input()
n=int(input())
rev=1
pre=''
suf=''

for i in range(n):
  q=input().split()
  if q[0]=='1':
    rev+=1
  elif (rev+int(q[1]))%2==0:
    pre=q[2]+pre
  else:
    suf=suf+q[2]
    
ans=pre+s+suf
  
if rev%2==0:
  print(ans[::-1])
else:
  print(ans)
#!/usr/bin/python3
# -*- coding:utf-8 -*-


def main():
  n, m = map(int, input().split())
  lxyz = [[0]*3 for _ in range(n)]
  for i in range(n):
    lxyz[i] = list(map(int, input().split()))
  
  def binary(x, k, t=1, f=0):
    return [t if (x >> ik)%2 else f for ik in range(k)]
  
  def calc_dp(lxyz):
    dp = [[0] * m for _ in range(n)]

    max_score = -(10 ** 15) 
    for i in range(n):
      max_score = max(lxyz[i], max_score)
      dp[i][0] = max_score
      
    for i in range(1, n):
      for j in range(1, m):
        if i == j == 0: 
          continue
        dp[i][j] = max(dp[i-1][j-1] + lxyz[i], dp[i-1][j])
    return dp[-1][-1]
    
  ans = -1
  for lh in [binary(i, 3, f=-1) for i in range(8)]:
    ans = max(ans, abs(calc_dp([sum(map(lambda x: x[0]*x[1], zip(lh, lxyz[i]))) for i in range(n)]))) 
  print(ans)
  
if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, m = map(int, input().split())
  lxyz = [[0]*3 for _ in range(n)]
  for i in range(n):
    lxyz[i] = list(map(int, input().split()))
  
  def binary(x, k, t=1, f=0):
    return [t if (x >> ik)%2 else f for ik in range(k)]
  
  ans = -1
  for lh in [binary(i, 3, f=-1) for i in range(8)]:
    ans = max(ans, abs(sum(sorted([sum(map(lambda x: x[0]*x[1], zip(lh, lxyz[i]))) for i in range(n)], reverse=True)[:m]))) 
  print(ans)
  
if __name__=='__main__':
  main()
N,K = map(int,input().split())
A = list(map(int,input().split()))

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

g = gcd(A[0],A[1])
for i in range(2,N):
    g = gcd(g,A[i])

if K%g==0 and K<=max(A):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

import sys
sys.setrecursionlimit(2000000)
N,K = map(int,input().split())
A = list(map(int,input().split()))
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)
if N ==1:
    g = A[0]
else:
    g = gcd(A[0],A[1])
    if N > 2:
        for i in range(2,N):
            g = gcd(g,A[i])
if K <= max(A) and K%g==0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


# show_flg = False
show_flg = True


def main():
    X, Y = MI()
    tmp = int(math.log2(Y/X))
    print(tmp + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###


from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


# show_flg = False
show_flg = True


def main():
    X, Y = MI()
    # tmp = math.log2(Y) - math.log2(X)
    # print(int(tmp) + 1)

    ans = 0
    c = X
    while c <= Y:
        c = c * 2
        ans += 1

    print(ans)



if __name__ == '__main__':
    main()
n,m=int(input())
if(n==m):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n,m=input().split()
if(n==m):
  print("Yes")
else:
  print("No")
A = input().split()

if A[0] == A[1] == A[2]:
  print("Yes"):
else:
  A = A[::-1]
  if A[0] == A[1] == A[2]:
    print("Yes"):
  else:
    print("No")

### FIXED CODE ###

A = input().strip()
if A[0] == A[1] == A[2] or A[1] == A[2] == A[3]:
    print("Yes")
else:
    print("No")
a, b, c, d = map(int, input().split())
ans = ''
if a + b + c + d == 7:
    ans = '{}+{}+{}+{}=7'
elif a - b + c + d == 7:
    ans = '{}-{}+{}+{}=7'
elif a + b - c + d == 7:
    ans = '{}+{}-{}+{}=7'
elif a + b + c - d == 7:
    ans = '{}+{}+{}-{}=7'
elif a - b - c + d == 7:
    ans = '{}-{}-{}+{}=7'
elif a + b - c - d == 7:
    ans = '{}+{}-{}-{}=7'
elif a - b + c - d == 7:
    ans = '{}-{}+{}-{}=7'
elif a - b - c - d == 7:
    ans = '{}-{}-{}-{}=7'
    
print(ans.format(a, b, c, d))

### FIXED CODE ###

a, b, c, d = map(int, input())
ans = ''
if a + b + c + d == 7:
    ans = '{}+{}+{}+{}=7'
elif a - b + c + d == 7:
    ans = '{}-{}+{}+{}=7'
elif a + b - c + d == 7:
    ans = '{}+{}-{}+{}=7'
elif a + b + c - d == 7:
    ans = '{}+{}+{}-{}=7'
elif a - b - c + d == 7:
    ans = '{}-{}-{}+{}=7'
elif a + b - c - d == 7:
    ans = '{}+{}-{}-{}=7'
elif a - b + c - d == 7:
    ans = '{}-{}+{}-{}=7'
elif a - b - c - d == 7:
    ans = '{}-{}-{}-{}=7'
    
print(ans.format(a, b, c, d))
import sys
from fractions import gcd

def main():
  s = input()
  t = input()
  sl = len(s)
  tl = len(t)


  def min_circ(a):
      for i in range(1, len(a)+1):
          if len(a) % i == 0:
              if a[:i] * (len(a)//i) == a:
                  return i


  tc = min_circ(t)
  if len(s) % tc == 0:
      if t[:tc]*(len(s)//min_circ(t)) == s:
          print(-1)
          sys.exit()


  s *= tl//sl + 5
  s *= 3

  sl = len(s)
  count = 0
  ans = 0

  r = 0
  while r + tl <= sl-1:
      if s[r:r+tl] == t:
          count += 1
          ans = max(ans, count)
          r += tl
      else:
          count = 0
          r += 1

  print(ans)

if __name__ == "__main__"
  main()

### FIXED CODE ###

import sys
import random
s = input()
t = input()
sl = len(s)
tl = len(t)

l = 0
r = 1500000//tl + 1
r2 = r
s *= 1499999//sl + 1
n = len(s)

base1 = 1007
mod1 = 10**9+7
modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
base1 = 1007
mod1 = 10**9+7
hash1 = [0]*(n+1)
power1 = [1]*(n+1)
for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1

def rolling_hash(i, j):
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1


while r - l > 1:
    m = l + (r-l)//2
    lt = len(t)*m
    hash2 = [0]*(lt+1)
    power2 = [1]*(lt+1)
    for i,e in enumerate(t*m):
        hash2[i+1] = (hash2[i]*base1 + ord(e))%mod1
        power2[i+1] = (power2[i]*base1)%mod1
    r_hash = hash2[-1]%mod1

    lt = len(t)*m
    flag = 0
    for i in range(len(s)-lt+1):
        if r_hash == rolling_hash(i, i+lt):
            flag = 1
            break

    if flag == 1:
        l = m
    else:
        r = m

if l*tl >= 1000000:
    print(-1)
else:
    print(l)
s= raw_input()
m = +float('inf')
for i in range(len(s)):
	if len(s[i:i+3]) == 3:
		m = min(abs(s[i:i+3] - 753), m)
	if len(s[i:i+4]) ==4:
		
		m = min(abs(s[i:i+4] - 753), m)
print m

### FIXED CODE ###


s= raw_input()
m = +float('inf')
for i in range(len(s)):
	if len(s[i:i + 3]) == 3: 
		m = min(abs(int(s[i:i + 3]) - 753), m)
print m
n,m=map(int,input().split())
li = []
h=list(map(int,input().split()))
for i in range(m):
    a,b=map(int,input().split())
    if h[a-1]=<h[b-1]:
        li.append(a)
    else:
        li.append(b)
print(n-len(set(li)))

### FIXED CODE ###

n,m=map(int,input().split())
li = []
h=list(map(int,input().split()))
for i in range(m):
    a,b=map(int,input().split())
    if h[a-1]<h[b-1]:
        li.append(a)
    elif h[a-1]==h[b-1]:
        li.append(a)
        li.append(b)
    else:
        li.append(b)
print(n-len(set(li)))
data = input().split()
 
a = int(data[0])
b = int(data[1])
 
pricea = a // 0.08
priceb = b // 0.1
 
if pricea == priceb:
  ans = pricea
elif pricea + 1 == priceb:
  ans = priceb
elif pricea == priceb + 1:
  ans = pricea
else:
  ans = -1
  
print(ans)


### FIXED CODE ###

com = input()
if com[0] == com[1] == com[2]:
  print("No")
else:
  print("Yes")
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

ans = [0] * max(A)
count = 0
for i in range(N):
    if ans[A[i]-1] == 0:
        ans[A[i]-1] = 1
        count += 1
    else:
        ans[A[i]-1] = 0
        count -= 1

print(count)

### FIXED CODE ###

N = int(input())

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

if N == 1:
    print(1)
    exit()

A.sort()

current_number = A[0]
current_count = 1
ans = 0

for i in range(1,N-1):
    if current_number == A[i]:
        current_count += 1
    else:
        current_number = A[i]
        if current_count % 2 != 0:
            ans += 1
        current_count = 1

if current_number == A[N-1]:
    current_count += 1
    if current_count % 2 != 0:
            ans += 1
else:
    if current_count % 2 != 0:
            ans += 1
    ans += 1
print(ans)
import typing
from typing import Deque, Set, Dict

class Island:
    def __init__(self, id: int) -> None:
        self.id: int = id
        self.connection: List['Island'] = []
        self.rank: int = 0
    
    def addConnection(self, other: 'Island') -> None:
        self.connection.append(other)
        other.connection.append(self)

    def setParent(self, other: 'Island') -> None:
        self.rank = other.rank +1

class Islands(Dict[int, Island]):
    def __init__(self, num: int):
        for id in range(1, num+1):
            self[id] = Island(id)

def bfs(root: Island, max_depth: int) -> None:
    root.setAsRoot()
    reserved: Deque[Island] = Deque([root])
    seen: Set[int] = {root.id}
    while len(reserved) != 0:
        current: Island = reserved.popleft()
        if current.rank > max_depth:
            break
        for connected in current.connection:
            if connected.id in seen:
                continue
            connected.setParent(current)
            seen.add(connected.id)
            reserved.append(connected)

def main() -> None:
    with open(0) as f:
        N, M = map(int, f.readline().split())
        ab = [map(int, line.split()) for line in f.readlines()]
    #諸島生成
    islands: Islands = Islands(N)
    #諸島間定期便生成
    for a, b in ab:
        islands[a].addConnection(islands[b])
    #bfs
    bfs(islands[1], 2)
    #出力
    print('POSSIBLE' if islands[N].rank in (1, 2) else 'IMPOSSIBLE')


if __name__ == '__main__':
    main()

### FIXED CODE ###

N, M = map(int, input().split())
graph = [[] for _ in range(N)] 
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def bfs(goal, graph, seen, next_v):
    for x in graph[next_v[0][0]]:
        if x == goal:
            return True
        if x in seen:
            continue
        next_v.append((x,next_v[0][1]+1))
        seen.add(x)
    return False


next_v = [(0,0)]
seen = {0}
#bfs
while True:
    if len(next_v) == 0 or next_v[0][1] == 2:
        ans = "IMPOSSIBLE"
        break
    if bfs(N-1, graph, seen, next_v):
        ans = "POSSIBLE"
        break
    next_v.pop(0)
print(ans)
a, b, x=map(int, input().split())
import math
if 2*x/(a*b)>=a:
  ans=a/(2*b-2*x/(a**2))
else:
  ans=2*x/(a*b**2)

print(math.degrees(math.atan(ans)))

### FIXED CODE ###

a, b, x=map(int, input().split())
if a*a*b==x:
  print(0)
  exit()
import math
if 2*x/(a*b)>=a:
  ans=a/(2*b-2*x/(a**2))
else:
  ans=2*x/(a*b**2)
print(90-math.degrees(math.atan(ans)))
a=['#'*(w+2)]
for i in range(h):
    b='#'+input()+'#'
    a.append(b)
a.append('#'*(w+2))
#print(a)

from collections import Counter

n=[(1,1)]
route={(1,1):0}
p=[[1,0],[0,1],[-1,0],[0,-1]]
count=1
while route.get((h,w),0)==0 and count != 10000:
    n2=[]
    #print(n,route)
    for i in n:
        for j in p:
            np=(i[0]+j[0],i[1]+j[1])
            if a[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                n2.append(np)
                if route.get(np,1000)>count:
                    route[np]=count
    n=n2
    #print(n,route)
    count+=1

    
a2=[]
for i in a:
    for j in range(len(i)):
        a2.append(i[j])
con=Counter(a2)


if count==10000:
    print('-1')
else:
    print(con['.']-route[(h,w)]-1)

### FIXED CODE ###

h, w =map(int, input().split())

a=['#'*(w+2)]
for i in range(h):
    b='#'+input()+'#'
    a.append(b)
a.append('#'*(w+2))
#print(a)

from collections import Counter

n=[(1,1)]
route={(1,1):0}
p=[[1,0],[0,1],[-1,0],[0,-1]]
count=1
while route.get((h,w),0)==0 and count != 10000:
    n2=[]
    #print(n,route)
    for i in n:
        for j in p:
            np=(i[0]+j[0],i[1]+j[1])
            if a[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                n2.append(np)
                if route.get(np,1000)>count:
                    route[np]=count
    n=n2
    #print(n,route)
    count+=1

    
a2=[]
for i in a:
    for j in range(len(i)):
        a2.append(i[j])
con=Counter(a2)


if count==10000:
    print('-1')
else:
    print(con['.']-route[(h,w)]-1)
import bisect
def put(a,b):
    l=max(len(a),len(b))
    a="0"*l+a
    b="0"*l+b
	s=""
    for i in range(-1,-l-1,-1):
      s+=a[i]+b[i]
    print(s[-1::-1])

def quad(i):
    s=""
    while i>0:
        s+=str(i%4)
        i//=4
    return s[-1::-1]

l=[0,1]
for i in range(1,18):
    l+=[4**i+j for j in l]

n=int(input())
for i in range(len(l)):
    if (n-l[i])%2==0:
        ind=bisect.bisect_left(l,(l[i]-n)//2)
        if l[i]-2*l[ind]==n:
            put(quad(l[i]),quad(l[ind]))
            break


### FIXED CODE ###

def f(n):
    s=""
    while n>0:
        s=str(n%2)+s
        n//=2
        if n==0:
            break
        if n%2==1:
            n+=2
            s="1"+s
        else:
            s="0"+s
        n//=2
    return s

n=int(input())
if n==0:
    print(0)
elif n<0:
    print(f(n*(-2))[:-1])
else:
    print(f(n))
while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    h = [0]
    for i in range(n):
        h.append(int(input()) + h[i])
    w = [0]
    for i in range(m):
        w.append(int(input()) + w[i])

    hList = [0] * 1000
    for i in range(n + 1):
        for j in range(i, n + 1):
            if i == j:
                continue
            else:
                hList[abs(h[i] - h[j])] += 1
    wList = [0] * 1000
    for i in range(m + 1):
        for j in range(i, m + 1):
            if i == j:
                continue
            else:
                wList[abs(w[i] - w[j])] += 1

    squareList = []
    for i in range(1000):
        squareList.append(hList[i] * wList[i])
    print(sum(squareList))


### FIXED CODE ###

while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    h = [0]
    for i in range(n):
        h.append(int(input()) + h[i])
    w = [0]
    for i in range(m):
        w.append(int(input()) + w[i])

    hDict = {}
    for i in range(n + 1):
        for j in range(i, n + 1):
            if i == j:
                continue
            else:
                diff = abs(h[i] - h[j])
                if diff in hDict:
                    hDict[diff] += 1
                else:
                    hDict[diff] = 1
    wDict = {}
    for i in range(m + 1):
        for j in range(i, m + 1):
            if i == j:
                continue
            else:
                diff = abs(w[i] - w[j])
                if diff in wDict:
                    wDict[diff] += 1
                else:
                    wDict[diff] = 1

    ans = 0
    for diff in hDict.keys():
        if diff in wDict:
            ans += hDict[diff] * wDict[diff]
    print(ans)