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

from math import factorial

N = int(input())
S = input()
LR = [0]*(2*N)
LR[0] = 0
if S[0] == "W" or S[-1] == "W":
    print(0)
    exit()
for i in range(1, 2*N):
    if S[i-1] == S[i]:
        LR[i] = (LR[i-1] + 1) % 2
    else:
        LR[i] = LR[i-1]
if LR.count(0) != LR.count(1):
    print(0)
    exit()
L = 0
R = 0
count = 1
for w in LR:
    if w == 0:
        L += 1
    else:
        count *= L - R
        R += 1
print(count * factorial(N) % int(1e9+7))

### FIXED CODE ###

MOD = int(1e9+7)
N = int(input())
S = input()
LR = [0]*(2*N)
LR[0] = 0
l, r = 1, 0
if S[0] == "W" or S[-1] == "W":
    print(0)
    exit()
for i in range(1, 2*N):
    if S[i-1] == S[i]:
        LR[i] = 0 if LR[i-1] == 1 else 1
    else:
        LR[i] = LR[i-1]
    if LR[i] == 0:
        l += 1
    else:
        r += 1
if l != r:
    print(0)
    exit()
L = 0
R = 0
count = 1
for w in LR:
    if w == 0:
        L += 1
    else:
        count *= L - R
        count %= MOD
        R += 1
for i in range(1, N+1):
    count = count * i % MOD
print(count)
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()

    cnt = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            a = L[i]
            b = L[j]
            r = bisect.bisect_left(L, b+a, lo=j+1)
            l = bisect.bisect_right(L, b-a, lo=j+1)
            cnt += r - l
    
    print(cnt)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()

    cnt = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            a = L[i]
            b = L[j]
            r = bisect.bisect_left(L, b+a, lo=j+1)
            l = bisect.bisect_right(L, b-a, lo=j+1)
            cnt += r - l
    
    print(cnt)


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

n,w = map(int,input().split())
dp = {(0,0)}
for i in range(n):
  weight,value = map(int,input().split())
  gone=set()
  for noww,nowv in dp:
    if noww + weight <= w:
      gone.add((noww + weight,nowv + value))
    gone.add((noww,nowv))
  dp = gone
ans = 0
for lastw,lastv in dp:
  ans = max(ans,lastv)
print(ans)

### FIXED CODE ###

def dp():
    n,w = map(int,input().split())
    lis = (map(int,input().split()) for i in range(n))
    
    dpp = [0] * (w + 1)
    for weight, value in lis:
        for j in range(w,weight-1,-1):
            dp = dpp[j-weight] + value
            if dpp[j] < dp:
                dpp[j] = dp
    return max(dpp)
print(dp())
### BUGGY CODE ###

from collections import Counter
import numpy as np


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

for k in range(N):
    c_a = count_A.copy()
    c_a[A[k]] -= 1
    a = np.array(list(c_a.values())).reshape(-1,)
    b = a-1
    print(np.dot(b, a) // 2)

### FIXED CODE ###

from collections import Counter


N = int(input())
A = list(map(int, input().split()))
count_A = Counter(A)
sum_A = sum([i*(i-1)//2 for i in count_A.values()])

for k in range(N):
    n = count_A[A[k]]
    ans = sum_A - n + 1
    print(ans)
### BUGGY CODE ###

n = int(input())
a = []
a = list(map(int, input().split()))
total = 1
if 0 in a:
    total = 0
else:
    for num in a:
        total *= num
if total > 10**18:
    total = -1

print(total)

### FIXED CODE ###

n = int(input())
a = []
a = list(map(int, input().split()))
total = 1
if 0 in a:
    total = 0
else:
    for num in a:
        total *= num
        if total > 10**18:
            total = -1
            break

print(total)
### BUGGY CODE ###

N=int(input())
l=[input() for _ in range(N)]

import collections
c = collections.Counter(l)

ans =[]

for i in range(len(c.most_common())):
    if c.most_common()[i][1] == c.most_common()[0][1]:
        ans.append(c.most_common()[i][0])

ans= sorted(ans)
for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

N=int(input())
l=[input() for _ in range(N)]

l= sorted(l)

import collections
c = collections.Counter(l)
d = c.most_common()

for i in range(len(d)):
    if d[i][1] == d[0][1]:
        print(d[i][0])
### BUGGY CODE ###

import itertools
import numpy as np

a = int(input())
result = 0
mat = np.array(list(itertools.product(range(1, a+1), repeat=3)))
result = np.sum(np.gcd(np.gcd(mat[:, 0], mat[:, 1]),mat[:, 2]))

print(result)

### FIXED CODE ###

from functools import reduce
import math

#def gcd(*numbers):
#    return reduce(math.gcd, numbers)

a = int(input())
result = 0

for i in range(1, a+1):
  for j in range(1, a+1):
    for k in range(1, a+1):
      result += math.gcd(math.gcd(i, j),k)
      
print(result)
### BUGGY CODE ###

n = int(input())

s = []
for nk in range(n):
  tmp = list(input())
  tmp.sort()
  mo = ''
  for i in tmp:
    mo += i

  s.append(mo)
  
count =0
for i in range(n):
  for j in range(i+1,n):
    if s[i] == s[j]:
      count += 1
      
print(count)

### FIXED CODE ###

n = int(input())

s = []
for nk in range(n):
  tmp = list(input())
  tmp.sort()
  mo = ''
  for i in tmp:
    mo += i

  s.append(mo)

def comb(x):
  res = x*(x-1)/2
  return res
  
s.sort()
tc = 1
l = []
ans = 0

for i in range(1,n):
  if s[i-1] == s[i]:
    tc += 1

  else:
    if tc >= 2 :
      ans += comb(tc)
      tc = 1

if tc >= 2 :
  ans += comb(tc)
  tc = 1

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

import sys
S = str(input())

S_inv = S[::-1]

while(1):
    if S_inv=="":
        print("YES")
        sys.exit()
    
    elif len(S_inv)<=4:
        print("NO")
        sys.exit()
    
    elif len(S_inv)==5 and S_inv=="maerd":
        print("YES")
        sys.exit()
    
    elif len(S_inv)==5 and S_inv=="esare":
        print("YES")
        sys.exit()
    
    elif len(S_inv)==5 and (S_inv!="maerd" or S_inv!="esare"):
        print("NO")
        sys.exit()
        
    elif len(S_inv)==6 and S_inv!="resare":
        print("NO")
        sys.exit()
        
    elif len(S_inv)==7 and S_inv!="remaerd":
        print("NO")
        sys.exit()
        
    elif S_inv[:5] == "maerd":
        S_inv = S_inv[5:]
    
    elif S_inv[:5] == "esare":
        S_inv = S_inv[5:]
        
    elif S_inv[:6] == "resare":
        S_inv = S_inv[6:]
        
    elif S_inv[:7] == "remaerd":
        S_inv = S_inv[7:]
  

### FIXED CODE ###

import re
s=input()
if re.search(r"^(dreamer|dream|erase|eraser)*$",s):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###



N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort(reverse = True)
F.sort()

max_f = A[0] * F[-1]

def binary_search(min_f, max_f):
	if min_f == max_f:
		return min_f

	mid_f = min_f + (max_f - min_f)//2
	tmp = 0
	for i in range(N):
		tmp += max(0,A[i] - mid_f // F[i])
	
	if tmp <= K:
		return binary_search(min_f, mid_f)
	else:
		return binary_search(mid_f+1, max_f)

print(binary_search(0, max_f))

### FIXED CODE ###



N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort(reverse = True)
F.sort()

max_f = A[0] * F[-1]

def binary_search(min_f, max_f):
	if min_f == max_f:
		return min_f

	mid_f = min_f + (max_f - min_f)//2
	tmp = 0
	for i in range(N):
		tmp += max(0,A[i] - mid_f // F[i])
	
	if tmp <= K:
		return binary_search(min_f, mid_f)
	else:
		return binary_search(mid_f+1, max_f)

print(binary_search(0, max_f))
### BUGGY CODE ###

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

def f(b):
    r = 0
    for i, ai in enumerate(A):
        r += abs(ai - (b + i + 1))
    return r

mx = (10 ** 9) + 1
mn = (-10 ** 9) - 1

# print(f(0))
while mx - mn > 2:
    m = (mx + mn) // 2
    x = f(m)
    y = f(m+1)
    if x < y:
        mx = m + 1
    else:
        mn = m


ans = []
for i in range(mn, mx+1):
    ans.append(f(i))
print(min(ans))

### FIXED CODE ###

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

def f(b):
    r = 0
    for i, ai in enumerate(A):
        r += abs(ai - (b + i + 1))
    return r


A2 = []
for i, ai in enumerate(A):
    A2.append(ai - (i+1))

SA2 = sorted(A2)
ans = f(SA2[((N+1)//2) - 1])
print(ans)
### BUGGY CODE ###

import bisect
from collections import defaultdict
N,M,Q = map(int,input().split())
lr = [tuple(map(int,input().split())) for i in range(M)]
pq = [tuple(map(int,input().split())) for i in range(Q)]
lr.sort()
l = [lr[i][0] for i in range(M)]
r = [lr[i][1] for i in range(M)]

l_I = {}
for p in range(1,N+1):
    l_I[p] = bisect.bisect_left(l,p)

r_d = {}
for i in range(1,N+1):
    r_d[i] = sorted(r[l_I[i]:])
ans = defaultdict(lambda:{})
for p in range(1,N+1):
    for q in range(p,N+1):
        ans[p][q] = bisect.bisect(r_d[p],q)
for i in range(Q):
    p,q = pq[i]
    print(ans[p][q])


### FIXED CODE ###

import numpy as np
N,M,Q = map(int,input().split())
c = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    c[l][r] += 1
c = np.cumsum(np.cumsum(c,axis=0),axis=1)
for i in range(Q):
    p,q = map(int,input().split())
    print(c[q][q]-c[q][p-1]-c[p-1][q]+c[p-1][p-1])
### BUGGY CODE ###

def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:sum(x))
    dp=[10**10]*(n+1)
    dp[0]=0
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=min(dp[k+1],dp[k]+p)
    for i in range(n,-1,-1):
        if dp[i]!=10**10:
            print(i)
            break
if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:sum(x))
    dp=[10**10]*(n+1)
    dp[0]=0
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=min(dp[k+1],dp[k]+p)
    for i in range(n,-1,-1):
        if dp[i]!=10**10:
            print(i)
            break
if __name__=='__main__':
    main()
### BUGGY CODE ###

inf = float('inf')

# dist[i][j]: iからjへのコスト,  n:頂点数
def warshall_floyd(dist,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    dist[i][j] = 0
                elif dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

N,M = map(int,input().split())
edges = []
ad = [[inf]*N for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1;  b -= 1
    edges.append((a,b,c))
    ad[a][b] = c
    ad[b][a] = c

warshall_floyd(ad,N)
ans = M

for a,b,c in edges:
    for s in range(N):
        for e in range(N):
            if ad[s][a] + c + ad[b][e] == ad[s][e]:
                ans -= 1
                break
        else:
            continue
        break

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

inf = float('inf')

# dist[i][j]: iからjへのコスト,  n:頂点数
def warshall_floyd(dist,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    dist[i][j] = 0
                elif dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

N,M = map(int,input().split())
edges = []
ad = [[inf]*N for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1;  b -= 1
    edges.append((a,b,c))
    ad[a][b] = c
    ad[b][a] = c

warshall_floyd(ad,N)
ans = M

for a,b,c in edges:
    if a > b:
        a,b = b,a
    for s in range(N):
        for e in range(s+1,N):
            if ad[s][a] + c + ad[b][e] == ad[s][e]:
                ans -= 1
                break
        else:
            continue
        break

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

k,s=map(int,input().split())
cnt=0

for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z==s:
        cnt+=1
      else:
        continue
print(cnt)

### FIXED CODE ###

k,s=map(int,input().split())
cnt=0

for x in range(k+1):
  for y in range(k+1):
    z=s-x-y
    if x+y<=s and z<=k:
      cnt+=1
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
#input = sys.stdin.readline
N, M = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(M)]


# In[9]:


union = set(range(1, N+1))
for i in range(M):
    union = union & set(range(lr[i][0], lr[i][1]+1))
print(len(union))


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[15]:


import sys
input = sys.stdin.readline
N, M = map(int, input().split())


# In[ ]:


"""
4 2
1 3
2 4
"""


# In[19]:


l_ = 0
r_ = N
for i in range(M):
    l, r = map(int, input().split())
    l_ = max(l_, l)
    r_ = min(r_, r)


# In[21]:


#print(l_, r_)
ids = r_-l_+1
if ids < 0:
    print(0)
else:
    print(ids)


# In[ ]:
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)

lis = []
for i in range(1, n+1):
    lis.append(str(a.index(i)))
print(" ".join(lis))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
x = np.array(a)
y = list(np.argsort(x)[1::])
#print(y)
y = map(str, y)
#print(y)
print(" ".join(y))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
N = int(input())

G = [[] for i in range(N+1)]
D = [0]*(N+1)
E = [[0]*(N+1) for i in range(N+1)]
Q = []
for i in range(N-1):
    a,b = map(int,input().split())
    Q.append((a,b))
    G[a].append(b)
    G[b].append(a)
    D[a]+=1
    D[b]+=1

mod = max(D)
print(mod)
def dfs(v,p):
    global G,D,E
    k = E[v][p]
    for c in G[v]:
        if c==p:continue
        k = (k+1)%mod
        E[v][c] = k
        E[c][v] = k
        dfs(c,v)
dfs(1,0)
for q in Q:print(E[q[0]][q[1]]+1)

### FIXED CODE ###

from collections import deque
N = int(input())
ab = [list(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
T = [[] for i in range(N)]
for a,b in ab:
    T[a].append(b)
q = deque([0])
color = [0]*N
while q:
    x = q.popleft()
    c = 1
    for y in T[x]:
        if c==color[x]:
            c+=1
        color[y] = c
        c+=1
        q.append(y)
print(max(color))
for i in range(N-1):
    print(color[ab[i][1]])
### BUGGY CODE ###

def calculate(arr,S):

    result = []
    even = 0
    for i in range(len(arr)):

        if i % 2 == 0:
            even = S-calculate2(i+1,arr[i+1:])
            result.append(even)
        else:
            odd = arr[i-1]*2-even
            result.append(odd)
            S = S - even - odd

    return result

def calculate2(i,arr):
    # 取偶数项
    result = 0
    for i in range(len(arr)):
        if i % 2 == 0:
            result += arr[i]
    return result * 2

def calculateTotaAmount(arr):
    return sum(arr)

def printArr(arr):
    result = ""
    for i in range(len(arr)):
        result += str(arr[i]) + " "

    return result



N = int(input())

S = input().split(" ")
aArr = [int(s) for s in S]


result = calculate(aArr,calculateTotaAmount(aArr))

print(" ".join([str(s) for s in result]))

### FIXED CODE ###

def calculate(N, arr, S):
    result = []
    tmp = 0
    for i in range(len(arr)):
        if i % 2 == 1:
            tmp += arr[i] * 2

    x0 = S - tmp

    result.append(x0)

    for i in range(1, N):
        result.append(arr[i - 1] * 2 - result[i - 1])

    return result


def calculate2(i, arr):
    # 取偶数项
    return sum(arr[::2]) * 2


def calculateTotaAmount(arr):
    return sum(arr)


def printArr(arr):
    result = ""
    for i in range(len(arr)):
        result += str(arr[i]) + " "

    return result



N = int(input())

S = input().split(" ")
aArr = [int(s) for s in S]

result = calculate(N, aArr, calculateTotaAmount(aArr))
print(" ".join([str(s) for s in result]))
### BUGGY CODE ###

# -*- coding:utf-8 -*-
"""解説
dp[j][k][s] := x1,...,xjから k枚選んで xiの合計をsにするような選び方の総数

[@lilium氏]
https://atcoder.jp/contests/abc044/submissions/5887235
"""

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

    max_x = max(X)
    dp = [[[0 for _ in range(4000+1)] for __ in range(N+1)] for ___ in range(N+1)]

    dp[0][0][0] = 1

    # dp[i][j][k] := i枚のうちj枚を選んで、和がkになる組み合わせ
    """
    dp[i][j][k] := i枚のうち、k枚のカードを選んで、選んだカードの総和がkになる選び方の総数
    i: i枚目のカード
    j: j枚のカードを選んだ
    k: 選んだカードの総和
    """
    for i in range(N):
        for j in range(N):
            for k in range(4000+1):
                if (k+X[i] < 4000+1) :
                    dp[i+1][j][k] += dp[i][j][k]  # i枚目を選ばなかった
                    dp[i+1][j+1][k+X[i]] += dp[i][j][k]  # i枚目を選んだ

    ans = 0
    for j in range(1, N+1):
        ans += dp[N][j][j*A]
    print(ans)

if __name__ == "__main__":
    solve()


### FIXED CODE ###

# -*- coding:utf-8 -*-
"""解説
dp[j][k][s] := x1,...,xjから k枚選んで xiの合計をsにするような選び方の総数

[@lilium氏]
https://atcoder.jp/contests/abc044/submissions/5887235
"""

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

    max_x = max(X)
    dp = [[[0 for _ in range(4000+1)] for __ in range(N+1)] for ___ in range(N+1)]

    dp[0][0][0] = 1

    # dp[i][j][k] := i枚のうちj枚を選んで、和がkになる組み合わせ
    for i in range(N):
        for j in range(N):
            for k in range(4000+1):
                if dp[i][j][k] != 0:
                    dp[i+1][j][k] += dp[i][j][k]  # i枚目を選ばなかった
                    dp[i+1][j+1][k+X[i]] += dp[i][j][k]  # i枚目を選んだ

    ans = 0
    for j in range(1, N+1):
        ans += dp[N][j][j*A]
    print(ans)

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

def main():
    B_MAX = (80 + 80 - 1) * 80
    H, W = list(map(int, input().split(' ')))
    A = [list(map(int, input().split(' '))) for _ in range(H)]
    B = [list(map(int, input().split(' '))) for _ in range(H)]
    dp = [[[0 for _ in range(B_MAX + 1)] for _ in range(W)] for _ in range(H)]
    dp[0][0][abs(A[0][0] - B[0][0])] = 1
    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            d = abs(A[h][w] - B[h][w])
            for b in range(B_MAX + 1):
                v = 0
                if h > 0:
                    v = max(v, dp[h - 1][w][abs(b - d)])
                    if b + d <= B_MAX:
                        v = max(v, dp[h - 1][w][b + d])
                if w > 0:
                    v = max(v, dp[h][w - 1][abs(b - d)])
                    if b + d <= B_MAX:
                        v = max(v, dp[h][w - 1][b + d])
                dp[h][w][b] = v
    ans = 0
    while dp[H - 1][W - 1][ans] == 0:
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    B_MAX = (80 + 80 - 1) * 80 // 2
    H, W = list(map(int, input().split(' ')))
    A = [list(map(int, input().split(' '))) for _ in range(H)]
    B = [list(map(int, input().split(' '))) for _ in range(H)]
    dp = [[[0 for _ in range(B_MAX + 1)] for _ in range(W)] for _ in range(H)]
    dp[0][0][abs(A[0][0] - B[0][0])] = 1
    max_b = abs(A[0][0] - B[0][0])
    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            d = abs(A[h][w] - B[h][w])
            max_b += d
            for b in range(min(B_MAX, max_b) + 1):
                v = 0
                if h > 0:
                    v = max(v, dp[h - 1][w][abs(b - d)])
                    if b + d <= B_MAX:
                        v = max(v, dp[h - 1][w][b + d])
                if w > 0:
                    v = max(v, dp[h][w - 1][abs(b - d)])
                    if b + d <= B_MAX:
                        v = max(v, dp[h][w - 1][b + d])
                dp[h][w][b] = v
    ans = 0
    while dp[H - 1][W - 1][ans] == 0:
        ans += 1
    print(ans)


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

n = int(input())
ls = [input() for i in range(n)]
ls.sort()
p = []
k = 0
for j in range(n-1):
    if ls[j] == ls[j+1]:
        k += 1
    else:
        p.append(k)
        k = 0
p.append(k)
new = list(set(ls))
new.sort()
for l in range(len(p)):
    if p[l] == max(p):
        print(new[l])
        

### FIXED CODE ###

import collections
n = int(input())
ls = [input() for i in range(n)]
c = collections.Counter(ls)
mx = max(c.values())
A = [e for e,j in c.items() if j == mx]
A.sort()
for p in A:
  print(p)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import collections

def main():
	N, Q = map(int, input().split(" "))
	S = input()
	S = list(S)
	gorlm_num = [1] * len(S)
	
	skill = []
	for _ in range(Q):
		t, d = input().split(" ")
		#print(gorlm_num)
		tmp = [i for i, x in enumerate(S) if x == t]
		for i in tmp:
			tt = gorlm_num[i]
			gorlm_num[i] = 0
			if d == "R" and i != len(S)-1:
				gorlm_num[i+1] += tt
			if d == "L" and i != 0:
				gorlm_num[i-1] += tt
				
	ans = 0
	for i in gorlm_num:
		ans = ans + i
		
	print(ans)
	
if __name__ == "__main__":
	main()
	

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
	
def main():
	N, Q = map(int, input().split())
	S = "_" + input() + "_"
	
	TD = []
	for _ in range(Q):
		tmp = input().split(" ")
		t = tmp[0]
		d = tmp[1]
		TD.append((t, d))
		
	TD.reverse()
	gake_L = 0
	gake_R = N - 1 + 2
	
	for i, val in enumerate(TD):
		t, d = val
		
		if d == "R":
			if t == S[gake_R-1]:
				gake_R -= 1
			if t == S[gake_L]:
				gake_L -= 1
		
		if d == "L":
			if t == S[gake_R]:
				gake_R += 1
			if t == S[gake_L+1]:
				gake_L += 1
	
	print(max(0, gake_R-gake_L-1))
	
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

N = int(input())
list = list(map(int,input().split()))
kosuu = []
total = 0
for i in range(N):
    a = list.count(i+1)
    kosuu.append(a)
    total += ( a * (a-1) ) //2
for i in range(N):
    a = kosuu[list[i]-1]
    print(total-a*(a-1)//2 + (a-1)*(a-2)//2)


### FIXED CODE ###

N = int(input())
list = list(map(int,input().split()))
kosuu = [0] * N
kosuuu = [0] * N
total = 0
listed = sorted(list)
listed.append(-1)
i = 0
count = 1
while i < N:
    a = listed[i]
    if a == listed[i+1]:
        count += 1
    else:
        kosuu[a-1] = count
        total += ( count * (count-1) ) //2
        count = 1
    i += 1
for i in range(N):
    a = kosuu[list[i]-1]
    print(total-a*(a-1)//2 + (a-1)*(a-2)//2)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n - 1):
    s = a.count(i + 1)
    print(s)
print('0')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
from collections import Counter
a_counter = dict(Counter(a))
for i in range(n):
    if i + 1 in a_counter:
        print(a_counter[i + 1])
    else:
        print('0')
### BUGGY CODE ###

from itertools import accumulate
import sys
input = sys.stdin.readline

n,c = map(int,input().split())
x1,v1 = [0],[0]
x2,v2 = [],[]
for _ in range(n):
  a,b = map(int, input().split())
  x1.append(a)
  x2 = [c-a] + x2
  v1.append(b)
  v2 = [b] + v2
x2 = [0] + x2
v2 = [0] + v2

v1, v2 = list(accumulate(v1)), list(accumulate(v2))

f1 = [v1[i] - x1[i] for i in range(n+1)]
f2 = [v2[i] - x2[i] for i in range(n+1)]
g1,x1_ = f1[0],x1[0]
g2,x2_ = f2[0],x2[0]
val = max(v1[n]-x1[n] + g2 - min(x1[n],x2_), v2[n]-x2[n] + g1 - min(x2[n],x1_))
for i in range(1,n+1):
  if g1<f1[i]:
	  g1,x1_ = f1[i], x1[i]
  if g2<f2[i]:
	  g2,x2_ = f2[i], x2[i]
  val = max(val, v1[n-i]-x1[n-i] + g2 - min(x1[n-i],x2_), v2[n-i]-x2[n-i] + g1 - min(x2[n-i],x1_))

print(val)

### FIXED CODE ###

from itertools import accumulate
import sys
input = sys.stdin.readline

def main():
    n,c = map(int,input().split())
    x1,v1 = [0],[0]
    for _ in range(n):
        a,b = map(int, input().split())
        x1.append(a)
        v1.append(b)
    x2 = [0]
    v2 = [0]
    for i in range(n,0,-1):
        x2.append(c-x1[i])
        v2.append(v1[i])

    v1, v2 = list(accumulate(v1)), list(accumulate(v2))
    g1,g2 = [v2[0]-x2[0]],[v2[0]-2*x2[0]]
    for i in range(1,n+1):
        f = v2[i] - x2[i]
        f2 = v2[i] - 2*x2[i]
        g1.append(max(g1[i-1],f))
        g2.append(max(g2[i-1],f2))
    val = max(v1[n]-x1[n] + g2[0], v1[n]-2*x1[n] + g1[0])
    for i in range(1,n+1):
        val = max(val, v1[n-i]-x1[n-i] + g2[i], v1[n-i]-2*x1[n-i] + g1[i])

    print(val)

if __name__=='__main__': main()