Harryxun/stf_run huggingface dataset:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, X, M = NMI()
    A = []
    A_ID = {}
    break_flag = False
    for i in range(M):
        if i == 0:
            A.append(X)
            A_ID[X] = 0
        else:
            x = A[-1]**2 % M
            if x not in A_ID:
                A.append(x)
                A_ID[x] = i
            else:
                A.append(x)
                start = A_ID[x]
                end = i
                break_flag = True
            if break_flag:
                break

    if N < start+1:
        print(sum(A[:N]))
        exit()

    ans = sum(A[:start])
    lp = sum(A[start:end])
    gap = end - start
    lp_n = (N - start) // gap
    rem = (N - start) % gap
    ans += lp * lp_n + sum(A[start: start + rem])
    print(ans)




if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, X, M = NMI()
    A = []
    A_ID = {}
    break_flag = False
    start = 0
    end = N
    for i in range(M):
        if i == 0:
            A.append(X)
            A_ID[X] = 0
        else:
            x = A[-1]**2 % M
            if x not in A_ID:
                A.append(x)
                A_ID[x] = i
            else:
                A.append(x)
                start = A_ID[x]
                end = i
                break_flag = True
            if break_flag:
                break

    if N < start+1:
        print(sum(A[:N]))
        exit()

    ans = sum(A[:start])
    lp = sum(A[start:end])
    gap = end - start
    lp_n = (N - start) // gap
    rem = (N - start) % gap
    ans += lp * lp_n + sum(A[start: start + rem])
    print(ans)




if __name__ == "__main__":
    main()
hoge

### FIXED CODE ###

#!/usr/bin/env python3

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

def gcd(a, b):
    if a > b:
        a, b = b, a
    # assert(a <= b)
    if b%a == 0:
        return a
    else:
        return gcd(b%a, a)

def gcd_many(l):
    # if len(l) == 1:
    #     return l
    # elif len(l) == 2:
    #     return gcd(l[0], l[1])
    # else:
    #     return gcd(l[0], gcd_many(l[1:]))
    if len(l) == 1:
        return l[0]
    g = l[0]
    for i in range(1,len(l)):
        g = gcd(g, l[i])
    return g

Amax = max(A)
g = gcd_many(A)

possible = "POSSIBLE"
impossible = "IMPOSSIBLE"


if K > Amax:
    print(impossible)
else:
    if K % g == 0:
        print(possible)
    else:
        print(impossible)
A,B = map(int(input().split()))
if A>=13:
  print(B)
elif A>=6
  print(B/2)
else
print(0)

### FIXED CODE ###

A,B = map(int,input().split())
if A>=13:
  print(B)
elif A>=6:
  print(int(B/2))
else:
  print(0)
N = int(input())
A = list(int(i) for i in input().split())
B = list(int(i) for i in input().split())
C = list(int(i) for i in input().split())
A.sort()
B.sort()
C.sort()
sum = 0
for j in range(N):
    low = low2 = 0
    high = high2 = N
    b = B[j]
    #print(b)
    while(high>low):
        mid = (high + low)//2
        if b > A[mid]:
            low = mid +1
        else:
            high = mid
    acount = mid
    while (high2>low2):
        mid2 = (high + low)//2
        if b < C[mid2]:
            high2 = mid2
        else:
            low2 = mid2 + 1
    ccount=N-mid2
    sum += acount*ccount
print(sum)

### FIXED CODE ###

N = int(input())
A = list(int(i) for i in input().split())
B = list(int(i) for i in input().split())
C = list(int(i) for i in input().split())
A.sort()
B.sort()
C.sort()
sum = 0
for j in range(N):
    low = low2 = 0
    high = high2 = N
    b = B[j]
    mid = mid2 = 0
    #print(b)
    while(high>low):
        mid = (high + low)//2
        if b > A[mid]:
            low = mid +1
        else:
            high = mid
    acount = low
    while (high2>low2):
        mid2 = (high2 + low2)//2
        if b < C[mid2]:
            high2 = mid2
        else:
            low2 = mid2 + 1
    ccount=N-low2
    sum += acount*ccount
print(sum)
N,M=map(int,input().split())
A=[input() for i in range(N)]
B=[input() for j in range(M)]
for i in range(N):
    for j in range(N-M):
        if A[i][j:j+M]==B[0]:
            if all(A[i+k][j:j+M]==B[k] for k in range(1,M)):
                print("Yes")
                exit()
print("No")

### FIXED CODE ###

N,M=map(int,input().split())
A=[input() for i in range(N)]
B=[input() for j in range(M)]
for i in range(N-M+1):
    for j in range(N-M+1):
        if A[i][j:j+M]==B[0]:
            if all(A[i+k][j:j+M]==B[k] for k in range(1,M)):
                print("Yes")
                exit()
print("No")
s = list(input())
l = ['K','I','H','B','R']
j = 0

for i in range(len(s)):
    if s[i] == 'A':
        if s[i - 1] == 'A':
            print('NO')
            exit(0)
        elif j ==  1 or j == 2:
            print('NO')
            exit(0)
        else:
            pass
    elif s[i] != l[j]:
        print('NO')
        exit(0)
    else:
        j += 1

print('YES')

### FIXED CODE ###

s = list(input())
l = ['K','I','H','B','R',-1]
j = 0

for i in range(len(s)):
    if s[i] == 'A':
        if i == 0:
            pass
        elif s[i-1] == 'A':
            print('NO')
            exit(0)
        elif j == 1 or j == 2:
            print('NO')
            exit(0)
        else:
            pass
    elif s[i] != l[j]:
        print('NO')
        exit(0)
    elif j > 4 and s[i] != 'A':
        print('NO')
        exit(0)
    else:
        j += 1

if j == 5:
    print('YES')
else:
    print('NO')
, b, c, d, e, f = map(int, input().split())

w = 0
s = 0
ratio = 0

for i in range(31):
    for j in range(31):
        water = a*i + b*j
        for k in range(1501):
            l = 0
            hoge = 1024
            while hoge:
                nl = l+hoge
                sugar = k*c+nl*d
                if 0 < water and water*100 + sugar <= f and sugar <= water*e:
                    l = nl
                hoge <<= 2
            sugar = k*c+l*d
            if ratio <= sugar / (water*100+sugar):
                w = water*100
                s = sugar
                ratio = sugar / (water*100+sugar)

print("%d %d"%(w+s,s))


### FIXED CODE ###

a,b,c,d,e,f = map(int, input().split(' '))

w = 0
s = 0
ratio = 0

for i in range((f // (b*100))+1):
    for j in range(((f-(i*b*100))//(a*100))+1):
        if i == 0 and j == 0:
            continue
        smax = min(f-(j*a+i*b)*100,(j*a+i*b)*e)
        sm = 0
        for k in range((smax//d)+1):
            sm = max(sm, k*d+c*((smax-(k*d))//c))
        if ratio <= sm/((j*a+i*b)*100+sm):
            ratio = sm/((j*a+i*b)*100+sm)
            w = (j*a+i*b)*100
            s = sm


print("%i %i" %(w+s,s))
N = int(input())
A = [int(x) for x in input().split()]
X = [0]*N
answer = 0
for i in range(N):
  if A[i]==i+1:
    X[i]=1
for i in range(N):
  if X[i]==1:
    answer +=1
    X[i+1]=0
print(answer)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
X = [0]*N
answer = 0
for i in range(N):
  if A[i]==i+1:
    X[i]=1
for i in range(N-1):
  if X[i]==1:
    answer +=1
    X[i+1]=0
if X[N-1]==1:
  answer +=1
print(answer)
import sys
data = []
for line in sys.stdin:
	data.append(line.split())

S = []
T = []
ans = []
S = data[1]
T = data[3]

count = 0
for t in T:
    l = 0
    r = len(S)

    while l < r :
        i = (l + r) / 2
        if int(S[i]) < int(t) :
            l = i + 1
        elif int(S[i]) > int(t) :
            r = i
        else :
            count = count + 1
            break

print(count)


### FIXED CODE ###

import sys

if __name__ == '__main__':
    data = []
    count = 0
    for line in sys.stdin:
        data.append(line.split())
    s = list(map(int, data[1]))
    n = int(data[0][0])
    q = int(data[2][0])
    t = list(map(int, data[3]))
    for i in range(0, q):
        head = 0
        tail = n - 1
        while True:
            if head > tail :
                break
            center = (head + tail)//2
            if s[center] == t[i] :
                count = count + 1
                break
            elif s[center] < t[i]:
                head = center + 1
            else :
                tail = center - 1
    print(count)
N=int(input())
aN=[int(input()) for _ in range(N)]
c=0
i=1
while True:
  c+=1
  if a[i]==2:
    print(c)
    break
  elif a[i]==0:
    print(-1)
  i=a[i]
  a[i]=0
  

### FIXED CODE ###

N=int(input())
aN=[int(input()) for _ in range(N)]
c=0
i=1
while True:
  c+=1
  if aN[i-1]==2:
    print(c)
    break
  elif aN[i-1]==0:
    print(-1)
    break
  t=aN[i-1]
  aN[i-1]=0
  i=t
N=int(input())
li = [list(map(int,input().split())) for i in range(N)]

def solve(li):
    for i in range(101):
        for j in range(101):
            flag=1
            Cx,Cy=i,j
            H_prev=0
            for k in li:
                if k[2]!=0:
                    H_prev=k[2]+abs(k[0]-Cx)+abs(k[1]-Cy)
                    break
            for k in li:
                H=max(k[2]+abs(k[0]-Cx)+abs(k[1]-Cy),0)
                if H_prev != H:
                    flag=0
                    break
                H_prev=H
            if flag==1 and H>=1:
                A=[i,j,H]
                return A
A=solve(li)
print(' '.join(map(str,A)))

### FIXED CODE ###

n=int(input())
p=[list(map(int,input().split()))for _ in range(n)] #[ax,ay,ah]をひとつの要素とする二重リスト
ax,ay,ah=list(filter(lambda x:x[2],p))[0] #x[2]がTrue、つまりahが0以外のリストの先頭の要素を取得
for x in range(101):
    for y in range(101):
        H=ah+abs(ax-x)+abs(ay-y) #Hの予測値
        if all([max(H-abs(t[0]-x)-abs(t[1]-y),0)==t[2]for t in p]): #ahのリストを生成し、予測したHから正しいかどうか判定
            print(x,y,H)
import fraction
N = int(input())
A = [int(i) for i in input().split()]

def gcd(a,b):
    

def mygcd(A):
    if len(A) == 1:
        return A[0]
    else:
        return fraction.gcd(A[0],mygcd(A[1:]))
        
ans = []
for i in range(N):
    ans.append(mygcd(A[:i]+A[i+1:]))

print(max(ans))

### FIXED CODE ###

from fractions import gcd
#input
N = int(input())
A = [int(i) for i in input().split()]
#cluc left and right gcd 
left = [0]*N
right = [0]*N
count = 0
left[0] = A[0]
right[-1] = A[-1]
Ans = []

for i in A[1:]:
    left[count+1] = gcd(left[count],i)
    count += 1

for i in reversed(A[:-1]):
    right[count-1] = gcd(right[count],i)
    count -= 1
# make ans
Ans.append(right[1])
Ans.append(left[-2])
for i in range(N-2):
    Ans.append(gcd(left[i],right[i+2]))
print(max(Ans))
KN = list(map(int, input().split()))
A = list(map(int, input().split()))

answer = []

for i,home in enumerate(A):
    kouho = home - A[i - 1]
    if kouho < 0:
        answer.append(20 + kouho)
    else:
        aanswer.append(kouho)

print(20 - max(answer))


### FIXED CODE ###

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

answer = []

for i,home in enumerate(A):
    if home < A[i - 1]:
        answer.append(home - A[i - 1] + KN[0])
    else:
        answer.append(home - A[i - 1])

print(KN[0] - max(answer))
s = list(input())

ans = 0
i = 0
if s[0] == 'A' and s[1] == 'B' and s[2] == 'C':
    s[0] = 'B'
    s[1] = 'C'
    s[2] = 'A'
    ans += 1
    i = 3

while i+2 < len(s):
    if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
        ans += 1
        s[i] = 'B'
        s[i+1] = 'C'
        s[i+2] = 'A'
        i -= 1
    else:
        i += 1

print(ans)

### FIXED CODE ###

s = input()

s = s.replace('BC', 'D')
ans = 0
a = 0
for c in s:
    if c == 'A':
        a += 1
    elif c == 'D':
        ans += a
    else:
        a = 0

print(ans)
import sympy
import sys
from sys import stdin
def input() : return stdin.readline().rstrip()
def mips():
    return map(int,input().split())
def ii():
    return int(input())
sys.setrecursionlimit(10**9)
A,VA = mips()
B,VB = mips()
T = ii()
if A <= B:
    d1 = A + VA * T
    d2 = B + VB * T
    if d1 >= d2:
        print("YES")
    else:
        print("NO")
else:
    d2 = B - VB * T
    d1 = A - VA * T
    if d1 <= d2:
        print("YES")
    else:
        print("NO")

### FIXED CODE ###


import sys
import itertools
from math import gcd
from math import sqrt
from sys import stdin
def input() : return stdin.readline().rstrip()
def mips():
    return map(int,input().split())
def ii():
    return int(input())
sys.setrecursionlimit(10**9)
A,VA = mips()
B,VB = mips()
T = ii()
if A <= B:
    d1 = A + VA * T
    d2 = B + VB * T
    if d1 >= d2:
        print("YES")
    else:
        print("NO")
else:
    d2 = B - VB * T
    d1 = A - VA * T
    if d1 <= d2:
        print("YES")
    else:
        print("NO")
nv,ne = [int(i) for i in input().split()]

g = []

for i in range(nv):
    g.append([])

for i in range(ne):
    s,t = [int(j) for j in input().split()]
    g[s].append(t)

done = []

f = 0

def put_forword(index):
    global f

    if index in done:
        return

    done.append(index)

    for i in g[index]:

        if i == 0:
            f = 1
            return
        put_forword(i)

put_forword(0)

print(f)



### FIXED CODE ###

import math

c1x,c1y,c1r = [int(i) for i in input().split()]
c2x,c2y,c2r = [int(i) for i in input().split()]

d = math.sqrt(pow(c1x-c2x, 2) +  pow(c1y-c2y, 2))

bcr = 0
scr = 0

if c1r > c2r:
    bcr = c1r
    scr = c2r
else:
    bcr = c2r
    scr = c1r


if d > bcr + scr:
    print(4)
elif d == bcr + scr:
    print(3)
elif d + scr > bcr:
    print(2)
elif d + scr == bcr:
    print(1)
else:
    print(0)
case = 0
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    case += 1
    # a list of [itemValue, itemWeight]
    items = [list(map(int,input().split(','))) for i in range(N)]
    dp = {}
    def bestVW(item, capa):
        if (item,capa) in dp:
            return dp[(item,capa)]
        elif item == 0:
            bestVWForCapa = items[item] if items[item][1] <= capa else [0,0]
            dp[(item,capa)] = bestVWForCapa
            return bestVWForCapa
        else:
            if items[item][1] > capa:
                bestVWForCapa = bestVW(item-1, capa)
                dp[(item,capa)] = bestVWForCapa
                return bestVWForCapa
            else:
                pickedVW = bestVW(item-1,capa)
                notPickedVW = list(map(sum, zip(items[item], bestVW(item-1, capa-items[item][1]))))
                bestVWForCapa = pickedVW if pickedVW[0] > notPickedVW[0] else notPickedVW 
                dp[(item,capa)] = bestVWForCapa
                return bestVWForCapa
    print('Case ',case, ':', sep='')
    print('\n'.join(map(str,bestVW(N-1,W))))



### FIXED CODE ###

nCase = 0
while True:
    W = int(input())
    if W == 0: break
    nCase += 1
    N = int(input())
    # [(value, weight), ... ]
    items = [tuple(map(int, input().split(','))) for _ in range(N)]
    bestValueFor = [0] * (W + 1) # item -> best value, idx -> capacity 
    for item in items:
        for capa in reversed(range(W-item[1]+1)):
            # if taken wins not taken
            if bestValueFor[capa] + item[0] > bestValueFor[capa + item[1]]:
                bestValueFor[capa + item[1]] = bestValueFor[capa] + item[0]
    bestValue = max(bestValueFor)
    bestWeight = bestValueFor.index(bestValue)
    print('Case ',str(nCase),':',sep='')
    print(bestValue)
    print(bestWeight)
import math
N,K = map(int, input().split())
a = list(map(int,input().split()))
l = 0
r = K - 1
Min = float("inf")
for i in range(N - K + 1):
    if(a[l]*a[r]<=0):#原点を跨ぐとき
        Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    elif(l == 0 and r == k-1):
        Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))        
    elif(l==0):#左端の時
        if(a[r]*a[r+1]<0 or a[0]>0 or (a[N-1]<0 and r == N-1)):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    elif(r==N-1):#右端の時
        if(a[l-1]*a[l]<0 or (a[l]>0 and l == 0) or a[r] <= 0):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    else:
        if(a[r]*a[r+1]<0 or a[l-1]*a[l]<0):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    l = l + 1
    r = r + 1
print(Min)

### FIXED CODE ###

import math
N,K = map(int, input().split())
a = list(map(int,input().split()))
l = 0
r = K - 1
Min = float("inf")
for i in range(N - K + 1):
    if(a[l]*a[r]<=0):#原点を跨ぐとき
        Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    elif(l == 0 and r == N-1):
        Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))        
    elif(l==0):#左端の時
        if(a[r]*a[r+1]<0 or a[0]>0 or (a[N-1]<0 and r == N-1)):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    elif(r==N-1):#右端の時
        if(a[l-1]*a[l]<0 or (a[l]>0 and l == 0) or a[r] <= 0):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    else:
        if(a[r]*a[r+1]<0 or a[l-1]*a[l]<0):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    l = l + 1
    r = r + 1
print(Min)
x = int(input())
for a in range(101. -101, -1):
  for b in range(-101, 101, 1):
    if x==a**5-b**5:
      print(a, b)
      exit() 

### FIXED CODE ###

x = int(input())
for a in range(200, -200, -1):
  for b in range(-200, 200, 1):
    if x==a**5-b**5:
      print(a, b)
      exit()
import io, sys, itertools
f = sys.stdin
 
 
def take2(iterable):
    i = iter(iterable)
    while True:
        yield next(i), next(i)
 
 
n = int(f.readline())
adj =[[(v, c) for v, c in take2(map(int, f.readline().split()[2:]))] for _ in range(n)]
d = [100000 * 100 + 1] * n
 
d[0] = 0
def search(parent, children):
    global d
    for v, c in children:
        if d[v] > d[parent] + c:
            d[v] = d[parent] + c
            search(v, adj[v])
     
search(0, adj[0])
     
for i in range(n):
    print(i, d[i])

### FIXED CODE ###

import sys, itertools
f = sys.stdin

def take2(iterable):
    i = iter(iterable)
    while True:
        yield next(i), next(i)

n = int(f.readline())
adj =[[(v, c) for v, c in take2(map(int, f.readline().split()[2:]))] for _ in range(n)]
d = [100000 * 100 + 1] * n

d[0] = 0
queue ={0}
while len(queue):
    parent = queue.pop()
    for v, c in adj[parent]:
        if d[v] > d[parent] + c:
            d[v] = d[parent] + c
            queue.update([v])

for i in range(n):
    print(i, d[i])
N,M = list(map(int,input().split()))
l_n = list(input())
l_a = [0] * (N+1)
for i in range(N):
    l_a[i+1] = l_a[i] + 1 if l_n[i] == "A" and l_n[i+1] == "C" else l_a[i]
for i in range(M):
    l,r = list(map(int,input().split()))
    print(l_a[r-1]-l_a[l-1])

### FIXED CODE ###

N,M = list(map(int,input().split()))
l_n = input()
l_a = [0] * (N+1)
for i in range(N):
    l_a[i+1] = l_a[i] + (1 if l_n[i:i+2] == 'AC' else 0)
for i in range(M):
    l,r = map(int,input().split())
    print(l_a[r-1]-l_a[l-1])
N=int(input())
L=list(map(int,input().split()))
L.sort()
L.reverse()
count=0
a=len(L)
#print(L)
for i in range(a-2):
  count1=0
  for j in range(i+1,a-1):
    for k in range(j+1,a):
      if L[i]<L[j]+L[k]:
        count+=1
        #print(L[i],L[j],L[k])
      else:
        count1+=1
        break
    if count1==1:
         break
print(count)

### FIXED CODE ###

a,b=map(int,input().split())
if a>=2*b:
  print(a-2*b)
else:
  print(0)
a, b = map(int, input().split())
def gcd(p, q):
    if p < q:
        p, q = q, p
    while q > 0:
        p, q = q, p%q
    return p
  
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

divisors = make_divisors(gcd(a, b))

def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

prime = [1] + prime(divisors[-1])
print(divisors, prime)
ans = set(divisors) & set(prime)
print(ans)
print(len(ans))

### FIXED CODE ###

a, b = map(int, input().split())
def gcd(p, q):
    if p < q:
        p, q = q, p
    while q > 0:
        p, q = q, p%q
    return p

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

divisors = make_divisors(gcd(a, b))
ans = []
while divisors:
    key = divisors[0]
    ans.append(key)
    divisors.remove(key)
    notans = []
    for value in divisors:
        if gcd(key, value) != 1:
            notans.append(value)
    for i in notans:
        divisors.remove(i)
            
print(len(ans))
def root(i):
  if par[i] == i:
    return i
  par[i] = root(par[i])
  return par[i]

def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx != ry:
    par[ry] = rx

def same(x, y):
  return par[x] == par[y]

n,m = map(int, input().split(" "))
p = [0] + list(map(int, input().split(" ")))
a = [(list(map(int, input().split(" ")))) for i in range(m)]
par = list(range(n + 1))
count = 0
for i, j in a:
  union(i, j)
  #print(par)
#print(p)
for i in range(1, n + 5):
  if same(root(par[p[i]]), root(par[i])):
    count += 1
print(count)

### FIXED CODE ###

import sys
import resource

def root(x):
  if par[x] == x:
    return x
  par[x] = root(par[x])
  return par[x]

def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx != ry:
    par[rx] = ry
  return 0

sys.setrecursionlimit(10 ** 6)
n, m=map(int, input().split(" "))
par = list(range(n + 1))
for i in range(m):
  a, b = map(int, input().split(" "))
  union(a, b)
#print(par)
maxi = 0
count = 1
#print(par)
countpar = [0 for i in range(n + 1)]
#print(len(countpar), len(par))
for i in range(1, n + 1):
  countpar[root(par[i])] += 1
print(max(countpar))
#print(countpar, par)
import collections
 
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
c=collections.Counter(a)
ans=0
for i in a:
  for j in range(31):
    if(2**j>i):
      k=2**j-i
      break
  if k in c.keys():
    if i==k and c[i]>1:
      c[i]-=2
      ans+=1
    elif i!=k and c[i]>0 and c[k]>0:
      c[i]-=1
      c[k]-=1
      ans+=1
print(ans)


### FIXED CODE ###

s=input()
n=0
c=0
for i in range(len(s)):
  if s[i]=='W':
    n+=i-c
    c+=1
print(n)