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

N,Q = map(int, input().split())
S = list(input())
lr = [list(map(int,input().split())) for i in range(Q)]
S_tmp = []
bef = ''
cnt = 0
for i in range(Q):
    for j in range(lr[i][0] - 1,lr[i][1]):
        S_tmp.append(S[j])
    for s in S_tmp:
        if s == 'C' and bef == 'A':
            cnt += 1
        bef = s
    print(cnt)
    cnt = 0
    S_tmp.clear()



### FIXED CODE ###

N,Q = map(int, input().split())
S = input()
lrs = [list(map(int, input().split())) for i in range(Q)]

total = []
total.append(0)
for i in range(1, N):
    if S[i - 1] == 'A' and S[i] == 'C':
        total.append(1)
    else:
        total.append(0)
totsum = 0
for idx, val in enumerate(total):
    totsum += val
    total[idx] = totsum

for lr in lrs:
    print(total[lr[1] - 1] - total[lr[0] - 1])
### BUGGY CODE ###

def putty(n):
    if (n == 0):
        return [1]
    return [0]+putty(n-1)+[1]+putty(n-1)+[0]

n, x = map(int, input().split())
a = putty(n)
a = a[:x]
print(sum(a))

### FIXED CODE ###

def f(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    elif x <= (a[n-1] + 1):
        return f(n - 1, x - 1)
    else:
        return p[n - 1] + 1 + f(n - 1, x - 2 - a[n - 1])


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

a, p=[1],[1]
for i in range(n):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)
    
print(f(n, x))
### BUGGY CODE ###

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

maxlist = 0
for i in range(N-K+1):
    p = pn[i:i+K]
    maxlist = max(maxlist, sum(p))

ans = (maxlist+K)/2
print('{:.12f}'.format(ans))


### FIXED CODE ###

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

pn_t = [0]
for i in range(N):
    pn_t.append(pn[i]+pn_t[i])

l = 0
for i in range(N-K+1):
    l = max(l, pn_t[K+i]-pn_t[i])
ans = (l+K)/2
print(ans)
### BUGGY CODE ###

N = int(input())
S = str(input())

l = []

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            l.append("{0}{1}{2}".format(S[i], S[j], S[k]))
print(len(list(set(l))))


### FIXED CODE ###

N = int(input())
S = str(input())

ans = 0

for i in range(0, 10):
    a = S.find(str(i))
    if a == -1:
        continue
    for j in range(0, 10):
        b = S.find(str(j), a + 1)
        if b == -1:
            continue
        for k in range(0, 10):
            c = S.find(str(k), b + 1)
            if c == -1:
                continue
            ans += 1
print(ans)
### BUGGY CODE ###

from bisect import bisect_left

N, *L= map(int, open(0).read().split())
X = sorted(L)
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        lb = bisect_left(X[j + 1:], X[j] - X[i])
        ub = bisect_left(X[j + 1:], X[j] + X[i])
        ans += ub - lb
        
print(ans)



### FIXED CODE ###

from bisect import bisect_left

N, *L= map(int, open(0).read().split())
X = sorted(L)
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        ub = bisect_left(X, X[i] + X[j])
        ans += ub - (j + 1)
        
print(ans)
### BUGGY CODE ###

from collections import Counter
input()
A = [int(a) for a in input().split()]
d = Counter(A)
sum_ = sum(A)
for q in range(int(input())):
    B,C = map(int,input().split())
    sum_ += ((C - B) * d[B])
    d[C] += d[B]
    del d[B]
    sum2 = 0
    for k,v in d.items():
        sum2 += k*v
    print(sum2)    

### FIXED CODE ###

import numpy as np

N = int(input())
A = np.array([int(a) for a in input().split()])
ans = sum(A)
lst = np.zeros(10**5+1)
for a in A:
    lst[a] += 1
   
for q in range(int(input())):
    B,C = map(int,input().split())
    ans += (C - B) * lst[B]
    print(int(ans))
    lst[C] += lst[B]
    lst[B] = 0
### BUGGY CODE ###

import numpy as np

D = int(input())
c = [list(map(int,input().split()))]
s = [list(map(int,input().split())) for i in range(D)]

#testcase=[1,17,13,14,13]
testcase=np.ones(D, dtype='int64')
goodChoise=np.ones(D, dtype='int64')

c=np.array(c, dtype='int64')
s=np.array(s, dtype='int64')
lastday=np.zeros(26, dtype='int64')

day=0

def manzokuCounter(D,c,s,testcase):

  manzoku=0
  for day in range(D):
    Plus=s[day,testcase[day]-1]

    lastday[testcase[day]-1] = day+1

    today=(day+1)*np.ones(26)
    LessDayArray=(today-lastday)*c
    Minus=np.sum(LessDayArray)

    manzoku+=Plus-Minus
  return int(manzoku)

manzoku=0

for i in range(D):
  for j in range(26):
    testcase[i]=j+1
    CaseManzoku=manzokuCounter(D,c,s,testcase)
    if CaseManzoku > manzoku:
      goodChoise[i]=j+1
      manzoku=CaseManzoku
    
#print(goodChoise)
#print(manzoku)
for c in goodChoise:
  print(c)

### FIXED CODE ###

import random
D = int(input())
c = [list(map(int,input().split()))]
s = [list(map(int,input().split())) for i in range(D)]

for i in range(D):
  print(random.randint(1,26))
### BUGGY CODE ###

N, M = map(int,input().split())
A_list = []
Dp_list = [0] * (N+1)
Dp_list[0] = 1
for i in range(M):
    A_list.append(int(input()))
if A_list:
    if A_list[0] == 1:
        Dp_list[1] = 0
    else:
        Dp_list[1] = 1
else:
    Dp_list[1] = 1
if N != 1:
    for i in range(2, N + 1):
        if i in A_list:
            continue
#        elif i in A_list and i-1 in A_list:
#            Dp_list = [0] * (N + 1)
#            break
        Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
#        else:
#            Dp_list[i] = 0
        if Dp_list[i] > 1000000007:
            Dp_list[i] -= 1000000007
    print(Dp_list[N])
else:
    print(1)

### FIXED CODE ###

N, M = map(int,input().split())
A_list = set([int(input()) for _ in range(M)])
Dp_list = [0] * (N+1)
Dp_list[0] = 1

if 1 in A_list:
    Dp_list[1] = 0
else:
    Dp_list[1] = 1

if N != 1:
    for i in range(2, N + 1):
        if i in A_list:
            continue

        Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
        Dp_list[i] %= 1000000007
    print(Dp_list[N])
else:
    print(1)
### BUGGY CODE ###

N, Y = map(int, input().split())
ax = ay = az = -1
if 10000*N == Y:
	ay = az = 0
	print(str(N)+" "+str(ay)+" "+str(az))
else:	
	for x in range(N+1):
		for y in range(N+1):
			for z in range(N+1):
				if x+y+z > N or N > x+y+z:
					continue
				total = 10000*x + 5000*y + 1000*z
				if total == Y and x+y+z == N:
					ax = x
					ay = y
					az = z
					break
			else:
				continue
			break
		else:
			continue
		break
	print(str(ax)+" "+str(ay)+" "+str(az))

### FIXED CODE ###

N, Y = map(int, input().split())
ax = ay = az = -1
for x in range(N+1):
	for y in range(N+1):
		if (N-x-y) < 0:
			continue
		total = 10000*x + 5000*y + 1000*(N-x-y)
		if total == Y:
			ax = x
			ay = y
			az = N-x-y
			break
	else:
		continue
	break
print(str(ax)+" "+str(ay)+" "+str(az))
### BUGGY CODE ###

h, w = map(int, input().split())
s = ['']*(h+2)
s[0] = '#'*(w+2)
for i in range(1, h+1):
  s[i] = '#'+input()+'#'
s[h+1] = '#'*(w+2)
m=0
for i in range(1, h+1):
  for j in range(1, w+1):
    if s[i][j]=='.':
      c=1
      px, nx=0, 0
      while s[i][j+px+1]=='.':
        px+=1
      while s[i][j-nx-1]=='.':
        nx+=1
      py, ny=0, 0
      while s[i+py+1][j]=='.':
        py+=1
      while s[i-ny-1][j]=='.':
        ny+=1
      c+=px+py+nx+ny
      if c>m:
        m=c
print(m) 

### FIXED CODE ###

h, w = map(int, input().split())
s = ['']*(h+2)
s[0] = '#'*(w+2)
for i in range(1, h+1):
  s[i] = '#'+input()+'#'
s[h+1] = '#'*(w+2)

l=[[0]*(w+2) for _ in range(h+2)]
r=[[0]*(w+2) for _ in range(h+2)]
u=[[0]*(w+2) for _ in range(h+2)]
d=[[0]*(w+2) for _ in range(h+2)]
for i in range(1, h+1):
  for j in range(1, w+1):
    if s[i][j]=='.':
      l[i][j]=l[i][j-1]+1
  for j in range(w, 0, -1):
    if s[i][j]=='.':
      r[i][j]=r[i][j+1]+1
for j in range(1, w+1):
  for i in range(1, h+1):
    if s[i][j]=='.':
      u[i][j]=u[i-1][j]+1
  for i in range(h, 0, -1):
    if s[i][j]=='.':
      d[i][j]=d[i+1][j]+1
m=0
for i in range(1, h+1):
  for j in range(1, w+1):
    c=l[i][j]+r[i][j]+u[i][j]+d[i][j]-3
    if m<c:
      m=c
print(m)
### BUGGY CODE ###

N = int(input())
from collections import Counter
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ca = Counter(A)
cb = Counter(B)
mod = 10**6
cnts = [[] for _ in range(N+1)]
for i in range(1,N+1):
  if ca[i]+cb[i]>N:
    print('No')
    exit()
  if ca[i]+cb[i]>0:
    cnts[ca[i]+cb[i]].append(i)

def get_any(counts,r):
  for k in counts.keys():
    if counts[k]>0 and k!=r:
      return k

lis = [[] for _ in range(N+1)]
for i in range(N,0,-1):
  if len(cnts[i])==2:
    p,q = cnts[i]
    for j in range(ca[p]):
      lis[p].append(q)
    for j in range(ca[q]):
      lis[q].append(p)
    break
  elif len(cnts[i])==1:
    p, = cnts[i]
    for j in range(ca[p]):
      q = get_any(cb,p)
      cb[q] -= 1
      lis[p].append(q)
    for j in range(cb[p]):
      q = get_any(ca,p)
      ca[q] -= 1
      lis[q].append(p)
    break
  else:
    p = get_any(ca,-1)
    q = get_any(cb,p)
    lis[p].append(q)
    cnts[ca[p]+cb[p]].remove(p)
    cnts[ca[q]+cb[q]].remove(q)
    ca[p] -= 1
    cb[q] -= 1
    cnts[ca[p]+cb[p]].append(p)
    cnts[ca[q]+cb[q]].append(q)
ans = []
for i in range(1,N+1):
  for b in lis[i]:
    ans.append(b)
print('Yes')
print(*ans)


### FIXED CODE ###

N = int(input())
from collections import Counter
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ca = Counter(A)
cb = Counter(B)
mod = 10**6
cnts = [set() for _ in range(N+1)]
for i in range(1,N+1):
  if ca[i]+cb[i]>N:
    print('No')
    exit()
  if ca[i]+cb[i]>0:
    cnts[ca[i]+cb[i]].add(i)

def get_any(counts,r):
  for k in counts.keys():
    if counts[k]>0 and k!=r:
      return k

def update_cnt(cnt_,r):
  cnt_[r] -= 1
  if cnt_[r]==0:
    del cnt_[r]

lis = [[] for _ in range(N+1)]
for i in range(N,0,-1):
  if len(cnts[i])==2:
    p,q = cnts[i]
    for j in range(ca[p]):
      lis[p].append(q)
    for j in range(ca[q]):
      lis[q].append(p)
    break
  elif len(cnts[i])==1:
    p, = cnts[i]
    for j in range(ca[p]):
      q = get_any(cb,p)
      update_cnt(cb,q)
      lis[p].append(q)
    for j in range(cb[p]):
      q = get_any(ca,p)
      update_cnt(ca,q)
      lis[q].append(p)
    break
  else:
    p = get_any(ca,-1)
    q = get_any(cb,p)
    lis[p].append(q)
    cnts[ca[p]+cb[p]].remove(p)
    cnts[ca[q]+cb[q]].remove(q)
    update_cnt(ca,p)
    update_cnt(cb,q)
    cnts[ca[p]+cb[p]].add(p)
    cnts[ca[q]+cb[q]].add(q)
ans = []
for i in range(1,N+1):
  for b in lis[i]:
    ans.append(b)
print('Yes')
print(*ans)
### BUGGY CODE ###

import bisect

_ = input()

heads = list(map(int,input().split()))
bodies = list(map(int,input().split()))
legs = list(map(int,input().split()))


cnt = 0
sorted_heads = list(sorted(heads))
sorted_legs = list(sorted(legs))

for body in bodies:
    #  頭は、体より小さくなければならない
    head_idx = bisect.bisect_left(sorted_heads, body)
    head_cnt = len(sorted_heads[:head_idx])

    #  足は、体より大きくなければならない
    leg_idx = bisect.bisect_right(sorted_legs, body)
    leg_cnt = len(sorted_legs[leg_idx:])

    cnt += head_cnt * leg_cnt # 組み合わせの掛け算

print(cnt)


### FIXED CODE ###

import bisect

N = int(input(), 10)

heads = list(sorted(map(int,input().split())))
bodies = list(map(int,input().split()))
legs = list(sorted(map(int,input().split())))


cnt = 0
for body in bodies:
    #  頭は、体より小さくなければならない
    head_cnt = bisect.bisect_left(heads, body)
    #  足は、体より大きくなければならない
    leg_cnt = N - bisect.bisect_right(legs, body)

    cnt += head_cnt * leg_cnt # 組み合わせの掛け算

print(cnt)
### BUGGY CODE ###

import sys
n, ma, mb = map(int, input().split())
tc = [[] for _ in range(100 * n + 1)]
tn = [[] for _ in range(100 * n + 1)]
high = 100 * n + 1
for i in range(n):
  a, b, c = map(int, input().split())
  if a * mb == b * ma:
    high = c + 1
  tn[c].append((a, b))
  for j in range(1, high):
    for aa, bb in tc[j]:
      tn[j].append((aa, bb))
      tn[c + j].append((a + aa, b + bb))
      if (a + aa) * mb == (b + bb) * ma:
        high = c + j + 1
  tc = tn
  tn = [[] for _ in range(100 * n + 1)]
for i in range(1, 100 * n + 1):
  for a, b in tc[i]:
    if a * mb == b * ma:
      print(i)
      sys.exit()
print(-1)


### FIXED CODE ###

import sys
inf = float('inf')
n, ma, mb = map(int, input().split())
t = [[inf] * 401 for _ in range(401)]
for _ in range(n):
  a, b, c = map(int, input().split())
  for aa in range(400, 0, -1):
    for bb in range(400, 0, -1):
      if t[aa][bb] == inf:
        continue
      if t[a + aa][b + bb] > c + t[aa][bb]:
        t[a + aa][b + bb] = c + t[aa][bb]
  if t[a][b] > c:
    t[a][b] = c
result = inf
for a in range(400, 0, -1):
  for b in range(400, 0, -1):
    if a * mb == b * ma and t[a][b] < result:
      result = t[a][b]
if result == inf:
  print(-1)
else:
  print(result)
### BUGGY CODE ###

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

#print(N,L)
count=0

for i in range(N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      if L[i]<L[j]+L[k]:
        if L[j]<L[i]+L[k]:
          if L[k]<L[i]+L[j]:
            count +=1
            
print(count)
        


### FIXED CODE ###

import bisect

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

L.sort()
#print(L)
count=0

for i in reversed(range(2,N)):
  for j in reversed(range(1,i)):
    index=bisect.bisect_right(L,L[i]-L[j])
    #print(index,j,i)
    if index<j:
     count += j-index
            
print(count)
### BUGGY CODE ###

import itertools
import functools

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

N,C = inp()
D = [[0] * (C+1)]
c = [[], [], []]
for i in range(C):
  D.append([0] + inp())
for i in range(N):
  l = inp()
  for j in range(N):
    c[(i+j)%3].append(l[j])

# print(N,C,D,c)

sc = list(itertools.permutations(list(range(1,C+1)), 3))
# print(sc)

ret = []
for sc_i in sc:
  ret.append(0)
  for i in range(3):    
    ret[-1] += (sum(list(map(lambda x: D[x][sc_i[i]], c[i]))))
  #print(ret[-1])

print(min(ret))

### FIXED CODE ###

import itertools
import functools

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

N,C = inp()
D = [[0] * (C+1)]
c = [[], [], []]
for i in range(C):
  D.append([0] + inp())
for i in range(N):
  l = inp()
  for j in range(N):
    c[(i+j)%3].append(l[j])

# print(N,C,D,c)

sc = list(itertools.permutations(list(range(1,C+1)), 3))
# print(sc)

ret = []
for i in range(3):
  ret.append([])
  for j in range(1,C+1):    
    ret[-1].append(sum(list(map(lambda x: D[x][j], c[i]))))
#  print(ret[-1])

ans = []
for sc_i in sc:
  ans.append(0)
  for i in range(3):
    ans[-1] += ret[i][sc_i[i]-1]
#  print(ans[-1])

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

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] = format(a[i], '060b')
s = 0
for i in range(60):
    c0 = 0
    c1 = 0
    for j in range(n):
        if a[j][i] == '0':
            c0 += 1
        else:
            c1 += 1
    s += pow(2,59-i,MOD)*c0*c1
print(s%MOD)

### FIXED CODE ###

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
s = 0
m = 1
for i in range(60):
    c = sum(ai & m for ai in a)
    c //= m
    s = (s + m*c*(n-c))%MOD
    m <<= 1
print(s)
### BUGGY CODE ###

def solve():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in range(m)]

    cnt = [0]*n
    for i in range(n):
        for j in range(m):
            a, b = ab[j]
            if a == i+1:
                if h[i] <= h[b-1]:
                    cnt[i] -= 1
            elif b == i+1:
                if h[i] <= h[a-1]:
                    cnt[i] -= 1
        


    return cnt.count(0)




print(solve())


### FIXED CODE ###

def solve():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in range(m)]

    cnt = [0]*n
    for j in range(m):
        a, b = ab[j]
        if h[a-1] < h[b-1]:
            cnt[a-1] -= 1
        elif h[b-1] < h[a-1]:
            cnt[b-1] -= 1
        elif h[a-1] == h[b-1]:
            cnt[a-1] -= 1
            cnt[b-1] -= 1

    
    return cnt.count(0)




print(solve())
### BUGGY CODE ###

n = int(input())
S = input()
ans = float("inf")

for i in range(n):
    res = S[:i].count("W") + S[i+1:].count("E")
    ans = min(ans,res)
    
print(ans)

### FIXED CODE ###

n = int(input())
S = input()
WE = [[] for _ in range(n)]
w = 0
e = 0

for i in range(n):
    if S[i] == "W":
        w += 1
    else:
        e += 1
    
    WE[i].append(w)
    WE[i].append(e)
    
ans = WE[n-1][1] - WE[0][1]

for i in range(1,n):
    res = WE[i-1][0] + (WE[n-1][1] - WE[i][1])
    ans = min(ans,res)
    
print(ans)
### BUGGY CODE ###

import sys, bisect, math, itertools, string, queue, copy
#import numpy as np
#import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
# input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

s=input().replace("\n","")
q=inp()

ql = []
for i in range(q):
    tmp = input()
    if tmp[0] == "1":
        ql.append("1")
    else:
        ql.append(tmp.split())

isrev=False
for i in range(q):
  if ql[i][0] == '1':
    isrev = not isrev
    continue
  if (ql[i][1] == '2') == isrev:
    s=ql[i][2]+s
  else:
    s=s+ql[i][2]
if isrev:
  s = s[::-1]

print(s)


### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
#import numpy as np
#import scipy
from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
# input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

s = input()
q = int(input())
ql = [input().split() for i in range(q)]

ans = deque(s)
isrev=False
for i in range(q):
  if ql[i][0] == '1':
    isrev = not isrev
    continue
  if (ql[i][1] == '2') == isrev:
    ans.appendleft(ql[i][2])
  else:
    ans.append(ql[i][2])

if isrev:
  ans.reverse()

s = ''.join(ans)

print(s)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
for i,j in enumerate(a):
    if (i+1) % 2 == 1:
        b.insert(0, j)
    else:
        b.append(j)
        
if len(a) % 2 == 0:
    for i in b[::-1]:
        print(i,end=" ")
else:
    for i in b:
        print(i,end=" ")
    

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b0=[]
b1=[]
for i,j in enumerate(a):
    if (i+1) % 2 == 1:#奇数
        b1.append(j)
    else:#偶数
        b0.append(j)
        
if len(a) % 2 == 0:#偶数だったら逆
    for i in b0[::-1]:
        print(i,end=" ")
    for i in b1:
        print(i,end=" ")
else:
    for i in b1[::-1]:
        print(i,end=" ")
    for i in b0:
        print(i,end=" ")
### BUGGY CODE ###

import sys
import heapq

input = sys.stdin.readline

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()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

q = [[(A[0]+B[0]+C[0])*(-1),0,0,0]]
heapq.heapify(q)
count = 0
alr = [[[False]*Z for i in range(Y)] for i in range(X)]
alr[0][0][0] = True

while count < K:
    poped = heapq.heappop(q)
    ans = poped[0]*(-1)
    print(ans)
    i, j, k = poped[1], poped[2], poped[3]
    if i+1 < X and not alr[i+1][j][k]:
        alr[i+1][j][k] = True
        heapq.heappush(q, [(A[i+1]+B[j]+C[k])*(-1), i+1, j, k])
    if j+1 < Y and not alr[i][j+1][k]:
        alr[i][j+1][k] = True
        heapq.heappush(q, [(A[i]+B[j+1]+C[k])*(-1), i, j+1, k])
    if k+1 < Z and not alr[i][j][k+1]:
        alr[i][j][k+1] = True
        heapq.heappush(q, [(A[i]+B[j]+C[k+1])*(-1), i, j, k+1])
    count += 1


### FIXED CODE ###

import sys

input = sys.stdin.readline

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 = []
ABC = []

for a in A:
    for b in B:
        AB.append(a+b)

AB.sort(reverse=True)
for i in range(min(len(AB), 3000)):
    for c in C:
        ABC.append(AB[i]+c)
        
ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

n = int(input())
s = 'E' + input() + 'W'
ans = len(s)
for i in range(len(s) - 1):
  if (s[i:i + 2] == 'EW'):
    x = s[:i].count('W') + s[i + 2:].count('E')
    if (ans >= x):
      ans = x
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = len(s)
wc = 0
ec = s.count('E')
for i in range(len(s)):
  if (s[i] == 'E'):
    ec -= 1
  if (ans > ec + wc):
    ans = ec + wc
  if (s[i] == 'W'):
    wc += 1
print(ans)
### BUGGY CODE ###

import math
q = int(input())

def isPrime(n):
  if n == 2:
    return True
  if n % 2==0 or n == 1:
    return False
  j = 3
  while j <= math.sqrt(n):
    if n % j == 0:
      return False
    j += 2
  return True

primes = []
for i in range(100000):
  if isPrime(i):
    primes.append(i)


C = []
for i in range(q):
  ran = list(map(int, input().split()))
  for i in range(q):
    if ran[0] % 2 == 0:
        j = ran[0]+1
    j = ran[0]
    count = 0
    while j <= ran[1] :
      if j in primes and (j+1)//2 in primes:
        count += 1
      j += 2
  C.append(count)

for i in range(q):
  print(C[i])


### FIXED CODE ###

primes = [True]*100000
for i in range(2,100000):
  if primes[i] == False:
    continue
  for j in range(2*i, 100000, i):
    primes[j] = False

c = [0]*100000

for i in range(3,100000):
  if primes[i] and primes[(i+1)//2] == True:
    c[i] = c[i-1]+1
  else:
    c[i] = c[i-1]


q = int(input())
ran = []
for i in range(q):
  ran.append(list(map(int, input().split())))
for i in range(q):
  print(c[ran[i][1]]-c[ran[i][0]-1])
### BUGGY CODE ###

from math import factorial
n, a, b = [int(i) for i in input().split()]
mod = 10**9 + 7
ans = 2**n - (factorial(n)//factorial(a)//factorial(n-a)) - (factorial(n)//factorial(b)//factorial(n-b)) -1
print(ans%mod)

### FIXED CODE ###

n, a, b = [int(i) for i in input().split()]
mod = 10**9+7

def func_156d(n, r):
    r =min(r, n-r)
    numerator = 1
    denominator = 1
    
    for i in range(n-r+1, n+1):
        numerator = numerator * i % mod
        
    for i in range(1, r+1):
        denominator = denominator * i % mod
        
    return numerator * pow(denominator, mod-2, mod) %mod

print((pow(2, n, mod) -1 - func_156d(n,a) - func_156d(n,b) + 2*mod) %mod )