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


p = 10**9+7
kai_ = [1]
for i in range(1, 10 ** 6 * 2):
    kai_.append(kai_[-1] * i % p)


def kai(x):
    return kai_[x]


def comb(a, b):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai(a)
    c *= pow(kai(b), p - 2, p)
    c *= pow(kai(a - b), p - 2, p)
    return c % p


r1, c1, r2, c2 = [int(i) for i in input().split()]


def s(r, c):
    a = 0
    for i in range(1, r + 1):
        a += comb(i + c + 1, c)
        a %= p
    return a


print((s(r2, c2) - s(r2, c1 - 1) - s(r1 - 1, c2) + s(r1 - 1, c1 - 1)) % p)


### FIXED CODE ###


p = 10**9+7
kai_ = [1]
for i in range(1, 10 ** 7):
    kai_.append(kai_[-1] * i % p)


def kai(x):
    return kai_[x]


def comb(a, b):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai(a)
    c *= pow(kai(b), p - 2, p)
    c *= pow(kai(a - b), p - 2, p)
    return c % p


r1, c1, r2, c2 = [int(i) for i in input().split()]


def s(r, c):
    return comb(r+c+2,r+1)


print((s(r2, c2) - s(r2, c1 - 1) - s(r1 - 1, c2) + s(r1 - 1, c1 - 1)) % p)
### BUGGY CODE ###

k,s=input().split()
K=int(k)
S=int(s)
count =0
for p in range(K+1):
    for q in range(K+1):
        for r in range(K+1):
            if p+q+r==S:
                count += 1
print(count)                
                



### FIXED CODE ###

k,s=input().split()
K=int(k)
S=int(s)
count =0
for p in range(K+1):
    for q in range(K+1):
        r=S-p-q
        if 0<=r and r<=K:
            count +=1
print(count)
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    max_A = max(A)
    dp = [float("inf")] * (H + max_A)
    dp[0] = 0
    for h in range(1, H + max_A):
        dp[h] = min(dp[max(0, h-a)]+b for a, b in zip(A, B))
    ans = min(dp[H:])
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

INF = float("inf")


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


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

n = int(input())
List = [input() for i in range(n)]

mydict = {}

for i in range(n):
    if List[i] in mydict.keys():
        mydict[List[i]] += 1
    else:
        mydict[List[i]] = 1
        
#sortdict = sorted(mydict.items(), reverse=True) 
res = [kv[0] for kv in mydict.items() if kv[1] == max(mydict.values())]


#print(sortdict)
res = sorted(res)
leng = len(res)
for i in range(leng):
    print(res[i])

### FIXED CODE ###

import collections

n = int(input())
List = [input() for i in range(n)]
res = []

c = collections.Counter(List)
m = 0
for v in c.values():
  m = max(m, v)
  
for k, v in c.items():
  if v == m:
    res.append(k)
    
res.sort()
for i in range(len(res)):
  print(res[i])
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
if len(a) == 1:
    ans = a[0] * (0.5) ** m
    print(int(ans))
    exit()
for i in range(m):
    a[a.index(max(a))] = a[a.index(max(a))] // 2
print(sum(a)) 

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
a = list(map(int,input().split()))
a = [ -i for i in a ]
heapq.heapify(a)

for i in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))
print(-sum(a))
### BUGGY CODE ###

n = int(input())
a = [0] * (n+1)
for i in range(n):
    a[i+1] = list(map(int, input().split()))
todo = [0] * (n+1)
days = 0
while True:
    update = []
    for i in range(1, n+1):
        if todo[i] < n - 1 and i not in update:
            p = a[i][todo[i]]
            if a[p][todo[p]] == i:
                update.append(i)
    for j in update:
        todo[j] += 1
    days += 1
    #print(todo)
    if update == []:
        days = -1
        break
    elif todo[1:] == [n - 1] * n:
        break
print(days)

### FIXED CODE ###

n = int(input())
a = []
for _ in range(n+1):
    a.append([-1])
for i in range(n):
    inp = list(map(int, input().split()))
    for j in range(n-2, -1, -1):
        a[i+1].append(inp[j])
matched = [i for i in range(1, n+1)]
finish = 0
days = 0
while True:
    used = set()
    while matched != []:
        i = matched.pop()
        p = a[i][-1]
        if p != -1 and a[p][-1] == i and (i not in used) and (p not in used) :
            a[i].pop()
            a[p].pop()
            used.add(i)
            used.add(p)
            if a[i][-1] == -1:
                finish += 1
            if a[p][-1] == -1:
                finish += 1
    days += 1
    matched = list(used)
    if len(used) == 0:
        days = -1
        break
    elif finish == n:
        break
print(days)
### BUGGY CODE ###

class TrieTree:
    def __init__(self):
        self.flag = 0
        self.next = [None, None, None, None]

def judge(c):
    if c == "A":
        return 0
    elif c == "C":
        return 1
    elif c == "G":
        return 2
    else:
        return 3

def find(key, trie):

    if(len(key)>=1):
        index = judge(key[0])
	if(trie.next[index]!=None):
            find(key[1:], trie.next[index])
        else:
            print("no")
    else:
        if(trie.flag):
            print("yes")
        else:
            print("no")

def insert(key, trie):
    if(len(key)>=1):
        index = judge(key[0])
        if(trie.next[index]!=None):
            insert(key[1:], trie.next[index])
        else:
            trie.next[index] = TrieTree()
            insert(key[1:], trie.next[index])
    else:
	trie.flag = 1

if __name__ == "__main__":

    root = TrieTree()
    n = int(raw_input())
    for i in range(n):
        com = raw_input().split()
        if(com[0][0] == "i"):
            insert(com[1], root)
        else:
            find(com[1], root)

### FIXED CODE ###

n = input()
table =	set()

for i in range(n):
    com	= raw_input().split()
    if(com[0][0] == "i"):
	table.add(com[1])
    else:
	if com[1] in table:
            print("yes")
	else:
            print("no")
### BUGGY CODE ###

H,W = map(int,input().split())
A = []
B_place = []
for i in range(H):
  a = list(input())
  for w in range(W):
    if a[w]=="#":
      B_place.append([i,w])
  A.append(a)
ans = 0
for h in range(H):
  for w in range(W):
    if A[h][w]==".":
      cou = 10**10  
      for B in B_place:
        s = abs(h-B[0])+abs(w-B[1])
        cou = min(cou,s)
      ans = max(ans,cou)
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
S = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            S[h][w] = H*W
for h in range(H):
    a = 0
    for w in range(W):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for w in range(W)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
for w in range(W):
    a = 0
    for h in range(H):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for h in range(H)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
ans = H*W
for h in range(H):
    for w in range(W):
        ans = min(ans,S[h][w])
print(H*W-ans)
### BUGGY CODE ###

from bisect import bisect

n = int(input())
a = sorted(map(int, input().split()))
b = sorted(map(int, input().split()))
c = sorted(map(int, input().split()))
ab = [bisect(b, ai) for ai in a]
bc = [bisect(c, bi) for bi in b]
cnt = 0
for bi in ab:
    if bi == n:
        continue
    for i in range(bi, n):
        if bc[i] == n:
            continue
        cnt += n - bc[i]
print(cnt)

### FIXED CODE ###

from bisect import bisect_left, bisect_right

n = int(input())
a = sorted(map(int, input().split()))
b = sorted(map(int, input().split()))
c = sorted(map(int, input().split()))
ba = [bisect_left(a, bi) for bi in b]
bc = [bisect_right(c, bi) for bi in b]
cnt = 0
for i in range(n):
    cnt += ba[i] * (n - bc[i])
print(cnt)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
mod = (10 ** 9) + 7
max_a = max(a)
ans = 0
for j in range(len(bin(max(a))) - 2):
    t = sum([1 & i for i in a]) 
    ans += (2 ** j) * t * (n - t)
    a = [i >> 1 for i in a]
    ans = ans % mod
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
mod = (10 ** 9) + 7
max_a = max(a)
ans = 0
for j in range(len(bin(max(a))) - 2):
    t = sum([1 & i for i in a]) 
    ans += (2 ** j) * t * (n - t)
    a = [i >> 1 for i in a]
    ans = ans % mod
print(ans)
### BUGGY CODE ###

k,s = list(map(int, input().split()))
count = 0
for i in range(0, k + 1):
    for j in range(0, k + 1):
        for k in range(0, k + 1):
            if i + j + k == s:
                count += 1
print(count)

### FIXED CODE ###

k, s = list(map(int, input().split()))
count = 0
for i in range(0, k + 1):  # X value
    for j in range(0, k + 1):  # Y value
        if 0 <= s - i - j <= k:  # s - i - j = Z
            count += 1
print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
suma = 0
for i in range(N-1):
    for j in range(i+1,N):
        if A[i] != A[j]:
            suma += (A[i]^A[j])%(10**9+7)
print(suma%(10**9+7))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
suma = 0
maxa = max(A)
bin = format(maxa,'b')
for i in range(len(bin)):
    count1 = 0
    for j in range(N):
        if (A[j] >> i) & 1 == 1:
            count1 += 1
    suma = (suma+(N-count1)*count1*((2**i))%(10**9+7))%(10**9+7)
print(suma)
### BUGGY CODE ###

N, M, *X = map(int, open(0).read().split())
A = []
for a in zip(*[iter(X)]*M):
  A.append(a)
log = set(range(1,M+1))
ans = []
while log:
  dic = {}
  for i in range(N):
    for j in range(M):
      if A[i][j] in log:
        dic[A[i][j]] = dic.get(A[i][j],0)+1
        break
  ans.append(max(dic.values()))
  c = max(dic.keys(),key=lambda x:dic[x])
  log.remove(c)
print(min(ans))

### FIXED CODE ###

N, M, *X = map(int, open(0).read().split())
A = []
for a in zip(*[iter(X)]*M):
  A.append(a)
log = set(range(1,M+1))
ans = []
while log:
  dic = {}
  for i in range(N):
    for j in range(M):
      if A[i][j] in log:
        dic[A[i][j]] = dic.get(A[i][j],0)+1
        break
  ans.append(max(dic.values()))
  c = max(dic.keys(),key=lambda x:dic[x])
  log.remove(c)
print(min(ans))
### BUGGY CODE ###

n, q = map(int, input().split())


class Node:
    def __init__(self, index):
        self.index = index
        self.point = 0

    def updatePoints(self, point):
        self.point += point

nodes = [Node(i) for i in range(1, n + 1)]


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


def selectNode(p):
    selected = [p]
    parent = []
    for a, b in edges:
        if a == p:
            selected.append(b)
            parent.append(b)
    while parent != []:
        for pnode in parent:
            for a, b in edges:
                if pnode == a:
                    selected.append(b)
            parent.remove(pnode)

    return selected

for _ in range(q):
    p, x = map(int, input().split())
    node_index_list = selectNode(p)
    for idx, node in enumerate(nodes):
        if idx + 1 in node_index_list:
            node.updatePoints(x)

print(*(node.point for node in nodes))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())

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

values = [0]*n
for _ in range(q):
    p, x = map(int, input().split())
    values[p-1] += x

def dfs(v1, parent, add):
    values[v1] += add
    for v2 in graph[v1]:
        if v2 == parent:
            continue
        dfs(v2, v1, values[v1])

dfs(0, 0, 0)
print(*values)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


n, m = map(int, readline().split())
a = list(map(int, read().split()))

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
for i in range(2, n + 1):
    if i not in a:
        dp[i] = dp[i - 1] + dp[i - 2]

print(dp[-1]%(10**9+7))

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7

n, m = map(int, readline().split())
a = set(map(int, read().split()))

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
cnt = 0
for i in range(2, n + 1):
    if i not in a:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
        cnt = 0
    else:
        cnt += 1
        if cnt == 2:
            print('0')
            exit()
print(dp[n])
### BUGGY CODE ###

N = int(input())
H = [int(n) for n in input().split()]

max_count = 0
for i in range(N):
    count = 0
    for j in range(0, N-i-1):
        if H[i+j+1] <= H[i+j]:
            count += 1
        else:
            max_count = max(max_count, count)
            break
    else:
        max_count = max(max_count, count)
print(max_count)

### FIXED CODE ###

N = int(input())
H = [int(n) for n in input().split()]
reached = [False] * N 

max_count = 0
for i in range(N):
    if reached[i] == True:
        continue
    else:
        count = 0
        for j in range(0, N-i-1):
            if H[i+j+1] <= H[i+j]:
                count += 1
                reached[i+j+1] = True
            else:
                max_count = max(max_count, count)
                break
        else:
            max_count = max(max_count, count)
print(max_count)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
N = int(input())
S = list(input())
Q = int(input())
D = {chr(ord('a') + i): [] for i in range(26)}
for i, s in enumerate(S):
    D[s].append(i)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1]), query[2]
        i -= 1
        s = S[i]
        if s == x:
            continue
        D[s].remove(i)
        ni = bisect_left(D[x], i)
        D[x].insert(ni, i)
        S[i] = x
    else:
        l, r = int(query[1]), int(query[2])
        l -= 1
        r -= 1
        ans = 0
        for i in range(26):
            s = chr(ord('a') + i)
            li = bisect_left(D[s], l)
            ri = bisect_right(D[s], r)
            if ri - li > 0:
                ans += 1
        print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right
N = int(input())
S = list(input())
Q = int(input())
D = {chr(ord('a') + i): [] for i in range(26)}
for i, s in enumerate(S):
    D[s].append(i)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1]), query[2]
        i -= 1
        s = S[i]
        if s == x:
            continue
        D[s].remove(i)
        ni = bisect_left(D[x], i)
        D[x].insert(ni, i)
        S[i] = x
    else:
        l, r = int(query[1]), int(query[2])
        l -= 1
        r -= 1
        ans = 0
        for i in range(26):
            s = chr(ord('a') + i)
            li = bisect_left(D[s], l)
            ri = bisect_right(D[s], r)
            if ri - li > 0:
                ans += 1
        print(ans)
### BUGGY CODE ###

INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
 
def dfs(x, y, m):
    if y > N :
        return 0
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]
 
while True:
    N, M = map(int, input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    mem = [[[INF for i in range(M + 1)] for j in range(N + 1)] for k in range(N + 4)]
    import sys
    sys.stdout.write(str((dfs(0, 0, M))) + "\n")

### FIXED CODE ###

INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
 
def dfs(x, y, m):
    if y > N :
        return 0
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]
 
while True:
    N, M = map(int, raw_input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, raw_input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    mem = [[[INF for i in range(M + 1)] for j in range(N + 1)] for k in range(N + 4)]
    print(dfs(0, 0, M))
### BUGGY CODE ###

n = int(input())
mylist = []
for _ in range(n):
    s = input()
    s_list = [ c for c in s]
    mylist.append("".join(sorted(s_list)))

myset = set(mylist)
mylist2 = list(myset)

ans=0
for i in range(len(mylist2)):
    count = mylist.count(mylist2[i])
    mylist3 = list(range(count))
    ans += sum(mylist3)
    mylist.remove(mylist2[i])

print(ans)


### FIXED CODE ###

n = int(input())
i = 0
sortedSet = {}
while i < n:
    temp = ''.join(sorted(input()))

    if temp in sortedSet:
        sortedSet[temp]+=1
    else:
        sortedSet[temp]=1
    i += 1

result = 0
for v in sortedSet.values():
    result = int(result + v*(v-1)/2)

print(result)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
dp = [10 ** 10] * N
dp[0] = 0
for i in range(1, N):
    for j in range(1, K + 1):
        if i - j < 0:
            break
        dp[i] = min(dp[i], dp[i - j] + abs(H[i - j] - H[i]))
print(dp[-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N , K = map(int,input().split())
h = list(map(int,input().split()))
inf = float('inf')
dp = [inf] * N
if K == 1:
    ans = 0
    for i in range(N - 1):
        ans += abs(h[i + 1] - h[i])
    print(ans)
    exit()

for i in range(N):
    if i == 0:
        min_cost = 0
    elif i == 1:
        min_cost = abs(h[1] - h[0])
    else:
        current = h[i]
        tmp_min = min(abs(current - h[i - K]) + dp[i - K] , abs(current - h[i - K + 1]) + dp[i - K + 1])
        for j in range(K - 2):
            tmp_min = min(abs(current - h[i - K + 2 + j]) + dp[i - K + 2 + j], tmp_min)
        min_cost = tmp_min
    dp[i] = min_cost
#print(dp)
print(dp[N - 1])
### BUGGY CODE ###

import heapq

N = int(input())
nb = [[] for _ in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    nb[a].append((c, b))
    nb[b].append((c, a))
for x in nb:
    x.sort()

Q, K = map(int, input().split())
K -= 1

dist = [2 ** 62] * N
visited = set()
h = [(0, K, -1)]
while h:
    d0, node, parent = heapq.heappop(h)
    if node in visited:
        continue
    visited.add(node)
    dist[node] = d0
    for d1, child in nb[node]:
        if child != parent and d0 + d1 < dist[child]:
            heapq.heappush(h, (d0 + d1, child, node))

for i in range(Q):
    x, y = map(int, input().split())
    # print(f"{x}->K = {dist[x]}, K->{y} = {dist[y]}")
    print(dist[x - 1] + dist[y - 1])


### FIXED CODE ###

import sys
import heapq

input = sys.stdin.readline


def main():

    N = int(input())
    nb = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        nb[a].append((c, b))
        nb[b].append((c, a))
    for x in nb:
        x.sort()

    Q, K = map(int, input().split())
    K -= 1

    dist = [2 ** 62] * N
    h = [(0, K, -1)]
    while h:
        d0, node, parent = heapq.heappop(h)
        if d0 >= dist[node]:
            continue
        dist[node] = d0
        for d1, child in nb[node]:
            if child != parent and d0 + d1 < dist[child]:
                heapq.heappush(h, (d0 + d1, child, node))

    for i in range(Q):
        x, y = map(int, input().split())
        # print(f"{x}->K = {dist[x]}, K->{y} = {dist[y]}")
        print(dist[x - 1] + dist[y - 1])


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

import sys
import heapq
import copy

n = int(input())
a = []

for _ in range(n):
	a.append(-1 * int(input()))

for i in range(n):
	b = copy.deepcopy(a)
	heapq.heapify(b)
	maximum = heapq.heappop(b)
	if maximum == a[i]:
		print(heapq.heappop(b) * (-1))
	else:
		print(maximum * (-1))


### FIXED CODE ###

import sys
import heapq
import copy

n = int(input())
a = []

for _ in range(n):
	a.append(-1 * int(input()))

b = copy.deepcopy(a)
heapq.heapify(b)

for i in range(n):
	maximum = heapq.heappop(b)
	if maximum == a[i]:
		tmp = maximum
		maximum = heapq.heappop(b)
		print(maximum * (-1))
		heapq.heappush(b,tmp)
	else:
		print(maximum * (-1))
	heapq.heappush(b,maximum)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

m = 1
j = 0

if 0 in AS:
    print(0)
    j = 1

for i in AS:
    m = m * i
    if m > 10**18 and j == 0:
        print(-1)
        j = 1
        break
    elif m == 0:
        break
    else:
        continue

if j == 0:
    print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

m = 1
j = 0

if 0 in AS:
    print(0)
    j = 1
    

if j == 0:
    for i in AS:
        m = m * i
        if m > 10**18 and j == 0:
            print(-1)
            j = 1
            break
        elif m == 0:
            break
        else:
            continue

if j == 0:
    print(m)
### BUGGY CODE ###

s = input()
t=s

while("01" in t or "10" in t):
	t = t.replace("01","")
	t = t.replace("10","")
print(len(s)-len(t))

### FIXED CODE ###

s = input()
x=0
for i in s:
	if(i=='0'):x+=1
	elif(i=='1'):x-=1

print(len(s)-abs(x))
### BUGGY CODE ###

S=input()
Q=int(input())
import sys
from collections import deque

lis=[]
d=deque()
for _ in S:
  lis.append(_)

for _ in range(Q):
  s = list(sys.stdin.readline())
  if s[0]=="1":
    lis=lis[::-1]
  else:
    if s[2]=="1":
      d=deque(lis)
      d.appendleft(s[4])
      lis=list(d)
    else:
      lis.append(s[4])
      
print("".join(lis))

### FIXED CODE ###

S=input()
Q=int(input())
import sys
from collections import deque
d=deque()
for _ in S:
  d.append(_)
flag=False

for _ in range(Q):
  s = list(sys.stdin.readline())
  if s[0]=="1":
    if flag:
      flag=False
    else:
      flag=True
  else:
    if s[2]=="1":
      if flag:
        d.append(s[4])
      else:
        d.appendleft(s[4])
    else:
      if flag:
        d.appendleft(s[4])
      else:
        d.append(s[4])
      
if flag:
  d.reverse()
  
print("".join(d))
### BUGGY CODE ###

s = input()
n = len(s)
c = []
ci = ""
nowR = True
nowL = False
for i in range(n-1):
  if s[i] != s[i+1]:
    ci += s[i]
    c.append(ci)
    ci = ""
  else:
    ci += s[i]
ci += "L"
c.append(ci)
cnt = [0]*n
j = -1
for i in range(len(c)):
  if i % 2 == 0:
    # R
    cil = len(c[i])
    j += cil
    cnt[j] += cil - cil//2
    cnt[j+1] += cil//2
  else:
    # L
    cil = len(c[i])
    cnt[j] += cil//2
    cnt[j+1] += cil - cil//2
    j += cil
print(*cnt)
    

### FIXED CODE ###

s = input()
n = len(s)
c = []
ci = ""
nowR = True
nowL = False
for i in range(n-1):
  if s[i] != s[i+1]:
    ci += s[i]
    c.append(ci)
    ci = ""
  else:
    ci += s[i]
ci += "L"
c.append(ci)
cnt = [0]*n
j = -1
for i in range(len(c)):
  if i % 2 == 0:
    # R
    cil = len(c[i])
    j += cil
    cnt[j] += cil - cil//2
    cnt[j+1] += cil//2
  else:
    # L
    cil = len(c[i])
    cnt[j] += cil//2
    cnt[j+1] += cil - cil//2
    j += cil
print(*cnt)