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

from collections import deque
h,w = map(int, input().split())
a = [list(input()) for _ in range(h)]

b_y = deque()
b_x = deque()
for i in range(h):
  for j in range(w):
    if a[i][j] == "#":
      b_y.append(i)
      b_x.append(j)
      a[i][j] = 0

d = [[1,0], [-1, 0], [0,-1], [0,1]]
while b_y:
  for y,x in d:
    if 0 <= b_y[0]+y <= h-1 and 0 <= b_x[0]+x <= w-1 and a[b_y[0]+y][b_x[0]+x] == ".":
      a[b_y[0]+y][b_x[0]+x] = a[b_y[0]][b_x[0]]+1
      b_y.append(b_y[0]+y)
      b_x.append(b_x[0]+x)
  b_y.popleft()
  b_x.popleft()

ans = 0
for v in a:
  if max(v) > ans: ans = max(v)
print(ans)

### FIXED CODE ###

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

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)] #全方向調べる

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

n = int(input())
li = []
for i in range(n):
    li.append(int(input()))
for i in range(n):
    k = li[i]
    li[i] = 0
    print(max(li))
    li[i] = k

### FIXED CODE ###

n = int(input())
li = []
for i in range(n):
    li.append(int(input()))
k = max(li)
l = li.index(k)
for i in range(n):
    if i == l:
        li[i] = 0
        print(max(li))
    else:
        print(k)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
ans = 0
count = [0]*n

while True:
    check = set()
    for i in range(n):
        if count[i] >= n-1:
            continue
        ind = l[i][count[i]]-1
        if l[ind].index(i+1) == count[ind]:
            if (not i in check) and (not ind in check): 
                check.add(i)
                check.add(ind)
                count[i] += 1
                count[ind] += 1
    if not check:
        if sum(count) != n*(n-1):
            print(-1)
            exit()
        else:
            print(ans)
            exit()
    ans += 1


### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]
    ans = 1
    count = [0]*n
    check = set()
    game = []
    for i in range(n):
        if count[i] >= n-1 or i in check:
            continue
        ind = l[i][count[i]]-1
        if ind in check:
            continue
        if l[ind].index(i+1) == count[ind]:
            check |= set([i,ind])
            game.append([i,ind])
            count[i] += 1
            count[ind] += 1
    while True:
        gamepre = game
        check = set()
        game = []
        for i,j in gamepre:
            ci = True
            cj = True
            if count[i] >= n-1 or i in check:
                ci = False
            if count[j] >= n-1 or j in check:
                cj = False
            if ci:
                ci = True
                ind = l[i][count[i]]-1
                if ind in check:
                    ci = False
                if ci and l[ind].index(i+1) == count[ind]:
                    check |= set([i,ind])
                    game.append([i,ind])
                    count[i] += 1
                    count[ind] += 1
            if cj:
                cj = True
                ind = l[j][count[j]]-1
                if ind in check:
                    cj = False
                if cj and l[ind].index(j+1) == count[ind]:
                    check |= set([j,ind])
                    game.append([j,ind])
                    count[j] += 1
                    count[ind] += 1
        if not check:
            if sum(count) != n*(n-1):
                print(-1)
                exit()
            else:
                print(ans)
                exit()
        ans += 1
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N=int(input())
mod=10**9+7
if N==1:
  print(0)
  exit()
dp=[[0,0,0,0]for i in range(N-1)]
dp[0]=[64,17,17,2]
for i in range(N-2):
  dp[i+1][3]=dp[i][1]+dp[i][2]+dp[i][3]*10
  dp[i+1][2]=dp[i][0]+dp[i][2]*9
  dp[i+1][1]=dp[i][0]+dp[i][1]*9
  dp[i+1][0]=dp[i][0]*8
  dp[i+1][3]%=mod
  dp[i+1][2]%=mod
  dp[i+1][1]%=mod
  dp[i+1][0]%=mod
print(dp[-1][-1])

### FIXED CODE ###

N=int(input())
mod=10**9+7
if N==1:
  print(0)
  exit()
dp=[[0,0,0]for i in range(N-1)]
dp[0]=[64,34,2]
for i in range(N-2):
  dp[i+1][2]=dp[i][1]+dp[i][2]*10
  dp[i+1][1]=dp[i][0]*2+dp[i][1]*9
  dp[i+1][0]=dp[i][0]*8
  dp[i+1][2]%=mod
  dp[i+1][1]%=mod
  dp[i+1][0]%=mod
print(dp[-1][-1])
### BUGGY CODE ###

n, m = map(int, input().split())
def zs(num):
  k = 6 - len(str(num))
  return '0' * k + str(num)
lst = [[-1] for i in range(n + 1)]
cities = []
for i in range(m):
  temp = tuple(map(int, input().split()))
  lst[temp[0]].append(temp[1])
  cities.append(temp)
for l in lst:
  l.sort()
for tpl in cities:
  a = lst[tpl[0]].index(tpl[1])
  print(zs(tpl[0]) + zs(a))

### FIXED CODE ###

n, m = map(int, input().split())
def zs(num):
    k = 6 - len(str(num))
    return '0' * k + str(num)
lst = []
for i in range(m):
  lst.append(tuple(map(int, input().split())))
slst = sorted(lst)
dic = {}
temp = 0
for i in range(m):
  if slst[i][0] == slst[i - 1][0]:
    temp += 1
  else:
    temp = 1
  dic[slst[i]] = zs(slst[i][0]) + zs(temp)
for i in lst:
  print(dic[i])
### BUGGY CODE ###

from math import sqrt, gcd
def factoring(k): #kを因数分解し、素因数とその個数を辞書に入れて返す。
    dic = dict()
    n = int(sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] = count
    if k != 1: #sqrt(k)までチェックしてもkが1になっていない --> kが素因数
        dic[k] = 1
    return dic

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


from collections import defaultdict


dic = defaultdict(int)

count = 0
for a in A:
    tmp = factoring(a)
    for i in tmp:
        dic[i] = max(tmp[i], dic[i])
        count += tmp[i]

tmp = 0
for i in dic:
    tmp += dic[i]

if count == tmp:
    print ('pairwise coprime')
    exit()

GCD = A[0]
for a in A:
    GCD = gcd(GCD, a)

if GCD == 1:
    print ('setwise coprime')
else:
    print ('not coprime')



### FIXED CODE ###

from math import sqrt, gcd
def factoring(k): #kを因数分解し、素因数とその個数を辞書に入れて返す。
    dic = dict()
    n = int(sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] = count
    if k != 1: #sqrt(k)までチェックしてもkが1になっていない --> kが素因数
        dic[k] = 1
    return dic

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

from collections import defaultdict
from bisect import bisect_left

n = bisect_left(A, 1.5) # 1の数

dic = defaultdict(int)

if N <= 10 ** 5 + n:
    count = 0
    for a in A[max(0, n - 1):]:
        tmp = factoring(a)
        for i in tmp:
            dic[i] = max(tmp[i], dic[i])
            count += tmp[i]

    tmp = 0
    for i in dic:
        tmp += dic[i]

    if count == tmp:
        print ('pairwise coprime')
        exit()

GCD = A[0]
for a in A:
    GCD = gcd(GCD, a)
    if GCD == 1:
        break

if GCD == 1:
    print ('setwise coprime')
else:
    print ('not coprime')
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
C = []
for i in range(M):
    b, c = map(int, input().split())
    for j in range(b):
        C.append(c)
A.sort()
C.sort(reverse=True)
ans = 0
for i in range(N):
    if i < len(C):
        ans += max(A[i], C[i])
    else:
        ans += A[i]
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
C = []
for i in range(M):
    b, c = map(int, input().split())
    C.append([c, b])
A.sort()
C.sort(reverse=True)
ans = 0
k = 0
c = C[k][0]
minC = min(C)
b = 1
flg = False
for i in range(N):
    if flg == True:
        ans += A[i]
    elif b <= C[k][1]:
        ans += max(A[i], c)
        b += 1
    else:
        if k < len(C) - 1:
            k += 1
            c = C[k][0]
            b = 1
            ans += max(A[i], c)
            b += 1
        else:
            flg = True
            ans += A[i]
print(ans)
### BUGGY CODE ###

s = input()
L = len(s)
while True:
    l = len(s)
    s = s.replace("01","")
    s = s.replace("10","")
    if l==len(s): 
        break
print(L-len(s))

### FIXED CODE ###

s = input()
one = s.count("1")
zero = s.count("0")
print(min(one, zero)*2)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
C=[]
for i in range(N):
  C.append(A.index(i+1)+1)
print(*C)



### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
C=[0]*N
for i in range(N):
  C[A[i]-1]=i+1
print(*C)
### BUGGY CODE ###

#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# a = [sys.stdin.readline() for _ in range(n)]
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
import sys,bisect,math
sys.setrecursionlimit(15000)

s = sys.stdin.readline().rstrip()
cum = [0]*(len(s)+1)#cumulative sum
import collections
d = collections.defaultdict(list)
for i in range(len(s)):
    cum[i+1]=cum[i]+int(s[i])
for i in range(len(s)+1):
    d[cum[i]%3].append(i)
ret = 0
#print(cum,d)
for l in d.values():
    #print(l)
    n = len(l)
    can = [[l[i],l[j]] for i in range(n) for j in range(i,n) if l[j] > l[i]+3]
    #print(can)
    #print([[i,j,int(s[i:j])] for i,j in can if int(s[i:j])>2019 and int(s[i:j])%2019==0])
    #print([1 for i,j in can if int(s[i:j])>2019 and int(s[i:j])%2019==0])
    ret += sum(1 for i,j in can if int(s[i:j])>2019 and math.gcd(int(s[i:j]),2019)==2019)
print(ret)


### FIXED CODE ###

# n = int(sys.stdin.readline())
import sys,bisect,math
sys.setrecursionlimit(15000)

s = sys.stdin.readline().rstrip()
cum = [0]*(len(s)+1)#cumulative sum
import collections
d = collections.defaultdict(int)
d[0] = 1
ret = 0
dig = 1
for i in range(len(s))[::-1]:
    cum[i]=(int(s[i])*dig+cum[i+1])%2019
    dig = (dig*10)%2019
    #cum[i+1]=int(s[i:])%2019
    if cum[i] in d:
        ret += d[cum[i]]
    d[cum[i]] += 1
#print(d,cum,ret)
print(ret)
### BUGGY CODE ###

n, k = map(int, input().split())
lis = []
for _ in range(n):
    lis.append(int(input()))
    
lis = sorted(lis)

tmp = 10000000000

for i in range(n-k+1):
    ma = max(lis[i:i+k])
    mi = min(lis[i:i+k])
    
    tmp = min(tmp, ma-mi)
    
print(tmp)

### FIXED CODE ###

n, k = map(int, input().split())
lis = []
for _ in range(n):
    lis.append(int(input()))
    
lis = sorted(lis)

tmp = 10000000000

for i in range(n-k+1):
    ma = lis[i+k-1]
    mi = lis[i]
    
    tmp = min(tmp, ma-mi)
    
print(tmp)
### BUGGY CODE ###

n,W = map(int,input().split())
w = [0]*n
v = [0]*n
for i in range(n): w[i],v[i] = map(int,input().split())
x = w[0]
for i in range(n): w[i] -= x
dp = [[[0]*(4*n+1) for _ in range(n+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(i+1):
        for k in range(4*n+1):
            if (j+1)*x+k <= W and k-w[i] >= 0:
                dp[i+1][j+1][k] = max(dp[i+1][j+1][k],dp[i][j][k-w[i]]+v[i])
            dp[i+1][j][k] = max(dp[i+1][j][k],dp[i][j][k])

"""
for i in range(n+1):
    print(i,"///////////////////////////////////////////////")
    for j in range(n+1):
        print(dp[i][j])
"""
print(max(max(dp[n][j]) for j in range(n+1)))

### FIXED CODE ###

n,W = map(int,input().split())
w = [0]*n
v = [0]*n
for i in range(n): w[i],v[i] = map(int,input().split())
x = w[0]
for i in range(n): w[i] -= x
dp = [[[0]*(4*n+1) for _ in range(n+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(i+1):
        for k in range(4*n+1):
            if (j+1)*x+k <= W and k-w[i] >= 0:
                dp[i+1][j+1][k] = max(dp[i+1][j+1][k],dp[i][j][k-w[i]]+v[i])
            dp[i+1][j][k] = max(dp[i+1][j][k],dp[i][j][k])

"""
for i in range(n+1):
    print(i,"///////////////////////////////////////////////")
    for j in range(n+1):
        print(dp[i][j])
"""
print(max(max(dp[n][j]) for j in range(n+1)))
### BUGGY CODE ###

n,m,q = map(int,raw_input().split())

imos = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
	f,t = map(int,raw_input().split())
	f -= 1
	t -= 1
	for j in range(f+1):
		imos[j][t] += 1

for i in range(n):
	for j in range(1,n):
		imos[i][j] = imos[i][j-1] + imos[i][j]


for i in range(q):
	a,b = map(int,raw_input().split())
	print imos[a-1][b-1]


### FIXED CODE ###

import numpy as np
n,m,q = map(int,raw_input().split())

imos = [[0 for i in xrange(n)] for j in xrange(n)]

for i in xrange(m):
	f,t = map(int,raw_input().split())
	f -= 1
	t -= 1
	imos[f][t] += 1

for i in range(n-1,0,-1):
	for j in range(n):
		imos[i-1][j] = imos[i][j] + imos[i-1][j]

for i in xrange(n):
	imos[i] = np.cumsum(imos[i])

for i in xrange(q):
	a,b = map(int,raw_input().split())
	print imos[a-1][b-1]
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[]
for i in range(x):
    for j in range(y):
        for n in range(z):
            ans.append(a[i]+b[j]+c[n])
ans.sort()
ans=ans[::-1]
cnt=0
while cnt!=k:
    print(ans[cnt])
    cnt+=1

### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ab=[s+t for s in a for t in b]
ab.sort()
ab=ab[-1:-k-1:-1]
abc=[s+t for s in ab for t in c]
abc.sort()
abc=abc[-1:-k-1:-1]
for i in range(len(abc)):
    print(abc[i])
### BUGGY CODE ###

N=int(input())
S=input()
ans=0
for i in range(0,N):
    a=S[0:i].count('E')
    b=S[i:N+1].count('W')
    ans=max(ans,a+b)
print(N-ans)

### FIXED CODE ###

N=int(input())
S=input()
left=0
right=S[1:N].count('E')
ans=left+right
for i in range(1,N):
    if S[i-1]=='W':
        left+=1
    if S[i]=='E':
        right-=1
    ans=min(ans,left+right)
print(ans)
### BUGGY CODE ###

x = list(reversed(input()))
cur = 1
for i in range(len(x)):
    if x[i]=="1":
        cur = cur*2 + 3**i
print(cur%1000000007)

### FIXED CODE ###

L = input()
waru = 1000000007
lis1 = 1
lis2 = 2
for i in range(1,len(L)):
    if L[i] == "0":
        lis1 = (lis1*3) % waru
        lis2 = lis2 % waru
    elif L[i] == "1":
        lis1 = (lis1*3+lis2) % waru
        lis2 = (lis2*2) % waru

print((lis1+lis2) % waru)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
N, Q = [int(i) for i in input().split()]
tree = {i:[] for i in range(1,N+1)}
cost_ls = {i:0 for i in range(1,N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

def plus(node, _from):
    #cost_ls[node] += num
    for child in tree[node]:
        if child == _from:
            continue
        cost_ls[child] += cost_ls[node]
        plus(child, node)

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

plus(1, 0)

print(' '.join(str(cost_ls[i]) for i in range(1,N+1)))

### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

N, Q = map(int, input().split())
V = {i: [] for i in range(1, N + 1)}
for _ in range(N - 1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

C = {i: 0 for i in range(1, N + 1)}

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


def propagate(u, p):
    for v in V[u]:
        if v == p:
            continue
        C[v] += C[u]
        propagate(v, u)


propagate(1, 0)

print(' '.join(str(C[i]) for i in range(1, N + 1)))
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
 
cnt = 0
num = P.index(min(P))+1

for i in range(1,num+1):
  M = min(P[:i])
  if M == P[i-1]:
    cnt += 1
    
print(cnt)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
 
cnt = 0
M = 10**6

for i in range(N):
  if M >= P[i]:
    cnt += 1
    M = P[i]
    
print(cnt)
### BUGGY CODE ###

from functools import reduce

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

MAX  = 10 ** 18
OVER = MAX + 1

result = reduce(lambda x, acc: x * min(acc, OVER), xs)

if result <= MAX:
  print(result)
else:
  print(-1)

### FIXED CODE ###

from functools import reduce

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

MAX  = 10 ** 18

if 0 in xs:
  print(0)
  exit(0)

result = 1
  
for x in xs:
  result *= x
  
  if result > MAX:
    print(-1)
    exit(0)
    
print(result)
### BUGGY CODE ###

from itertools import accumulate
from functools import lru_cache

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

if k > 41:
    k = 41

@ lru_cache(maxsize=None)
def main():
    global a
    for _ in range(k):
        b = [0]*(n+1)
        for i,j in enumerate(a):
            b[max(0,i-j)] += 1
            b[min(n,i+j+1)] -= 1
        a = list(accumulate(b))
        for i in range(n+1):
            if a[i] >= n:
                a[i] = n
    print(*a[:-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

from itertools import accumulate
from copy import deepcopy

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

if k > 41:
    k = 41

for _ in range(k):
    b = [0]*(n+1)
    for i,j in enumerate(a):
        b[max(0,i-j)] += 1
        b[min(n,i+j+1)] -= 1
    a = list(accumulate(b))
    for i in range(n+1):
        if a[i] >= n:
            a[i] = n

print(*a[:-1])
### BUGGY CODE ###

import numpy as np

def solve():
    N,M,K = list(map(int,input().split()))
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))

    C = np.sort(A + B)

    if sum(C) <= K:
        print(int(N+M))
        return

    for i in range(len(C)):
        if sum(C[:i]) <= K and K < sum(C[:i+1]):
             print(int(i))
             return


solve()


### FIXED CODE ###

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

a = [0]*(N+1)
b = [0]*(M+1)

for i in range(N):
    a[i+1] = a[i] + A[i]
for j in range(M):
    b[j+1] = b[j] + B[j]

n_b = M
best = 0

for n_a in range(N+1):
    if K < a[n_a]:
        break

    while  K < a[n_a] + b[n_b]:
        n_b -= 1

    best = max(n_a + n_b,best)

print(int(best))
### BUGGY CODE ###

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

ans = 2018
if l-n >= 672:
    ans = 0
else:
    for i in range(l,n+1):
        ii = i % 2019
        for j in range(l,n+1):
            if i != j:
                jj = j % 2019
                ansss = ii*jj%2019
                if ansss == 0:
                    ans = 0
                    break
                elif ansss < ans:
                    ans = ansss

print(ans)


### FIXED CODE ###

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

ll = l % 2019
ans = 2018
if l-n >= 672:
    ans = 0
else:
    for i in range(ll,ll + n-l +1):
        if i % 673 == 0:
            ans = 0
            break
        else:
            for j in range(ll,ll + n-l +1):
                if i != j:
                    ansss = i*j%2019
                    if ansss == 0:
                        ans = 0
                        break
                    elif ansss < ans:
                        ans = ansss

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

def main():
    h = int(input())
    cnt = 0
    ans = 0
    tmp = 1
    while True:
        h //=2

        cnt += tmp
        tmp *= 2
        if h==1:
            break

    print(cnt+tmp)
if __name__=='__main__':
    main()


### FIXED CODE ###

import math
def main():
    h = int(input())
    cnt = 0
    ans = 0
    tmp = 1
    a = int(math.log2(h))
    cnt = 2 **a
    ans = (1-2**a)//(1-2)
    print(ans+cnt)
    
if __name__=='__main__':
    main()
### BUGGY CODE ###

def ind(l, x):
    if x in l:
        return l.index(x)
    else:
        return False

a=[]
N = int(input())
for i in range(N):
    nu=int(input().strip())
    if nu in a:
        ind=a.index(nu)
        a=a[:ind]+a[ind+1:]
    else:
        a.append(nu)
#    print(a)
    


print(len(a))

### FIXED CODE ###

d={}
N = int(input())
    
for i in range(N):
    b=int(input().strip())
    if b in d:
        d.pop(b)
    else:
        d[b]=-1
print(len(d))
### BUGGY CODE ###

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

  num_ones = [0 for x in range(60)]
  for i in range(N):
    k = A[i]
    cnt = 0
    while k:
      num_ones[cnt] += k % 2
      cnt += 1
      k >>= 1

  powers_of_two = [1]
  for i in range(1,60):
    powers_of_two.append((powers_of_two[-1] * 2) % 1000000007)
  
  ans = 0
  for i in range(N-1):
    for j in range(60):
      if A[i] & 1 == 0:
        ans = (ans + powers_of_two[j] * num_ones[j]) % 1000000007
      else:
        num_ones[j] -= 1
        ans = (ans + powers_of_two[j] * (N - i - 1 - num_ones[j])) % 1000000007
      A[i] >>= 1
  print(ans)
        
d()

### FIXED CODE ###

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

ans = 0
for i in range(60):
  p = 1 << i
  num_one = len([1 for x in A if x & p])
  ans = ans + p * num_one * (N - num_one)
print(ans % 1000000007)
### BUGGY CODE ###

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
k = int(input())

ans = 0

for x in range(1,k+1):
    for y in range(1,k+1):
        xy = gcd(x,y)
        for z in range(1,k+1):
            ans += gcd(xy,z)

print(ans)


### FIXED CODE ###

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
k = int(input())

ans = 0

for x in range(1,k+1):
    for y in range(1,k+1):
        xy = gcd(x,y)
        for z in range(1,k+1):
            ans += gcd(xy,z)

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

# sys.stdin.readline()
import math

def decision(s,td,index):
    #index番目の文字が落ちるかどうかを判別
    #右に落ちるときは1，左に落ちるときは-1，落ちないときは0を返す
    global N,Q
    qi = 0
    j = index
    for qi in range(Q):
        if j < 0 or j >= N:
            break
        if s[j] == td[qi][0]:
            if td[qi][1] == 'L':
                j -= 1
            elif td[qi][1] == 'R':
                j += 1
    if j == -1:
        return -1
    elif j == N:
        return 1
    else:
        return 0
 
N,Q = map(int,input().split())
s = input()

td = [input().split() for _ in range(Q)]
    
#td[i][j]:i番目の文字(j=0)と方向(j=1)
    
    
RN = math.ceil(math.log2(N))
#2分探索
left = 0
right = N-1
#右側のボーダー
for i in range(RN):
    mid = int((right+left)/2)
    state = decision(s,td,mid)
    if state < 1:
        left = mid
    else:
        right = mid
    if (right - left) == 1:
        break
if right == N-1 and decision(s,td,right) == 0:
    right += 1
border_r = right
    
left = 0
right = N-1
#左側のボーダー
for i in range(RN):
    mid = int((right+left)/2)
    state = decision(s,td,mid)
    if state > -1:
        right = mid
    else:
        left = mid
    if (right - left) == 1:
        break
if left == 0 and decision(s,td,left) == 0:
    right -= 1
border_l = right
print(border_r-border_l)
 

### FIXED CODE ###

# sys.stdin.readline()
import math
import sys
input = sys.stdin.readline


def decision(s,td,j):
    #index番目の文字が落ちるかどうかを判別
    #右に落ちるときは1，左に落ちるときは-1，落ちないときは0を返す
    global N,Q
    for [qi,v] in td:
        if j < 0 or j >= N:
            break
        if s[j] == qi:
            if v == 'L':
                j -= 1
            else:
                j += 1
    if j == -1:
        return -1
    elif j == N:
        return 1
    else:
        return 0
 
N,Q = map(int,input().split())
s = input()
td = [input().split() for _ in range(Q)]
    
#td[i][j]:i番目の文字(j=0)と方向(j=1)
    
    
RN = math.ceil(math.log2(N))
#2分探索
left = 0
right = N-1
#右側のボーダー
for i in range(RN):
    mid = (right+left)//2
    state = decision(s,td,mid)
    if state < 1:
        left = mid
    else:
        right = mid
    if (right - left) == 1:
        break
if right == N-1 and decision(s,td,right) == 0:
    right += 1
border_r = right
    
left = 0
right = N-1
#左側のボーダー
for i in range(RN):
    mid = ((right+left)//2)
    state = decision(s,td,mid)
    if state > -1:
        right = mid
    else:
        left = mid
    if (right - left) == 1:
        break
if left == 0 and decision(s,td,left) == 0:
    right -= 1
border_l = right
print(border_r-border_l)