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

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

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**10, N)

dp = np.zeros((n, 10**5+1), np.int64)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V][L])
    else:
        d = {0: 0}
        while V >= n:
            v, w = vws[V]
            iterator = list(d.items())
            for w_sum, v_sum in iterator:
                if w_sum + w not in d:
                    d[w_sum + w] = v_sum + v
                else:
                    d[w_sum + w] = max(v_sum + v, d[w_sum + w])
            V = (V-1) // 2

        v_max = 0
        for w1, v1 in d.items():
            if 0 <= L-w1:            
                v_max = max(v_max, v1 + dp[V][L-w1])
        print(v_max)


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

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

blue = [1 for _ in range(A)]
red = [0 for _ in range(B)]
tkhs = []
while len(tkhs) < N:
    tkhs += (blue + red)
print(sum(tkhs[: N]))

### FIXED CODE ###

N, A, B = map(int, input().split())
AB = A + B

if N >= AB:
    iters, div = divmod(N, AB)
    if div <= A:
        print((A*iters + div))
    else:
        print((A*(iters + 1)))
elif N >= A:
    print(A)
else:
    print(N)
### BUGGY CODE ###

numN = int(input())
input_line = input().split(' ')
brick = [int(i) for i in input_line]

bestSeq = 0

for i, b in enumerate(brick):
  if numN - i < bestSeq:
    break
  seq = 0
  if b == 1:
    seq += 1
    cur = 2
    for c in brick[i:]:
      if c == cur:
        seq += 1
        cur += 1
    if seq > bestSeq:
      bestSeq = seq

if bestSeq == 0:
  print(-1)
else:
  print(numN - bestSeq)


### FIXED CODE ###

numN = int(input())
input_line = input().split(' ')
brick = [int(i) for i in input_line]

seq = 0

for i, b in enumerate(brick):
  if b == 1:
    seq += 1
    cur = 2
    for c in brick[i + 1:]:
      if c == cur:
        seq += 1
        cur += 1
    break

if seq == 0:
  print(-1)
else:
  print(numN - seq)
### BUGGY CODE ###

import sys
N=int(input())
if N%4==0:
    print(int(3*N/4),int(3*N/4),int(3*N/4))
else:
    for h in range(1,3501):
        for n in range(1,3501):
            for w in range(1,3501):
                if N*(h*n+n*w+w*h)==4*h*n*w:
                    print(h,n,w)
                    sys.exit()

### FIXED CODE ###

import sys
N=int(input())
for h in range(1,3501):
    for n in range(h,3501):
        if 4*n*h-N*h-N*n >0:
            if (N*h*n)%(4*n*h-N*h-N*n)==0:
                w=int((N*h*n)/(4*n*h-N*h-N*n))
                print(h,n,w)
                sys.exit()
### BUGGY CODE ###

from collections import deque
from itertools import product
from copy import deepcopy

h, w = map(int, input().split())
ls = [list(input()) for _ in range(h)]

sls = list(product(range(h),range(w)))
gls = list(product(range(h),range(w)))
ans = 0
move = [[0,1], [1,0],[0,-1], [-1,0]]
for s in sls:
    for g in gls:
        if s==g or ls[s[0]][s[1]] == '#' or ls[g[0]][g[1]] == '#' :
            continue
        else:
            lss = deepcopy(ls)
            d=deque()
            d.append(s)
            lss[s[0]][s[1]] = 0
            while d:
                x,y = d.popleft()
                c = lss[x][y]
                for dx,dy in move:
                    if 0<=x+dx<h and 0<=y+dy<w and lss[x+dx][y+dy] == '.' :
                        lss[x+dx][y+dy] = c+1
                        d.append([x+dx, y+dy])
            ans = max(ans, lss[g[0]][g[1]])

print(ans)


### FIXED CODE ###

from collections import deque
from itertools import product
from copy import deepcopy

h, w = map(int, input().split())
ls = [list(input()) for _ in range(h)]

sls = list(product(range(h),range(w)))
ans = 0
move = [[0,1], [1,0],[0,-1], [-1,0]]
for s in sls:
    if ls[s[0]][s[1]] == '#':
        continue
    else:
        lss = deepcopy(ls)
        d=deque()
        d.append(s)
        lss[s[0]][s[1]] = 0
        while d:
            x,y = d.popleft()
            c = lss[x][y]
            for dx,dy in move:
                if 0<=x+dx<h and 0<=y+dy<w and lss[x+dx][y+dy] == '.' :
                    lss[x+dx][y+dy] = c+1
                    d.append([x+dx, y+dy])
                    

        dist = 0
        for i in range(h):
            for j in range(w):
                if type(lss[i][j]) is int:
                    dist = max(dist, lss[i][j])

        ans = max(ans, dist)

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

N = int(input())
numbers =[i for i in map(int,input().split())]
result =1
standard = 10**18
for i in range(N):
  result *= numbers[i]
  if result == 0:
    print("0")
    break
else:
  if result > standard:
    print("-1")
  else:
  	print(result)

### FIXED CODE ###

n = int(input())
a = [i for i in map(int, input().split())]
 
if a.count(0) != 0:
  print(0)
else:
  result = 1
  for i in range(n):
    result *= a[i]
    if result > (10**18):
      print(-1)
      break
    else:
      continue
  else:
    print(result)
### BUGGY CODE ###

n,k=map(int,input().split())
dp=[0 for i in range(n)]
num=set()
dp[0]=1
mod=998244353
for i in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        num.add(j)
for i in range(n):
    for j in num:
        if i+j<=n-1:
            dp[i+j]+=dp[i]
            dp[i+j]%=mod
print(dp[n-1]%mod)

### FIXED CODE ###

n,k=map(int,input().split())
dp=[0 for i in range(n+1)]
acc=[0 for i in range(n+1)]
dp[1]=1
mod=998244353
acc[1]=1
l,r=[],[]
for i in range(k):
    a,b=map(int,input().split())
    l.append(a)
    r.append(b)
for i in range(2,n+1):
    for j in range(k):
        if i-l[j]<0:
            continue
        dp[i]+=(acc[i-l[j]]-acc[max(0,i-r[j]-1)])
        dp[i]%=mod
    acc[i]=(acc[i-1]+dp[i])%mod
print(dp[-1])
### BUGGY CODE ###

S=input()
Q=int(input())
for i in range(Q):
    temp=input().split()
    if len(temp)==1:
        S=S[::-1]
    else:
        if int(temp[1])==1:
            S=temp[2]+S

        if int(temp[1])==2:
            S=S+temp[2]
print(S)

### FIXED CODE ###

def string():
    s = input()
    q = int(input())
    l = ''
    r = ''
    re = False
    for _ in range(q):
        t = input().split()
        if t[0] == '1':
            re = not re
        else:
            if re:
                if t[1] == '1':
                    r = r + t[2]
                else:
                    l = t[2] + l
            else:
                if t[1] == '1':
                    l = t[2] + l
                else:
                    r = r + t[2]
    s = l + s + r
    if re:
        s = s[::-1]
    print(s)
string()
### BUGGY CODE ###

import copy

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

A_copy = copy.deepcopy(A)
cnt = 0
while True:
    for p in range(H):
        if '.' in A[p]:
            for i in range(H):
                for j in range(W):
                    if A[i][j] == '#':
                        if i != 0:
                            A_copy[i-1][j] = '#'
                        if i != H-1:
                            A_copy[i+1][j] = '#'
                        if j != 0:
                            A_copy[i][j-1] = '#'
                        if j != W-1:
                            A_copy[i][j+1] = '#'
            A = copy.deepcopy(A_copy)
            cnt += 1
            break
    else:
        break

print(cnt)


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

INF = 10 ** 5
d = [[10 ** 5] * W for _ in range(H)]

q = deque()

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            d[i][j] = 0
            q.append((i, j))

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

while q:
    y, x = q.popleft()

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if (0 <= ny < H and 0 <= nx < W and
            A[ny][nx] != '#' and d[ny][nx] == INF):

            d[ny][nx] = d[y][x] + 1
            q.append((ny, nx))

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, d[i][j])

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

import sys

inf = float('inf')

h, n, *ab = map(int, sys.stdin.read().split())
ab = list(zip(*[iter(ab)] * 2))

def main():
    dp = [inf] * (h + 1)
    dp[0] = 0
    for i in range(1, h+1):
        for a, b in ab:
            dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        
    return dp[h]

if __name__ == '__main__':
    ans = main()
    print(ans)

### FIXED CODE ###

import sys
import numpy as np

inf = float('inf')

h, n, *ab = map(int, sys.stdin.read().split())
a, b = np.array(ab, dtype=np.int64).reshape(n, 2).T

def main():
    dp = np.zeros(h+1, dtype=np.int64)
    for i in range(1, h+1):
        dp[i] = np.amin(dp[np.maximum(i-a, 0)] + b)
        
    return dp[h]

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

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h):
        a[i][0]=1if s[i][0]=='.'else 0
        b[i][-1]=1if s[i][-2]=='.'else 0
        for j in range(1,w):
            a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
            b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
    for j in range(w):
        c[0][j]=1if s[0][j]=='.'else 0
        d[-1][j]=1if s[-1][j]=='.'else 0
        for i in range(1,h):
            c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
            d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(sum(u)-3for t in zip(a,b,c,d)for u in zip(*t)))
main()

### FIXED CODE ###

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h*w):
        i,j=divmod(i,w)
        a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
        b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
        c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
        d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(a[i][j]+b[i][j]+c[i][j]+d[i][j]-3for i in range(h)for j in range(w)))
main()
### BUGGY CODE ###

from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
mw=min(wr)
def maxv(i,w):
	if dd[(i,w)]!=0:
		
		return dd[(i,w)]
	if i==n:
		return 0
	if W-w<mw:
		return 0
	if w+wr[i]<=W:
		a=vr[i]+maxv(i+1,w+wr[i])
	else:
		a=0
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))



### FIXED CODE ###

n,W=map(int,input().split())
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=map(int,input().split())
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print(dp[W])
### BUGGY CODE ###

n=int(input())
s=input()
count=0
for i in range(0,n-2):
    s1=s[i]
    for j in range(i+1,n-1):
        s2=s[j]
        if s1!=s2:
            for k in range(j+1,n):
                if j-i!=k-j: 
                    if s1!=s[k]: 
                        if s2!=s[k]:
                            count=count+1
print(count)


### FIXED CODE ###

n=int(input())
s=input()
count=0
A=[[0,0,0]for i in range(n)]
for i in range(0,n):
    if s[n-i-1]=="R":
        A[n-i-2][0]=A[n-i-1][0]+1
        A[n-i-2][1]=A[n-i-1][1]
        A[n-i-2][2]=A[n-i-1][2]
    if s[n-i-1]=="G":
        A[n-i-2][0]=A[n-i-1][0]
        A[n-i-2][1]=A[n-i-1][1]+1
        A[n-i-2][2]=A[n-i-1][2]
    if s[n-i-1]=="B":
        A[n-i-2][0]=A[n-i-1][0]
        A[n-i-2][1]=A[n-i-1][1]
        A[n-i-2][2]=A[n-i-1][2]+1
for i in range(0,n-3):
    s1=s[i]
    for j in range(i+1,n-1):
        s2=s[j]
        if s1!=s2:
            if s1=="R" and s2=="G":
                s3="B"
            elif s1=="G" and s2=="R":
                s3="B"
            elif s1=="R" and s2=="B":
                s3="G"
            elif s1=="B" and s2=="R":
                s3="G"
            elif s1=="B" and s2=="G":
                s3="R"
            elif s1=="G" and s2=="B":
                s3="R"
            if s3=="R":
                s4=0
            if s3=="G":
                s4=1
            if s3=="B":
                s4=2
            count=count+A[j][s4]
            if j+j-i+1<=n: 
                if s[j+j-i]==s3:
                    count=count-1
print(count)
### BUGGY CODE ###

n,m,s,t=map(int,input().split())
uvab=[list(map(int,input().split())) for i in range(m)]
c1=[[0]*n for i in range(n)]
c2=[[0]*n for i in range(n)]
for u,v,a,b in uvab:
    c1[u-1][v-1]=c1[v-1][u-1]=a
    c2[u-1][v-1]=c2[v-1][u-1]=b
from scipy.sparse import csr_matrix
g1=csr_matrix(c1)
g2=csr_matrix(c2)
from scipy.sparse.csgraph import dijkstra
d1=dijkstra(g1,directed=False,indices=s-1)
d2=dijkstra(g2,directed=False,indices=t-1)
r=[0]*n
for i in range(n):
    r[-i-1]=max(r[-i],10**15-int(d1[-i-1])-int(d2[-i-1]))
print(*r,sep='\n')

### FIXED CODE ###

n,m,s,t=map(int,input().split())
uvab=[map(int,input().split()) for i in range(m)]
inf=10**20
c1=[[] for i in range(n)]
c2=[[] for i in range(n)]
for u,v,a,b in uvab:
    c1[u-1].append((v-1,a))
    c1[v-1].append((u-1,a))
    c2[u-1].append((v-1,b))
    c2[v-1].append((u-1,b))
from heapq import heappop,heappush
def dij(c,N,start):
    d=[inf]*N
    d[start]=0
    prev=[-1]*N
    q=[]
    heappush(q,(0,start))
    while len(q)>0:
        u=heappop(q)[1]
        for v,w in c[u]:
            if w<inf:
                temp=d[u]+w
                if d[v]>temp:
                    d[v]=temp
                    prev[v]=u
                    heappush(q,(d[v],v))
    return d
d1=dij(c1,n,s-1)
d2=dij(c2,n,t-1)
r=[0]*n
for i in range(n):
    r[-i-1]=max(r[-i],10**15-int(d1[-i-1])-int(d2[-i-1]))
print(*r,sep='\n')
### BUGGY CODE ###

N = int(input())
s = input()
count = 0

while 'WR' in s:
    w_i = s.find('W')
    r_i = s.rfind('R')
    s = s[:w_i] + 'R' + s[w_i + 1:r_i] + 'W' + s[r_i + 1:]
    count += 1

print(count)


### FIXED CODE ###

N = int(input())
s = input()
r_count = s.count('R')
new_s = s[:r_count]
print(new_s.count('W'))
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
A=1
for i in range(N):
  A=A*L[i]
if 10**18>=A:
  print(A)
else:
  print(-1)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
A=1
if 0 in L:
  print(0)
  exit()
for i in range(N):
  A=A*L[i]
  if 10**18<A:
    print(-1)
    exit()
print(A)
### BUGGY CODE ###

import heapq
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

input = sys.stdin.readline

MAX  = 10 ** 15

N, M, s, t = map(int, input().split())

edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
g1 = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
g2 = csr_matrix((edge[3], (edge[:2] - 1)), (N, N))

d1 = dijkstra(g1, directed = False, indices = s - 1)
d2 = dijkstra(g2, directed = False, indices = t - 1)

# print (d1)
# print (d2)

# print (g1)
# print (g2)

# print (edge)

tmp = MAX
ans = [MAX] * N
for i in range(N - 1, -1, -1):
    tmp = min(tmp, d1[i] + d2[i])
    ans[i] -= int(tmp)

print (*ans, sep = '\n')



### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline

MAX  = 10 ** 15

N, M, s, t = map(int, input().split())

g1 = [[] for _ in range(N + 1)]
g2 = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    
    g1[u].append((a, v))
    g1[v].append((a, u))
    
    g2[u].append((b, v))
    g2[v].append((b, u))

d1 = [MAX] * (N + 1)
d2 = [MAX] * (N + 1)

d1[s] = 0 #始点の距離を0にする
pque = []
heapq.heappush(pque, [0, s]) #要素を[距離、頂点]として管理　最初の位置を入れる

while len(pque) != 0: #queの中に要素が残っている時
    p = heapq.heappop(pque) #最も距離が短いものを取り出す
    v = p[1] #距離が最も短い頂点
    if d1[v] < p[0]: #取り出した値より既に小さい値がdに入っているときは無視して次へ
        continue
    for i in range(len(g1[v])): #頂点vの隣接リストを走査
        e = g1[v][i]
        if d1[e[1]] > d1[v] + e[0]: #距離が更新できるかを検討
            d1[e[1]] = d1[v] + e[0]
            heapq.heappush(pque, [d1[e[1]], e[1]]) #更新できた場合、その値をpqueに入れる

# print (d1)

d2[t] = 0 #始点の距離を0にする
pque = []
heapq.heappush(pque, [0, t]) #要素を[距離、頂点]として管理　最初の位置を入れる

while len(pque) != 0: #queの中に要素が残っている時
    p = heapq.heappop(pque) #最も距離が短いものを取り出す
    v = p[1] #距離が最も短い頂点
    if d2[v] < p[0]: #取り出した値より既に小さい値がdに入っているときは無視して次へ
        continue
    for i in range(len(g2[v])): #頂点vの隣接リストを走査
        e = g2[v][i]
        if d2[e[1]] > d2[v] + e[0]: #距離が更新できるかを検討
            d2[e[1]] = d2[v] + e[0]
            heapq.heappush(pque, [d2[e[1]], e[1]]) #更新できた場合、その値をpqueに入れる

# print (d2)

tmp = MAX
ans = [MAX] * N
for i in range(N, 0, -1):
    tmp = min(tmp, d1[i] + d2[i])
    ans[i - 1] -= tmp

print (*ans, sep = '\n')
### BUGGY CODE ###

S=input()
MOD=10**9+7
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
for i in range(len(S)):
    if S[i]=="?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(10*k+j)%13]=(dp[i+1][(10*k+j)%13]+dp[i][k])%MOD
    else:
        a=int(S[i])
        for k in range(13):
            dp[i+1][(10*k+a)%13]=(dp[i+1][(10*k+a)%13]+dp[i][k])%MOD
print(dp[len(S)][5]%MOD)

### FIXED CODE ###

S=input()
MOD=10**9+7
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
for i in range(len(S)):
    if S[i]=="?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(10*k+j)%13]+=dp[i][k]%MOD
    else:
        a=int(S[i])
        for k in range(13):
            dp[i+1][(10*k+a)%13]+=dp[i][k]%MOD
print(dp[len(S)][5]%MOD)
### BUGGY CODE ###

import collections
S = input()
T = input()
N = len(S)
ss = set(S)
st = set(T)


sa = [0]*N
ta = [0]*N
table = collections.defaultdict(set)
table2 = collections.defaultdict(set)

for i, xy in enumerate(zip(S, T)):
    x, y = xy
    table[x].add(i)
    table2[y].add(i)

flag = True
for x, y in zip(S, T):

    if table[x] == table2[y]:
        continue
    else:
        flag = False
        break

if flag:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import collections
S=input()
T=input()
tableS=collections.defaultdict(list)
tableT=collections.defaultdict(list)

for i in range(len(S)):
  tableS[S[i]].append(i)
  tableT[T[i]].append(i)
listS=tableS.values()
listT=tableT.values()

for x in listS:
  flag=False
  for y in listT:
    if x in y or x in listT:
      flag=True
      break
  if not flag:
    print("No")
    exit(0)
print("Yes")
### BUGGY CODE ###

N, Q = (int(x) for x in input().split())
S = input()

a_loc = set()
for i in range(len(S)):
    if S[i:i+2] == 'AC':
        a_loc.add(i)
ans = []
for i in range(Q):
    l, r = (int(x) for x in input().split())
    num = 0
    for j in range(l-1, r-1):
        if j in a_loc:
            num += 1
    ans.append(num)

for i in range(Q):
    print(ans[i])


### FIXED CODE ###

N, Q = (int(x) for x in input().split())
S = input()

a_loc = [0] * (N + 1)
for i in range(N):
    a_loc[i+1] = a_loc[i] + (1 if S[i:i+2] == 'AC' else 0)

ans = [0] * Q
for i in range(Q):
    l, r = (int(x) for x in input().split())
    ans[i] = a_loc[r-1] - a_loc[l-1]
    
for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
n, q = map(int, input().split())
d = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append(b)
    d[b].append(a)
d2 = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    d2[p-1] += x

ans = [0] * n

def dfs(cur, pre, point):
    point += d2[cur]
    ans[cur] = point
    for e in d[cur]:
        if e != pre:
            dfs(e, cur, point)
dfs(0, -1, 0)
print(" ".join(map(str, ans)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, q = map(int, input().split())
d = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append(b)
    d[b].append(a)
d2 = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    d2[p-1] += x

ans = [0] * n

def dfs(cur, pre, point):
    point += d2[cur]
    ans[cur] = point
    for e in d[cur]:
        if e != pre:
            dfs(e, cur, point)
dfs(0, -1, 0)
print(" ".join(map(str, ans)))
### BUGGY CODE ###

import sys
x,y = map(int, input().split())
temp = x
if x == y:
    print(-1)
    sys.exit()
while True:
    temp += x
    if temp % y != 0:
        print(temp)
        sys.exit()
    elif temp > 100000000000000000:
        print(-1)
        sys.exit()

### FIXED CODE ###

import sys
def gcd(a, b):
        while b:
                a, b = b, a % b
        return a
def lcm(a, b):
    return a * b // gcd (a, b)

x,y = map(int, input().split())
temp = x
if x == y:
    print(-1)
    sys.exit()
while True:
    temp += x
    if temp % y != 0:
        print(temp)
        sys.exit()
    elif temp > lcm(x, y):
        print(-1)
        sys.exit()
### BUGGY CODE ###

n, k = map(int,input().split())
al = list(map(int,input().split()))
dics = {}

for i in range(n):
    if al[i] in dics:
        dics[al[i]] = dics[al[i]] + 1
    else:
        dics.update({al[i]:1})
        
counts = len(dics.values())
kesu = 0
sortv = list(dics.values())
while len(sortv) > k:
    kesu = kesu + min(sortv)
    sortv.remove(min(sortv))
print(kesu)


### FIXED CODE ###

n, k = map(int,input().split())
al = list(map(int,input().split()))
dics = {}
 
for i in range(n):
    if al[i] in dics:
        dics[al[i]] = dics[al[i]] + 1
    else:
        dics.update({al[i]:1})
        
counts = len(dics.values())
kesu = 0
sortv = list(sorted(list((dics.values()))))

i = counts
j = 0
while i > k:
    kesu = kesu + sortv[j]
    i = i - 1
    j = j + 1
print(kesu)
### BUGGY CODE ###

#2
s = list(input())
l = len(s)
cnt = 0

for i in range(l*l):
    for j in range(l-1):
        if s[j] =="B" and s[j+1] == "W":
            cnt += 1
            s[j],s[j+1] = s[j+1],s[j]
            break
    else:
        break
print(cnt)

### FIXED CODE ###

s=input()

ans=0
b_cnt=0
for i in range(len(s)):
  if s[i]=='B':
    b_cnt+=1
  else:
    ans+=b_cnt

print(ans)