Harryxun/stf_run huggingface dataset:
import sys

def isleft(ox, oy, ax, ay, px, py):
    oax, oay = ax - ox, ay - oy
    opx, opy = px - ox, py - oy
    if oax * opy > oay * opx:
        return 1
    else:
        return 0

for line in sys.stdin:
    x1, y1, x2, y2, x3, y3, xp, yp = list(map(float, line.split()))
    A, B, C, P = (x1, y1), (x2, y2), (x3, y3), (xp, yp)
    if isleft(*A, *B, *P) == isleft(*B, *C, *P) == isleft(*C, *A, *P):
        print("YES")
    else:
        print("NO")

### FIXED CODE ###

import sys

def isleft(ox, oy, ax, ay, px, py):
    oax, oay = ax - ox, ay - oy
    opx, opy = px - ox, py - oy
    if oax * opy > oay * opx:
        return 1
    else:
        return 0

for line in sys.stdin:
    x1, y1, x2, y2, x3, y3, xp, yp = map(float, line.split())
#    A, B, C, P = (x1, y1), (x2, y2), (x3, y3), (xp, yp)
#    if isleft(*A, *B, *P) == isleft(*B, *C, *P) == isleft(*C, *A, *P):
    if isleft(x1, y1, x2, y2, xp, yp) == isleft(x2, y2, x3, y3, xp, yp) == isleft(x3, y3, x1, y1, xp, yp):
        print("YES")
    else:
        print("NO")
while 1:
    a = int(input())
    if a ==0:
    break
    a = str(a)
    print([a[i] for i in range(len(a))])


### FIXED CODE ###

while 1:
    n = input()
    if n == '0':
        break
    print(sum(int(x) for x in n))
s=input()
l=len(s)
a=[]
b=[]
i=0
for _ in range(l//2):
  a.append(s[i])
  b.append(s[i+1])
  i+=2
if l%2==1:
  a.append(s[l-1])
a0=a.count('0)
a1=a.count('1')
b0=b.count('0')
b1=b.count('1')
x=max(a0+b1,a1+b0)
print(l-x)

### FIXED CODE ###

s=input()
l=len(s)
a=[]
b=[]
i=0
for _ in range(l//2):
  a.append(s[i])
  b.append(s[i+1])
  i+=2
if l%2==1:
  a.append(s[l-1])
a0=a.count('0')
a1=a.count('1')
b0=b.count('0')
b1=b.count('1')
x=max(a0+b1,a1+b0)
print(l-x)
n,m=map(int,input().split())
adj=[]
dp=[0 for i in range(0,n+1)]
def dfs(i,p,adj,dp):
    # print(i)
    # print(i,p)
    if dp[i]!=0:
        return dp[i]
    for j in (adj[i]):
        if j==p:
            continue 
        else:
            dfs(j,i,adj,dp)
            dp[i]=max(dp[i],1+dp[j])
    return dp[i]
    
for i in range(n+1):
    adj.append([])
for _ in range(m):
    u,v=map(int,input().split())
    adj[u].append(v)

for i in range(1,n+1):
    if dp[i]==0:
        dfs(i,i,adj,dp)
# print(dp)
print(max(dp))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
adj=[]
dp=[0 for i in range(0,n+1)]
def dfs(i,p,adj,dp):
    # print(i)
    # print(i,p)
    if dp[i]!=0:
        return dp[i]
    for j in (adj[i]):
        if j==p:
            continue 
        else:
            dfs(j,i,adj,dp)
            dp[i]=max(dp[i],1+dp[j])
    return dp[i]
    
for i in range(n+1):
    adj.append([])
for _ in range(m):
    u,v=map(int,input().split())
    adj[u].append(v)

for i in range(1,n+1):
    if dp[i]==0:
        dfs(i,i,adj,dp)
# print(dp)
print(max(dp))
N,X = map(int,input().split())
L = list(map(int,input().split()))
D = [0]*(N+1)
x = 0
for i in range(1,N+1):
  D[i] = D[i-1]+L[i-1]
while D[x] <= X:
  x += 1
print(x)

### FIXED CODE ###

N,X = map(int,input().split())
L = list(map(int,input().split()))
D = [0]*(N+1)
x = 0
for i in range(1,N+1):
  D[i] = D[i-1]+L[i-1]
for i in D:
  if i <= X:
    x += 1
print(x)
def main():
    h,w,n=map(int,input().split(' '))
    draw_list=[]
    for i in range(n):
        draw=tuple(map(int,input().split(' ')))
        for j in range(3):
            for k in range(3):
                if 0<draw[0]-j<=h-2 and 0<draw[1]-k<=w-2:
                    draw_list.append((draw[0]-j,draw[1]-k))
    ans = [0]*9
    sorted_draw = sorted(draw_list)
    tmp = sorted_draw[0]
    ans_num = 0
    for i in range(len(sorted_draw)-1):
        if sorted_draw[i] == sorted_draw[i+1]:
            ans_num += 1
        else:
            ans[ans_num] += 1
            ans_num = 0
    if ans_num:
        ans[ans_num]+=1

    print((h-2)*(w-2)-sum(ans))
    for i in ans[1:]:
        print(i)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    h,w,n=map(int,input().split(' '))
    if n==0:
        print((h-2)*(w-2))
        for i in range(9):
            print(0)
        exit()
    draw_list=[]
    for i in range(n):
        draw=tuple(map(int,input().split(' ')))
        for j in range(3):
            for k in range(3):
                if 0<draw[0]-j<=h-2 and 0<draw[1]-k<=w-2:
                    draw_list.append((draw[0]-j,draw[1]-k))
    ans = [0]*9
    sorted_draw = sorted(draw_list)
    for n,i in enumerate(sorted_draw):
        if not n:
            ans_num=0
            tmp = i
            continue
        if tmp == i:
            ans_num+=1
        else:
            ans[ans_num] += 1
            tmp = i
            ans_num = 0
    ans[ans_num] += 1
    print((h-2)*(w-2)-sum(ans))
    for i in ans:
        print(i)



if __name__ == '__main__':
    main()
s = input()
N = int(input())
l = len(s)
result=[]
for first in range(l):
  for scope in range(1,1+l-first):
    if not s[first:first+scope]:
      result.append(s[first:first+scope])
result.sort()
print(result[N-1])

### FIXED CODE ###

str=input()
K=int(input())
s=set()
for scope in range(1,K+1):
    for f in range(len(str)-scope+1):
        s.add(str[f:f+scope])
print(sorted([x for x in s])[K-1])
def acinput():
    return list(map(int,input().split(" ")))


N,M=acinput()
a=[0]*(N+1)
for i in range(M):
    a[int(input())]=1


M=1000000007

def solve(x):
    global dp,M
    if dp[x]>=0:
        return dp[x]

    res=0
    zeroflg=True
    if  a[x-1]!=1:
        res+=solve(x-1)%M
        zeroflg=False
    if a[x-2]!=1:
        res+=solve(x-2)%M
        zeroflg=False
    
    if zeroflg:
        return 0
    dp[x]=res
    return res

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

print(solve(N)%M)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def acinput():
    return list(map(int, input().split(" ")))


N, M = acinput()
a = [0]*(N+1)
for i in range(M):
    a[int(input())] = 1


Mod = 1000000007


def solve(x):
    global dp, Mod
    if dp[x] >= 0:
        return dp[x]

    if x < 0:
        return 0

    res = 0
    zeroflg = True

    if  a[x-2] != 1:
        res += solve(x-2) 
        zeroflg = False

    if a[x-1] != 1:
        res += solve(x-1)
        zeroflg = False

    if zeroflg:
        return 0
    dp[x] = res% Mod
    return res


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

print(solve(N) % Mod)


'''
5 1
1
'''
h, w = int(input().split(" "))
n = h * w
a = n/2
if n%2==0:
  print(a)
  
else:
  print(a+0.5)

### FIXED CODE ###

h, w = input().split()
n = int(h) * int(w)
a = n//2
if int(h)==1 or int(w)==1:
  print(1)
  
elif n%2==1:
  print(a+1)
  
else:
  print(a)
n, r = map(int, input().split())

if n >= 10 :
  pint(r)
else:
  print(r - 100 * (10 - n))

### FIXED CODE ###

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

if n >= 10 :
  print(r)
else:
  print(r + 100 * (10 - n))
def c_gcd_on_blackboard(N, A):
    from functools import reduce
    from fractions import gcd
    odd, even = set(), set()
    for a in A:
        if a % 2 == 0:
            even.add(a)
        else:
            odd.add(a)
    if len(odd) >= 3:
        return 1
    if len(odd) == 0:
        even = sorted(even)
        even[0] = even[-1]
        return reduce(gcd, even)
    ans = 1
    for o in odd:
        ans = max(ans, reduce(gcd, even))
    return ans

N = int(input())
A = [int(i) for i in input().split()]
print(c_gcd_on_blackboard(N, A))

### FIXED CODE ###

def c_gcd_on_blackboard(N, A):
    # editorial通り
    from fractions import gcd

    left, right = [0] * (N + 1), [0] * (N + 1)
    for i in range(N):
        left[i + 1] = gcd(left[i], A[i])
    for i in range(N - 1, -1, -1):
        right[i] = gcd(right[i + 1], A[i])

    return max([gcd(left[i], right[i + 1]) for i in range(N)])

N = int(input())
A = [int(i) for i in input().split()]
print(c_gcd_on_blackboard(N, A))
import sys
sys.setrecursionlimit(10**11)

a, b, m = map(int, input().split())
a1 = list(map(int, input().split()))
b1 = list(map(int, input().split()))

disc = [list(map(int, input().split())) for i in range(m)]

import itertools
import numpy as np

b2 = np.array(b1)
b2 = np.tile(b2, (a,1))

ans = []
from collections import deque
ans = deque(ans)

for i in range(a):
    ans.append( np.min( b2[i] + np.tile(a1[i], b) ) )


for i in range(m):
    ans.append( a1[disc[i][0]-1] + b1[disc[i][1]-1] - disc[i][2] )

ans = list(ans)
print(min(ans))

### FIXED CODE ###

a, b, m = map(int, input().split())
a1 = list(map(int, input().split()))
b1 = list(map(int, input().split()))

disc = [list(map(int, input().split())) for i in range(m)]
import numpy as np


from collections import deque
ans = []

ans = deque(ans)

for i in range(m):
    ans.append( a1[disc[i][0]-1] + b1[disc[i][1]-1] - disc[i][2] )

ans = list(ans)

print(min( min(ans), min(a1)+min(b1) ))
import collections
N,M=map(int,input().split(" "))
List=[input().split(" ") for _ in range(M)]

List3=[]
for i in range(M):
    List2=[x for x in range(int(List[i][0]),int(List[i][1])+1)]
    for j in range(len(List2)):
        List3.append(List2[j])
List3.sort()
List4=list(set(List3))

Ans=[0]*len(List3)
for i in range(len(List3)):
    Ans[List3[i]-1]+=1

count=0    
for i in range(len(Ans)):
    if Ans[i]==M:
        count+=1
print(count)

### FIXED CODE ###

n, m = list(map(int, input().split()))
 
R, L = [], []
for i in range(m):
    l, r = list(map(int, input().split()))
    R.append(r)
    L.append(l)
  
print(max(min(R) - max(L) + 1, 0))
#!/usr/bin/env python3
a, b, c, k = map(int, input().split())
A = [1] * a
B = [0] * b
C = [-1] * c
A.extend(B)
A.extend(C)
print(sum(A[:k]))

### FIXED CODE ###

#!/usr/bin/env python3
a, b, c, k = map(int, input().split())
if a + b <= k:
    print(a - (k - (a + b)))
    exit()
elif a <= k:
    print(a)
else:
    print(k)
x=input()
c=0
for i in range(len(x)):
  c+=ord(x[i])-ord('0')
x=int(x)
if x%c==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

x=input()
c=0
for i in range(len(x)):
  if x[i]=='-':
  	c-=1
  else:
    c+=1
print(c)
W, H=map(int,input().split())
arr = [input() for j in range(W)]
ans = ['' for i in range(H)] 

for i in range(0, W):
    for j in range(0, H):
        bomb_num = 0
        if arr[i][j] == '#':
            ans[i] += '#'
        else:
            for k in (-1, 0, 1):
                for l in (-1, 0, 1):
                    if (-1<i+k<W) and (-1<j+l<H):
                        if arr[i+k][j+l] == '#':
                            bomb_num += 1
                        
            ans[i] += str(bomb_num)
            
for i in range(W):
        print(ans[i])

### FIXED CODE ###

W, H=map(int,input().split())
arr = [input() for j in range(W)]
ans = ['' for i in range(W)] 

for i in range(0, W):
    for j in range(0, H):
        bomb_num = 0
        if arr[i][j] == '#':
            ans[i] += '#'
        else:
            for k in (-1, 0, 1):
                for l in (-1, 0, 1):
                    if (-1<i+k<W) and (-1<j+l<H):
                        if arr[i+k][j+l] == '#':
                            bomb_num += 1
                        
            ans[i] += str(bomb_num)
            
for i in range(W):
        print(ans[i])
rom numpy import sqrt
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
fac = factorization(n)
s = 0
for i in fac:
    s += (-1+sqrt(1+4*i[1]*2))//2
print(int(s))

### FIXED CODE ###

from math import sqrt
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
fac = factorization(n)
s = 0
for i in fac:
    if i[0] != 1:
        s += (-1+sqrt(1+4*i[1]*2))//2
print(int(s))
d = int(input())
a=['Christmas']
for i in range(25-d):
  a.append('Eve')
print(' '.join

### FIXED CODE ###

d = int(input())
a=['Christmas']
for i in range(25-d):
  a.append('Eve')
print(' '.join(a))
N = int(input())
a = sorted(list(map(int, input().split())), reverse=True)


print(sum(a[1:2*n:2]))

### FIXED CODE ###

n=int(input())
a=list(map(lambda x: int(x), input().split()))
a.sort(reverse=True)
print(sum(a[1:2*n:2]))
n = input()
s = list(map(int,input().split()))

MAX = max(s)
nums = [0]*(MAX+1)

for i in s:
    if i == 0:
        nums[0] += 1
        nums[1] += 1
    elif i == MAX:
        nums[-1] += 1
        if i != 0:
            nums[-2] += 1
    else:
        nums[i-1] += 1
        nums[i] += 1
        nums[i+1] += 1

print(max(nums))

### FIXED CODE ###

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

MAX = max(s)
nums = [0]*(MAX+1)

if MAX == 0:
    print(n)
    exit()

for i in s:
    if i == 0:
        nums[0] += 1
        nums[1] += 1
    elif i == MAX:
        nums[-1] += 1
        nums[-2] += 1
    else:
        nums[i-1] += 1
        nums[i] += 1
        nums[i+1] += 1

print(max(nums))
N = int(input())
A = [0]*N

for r in range(N): A[r] = int(input())
A_max = max(A)
A_sec = sorted(set(A))[-2]

for r in range(N):
  if A[r] == A_max: print(A_sec)
  elif A[r] == A_sec: print(A_max)
  else: print(A_max)

### FIXED CODE ###

N = int(input())
A = [0]*N

for r in range(N): A[r] = int(input())
A_max = max(A)
A_sec = sorted(A)[-2]

for r in range(N):
  if A[r] == A_max: print(A_sec)
  elif A[r] == A_sec: print(A_max)
  else: print(A_max)
import math
def dist(x,y):
  return math.sqrt(x**2+y**2)

n,d=map(int,input().split())
i=0
for _ in range(d):
  x,y=map(int,input().split())
  if dist(x,y)<=d:
    i+=1
print(i)

### FIXED CODE ###

import math

def dist(x,y):
  return math.sqrt(x**2+y**2)

n,d=map(int,input().split())
i=0
for _ in range(n):
  x,y=map(int,input().split())
  if dist(x,y)<=d:
    i+=1
    
print(i)
import math
a,b = map(int,input().split())

print(math.floor(a*b))

### FIXED CODE ###

a,b = input().split()
a = int(a)
b = int(b.replace(".",""))
print(int(a*b//100))
a=int(input())
tl=[]
xl=[]
yl=[]
for i in range(a):
  t,x,y=map(int,input().split())
  tl.append(t)
  xl.append(x)
  yl.append(y)

#print(tl)
for i range(a):
  if (xl[i]+yl[i] > tl[i]):
    print("No")
    exit()
print("Yes")

### FIXED CODE ###

a,b=map(int,input().split())
if a*b % 2==0:
  print("Even")
else:
  print("Odd")
n, k = map(int, input().split())
H = list(map(int, input().split()))
cnt = 0
for i in n:
    if H[i] >= k
    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 H[i] >= k:
        cnt += 1
print(cnt)
import sys

sys.setrecursionlimit(100000)


H,W=map(int,input().split())
S=[]
for i in range(H):
    S.append(input())

def DFS(h,w,black,white,m):
    black,white=BorW(h,w,black,white)
    step=[[0,1],[0,-1],[1,0],[-1,0]]
    seen[h][w]=1
    for dh,dw in step:
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if seen[nh][nw]==0 and m!=S[nh][nw]:
                seen[nh][nw]=1
                black,white=DFS(nh,nw,black,white,S[nh][nw])
    return black,white


def BorW(h,w,black,white):
    if S[h][w]=="#":
        black+=1
    else:
        white+=1
    return black,white


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

L=[]
for h in range(H):
    for w in range(W):
        black=0
        white=0
        if seen[h][w]==0:
            black,white=DFS(h,w,black,white,S[h][w])
            L.append([black,white])
ans=0
for b,w in L:
     ans+=b*w

print(ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)


H,W=map(int,input().split())
S=[]
for i in range(H):
    S.append(input())

def DFS(h,w,black,white,m):
    black,white=BorW(h,w,black,white)
    step=[[0,1],[0,-1],[1,0],[-1,0]]
    seen[h][w]=1
    for dh,dw in step:
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if seen[nh][nw]==0 and m!=S[nh][nw]:
                seen[nh][nw]=1
                black,white=DFS(nh,nw,black,white,S[nh][nw])
    return black,white


def BorW(h,w,black,white):
    if S[h][w]=="#":
        black+=1
    else:
        white+=1
    return black,white


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

L=[]
for h in range(H):
    for w in range(W):
        black=0
        white=0
        if seen[h][w]==0:
            black,white=DFS(h,w,black,white,S[h][w])
            L.append([black,white])
ans=0
for b,w in L:
     ans+=b*w

print(ans)
import math
a,b=map(float,input())

print(math.floor(int(a)*b))

### FIXED CODE ###

a,b=input().split()
a=int(a)
b=int(b[0]+b[2:])
print(a*b//100)
import sys
s = sorted(list(str(input())))
t = sorted(list(str(input())), reverse = True)
x = 0
y = 0
for i in range(len(s)):
    if s[i] < t[i]:
        print('Yes')
        sys.exit()
    if s[i] > t[i]:
        print('No')
        sys.exit()
if s == t[:len(s)] and len(s) < len(t):
    print('Yes') 
elif s == t[:len(s)] and len(s) >= len(t):
    print('No')

### FIXED CODE ###

import sys
s = sorted(list(str(input())))
t = sorted(list(str(input())), reverse = True)
u = min(len(s), len(t))
for i in range(min(len(s), len(t))):
    if s[i] < t[i]:
        print('Yes')
        sys.exit()
    if s[i] > t[i]:
        print('No')
        sys.exit()
if s[0:u] == t[0:u] and len(s) < len(t):
    print('Yes')
elif s[0:u] == t[0:u] and len(s) >= len(t):
    print('No')
import fractions
import numpy as np
n,x=map(int,input().split())
li=np.array(input().split(),dtype=np.int64)

li=abs(li-x)

if len(li)==1:
    print(li[0])
else:
    mini=fractions.gcd(li[0],li[i+1])
    for i in range(1,n):
        gc=math.gcd(mini,li[i])
        mini=min(mini,gc)
    print(mini)
    

### FIXED CODE ###

import fractions
import numpy as np
n,x=map(int,input().split())
li=np.array(input().split(),dtype=np.int64)

li=abs(li-x)

if n==1:
    print(li[0])
else:
    ans=0
    for i in li:
        ans=fractions.gcd(ans,i)
    print(ans)
import sys
input = sys.stdin.readline
N,L = map(int,input().split())
lst = [L]
for i in range(n-1):
  lst.append(lst[-1]+1)
arr = [abs(i) for i in lst]
del lst[arr.index(min(arr))]
print(sum(lst))


### FIXED CODE ###

import sys
input = sys.stdin.readline
N,L = map(int,input().split())
lst = [L]
for i in range(N-1):
  lst.append(lst[-1]+1)
arr = [abs(i) for i in lst]
del lst[arr.index(min(arr))]
print(sum(lst))
n=int(input())
count=0
for i in range(1, int(n**0.5)+1):
    if  n%i==0:
        if i==n%((n//i)-1):
            count+=(n//i)-1
print(count)

### FIXED CODE ###

n=int(input())
count=0
if n==1:count=0
else:
    for i in range(1, int(n**0.5)+1):
        if  n%i==0:
            if i==n%((n//i)-1):
                count+=(n//i)-1
print(count)
n,k=map(int,input().split())
hashmap=dict()
for i in range(k):
  d=int(input())
  for j in range(d):
    key=int(input())
    hashmap[key]=d
count=0
for i in range(1,n+1):
  if hashmap.get(i)==None:
    count+=1
print(count)

### FIXED CODE ###

n,k=map(int,input().split())
hashmap=dict()
for _ in range(k):
  d=int(input())
  arr=[int(p) for p in input().split()]
  for key in arr:
    hashmap[key]=d
count=0
for i in range(1,n+1):
  if hashmap.get(i)==None:
    count+=1
print(count)
#Mo
n,q=map(int, input().split())
*c,=map(int, input().split())
c.append(-1)
que=[]
cdef int i,j,l,r,ll,rr
for i in range(q):
    li,ri=map(int, input().split())
    que.append((li-1,ri-1,i))

que.sort(key
    =lambda x:(x[0]//700,x[1]))

ll=0;rr=0
cnt=[0 for _ in range(500001)]
ans=[0 for _ in range(500001)]
col=0
cnt[c[0]]=1
for i in range(q):
    l,r,j=que[i]
    while rr<r:
        if cnt[c[rr+1]]==0:
            col+=1
        cnt[c[rr+1]]+=1
        rr+=1
    while rr>r:
        if cnt[c[rr]]==1:
            col-=1
        cnt[c[rr]]-=1
        rr-=1
    while ll>l:
        if cnt[c[ll-1]]==0:
            col+=1
        cnt[c[ll-1]]+=1
        ll-=1
    while ll<l:
        if cnt[c[ll]]==1:
            col-=1
        cnt[c[ll]]-=1
        ll+=1
    ans[j]=col+1
for i in range(q):
    print(ans[i])


### FIXED CODE ###

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

qu=[list(map(int, input().split())) +[i] for i in range(q)]
qu.sort(key=lambda x:x[1])
bit=[0]*(n+1)

last=[-1]*(n+1)

def add(t,x):
    while t<=n:
        bit[t]+=x
        t += t&(-t)

def query(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

used=1
ans=[0]*q
for l,r,i in qu:
    while used<=r:
        add(used,1)
        if last[c[used-1]]>=0:
            add(last[c[used-1]],-1)
        last[c[used-1]]=used
        used+=1
    ansi=query(r)-query(l-1)
    ans[i]=ansi
for ansi in ans:
    print(ansi)
n, p = map(int, input().split())

a = list(input())

for i in len(a):
    if i % 2 == 1:
        print(2 ** (n - 1))
        exit(0)

if p == 0:
    print(2 ** n)

else:
    print(0)


### FIXED CODE ###

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

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

#print(a)

for i in a:
    if i % 2 == 1:
        print(2 ** (n - 1))
        exit(0)

if p == 0:
    print(2 ** n)

else:
    print(0)
q=int(input())
while q>0:
    q-=1
    a,b=map(int,input().split())
    s=int((a*b-1)**0.5)
    ret=2*s
    if (a*b-1)//s==s:
        ret-=1
    if min(a,b)<=s:
        ret-=1
    print(ret)

### FIXED CODE ###

q=int(input())
for i in range(q):
    a,b=map(int,input().split())
    left=0
    right=a*b
    for i in range(100):
        mid=(left+right)//2
        if mid*mid<a*b:
            left=mid
        else:
            right=mid
    ret=left*2
    if ret==0:
        print(ret)
        continue
    if (a*b-1)//left==left:
        ret-=1
    if min(a,b)<=left:
        ret-=1
    print(ret)
a,b,h=map(int,input().split());print((a+b)*h/2)

### FIXED CODE ###

a,b,h=[int(input()) for i in range(3)];print(int((a+b)*h/2))
N = int(input()) - 1
T,A = map(int,input().split())
tmp = 0
X = 0
List = list(map(int,input().split()))
List2 = []
for i in range(N):
  tmp =abs(A - (T - List.pop(i) * 0.001))
  List2.append(tmp)
X = min(List2)
print(List2.index(X) + 1)

### FIXED CODE ###

N = int(input())
T,A = map(int,input().split())
List = list(map(int,input().split()))
List = [abs(A - (T - x * 0.006)) for x in List]
x = min(List)
print(str(List.index(x) + 1))
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())

class Node():
    def __init__(self):
        self.children = []
        self.count = 0



def add_count(G, v):
    for child in G[v].children:
        G[child].count += G[v].count
        add_count(G, child)


def main():
    G = [Node() for _ in range(N)]
    for _ in range(N-1):
        p, c = map(int, input().split())
        G[p-1].children.append(c-1)

    for _ in range(Q):
        p, x = map(int, input().split())
        G[p-1].count += x

    add_count(G, 0)

    counts = [node.count for node in G]
    print(*counts)

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

# 遅延評価で加えてあげるだけ

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x
    
q = [(1,0)]
while q:
    x,parent = q.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        q.append((y,x))

answer = ' '.join(map(str,value[1:]))
print(answer)
n = int(input())
s = input()
ans = 0


for i in range(n):
    if s[i:i+3] == 'ABC':
        res += 1

print(ans)

### FIXED CODE ###

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

print(s.count('ABC'))
def a(t,i):
    if i == n-1:
        return sum(map(int,t.split()))
    return a(t+s[i+1],i+1)+ a(t+"+"+s[i+1],i+1)

s = input()
n = len(s)
i=0
print(a(s[0],0))


### FIXED CODE ###

def dfs(i,s):
    if i==n-1:
        return sum(map(int,s.split('+')))
    return dfs(i+1,s+S[i+1])+dfs(i+1,s+'+'+S[i+1])

S=input()
n=len(S)
ans=dfs(0,S[0])
print(ans)