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

from sys import stdin
from collections import defaultdict
readline = stdin.readline



#readline = open('???.txt').readline

def main():
    v, e = map(int, readline().split())
    g = defaultdict(list)
    residual = [[0] * v for _ in range(v)]
    source, sink = 0, v - 1

    for _ in range(e):
        s, t, c = map(int, readline().split())
        if 0 < c:
            g[s].append(t)
            g[t].append(s)
            residual[s][t] = c

    capacity = sum(residual[source][i] for i in g[source])

    while True:
        route, flow = search(g, residual, source, sink)
        if route is None:
            break
        for i in range(1, len(route)):
            residual[route[i - 1]][route[i]] -= flow
            residual[route[i]][route[i - 1]] += flow
    print(capacity - sum(residual[source][i] for i in g[source]))

def search(g, residual, source, sink):
    dfs_stack = [(source, None, float('inf'))]
    route = [None]
    visited = set()
    while dfs_stack:
        u, prev, flow = dfs_stack.pop()
        while route[-1] != prev:
            route.pop()
        route.append(u)
        visited |= {u}
        if u == sink:
            return route[1:], flow
        for v in g[u]:
            if v in route:
                continue
            next_flow = min(residual[u][v], flow)
            if 0 < next_flow:
                dfs_stack.append((v, u, next_flow))
    return None, None
main()

### FIXED CODE ###

from sys import stdin
from collections import defaultdict
readline = stdin.readline


def main():
    v, e = map(int, readline().split())
    g = defaultdict(set)
    residual = [[0] * v for _ in range(v)]
    source, sink = 0, v - 1

    for _ in range(e):
        s, t, c = map(int, readline().split())
        if 0 < c and s != sink and t != source:
            g[s] |= {t}
            g[t] |= {s}
            residual[s][t] = c

    while True:
        route, flow = search(g, residual, source, sink)
        if not route:
            break
        for s, t in zip(route, route[1:]):
            residual[s][t] -= flow
            residual[t][s] += flow

    print(sum(residual[sink][i] for i in g[sink]))


def search(g, residual, source, sink):
    dfs_stack = [(source, None, float('inf'))]
    route = [None]
    visited = set()
    while dfs_stack:
        u, prev, flow = dfs_stack.pop()
        while route[-1] != prev:
            route.pop()
        route.append(u)
        visited |= {u}
        if u == sink:
            return route[1:], flow
        for v in g[u]:
            if v not in visited and 0 < residual[u][v]:
                dfs_stack.append((v, u, min(residual[u][v], flow)))
    return [], 0
main()
### BUGGY CODE ###

H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))

ans = float('inf')
anskouho = 0
h = -1
binhh = []
for j in range(2**(H-1)):
  h += 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  c = 0
  for k in range(len(binh)):
    if binh[k] == '1':
      c += 1
  binhh.append([binh, c])
binhh.sort(key = lambda x:x[1]) #, reverse= True)

for j in range(2**(H-1)):
  hlist=[]
  for k in range(H-1):
    if binhh[j][0][k] == '1':
      hlist.append(k)
  hlist.append(-1)
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      counter[0] += hsummation[now][hlist[0]]
      if counter[0] > K:
        anskouho += 1
        break
      for l in range(1, len(hlist)):
        counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
        if counter[l] > K:
          anskouho += 1
          break
      else:
        now += 1
        continue
      break
    if anskouho > ans:
      break
  else:
    ans = anskouho
print(ans)

### FIXED CODE ###

H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))
#print(hsummation)
ans = float('inf')
anskouho = 0
h = 2**(H-1)
for j in range(2**(H-1)):
  h -= 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  hlist=[]
  for k in range(H-1):
    if binh[-k-1] == '1':
      hlist.append(k)
  hlist.append(-1)
  #print(hlist)
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      for l in range(len(hlist)):
        if l == 0:
          counter[l] += hsummation[now][int(hlist[l])]
          continue
        else:
          counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
      if max(counter) > K:
        anskouho += 1
        break
      else:
        now += 1
    if anskouho > ans:
      break
  else:
    ans = min(ans, anskouho)
 
      #print(counter)
#print(anskouho)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0

for i in range(N-1):
    while A[i] > A[i+1]:
        A[i + 1] = A[i + 1] + 1
        count = count + 1
print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(1,N):
    if A[i-1] > A[i]:
        count += A[i-1] - A[i]
        A[i] = A[i - 1]
print(count)
### BUGGY CODE ###

n=int(input())
a_list=list(map(int, input().split()))
multi_sum=1
LIMIT=10**18

if 0 not in a_list:
    for a_i in a_list:
        multi_sum*=a_i
else:
    multi_sum=0
if multi_sum > LIMIT:
    multi_sum=-1
print(multi_sum)



### FIXED CODE ###

n=int(input())
a_list=list(map(int, input().split()))
multi_sum=1
LIMIT=1000000000000000000

if 0 not in a_list:
    for a_i in a_list:
        multi_sum*=a_i
        if multi_sum > LIMIT:
            multi_sum=-1
            break
else:
    multi_sum=0

print(multi_sum)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
    if i-1 not in a and i-2 not in a:
        dp[i]=dp[i-1]+dp[i-2]
    elif i-1 in a and i-2 not in a:
        dp[i]=dp[i-2]
    elif i-1 not in a and i-2 in a:
        dp[i]=dp[i-1]
    elif i-1 in a and i-2 in a:
        dp[i]=0
print(dp[n]%1000000007)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
b=[]
for i in range(m):
    b.append(int(input()))
a=set(b)
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for i in range(2,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%1000000007)
### BUGGY CODE ###

n = int(raw_input())
d = map(int,raw_input().split(" "))
m = int(raw_input())
t = map(int,raw_input().split(" "))

dic = {}

for a in t:
  if a not in dic:
    dic[a]=1
  else:
    dic[a] += 1

for a in dic:
  if dic[a] > d.count(a):
    print "NO"
    exit(0)

print "YES"


### FIXED CODE ###

n = int(raw_input())
d = sorted(map(int,raw_input().split(" ")))
m = int(raw_input())
t = sorted(map(int,raw_input().split(" ")))

dic = {}
dic2 = {}

for a in t:
  if a not in dic:
    dic[a]=1
  else:
    dic[a] += 1

for a in d:
  if a not in dic2:
    dic2[a]=1
  else:
    dic2[a] += 1

for a in dic:
  if a not in dic2:
    print "NO"
    exit(0)
  if dic[a] > dic2[a]:
    print "NO"
    exit(0)

print "YES"
### BUGGY CODE ###

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

lower_a = list(map(lambda x: x - 1, a))
upper_a = list(map(lambda x: x + 1, a))

temp_max = 0
for k in range(min(a) -1, max(a) + 2):
    cnt = 0
    for lower, upper in zip(lower_a, upper_a):
        if lower <= k <= upper:
            cnt += 1
    temp_max = max(temp_max, cnt)
print(temp_max)

### FIXED CODE ###

import collections

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

lower_a = list(map(lambda x: x - 1, a))
upper_a = list(map(lambda x: x + 1, a))
extended_a = collections.Counter(a + lower_a + upper_a)

print(extended_a.most_common()[0][1])
### BUGGY CODE ###

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

count = 0
for i in range(0,n-2):
  ii = s[i]
  for j in range(i+1, n-1):
    jj = s[j]
    for k in range(j+1,n):
      kk=s[k]
      if j-i != k-j:
        if ii != jj and jj != kk and kk!=ii:
          count = count + 1
print(count)


### FIXED CODE ###

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

count = 0
r=0
g=0
b=0
for i in range(0,n):
  if s[i] == 'R':
    r = r + 1
  if s[i]=='G':
    g = g+1
  if s[i]=='B':
    b = b+1
    
for i in range(0,n):
  ii = s[i]
  for j in range(i+1, n):
    jj = s[j]
    if ii==jj:
      continue
    if (2*j-i)<=(n-1):
      if ii!=s[2*j-i] and jj!=s[2*j-i]:
        count = count + 1
print(r*g*b-count)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from collections import deque
H, W, K = mapint()
y1, x1, y2, x2 = mapint()
query = [list(str(input())) for _ in range(H)]
dirc = [(0, 1), (-1, 0), (0, -1), (1, 0)]

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

queue = deque([(y1-1, x1-1, 0)])
def bfs(queue):
    while queue:
        y, x, cnt = queue.popleft()
        if y==y2-1 and x==x2-1:
            return cnt
        if checked[y][x]==1:
            continue
        checked[y][x]=1
        for dy, dx in dirc:
            for i in range(1, K+1):
                ny, nx = y+(dy*i), x+(dx*i)
                if ny>=H or ny<0 or nx>=W or nx<0:
                    continue
                if query[ny][nx]=='@':
                    break
                if not checked[ny][nx]:
                    queue.append((ny, nx, cnt+1))
    return -1

print(bfs(queue))

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from collections import deque
inf = 10**18
H, W, K = mapint()
y1, x1, y2, x2 = mapint()
query = [list(str(input())) for _ in range(H)]
dirc = [(0, 1), (-1, 0), (0, -1), (1, 0)]

checked = [[-1]*W for _ in range(H)]
checked[y1-1][x1-1] = 0

queue = deque([(y1-1, x1-1)])
def bfs(queue):
    while queue:
        y, x = queue.popleft()
        if y==y2-1 and x==x2-1:
            return checked[y][x]
        for dy, dx in dirc:
            for i in range(1, K+1):
                ny, nx = y+(dy*i), x+(dx*i)
                if ny>=H or ny<0 or nx>=W or nx<0:
                    continue
                if query[ny][nx]=='@':
                    break
                if checked[ny][nx]<0:
                    checked[ny][nx] = checked[y][x]+1
                    queue.append((ny, nx))
                elif checked[ny][nx]<=checked[y][x]:
                    break
    return -1

print(bfs(queue))
### BUGGY CODE ###

N,P = map(int,input().split())
if N == 1:
    print(P)
else:
    for i in range(int(P**(0.5))+1,0,-1):
        if P%(i**N) == 0:
            print(i)
            break

### FIXED CODE ###

from collections import Counter
N,P = map(int,input().split())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
p = Counter(prime_factorize(P))
ans = 1
for k,v in p.items():
    if v >= N:
        ans *= k**(v//N)
print(ans)
### BUGGY CODE ###

import  heapq

n,m,s,t=map(int,raw_input().split())
src = [ tuple( map( int, raw_input().split() ) )   for i in range(m)]

nl=[ [ ] for j in range(n+1) ] 

for u,v,a,b in src:
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heapq.heappush(Q,v)

	while Q:
		u=heapq.heappop(Q)
		for i in nl[u]:
			v=i[0]
			yen=i[1]
			sunuku=i[2]
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heapq.heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

### FIXED CODE ###

import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)
### BUGGY CODE ###

# C - Tsundoku
import sys
sys.setrecursionlimit(10**9)

N, M, K = map(int, input().split())
A = list(int(a) for a in input().split())
B = list(int(b) for b in input().split())
la = len(A)
lb = len(B)
T = 0
r = 0
ans = 0
def dfs(i, j, T, r):
    global ans
    ans = max(ans, r)
    if i < la and T+A[i] <= K:
        dfs(i+1, j, T+A[i], r+1)
    if j < lb and T+B[j] <= K:
        dfs(i, j+1, T+B[j], r+1)
    return

dfs(0, 0, T, 0)
print(ans)

### FIXED CODE ###

# C - Tsundoku

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

Asum = [0]
for i in range(N):
    Asum.append(Asum[i] + A[i])

Bsum = [0]
for j in range(M):
    Bsum.append(Bsum[j] + B[j])

ans = 0
for i in range(N+1):
    if Asum[i] > K:
        continue
    tmp = K - Asum[i]
    j = bisect.bisect_right(Bsum, tmp) - 1
    ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

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

k = int(input())

cnt = [[str(i)] for i in range(10)]

d = 2
# from functools import reduce
total = 9
while total < 10 ** 5:
    new_cnt = [[] for i in range(10)]
    for i in range(10):
        if i - 1 >= 0:
            new_cnt[i].append(str(i) + cnt[i - 1][-1])
        if i + 1 < 10:
            new_cnt[i].append(str(i) + cnt[i + 1][-1])
        new_cnt[i].append(str(i) + cnt[i][-1])

        if i != 0:
            total += len(new_cnt[i])
    for i in range(10):
        cnt[i] += new_cnt[i]

ans = sorted(map(int, sum(cnt[1:10], [])))
print(ans[k - 1])



### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

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

k = int(input())


import queue
q = queue.Queue()

for i in range(1, 10):
    q.put(i)

if k <= 9:
    print(k)
    exit()

total = 9
while total <= k:
    x = q.get()
    if x % 10 != 0:
        val = x * 10 + x % 10 - 1
        q.put(val)
        total += 1
        if total == k:
            print(val)
            exit()

    val = x * 10 + x % 10
    q.put(val)
    total += 1
    if total == k:
        print(val)
        exit()
    if x % 10 < 9:
        val = x * 10 + x % 10 + 1
        q.put(val)
        total += 1
        if total == k:
            print(val)
            exit()
    
    if total >= k:
        for i in range(total - k):
            q.get()
        print(q.get())
        exit()
### BUGGY CODE ###

mod = 10**9 + 7

n, m = list(map(int, input().split()))
a = [int(input()) for _ in range(m)]

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

print(dp[n] % mod)


### FIXED CODE ###

mod = 10**9 + 7

n, m = list(map(int, input().split()))
a = set([int(input()) for _ in range(m)])

dp = {}
for i in range(n + 1):
    dp[i] = 1
dp[1] = 0 if 1 in a else 1
for i in range(2, n + 1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = dp[i - 1] % mod + dp[i - 2] % mod
        dp[i] %= mod

print(dp[n] % mod)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
LR=[list(map(int,input().split())) for i in range(Q)]
for i in range(Q):
  l=LR[i][0]-1
  r=LR[i][1]-1
  ans=0
  s=S[l:r+1]
  
  print(s.count("AC"))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
LR=[list(map(int,input().split())) for i in range(Q)]
I = [0 for i in range(N)]
for i in range(N-1):
  if S[i]=="A" and S[i+1]=="C":
    I[i+1]=I[i]+1
  else:
    I[i+1]=I[i]
      
for i in range(Q):
  l=LR[i][0]-1
  r=LR[i][1]-1
  print(I[r]-I[l])
### BUGGY CODE ###

import bisect, heapq
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

for i in range(1,N+1):
    a = bisect.bisect_right(A,i) - bisect.bisect_left(A,i)
    b = bisect.bisect_right(B,i) - bisect.bisect_left(B,i)

    if a + b > N:
        print("No")
        exit()

new_B = B[::-1]

for i in range(N):
    if A[i] == new_B[i]:
        for j in range(N):
            if A[j] != new_B[i] and new_B[j] != A[i]:
                new_B[i], new_B[j] = new_B[j], new_B[i]

print("Yes")
for b in new_B:
    print(b,end=" ")
print("")

### FIXED CODE ###

import bisect, heapq
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

for i in range(1,N+1):
    a = bisect.bisect_right(A,i) - bisect.bisect_left(A,i)
    b = bisect.bisect_right(B,i) - bisect.bisect_left(B,i)

    if a + b > N:
        print("No")
        exit()

B = B[::-1]

j, bef = 0, -1
for i in range(N):
    if A[i] != bef:
        j = 0
    if A[i] == B[i]:
        while j < N:
            if A[j] != B[i] and B[j] != A[i]:
                B[i], B[j] = B[j], B[i]
                break
            j += 1
    bef = A[i]

print("Yes")
for b in B:
    print(b,end=" ")
print("")
### BUGGY CODE ###

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

n = int(input())
l = [int(i) for i in input().split()]

count = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if l[i] + l[j] > l[k] and l[j] + l[k] > l[i] and l[k] + l[i] > l[j]:
                count += 1

print(count)


### FIXED CODE ###

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

import bisect

n = int(input())
l = [int(i) for i in input().split()]
l.sort() # 二分探索するために整列

# l[i]+l[j]>l[x]を満たすxは
# 昇順に整列した配列を使うと
# 固定した2本の次のインデックスから必ず連続している
# そのため条件を満たす最大のxを二分探索で求めれば良い

count = 0
# 2本を固定して
for i in range(n-2):
    for j in range(i+1, n-1):
        # 3本目を探索
        index = bisect.bisect_left(l, l[i]+l[j])
        count += index - (j+1)

print(count)
### BUGGY CODE ###

#D - Friends
N,M = map(int,input().split())
par = [i for i in range(N+1)]

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]

def size(x):
    return par.count(find(x))

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    if par[x] > par[y]:
        x,y = y,x
    #par[x] += par[y]
    par[y] = x
#    par[x] = y

#print(par)
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    unite(a,b)
#    print(par)

group_count = 0

for i in range(N):
    group_count = max(group_count,size(i))

# 出力
print(group_count)


### FIXED CODE ###

#D - Friends
N,M = map(int,input().split())
par = [i for i in range(N)]
rank = [1] * (N)

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]

def size(x):
    return par.count(find(x))

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y : return 0
    if par[x] > par[y]:
        x,y = y,x
    par[y] = x
#    par[x] = x
    if par[x] == par[y]:
        rank[x] += rank[y]
#        rank[y] += rank[x]
#print(par)
#print(rank)
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    unite(a,b)
#    print(par)
#    print(rank)
group_count = 0

group_count = max(rank)

# 出力
print(group_count)
### BUGGY CODE ###

N, M = list(map(int, input().split(' ')))
A = list(map(int, input().split(' ')))
A.sort(reverse=True)

for k in range(M):
    A[0] //= 2
    A.sort(reverse=True)
print(sum(A))

### FIXED CODE ###

N, M = list(map(int, input().split(' ')))
A = list(map(int, input().split(' ')))
A_ = [-1 * num for num in A]

import heapq
import math

heapq.heapify(A_)

for k in range(M):
    maxA_ = heapq.heappop(A_)
    heapq.heappush(A_, math.ceil(maxA_ / 2))
    #print(maxA_, math.ceil(maxA_ / 2))
    #print(A_)
print(sum(A_) * (-1))
### BUGGY CODE ###

s = input()
total = 0

while '01' in s or '10' in s:

  s = s.replace('01', 'x').replace('10', 'x')
  total += s.count('x') * 2
  s = s.replace('x', '')
  
print(total)


### FIXED CODE ###

s = input()
total = 0

count_0 = s.count('0') * 2
count_1 = s.count('1') * 2

if count_0 < count_1:
  print(count_0)
else:
  print(count_1)
### BUGGY CODE ###

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

ans = sum([1 for tmp_t in T if tmp_t in S])

print(ans)

### FIXED CODE ###

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

ans = 0
for tmp_t in T:
    left = 0
    right = n
    while(left<right):
        mid = (left + right)//2
        if S[mid]==tmp_t:
            ans += 1
            break
        elif S[mid]>tmp_t:
            right = mid
        else:
            left = mid+1

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

N = int(input())
As = list(map(int, input().split()))
modNum = 10**9 + 7
sum = 0
for d in range(60):
	n1 = 0
	for A in As:
		if (A >> d) & 1 == 1:
			n1 += 1
	sum += (2 ** d) * n1 * (N - n1)
print(sum % modNum)

### FIXED CODE ###

import numpy as np
N = int(input())
As = np.array(list(map(int, input().split())))
modNum = 10**9 + 7
sum = 0
for d in range(60):
	n1 = np.count_nonzero((As >> d) & 1 == 1)
	sum += (2 ** d) * n1 * (N - n1)
print(sum % modNum)
### BUGGY CODE ###

from collections import defaultdict

s = list(input())
n = len(s)
k = int(input())

part = set()
for i in range(n):
    for j in range(i, n):
        part.add("".join(s[i:j+1]))

print(sorted(part)[k-1])


### FIXED CODE ###

s = list(input())
n = len(s)
k = int(input())

part = set()
for i in range(n):
    for j in range(k):
        part.add("".join(s[i:i+j+1]))

print(sorted(part)[k-1])
### BUGGY CODE ###

import sys
import numpy
from collections import deque
sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

childsof = {i:deque([]) for i in range(N+1)}

for _ in range(N-1):
    u,v,w = list(map(int, input().split()))
    childsof[u].append((v,w))
    childsof[v].append((u,w))

distances = numpy.full(N+1, -1, dtype=numpy.int32)
distances[1] = 0

def dfs(i):
    childs = childsof[i]

    for c in childs:
        j = c[0]
        if distances[j] == -1:
            distances[j] = distances[i] + c[1]
            dfs(j)

dfs(1)

for d in distances[1:]:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)


### FIXED CODE ###

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

import sys
#import numpy
#from collections import deque
sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

childsof = [[] for _ in range(N+1)]

for _ in range(N-1):
    u,v,w = list(map(int, input().split()))
    childsof[u].append((v,w))
    childsof[v].append((u,w))

distances = [-1]*(N+1)
distances[1] = 0

def dfs(i):
    childs = childsof[i]

    for c in childs:
        j = c[0]
        if distances[j] == -1:
            distances[j] = distances[i] + c[1]
            dfs(j)

dfs(1)

for d in distances[1:]:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)