Harryxun/stf_run huggingface dataset:
from time import time
start = time()

# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())
  q = [tuple(map(int,input().split())) for _ in range(Q)]

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((-1,tmp_dict[C[i]],i))
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i
    
  #assert time() - start < 0.1

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = q[i]
    # (元のクエリの順番、l, r)
    X.append((i,l-1,r-1))

  assert time() - start < 0.1
    
  X.extend(res) 
  X = sorted(X,key=lambda x:(x[1],-x[0]))
  
  #assert time() - start < 0.1

  # 平面走査
  bit = BIT(N)
  ans=[]
  for idx,l,r in reversed(X):
    if idx == -1:
      bit.add(r,1)
    else:
      ans.append((idx,r-l+1-bit.query(l-1,r)))

  # 元の順番にソートし直して出力
  print(*list(zip(*sorted(ans)))[1])
  
if __name__=="__main__":
  main()

### FIXED CODE ###

from time import time
start = time()

# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())
  q = [tuple(map(int,input().split())) for _ in range(Q)]

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((tmp_dict[C[i]]<<40) | (Q<<20) | i)
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = q[i]
    # (元のクエリの順番、l, r)
    X.append(((l-1)<<40) | (i<<20) | r-1)
    
  X.extend(res) 
  X = sorted(X)

  # 平面走査
  bit = BIT(N)
  ans=[0]*Q
  mask = (1<<20) - 1
  for l in reversed(X):
    r = l & mask
    l >>= 20
    idx = l & mask
    l >>= 20
    if idx == Q:
      bit.add(r,1)
    else:
      ans[idx] = r-l+1-bit.query(l-1,r)
      
  print(*ans)
  
if __name__=="__main__":
  main()
from operator import itemgetter

N = int(input())


A = []
for i in range(N - 1):
    A.append([int(i) for i in input().split()])

B = []
for row in A:
    B.append(sorted(row))
B.sort(key = itemgetter(0))

link_list = [[] for i in range(N)]
for row in B:
    link_list[row[0] - 1].append(row[1] - 1)
    link_list[row[1] - 1].append(row[0] - 1)
edge_color = dict()
marker = [0] * N

def DFS_color(node, pre_color):
    target_list = link_list[node]
    color = 1
    for ko_node in target_list:
        if marker[ko_node] == 0:
            if pre_color == color:
                color += 1
            edge_color[node, ko_node] = color
            edge_color[ko_node, node] = color 
            marker[ko_node] = 1
            DFS_color(ko_node, color)
            color += 1
        else:
            pass

marker[0] = 1
DFS_color(0, 0)

print(1)
#print(max(edge_color.values()))
for node1, node2 in A:
    if (node1-1, node2-1) in edge_color:
        print(edge_color[node1 - 1, node2 - 1])
    else:
        print("a")

### FIXED CODE ###

from operator import itemgetter
import sys
sys.setrecursionlimit(10**7)

N = int(input())


A = []
for i in range(N - 1):
    A.append([int(i)-1 for i in input().split()])

B = []
for row in A:
    B.append(sorted(row))
B.sort(key = itemgetter(0))

link_list = [[] for i in range(N)]
for row in B:
    link_list[row[0]].append(row[1])
    link_list[row[1]].append(row[0])
edge_color = dict()
marker = [0] * N


def DFS_color(node, pre_color):
    target_list = link_list[node]
    color = 1
    for ko_node in target_list:
        if marker[ko_node] == 0:
            if pre_color == color:
                color += 1
            edge_color[node, ko_node] = color
            edge_color[ko_node, node] = color 
            marker[ko_node] = 1
            DFS_color(ko_node, color)
            color += 1
        else:
            pass

marker[0] = 1
DFS_color(0, 0)

print(max(edge_color.values()))
for node1, node2 in A:
    print(edge_color[node1, node2])
N, Q = map(int, input().split())
S = input()
AClst = [] #ACのAを抜き出すリスト

for i in range(len(s)-1):
  if S[i,i+2]=="A":
    AClst.append(1)
  else:
    AClst.append(0)

for i in range(N):
  l, r = map(int, input().split())
  print(AClst[l:r].count(1))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
AClst = [0]
c = 0

for i in range(N-1):
  if S[i:i+2]=="AC":
    c += 1
  AClst.append(c)

for q in range(Q):
  l, r = map(int, input().split())
  print(AClst[r-1]-AClst[l-1])
n = input()
count=0
m = 0
for i in n:
  if s =="A" or s == "C" or s == "G" or s== "T" :
    count+=1
  else:
    m =max(m,count)
    count=0
print(m)

### FIXED CODE ###

n = input()
count=0
m = 0
for s in n:
  if s =="A" or s == "C" or s == "G" or s== "T" :
    count+=1
    m =max(m,count)
  else:
    count=0
print(m)
#abc089b

n=int(raw_input())
s=map(str,raw_input().split())
ss=set(s)
cnt=len(ss)
1f cnt=3:
 print 'Three'
else:
 print 'Four'


### FIXED CODE ###

#abc089b

n=int(raw_input())
s=map(str,raw_input().split())
ss=set(s)
cnt=len(ss)
if cnt==3:
 print 'Three'
else:
 print 'Four'
from sys import exit
import queue
V,E = [int(n) for n in input().split()]
ans = []

# N = int(input())
graph = [[] for _ in range(V)]
indeg = [0]*E
yet = [True]*E
def bfs(s):
    q = queue.Queue()
    q.put(s)
    while(not q.empty()):
        u = q.get()
        ans.append(u)
        yet[u]=False
        for v in graph[u]:
            indeg[v]-=1
            if(indeg[v]==0):
                q.put(v)

for i in range(E):
    s, t = [int(n) for n in input().split()]
    graph[s].append(t)
    indeg[t]+=1
for i in range(E):
    if(indeg[i]==0 and yet[i]):
        bfs(i)
for a in ans:
    print(a)
# a = [int(input()) for _ in range(N)]
# S = str(input())
# L = len(S)
# T = str(input())
# exit()



### FIXED CODE ###

from sys import exit
import queue
V,E = [int(n) for n in input().split()]
ans = []

# N = int(input())
graph = [[] for _ in range(V)]
indeg = [0]*V
yet = [True]*V
def bfs(s):
    q = queue.Queue()
    q.put(s)
    while(not q.empty()):
        u = q.get()
        ans.append(u)
        yet[u]=False
        for v in graph[u]:
            indeg[v]-=1
            if(indeg[v]==0):
                q.put(v)

for i in range(E):
    s, t = [int(n) for n in input().split()]
    graph[s].append(t)
    indeg[t]+=1
for i in range(V):
    if(indeg[i]==0 and yet[i]):
        bfs(i)
for a in ans:
    print(a)
# a = [int(input()) for _ in range(N)]
# S = str(input())
# L = len(S)
# T = str(input())
# exit()
A, B=list(map(int, input().split()))
print(math.ceil((A+B)/2))

### FIXED CODE ###

import math

A, B=list(map(int, input().split()))
# A = 5
# B = 5
print(math.ceil((A+B)/2))
x = "2"

print x*x*x

### FIXED CODE ###

x = input()
print x*x*x
N = int(input())
a = list(map(int, input().split()))

aa = [ai - i-1 for i,ai in enumerate(a)]

def tri_search(f:"f(x:float)->float", left, right, iter=100)->float:
    for _ in range(iter):
        ml = (left*2 + right) / 3
        mr = (left + right*2) / 3
        if f(ml) < f(mr):
            right = mr
        else:
            left = ml
    # print(left, right)
    return (right + left) / 2

def f(x):
    ret = 0
    x = int(x+0.5)
    for aai in aa:
        ret += abs(aai - x)
    return ret

b = tri_search(f, -10**9, 10**9)
print(min(f(b), f(b)+1, f(b)-1)


### FIXED CODE ###

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

aa = [ai - i-1 for i,ai in enumerate(a)]

def tri_search(f:"f(x:float)->float", left, right, iter=100)->float:
    for _ in range(iter):
        ml = (left*2 + right) / 3
        mr = (left + right*2) / 3
        if f(ml) < f(mr):
            right = mr
        else:
            left = ml
    # print(left, right)
    return (right + left) / 2

def f(x):
    ret = 0
    x = int(x+0.5)
    for aai in aa:
        ret += abs(aai - x)
    return ret

b = tri_search(f, -10**9, 10**9)
print(min(f(b), f(b+1), f(b-1)))
# -*- coding: <encoding name> -*-

import math
n = map(int, input())
print(math.ceil(n / 2)

### FIXED CODE ###

# -*- coding: <encoding name> -*-

import math
n = int(input())
print(math.ceil(n / 2))
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
if m>1:
    for i in range(m-1):
        if a[i+1]-a[i]==1:
            print(0)
            exit()
def fb(num):
    a,b = 1,0
    for _ in range(num+1):
        a,b = a+b,a
    return b
c=0
for i in range(m):
    if i==0 and a[0]==1:
        c+=1
    elif i==0:
        c+=fb(a[0]-1)
    else:
        c*=(fb(a[i]-a[i-1]-2)%(10**9+7))
c*=fb(n-a[-1]-1)%(10**9+7)
print(c%(10**9+7))

### FIXED CODE ###

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
def fb(num):
    a,b = 1,0
    for _ in range(num+1):
        a,b = a+b,a
    return b
if m==0:
    print(fb(n)%(10**9+7))
    exit()
if m>1:
    for i in range(m-1):
        if a[i+1]-a[i]==1:
            print(0)
            exit()
c=0
for i in range(m):
    if i==0 and a[0]==1:
        c+=1
    elif i==0:
        c+=fb(a[0]-1)
    else:
        c*=(fb(a[i]-a[i-1]-2)%(10**9+7))
c*=fb(n-a[-1]-1)%(10**9+7)
print(c%(10**9+7))
a,b=[int(i) for i in input().split()]
c=list(input())

c[b] = str.lower(c[b])

c = ''.join(c)

print(c)

### FIXED CODE ###

a,b=[int(i) for i in input().split()]
c=list(input())

c[b-1] = str.lower(c[b-1])

c = ''.join(c)

print(c)
A = [int(x) for x in input().split()]
sum=0
for i in A:
  sum=+i
  
if sum<22:
  print('win')
elif:
  print('bust')

### FIXED CODE ###

A = (int(x) for x in input().split())
print("bust") if sum(A) >= 22 else print("win")
# C
from collections import deque

N, M = map(int, input().split())
s = list(input())
s_ = s.copy()

# Graph
G = dict()
for i in range(1, N+1):
    G[i] = dict()

for _ in range(M):
    a, b = map(int, input().split())
    G[a][b] = 1
    G[b][a] = 1
    
# clean up
queue = degue()
go = True

As = [0]*N
Bs = [0]*N

for i in range(1, N+1):
    if s[i-1] != "C":
        a = 0
        b = 0
        for k in G[i].keys():
            v = s[k-1]
            if v == "A":
                a += 1
            elif v == "B":
                b += 1
        As[i-1] = a
        Bs[i-1] = b
        if a*b == 0:
            queue.append(i)
            s[i-1] = "C"

while len(queue) > 0:
    j = queue.popleft()
    for i in G[j].keys():
        if s[i-1] != "C":
            if s_[j] == "A":
                As[i-1] -= 1
            else:
                Bs[i-1] -= 1
            if As[i-1] * Bs[i-1] == 0:
                queue.append(i)
                s[i-1] = "C"

if "A" in s and "B" in s:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

# C
from collections import deque

N, M = map(int, input().split())
s = list(input())
s_ = []
for c in s:
    s_.append(c)

# Graph
G = dict()
for i in range(1, N+1):
    G[i] = dict()

for _ in range(M):
    a, b = map(int, input().split())
    G[a][b] = 1
    G[b][a] = 1
    
# clean up
queue = deque()
go = True

As = [0]*N
Bs = [0]*N

for i in range(1, N+1):
    if s[i-1] != "C":
        a = 0
        b = 0
        for k in G[i].keys():
            v = s_[k-1]
            if v == "A":
                a += 1
            elif v == "B":
                b += 1
        As[i-1] = a
        Bs[i-1] = b
        if a*b == 0:
            queue.append(i)
            s[i-1] = "C"

while len(queue) > 0:
    j = queue.popleft()
    for i in G[j].keys():
        if s[i-1] != "C":
            if s_[j-1] == "A":
                As[i-1] -= 1
            else:
                Bs[i-1] -= 1
            if As[i-1] * Bs[i-1] == 0:
                queue.append(i)
                s[i-1] = "C"

if "A" in s and "B" in s:
    print("Yes")
else:
    print("No")
import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
inf = float('inf')
d = [[inf for j in range(N)] for i in range(N)]

for i in range(N):
    d[i][i] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    t = min(c, d[a][b])
    if d[a][b] > c:
        d[a][b], d[b][a] = t, t

for i in range(N):
    for j in range(N):
        for k in range(N):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = inf
for i in list(itertools.permutations(r)):
    temp = 0
    for j in range(len(i)):
        temp += d[i[j]-1][i[j+1]]
        if temp > ans:
            break
    ans = min(ans, temp)

print(ans)

### FIXED CODE ###

from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())
    inf = float('inf')
    d = [[inf] * N for i in range(N)]

    for i in range(N):
        d[i][i] = 0

    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if d[a][b] > c:
            d[a][b], d[b][a] = c, c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                temp = d[i][k] + d[k][j]
                if d[i][j] > temp:
                    d[i][j] = temp

    ans = inf
    for i in permutations(r):
        temp = 0
        for j in range(len(i)-1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        if ans > temp:
            ans = temp

    print(ans)


main()
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    ab[a].append(-b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,v)
    if len(h)!=0:
        s+=-1*heapq.heappop(h)
print(s)

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    if a<=m:
        ab[a].append(b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,-1*v)
    if len(h)>0:
        s+=-1*heapq.heappop(h)
print(s)
N, M = map(int, input().split())
graph ={i+1:[] for i in range(N)}
for _ in range(N):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def DFS(graph, start, end):
    stack = [start]
    visited = []
    cnt = 0
    while stack:
        label = stack.pop(0)
        if label == end:
            visited.append(label)
            cnt += 1
        if label not in visited:
            visited.append(label)
            stack = graph.get(label, [])+stack
    return cnt
print(DFS(graph, 1, N))

### FIXED CODE ###

N, M = map(int, input().split())
graph ={i+1:[] for i in range(N)}
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def dfs(path, n, cnt):
    if(len(path) == N):
        return cnt+1
    for j in graph[n]:
        if(j in path):
            continue
        cnt = dfs(path+[j], j, cnt)
    return cnt
print(dfs([1], 1, 0))
N = int(input())
S = input()
abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
w = ""
for x in S:
    if abc.index(x) + N > 26:
        w += abc[abc.index(x) + N - 26]
    else:
        w += abc[abc.index(x) + N]
print(w)

### FIXED CODE ###

N = int(input())
S = input()
abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
w = ""
for x in S:
    if abc.index(x) + 1 + N > 26:
        w += abc[abc.index(x) + N - 26]
    else:
        w += abc[abc.index(x) + N]
print(w)
import sys
input = sys.stdin.readline
n,m,p = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
come = [[] for i in range(n+1)]
for a,b,d in abd:
  come[b].append(a)
visitable = [0]*(n+1)
stack = [n]
visitable[n] = 1
while stack:
  x = stack.pop()
  for y in come[x]:
    if visitable[y] == 0:
      visitable[y] = 1
      stack.append(y)
score = [10**15 for i in range(n+1)]
score[1] = 0
for j in range(n+1):
  flg = 0
  for i in range(m):
    v1,v2,e = abd[i]
    if visitable[v1] & visitable[v2] == 0:
      continue 
    e = -e+p
    if score[v1] != 10**15 and score[v2] > score[v1]+e:
      score[v2] = score[v1]+e
      flg = 1
      if j == n-1:
        last = -score[n]
      if j == n:
        onemore = -score[n]
  if flg == 0:
    break
if flg == 0:
  print(max(0,-score[n]))
else:
  if last == onemore:
    print(max(last,0))
  else:
    print(2/0)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m,p = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
come = [[] for i in range(n+1)]
for a,b,d in abd:
  come[b].append(a)
visitable = [0]*(n+1)
stack = [n]
visitable[n] = 1
while stack:
  x = stack.pop()
  for y in come[x]:
    if visitable[y] == 0:
      visitable[y] = 1
      stack.append(y)
score = [10**15 for i in range(n+1)]
score[1] = 0
for j in range(n+1):
  flg = 0
  for i in range(m):
    v1,v2,e = abd[i]
    if visitable[v1] & visitable[v2] == 0:
      continue 
    e = -e+p
    if score[v1] != 10**15 and score[v2] > score[v1]+e:
      score[v2] = score[v1]+e
      flg = 1
      if j == n-1:
        last = score[:]
      if j == n:
        onemore = score[:]
  if flg == 0:
    break
if flg == 0:
  print(max(0,-score[n]))
else:
  if last == onemore:
    print(max(last[n],0))
  else:
    print(-1)
n, h, d = map(int, input().split())
MOD = 10 ** 9 + 7


if n * h * d >= 10 ** 7:
    print(re)

# dp[i][j] := 高さiのブロックが最大高さでj個ある時の通り数
dp = [[0] * (n + 1) for i in range(h + 1)]
dp[0][n] = 1

# O(HDN)
for i in range(h):
    # j = 0 -> j = 1 にする
    for diff in range(1, d + 1):
        if i + 1 - diff < 0:
            continue
        for cnt in range(1, n + 1):
            dp[i + 1][1] += dp[i + 1 - diff][cnt] * cnt
            dp[i + 1][1] %= MOD

    # j -> j + 1 にする
    for j in range(2, n + 1):
        dp[i + 1][j] += dp[i + 1][j - 1] * (n - (j - 1))
        dp[i + 1][j] %= MOD

print(dp[-1][-1] % MOD)

### FIXED CODE ###

n, h, d = map(int, input().split())
MOD = 10 ** 9 + 7


fact = [1] * (n + 1)
for i in range(n):
    fact[i + 1] = fact[i] * (i + 1)
    fact[i + 1] %= MOD

# fact_sum = fact[1] + fact[2] + ... + fact[n]
fact_sum = 0
for i in range(1, n + 1):
    fact_sum += fact[i]
    fact_sum %= MOD

dp = [0] * (h + 1)
ru = [0] * (h + 2)
dp[0] = 1
ru[1] = 1
for i in range(h):
    l = max(i + 1 - d, 0)
    dp[i + 1] += (ru[i + 1] - ru[l]) * fact_sum
    dp[i + 1] %= MOD
    ru[i + 2] = ru[i + 1] + dp[i + 1]
    ru[i + 2] %= MOD

print((dp[-1] * fact[n] * pow(fact_sum, MOD - 2, MOD)) % MOD)
ref=input()

count=0
seq=["A","T","G,","C"]
for base in ref:
    if base in ref:
        count +=1
    else count =0

print(count)

### FIXED CODE ###

ref=input()
count=0
count_list=[]
seq=["A","T","G","C"]
for base in ref:
    if base in seq:
        count +=1
       
    else:
        count_list.append(count)
        count =0
    count_list.append(count)

print(max(count_list))
n,k = int(input())
h = list(map(int,input().split()))
cnt=0
for i in range(n):
	if k<=h[i]:
		cnt+=1
print(cnt)

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
cnt=0
for i in range(n):
	if k<=h[i]:
		cnt+=1
print(cnt)
from math import gcd

def lcm(a, b):
    return a // gcd(a, b) * b

MOD = 10**9 + 7

N = int(input())
a = [int(x) for x in input().split()]

m = 1
for e in a:
    m = lcm(m, e)

ans = 0
for e in a:
    ans += m // e
    ans %= MOD

print(ans)


### FIXED CODE ###

def lcm(a, b):
    from fractions import gcd

    return a // gcd(a, b) * b


def main():
    _ = int(input())
    a = list(map(int, input().split()))
    x = 1

    for e in a:
        x = lcm(x, e)

    ans = 0
    for e in a:
        ans += x // e

    print(ans % int(1e9 + 7))


main()
A, B, C = map(int,input().split())

n = 100 * B

for i in range(1, n, B):
  if A * i % B == C:
    print("YES")
    flag = True
    break
  else:
    continue

if flag != True:
  print("No")
  


### FIXED CODE ###

A, B, C = map(int,input().split())

for i in range(B):
  if A * i % B == C:
    print("YES")
    exit()
  else:
    continue
print("NO")
arr = input().split(" ")
A = int(arr[0])
B = int(arr[1])

if A == B:
  print(A + B)
 elif A > B and (A - B) == 1:
  print(A + (A -1))
 elif A > B and (A - B) >= 2:
  print(A + (A - 1))
 elif A < B and (B - A) == 1:
  print(A + B)
 elif A < B and (B - A) >= 2:
  print(B + (B -1))

### FIXED CODE ###

arr = input().split(" ")
A = int(arr[0])
B = int(arr[1])

if A == B:
  print(A + B)
elif A > B and (A - B) == 1:
  print(A + (A -1))
elif A > B and (A - B) >= 2:
  print(A + (A - 1))
elif A < B and (B - A) == 1:
  print(A + B)
elif A < B and (B - A) >= 2:
  print(B + (B -1))
input()
a, b = map(int, input().split())
if a * b % 2 == 0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

a, b = map(int, input().split())
if a * b % 2 == 0:
  print("Even")
else:
  print("Odd")
n=map(int,input())
fact=[1,1,2,6,24,120,720,5040,40320]
p=list(map(int,input().split()))
q=list(map(int,input().split()))
a=0
b=0
for i in range(n):
	a=a+((p[i]-1)*(fact[n-i-1]))
	b=b+((q[i]-1)*(fact[n-i-1]))
	for j in range(i+1,n):
		if(p[j]>p[i]):
			p[j]=p[j]-1
		if(q[j]>q[i]):
			q[j]=q[j]-1
print(abs(a-b))

### FIXED CODE ###

n=int(input())
fact=[1]*13
for i in range(2,13):
	fact[i]=i*fact[i-1]
p=list(map(int,input().split()))
q=list(map(int,input().split()))
a=0
b=0
for i in range(n):
	a=a+((p[i]-1)*(fact[n-i-1]))
	b=b+((q[i]-1)*(fact[n-i-1]))
	for j in range(i+1,n):
		if(p[j]>p[i]):
			p[j]=p[j]-1
		if(q[j]>q[i]):
			q[j]=q[j]-1
print(abs(a-b))
import math as mt
import numpy as np

string = input()
use = string.split('x')
word =''
for x in use:
    word += x
i = 0
n = len(word) - 1
while i < n:
    if word[i] != word[n]:
        print(-1)
        exit()
    i += 1
    n -= 1
if len(word) % 2 == 0:
    fh = []
    i = 0
    mid = int(len(word)/2)
    count = 0
    n = len(string) - 1
    for x in string:
        if x == word[i]:
            i += 1
            fh.append(count)
            count = 0
            if i == mid:
                break
        else:
            count += 1
    i = len(word) - 1
    lh = []
    count = 0
    while i != mid - 1:
        if string[n] == word[i]:
            i -= 1
            lh.append(count)
            count = 0
        else:
            count += 1
        n -= 1
    if len(lh) != len(fh):
        print(12222)
        exit()
    print(np.sum(np.abs(np.array(fh)-np.array(lh))))

else:
    fh = []
    i = 0
    mid = int((len(word) - 1)/2)
    count = 0
    n = len(string) - 1
    for x in string:
        if x == word[i]:
            i += 1
            fh.append(count)
            count = 0
            if i > mid:
                break
        else:
            count += 1
    i = len(word) - 1
    lh = []
    count = 0
    while i != mid - 1:
        if string[n] == word[i]:
            i -= 1
            lh.append(count)
            count = 0
        else:
            count += 1
        n -= 1
    if len(lh) != len(fh):
        print(12222)
        exit()
    print(np.sum(np.abs(np.array(fh)-np.array(lh))))


### FIXED CODE ###

import math as mt
import numpy as np

string = input()
collect = []
word = ''
count = 0
n = len(string)
i = 0
for x in string:
    if x != 'x':
        word += x
        collect.append(count)
        if i == n-1:
            collect.append(0)
        count = 0
    elif i == n-1:
        count += 1
        collect.append(count)
    else:
        count += 1
    i += 1

nl = len(word) - 1
i = 0
while i < nl:
    if word[i] != word[nl]:
        print(-1)
        exit()
    i += 1
    nl -=  1
nl = len(collect) - 1
i = 0
out = 0
while i < nl:
    out += np.abs(collect[i] - collect[nl])
    i += 1
    nl -= 1
print(out)