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

from bisect import bisect_left as bl
from bisect import bisect_right as br
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    l = [[] for i in range(30)]
    b.sort()
    for i in range(29):
        mod = 2**(i+1)
        for j in b:
            l[i].append(j%mod)
        l[i].sort()

    ans = [0]*30

    for i in a:
        
        for j in range(29):
            mod = pow(2,j)
            x = i%(mod*2)
            ans[j] += br(l[j],2*mod-x-1)-bl(l[j],mod-x)+n-bl(l[j],3*mod-x)
            
    count = 0
    for i in range(30):
        count += pow(2,i)*(ans[i]%2)
    print(count)

if __name__ =="__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline


n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
l = [[] for i in range(29)]
for i in range(29):
    mod = 2**(i+1)
    for j in b:
        l[i].append(j%mod)
    l[i].sort()

ans = 0
for i in range(29):
    al = []
    count = 0
    mod = 2**i
    for j in a:
        al.append(j%(2*mod))
    al.sort(reverse = True)
    r1 = r2 = r3 = 0
    for j in al:
        while r1 < n and l[i][r1]+j < mod:
            r1 += 1
        while r2 < n and l[i][r2]+j < 2*mod:
            r2 += 1
        while r3 < n and l[i][r3]+j < 3*mod:
            r3 += 1
        count += n-r3+r2-r1
    ans += (count%2) << i
print(ans)
### BUGGY CODE ###

import bisect
n = int(input())
list_A = list(map(int, input().split()))
list_B = list(map(int, input().split()))
list_C = list(map(int, input().split()))
list_A.sort()
list_B.sort()
list_C.sort()
ans = 0
list_U = []
list_D = []

for i in range(n):
    b = list_B[i]
    index = bisect.bisect_left(list_A, b)
    list_U.append(index)

for i in range(n):
    c = list_C[i]
    index = bisect.bisect_left(list_B, c)
    list_D.append(index)

for i in range(n):
    j = list_D[i]
    for k in range(j):
        ans += list_U[k]

print(ans)

### FIXED CODE ###

n = int(input())
list_A = list(map(int, input().split()))
list_B = list(map(int, input().split()))
list_C = list(map(int, input().split()))
list_A.sort()
list_B.sort()
list_C.sort()
b = 0
list_UP = []
for i in range(n):
    while True:
        if b > n-1 or list_A[i] < list_B[b]:
            break
        b += 1
    list_UP.append(n-b)


c = 0
list_DOWN = []
for i in range(n):
    while True:
        if c > n-1 or list_B[i] < list_C[c]:
            break
        c += 1
    list_DOWN.append(n-c)


ans = 0
num = 0
sum_value = sum(list_DOWN)
for i in list_UP:
    while True:
        if num == n-i:
            break
        sum_value -= list_DOWN[num]
        num += 1
    ans += sum_value

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

N=int(input())
A=list(map(int,input().split()))
L=sorted(A)
l=[]
for i in L:
    if L.count(i)==1:
        l.append(i)
for i in l:
    for j in l[l.index(i)+1:]:
        if j%i==0:
            l.pop(l.index(j))
        else:
            None
print(len(l))



    
















        


























            
    


    


    
    














    


    














### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
Amax=A[-1]
dp=[True]*(Amax+1)
ans=0
for i in range(N-1):
    p=A[i]
    if dp[p]:
        for j in range(1,Amax//p+1):
            dp[p*j]=False
        if p!=A[i+1]:
            ans+=1
if dp[Amax]:
    ans+=1
print(ans)
### BUGGY CODE ###

N=input()
d=list(map(int, input().strip().split()))
ans=0

for i in range(int(max(d)+1)):
    ABC=0
    ARC=0
    for j in range(int(N)):

        if d[j]<i:
            ABC+=1
        else:
            ARC+=1

    if ARC==ABC:
        ans+=1

print(ans)


### FIXED CODE ###

N=int(input())
d=list(map(int, input().strip().split()))
ans=0

d.sort()

#for i in range(int(d[int(N/2)-1]),int(d[int(N/2)]+1)):

print(int(d[int(N/2)])-int(d[int(N/2)-1]))
### BUGGY CODE ###

#!/usr/bin/python
# coding: UTF-8

def main():
    A,B,M = list(map(int, input().split(' ')))

    a_list = list(map(int, input().split(' ')))
    b_list = list(map(int, input().split(' ')))

    dic = {}
    for i in range(A):
        dic[i]={}
    for i in range(A):
        for j in range(B):
            dic[i][j] = 0


    price_list = 2*10**5
    for i in range(M):
        temp = list(map(int, input().split(' ')))
        if price_list > a_list[temp[0]-1] + b_list[temp[1]-1] - temp[2]:
            price_list = a_list[temp[0]-1] + b_list[temp[1]-1] - temp[2]

    lower = min(a_list) + min(b_list)
    if lower < price_list:
        print(lower)
    else:
        print(price_list)

if __name__=='__main__':
    main()


### FIXED CODE ###

#!/usr/bin/python
# coding: UTF-8

def main():
    A,B,M = list(map(int, input().split(' ')))

    a_list = list(map(int, input().split(' ')))
    b_list = list(map(int, input().split(' ')))


    price_list = 2*10**5
    for i in range(M):
        temp = list(map(int, input().split(' ')))
        if price_list > a_list[temp[0]-1] + b_list[temp[1]-1] - temp[2]:
            price_list = a_list[temp[0]-1] + b_list[temp[1]-1] - temp[2]

    lower = min(a_list) + min(b_list)
    if lower < price_list:
        print(lower)
    else:
        print(price_list)

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

#!/usr/bin/env python3

def main():
    N, M = map(int, input().split())
    Card = [[] for i in range(M)]
    Diff = [i for i in range(1, N + 1)]

    for i in range(0, M):
        L, R = map(int, input().split())
        for j in range(L, R + 1):
            Card[i].append(j)
        Diff = list(set(Diff) & set(Card[i]))
    print(len(Diff))


main()

### FIXED CODE ###

#!/usr/bin/env python3

def main():
    N, M = map(int, input().split())
    L =[0 for i in range(M)]
    R = [0 for i in range(M)]

    for i in range(0, M):
        L[i], R[i] = map(int, input().split())
    
    print(max(min(R) - max(L) + 1, 0))


main()
### BUGGY CODE ###

S=input()
T=input()


def search():
    pos=0
    now=""
    for t in T:
        if t in S:
            if not t in now:
                now+=S
            ind=now.index(t)+1
            now=now[ind:]
            pos+=ind
        else:
            return -1
    return pos

print(search())

### FIXED CODE ###

import collections
import bisect
S = input()
T = input()
N = len(S)

d = collections.defaultdict(list)
for i, s in enumerate(S):
    d[s].append(i + 1)

ans = 0
end = 0
isOK = True
i = 0

for t in T:
    if len(d[t]) == 0:
        isOK = False
        break
    dic = d[t]
    idx = bisect.bisect_right(dic, i)
    if len(dic) == idx:
        i = dic[0]
        end += 1
    else:
        i = dic[idx]

if isOK:
    ans = N * end + i
else:
    ans = -1

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

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

s = [[i for i in list(str(input()))] for i in range(h)]

board_w = [[0 for i in range(w)] for i in range(h)]
board_h = [[0 for i in range(h)] for i in range(w)]

# 横、縦の順に走査
for i in range(h):
    cnt_continue = 0
    for j, c in enumerate(s[i]):
        if c == ".":
            cnt_continue += 1
        elif cnt_continue > 0:
            for k in range(1, cnt_continue+1):
                board_w[i][j-k] = cnt_continue
            cnt_continue = 0
    for k in range(cnt_continue):
        board_w[i][w-1-k] = cnt_continue
    cnt_continue = 0

s = list(map(list, zip(*s)))

for i in range(w):
    cnt_continue = 0
    for j, c in enumerate(s[i]):
        if c == ".":
            cnt_continue += 1
        elif cnt_continue > 0:
            for k in range(1, cnt_continue+1):
                board_h[i][j-k] = cnt_continue
            cnt_continue = 0
    for k in range(cnt_continue):
        board_h[i][h-1-k] = cnt_continue
    cnt_continue = 0

board_h = list(map(list, zip(*board_h)))
ans = 0

for i in range(h):
    for j in range(w):
        v = int(board_w[i][j]) + int(board_h[i][j])
        ans = max(ans, v)

print(ans-1)


### FIXED CODE ###

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

s = [input() for i in range(h)]

board_w = [[0 for _ in range(w)] for _ in range(h)]
board_h = [[0 for _ in range(w)] for _ in range(h)]

# 右、左、上、下の順に走査
for i in range(h):
    cnt_continue = 0
    for j in range(w):
        if s[i][j] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board_w[i][j] = cnt_continue

    for j in reversed(range(w-1)):
        if board_w[i][j] == 0:
            continue
        board_w[i][j] = max(board_w[i][j], board_w[i][j+1])

for i in range(w):
    cnt_continue = 0
    for j in range(h):
        if s[j][i] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board_h[j][i] = cnt_continue

    for j in reversed(range(h-1)):
        if board_h[j][i] == 0:
            continue
        board_h[j][i] = max(board_h[j][i], board_h[j+1][i])


ans = 0

for i in range(h):
    for j in range(w):
        v = board_w[i][j] + board_h[i][j] - 1
        ans = max(ans, v)

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

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

ans = 0

for i in range(N):
    for j in range(i+1,N):
        ans += A[i]*A[j]

ans = ans % (10**9+7)
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
a = 10**9+7
sumA = sum(A)

ans = 0

for i in range(N):
    sumA -= A[i]
    ans += A[i] * sumA
    ans %= a
    
print(ans)
### BUGGY CODE ###

import collections
N,K = map(int, input().split())
A = list(map(int, input().split()))
List = {}
for i in A:
    if List.get(i,None)==None:
        List[i]=1
    else:
        List[i]+=1

List_sorted = sorted(List.items(), key=lambda x:x[1])
tmp=0
Num=len(List_sorted)-K

for i in range(Num):
    tmp+=list(List_sorted[0])[1]
    del List_sorted[0]

print(tmp)


### FIXED CODE ###

import heapq

N,K=map(int,input().split())
A=list(map(int,input().split()))
l=[0]*max(A)
ans=0
for item in A:
    l[item-1]+=1
    
heapq.heapify(l)

while len(l)>K:
    ans+=heapq.heappop(l)
    
print(ans)
### BUGGY CODE ###

# D - I hate Factorization

X = int(input())
fact = []
for i in range(10**5):
    fact.append(pow(i,5))

for i in range(10**5):
    for j in range(10**5):
        if fact[i]-fact[j]==X:
            print(i, j)
            break
        elif fact[i]+fact[j]==X:
            print(i, -j)
            break
    else:
        continue
    break




### FIXED CODE ###

# D - I hate Factorization

X = int(input())
fact = []
for i in range(300):
    fact.append(pow(i,5))

for i in range(300):
    for j in range(300):
        if fact[i]-fact[j]==X:
            print(i, j)
            break
        elif fact[i]+fact[j]==X:
            print(i, -j)
            break
    else:
        continue
    break
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

BC.sort(key=lambda x:x[1],reverse=True)

R=[]
n=0
for i in BC:
    R = R+[i[1]]*i[0]
    n = n + i[0]
    if n >= N:
        break

R=sorted(A+R, reverse=True)[:N]
print(sum(R))



### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

A.sort(reverse=True)
BC.sort(key=lambda x:x[1],reverse=True)

R=[]
n=0
for i in range(M):
    R.extend([BC[i][1]]*BC[i][0])
    n = n + BC[i][0]
    if n >= N:
        break

R=sorted(A+R, reverse=True)[:N]
print(sum(R))
### BUGGY CODE ###

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

for i, alst in enumerate(a_lst):
    if i == 0:
        b = alst
    else:
        b = b * alst

if b > 1000000000000000000:
    print('-1')
else:
    print(b)

### FIXED CODE ###

N = int(input())
A= list(map(int, input().split()))
result=1
if 0 in A:
    result = 0
else:
    for t in range(N):
        result *= A[t]
        if result > 10 ** 18:
            result = -1
            break
print(result)
### BUGGY CODE ###

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

total = 1
for a in li:
    total *= a
    if a == 0:
        total = 0
        break
    elif 10 ** 18 < total:
        total = -1


  
print(total)

### FIXED CODE ###

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

total = 1
li.sort()
for a in li:
    if a == 0:
        total = 0
        break
    total *= a
    if 10 ** 18 < total:
        total = -1
        break
print(total)
### BUGGY CODE ###

N = int(input())

for n in range(1,N+1):
  ans = 0
  check = False
  for x in range(1,n):
    for y in range(x,n):
      for z in range(y,n):
        if (x**2 + y**2 + z**2 + x*y + y*z + z*x) == n:
          if x == y and y == x and z == x:
            ans += 1
          elif x == y  or z == x or y == z:
            ans += 3
          elif x != y and y != z and z != x:
            ans += 6
          check = True
          break
      if check:
        break
    if check:
      break
  print(ans)

### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10001)]

for i in range(1,101):
  for j in range(1,101):
    for k in range(1,101):
      v = i*i + j*j + k*k + i*j + j*k + k*i
      if v < 10001:
        ans[v] += 1

for i in range(n):
  print(ans[i+1])
### BUGGY CODE ###

n= int(input())
s = {}

for _ in range(n):
    t = input()
    s.setdefault(t, 1)
    s[t] += 1

max_k_list = [kv[0] for kv in s.items() if kv[1] == max(s.values())]

max_k_list.sort()

for i in range(len(max_k_list)):
    print(max_k_list[i])

### FIXED CODE ###

n= int(input())
s = {}

for _ in range(n):
    t = input()
    s.setdefault(t, 1)
    s[t] += 1

ans = []
m = max(s.values())
for k, v in s.items():
    if v == m:
        ans.append(k)

for m in sorted(ans):
    print(m)
### BUGGY CODE ###

n, m = map(int, input().split())
H = list(map(int, input().split()))
R = [[0]*n for _ in range(n)]
G = [1]*n 

for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  if H[a]>=H[b]:
    G[b] = 0
  if H[b]>=H[a]:
    G[a] = 0
  
print(sum(G))

### FIXED CODE ###

n, m = map(int, input().split())
H = list(map(int, input().split()))
G = [1]*n 

import sys

for i in range(m):
  a, b = map(int, sys.stdin.readline().rstrip().split())
  a -= 1
  b -= 1
  if H[a]>=H[b]:
    G[b] = 0
  if H[b]>=H[a]:
    G[a] = 0
  
print(sum(G))
### BUGGY CODE ###

N = int(input())
input_v_list = list(map(int, input().split()))

cnt = 0             # 出力の個数
check_list = []     # 比較用リスト

# 比較用リストに一つずつ値をセット
for i in input_v_list:
    check_list.append(i)
    min_var = min(check_list)
    # i <= min のとき個数をカウント
    if(i <= min_var):
        cnt += 1

# 出力
print(cnt)

### FIXED CODE ###

N = int(input())
input_v_list = list(map(int, input().split()))

cnt = 0             # 出力の個数
min_var = 2 * 10**6 # 最小値(初期値2*10^5以上)

# 比較用リストに一つずつ値をセット
for i in input_v_list:
    
    # 最小値更新
    if(min_var > i):
        min_var = i

    # i <= min のとき個数をカウント
    if(i <= min_var):
        cnt += 1

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

import numpy as np
import sys
input=sys.stdin.readline

n,k=map(int,input().split())
p=np.array(list(map(int,input().split())))
p=(p+1.)/2.
max_p=0

for i in range(n-k+1):
    s=np.sum(p[i:i+k])
    if  max_p < s:
        max_p=s

print(max_p)

### FIXED CODE ###

#import numpy as np
import sys
input=sys.stdin.readline

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

#p=np.array(list(map(int,input().split())))
func=lambda x: ((int(x)+1.)/2.)
p=list(map(func,input().split()))

#p=(p+1.)/2.
s=sum(p[0:k])
max_p=s

#for i in range(n-k+1):
for i in range(n-k):
    #s=np.sum(p[i:i+k])
    s=s-p[i]+p[i+k]
    if  max_p < s:
        max_p=s

print(max_p)
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())[:-1]
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
class node():
    def __init__(self):
        self.value = 0
        self.ans=""
value = [[0]*(m+1) for i in range(n+1)]
ans = [[""]*(m+1) for i in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
            ans[i + 1][j + 1] = "".join([ans[i][j], s[i]])
        elif value[i][j + 1] > value[i + 1][j]: #UP
            ans[i + 1][j + 1] = ans[i][j + 1]
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            ans[i + 1][j + 1] = ans[i + 1][j]
            value[i + 1][j + 1] = value[i + 1][j]

print(ans[n][m])


### FIXED CODE ###

import sys
input = sys.stdin.readline

s = list(input())
t = list(input())
n = len(s)-1
m = len(t)-1
value = [[0]*(m+1) for i in range(n+1)]


for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
        elif value[i][j + 1] > value[i + 1][j]: #UP
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            value[i + 1][j + 1] = value[i + 1][j]
i = n-1
j = m-1
ans=""
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ans = s[i] + ans
        i -= 1
        j -= 1
    elif value[i][j + 1] > value[i + 1][j]:
        i -= 1
    else:
        j -= 1
print(ans)
### BUGGY CODE ###

S = input()
origin_length = len(S)
while True:
    length = len(S)
    S = S.replace('01','')
    S = S.replace('10','')
    if len(S) == length:
        break
print(origin_length-len(S))

### FIXED CODE ###

S = input()
origin_length = len(S)
zero_cnt = S.count('0')
ones_cnt = S.count('1')
print(min(zero_cnt,ones_cnt)*2)
### BUGGY CODE ###

import math

n , k = map(int, input().split())
a = list(map(int,input().split()))
b = [1]*n

for i in range(k):
    t = a.index(max(a))
    a[t]=a[t]*b[t]/(b[t]+1)
    b[t]+=1

print(math.ceil(max(a)))


### FIXED CODE ###

import math

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

left=0
right=max(a)
mid = (left+right)/2
while right - left > 0.5:
    times = 0
    for i in range(n):
        times+=math.ceil(a[i]/mid)-1
    if times<=k:
        right=mid
        mid=(left+right)/2
    else:
        left = mid
        mid =(left+right)/2

print(math.ceil(mid))
### BUGGY CODE ###

S = input()
dp = [[0]*13 for i in range(len(S)+1)]
MOD = 10**9+7

a = [0] + [(10**i) % 13 for i in range(len(S))]
dp[0][0] = 1

cnt = 1
for i, c in enumerate(S[::-1], 1):
    t = a[i]
    for j in range(13):
        if c == "?":
            for k in range(10):
                nj = (k*t+j) % 13
                dp[i][nj] = dp[i][nj] + dp[i-1][j]
                dp[i][nj] %= MOD
        else:
            nj = (int(c)*t+j) % 13
            dp[i][nj] = dp[i][nj] + dp[i-1][j]
            dp[i][nj] %= MOD
print(dp[-1][5])

### FIXED CODE ###

from sys import stdin
S = (stdin.readline().rstrip())
dp = [[0]*13 for i in range(len(S)+1)]
MOD = 10**9+7
 
S = list(reversed(S))
dp[0][0] = 1
 
t = 1
for i, c in enumerate(S, 1):
    for j in range(13):
        if c == "?":
            for k in range(10):
                nj = (k*t+j) % 13
                dp[i][nj] = dp[i][nj] + dp[i-1][j]
                dp[i][nj] %= MOD
        else:
            nj = (int(c)*t+j) % 13
            dp[i][nj] = dp[i][nj] + dp[i-1][j]
            dp[i][nj] %= MOD
    t = (t*10)%13
print(dp[-1][5])
### BUGGY CODE ###

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

A.sort()
count = 0
for i in range(n - 1):
    if A[i] % A[i + 1] == 0:
        count += 1
        continue
    for j in range(i):
        if A[i] % A[j] == 0:
            count += 1
            break
i = n - 1
for j in range(i):
    if A[i] % A[j] == 0:
        count += 1
        break
print(n - count)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
A.sort()

dp = [False] * (A[-1] + 1)
for a in A:
    dp[a] = True

for idx, a in enumerate(A):
    if A[idx] == A[idx - 1]:
        if idx == 0:
            None
        else:
            dp[a] = False
    for j in range(2, A[-1]//a + 1):
        dp[a * j] = False

count = 0
for d in dp:
    if d:
        count += 1
print(count)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    string = int(input())
    if a.count(string) == 0:
        a.append(string)
    else:
        a.remove(string)
print(len(a))


### FIXED CODE ###

import sys
import collections
import bisect


def main():
    n = int(input())
    A = [int(input()) for _ in range(n)]
    c = collections.Counter(A)
    sumA = 0
    cKeys = c.keys()
    for cKey in cKeys:
        sumA += c[cKey] % 2
    print(sumA)


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

N = int(input())
light_rule = {n:int(input())-1 for n in range(N)}

light = "1"+"0"*(N-1)
target = "0"+"1"+"0"*(N-2)
searched = {light:1}

def replace_str(source_s, to_s, idx):
    return source_s[:idx]+to_s+source_s[idx+1:]

flag = 0
num = 0
bottun = 0
while True:
    if light == target:
        flag = 1
        break
    num += 1
    light = replace_str(light, "0", bottun)
    light = replace_str(light, "1", light_rule[bottun])
    bottun = light_rule[bottun]
    if searched.get(light):
        break
    else:
        searched[light] = 1
    
if flag:
    print(num)
else:
    print(-1)

### FIXED CODE ###

N = int(input())
light_rule = {n:int(input())-1 for n in range(N)}

light = ["1"]+["0"]*(N-1)

flag = 0
num = 0
bottun = 0
for _ in range(N):
    if light[1] == "1":
        flag = 1
        break
    num += 1
    # print(bottun, light_rule[bottun])
    light[bottun] = "0"
    light[light_rule[bottun]] = "1"
    bottun = light_rule[bottun]
    # print(light)
    
if flag:
    print(num)
else:
    print(-1)
### BUGGY CODE ###

s = input()
n = len(s)
cA = ord('a')


even = [10**18]*n
odd = [[10**18]*26 for i in range(n)]
su = [0]*n
cp = 1 << (ord(s[0])-cA)
P = {cp: 0}
prev = [-1]*26
dp = [10**18 for i in range(n)]

dp[0] = 1
su[0] = cp
prev[ord(s[0])-cA] = 0
for i in range(1, n):
    code = ord(s[i]) - cA
    dp[i] = min(dp[i], dp[i-1] + 1)
    pv = prev[code]
    if pv != -1:
        need = su[i-1] ^ su[pv]
        #print(need, pv)
        state = need ^ su[pv] ^ (1 << code)
        #print(i, state, P)
        if state == 0:
            dp[i] = 1
        elif state in P:
            j = P[state]
            dp[i] = min(dp[i], dp[j] + 1)
    if cp == 0:
        dp[i] = 1
    if cp in P:
        j = P[cp]
        dp[i] = min(dp[i], dp[j] + 1)
    cp ^= 1 << code
    if cp not in P:
        P[cp] = i
    prev[code] = i
    su[i] = cp

    for j in range(26):
        pv = prev[j]
        if pv != -1:
            need = su[i] ^ su[pv]
            state = need ^ su[pv] ^ (1 << j)
            if state == 0:
                dp[i] = 1
            elif state in P:
                k = P[state]
                dp[i] = min(dp[i], dp[k] + 1)
ans = dp[n-1]
#print(dp)
for i in range(26):
    pv = prev[i]
    if pv != -1:
        need = su[n-1] ^ su[pv]
        #print(bin(need), pv)
        state = need ^ su[pv] ^ (1 << i)
        #print(i, state, P)
        if state == 0:
            ans = 1
        elif state in P:
            j = P[state]
            #print(">", i, j)
            ans = min(ans, dp[j] + 1)
print(ans)


### FIXED CODE ###

s = input()
n = len(s)
cA = ord('a')
P = {0: 0}
cur = 0

dp = [10**18]*(n+1)
dp[-1] = 0

for i in range(n):
    c = ord(s[i]) - cA
    dp[i] = dp[i-1] + 1
    cur ^= 1 << c
    # even
    if cur in P:
        dp[i] = min(dp[i], P[cur] + 1)
    # odd
    for k in range(26):
        need = cur ^ (1 << k)
        if need in P:
            dp[i] = min(dp[i], P[need] + 1)
    P[cur] = min(P.get(cur, 10**18), dp[i])
print(dp[n-1])