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

n = int(input())
xys = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        xys[i].append((x-1, y))

def digitsum(x):
    ret = 0
    while x>0:
        ret += x & 1
        x <<= 1
    return ret

ans = 0
for i in range(1<<n):
    ok = True
    for j in range(n):
        # if jth person may be honest, verify testimony of him.
        if (i>>j) & 1 == 1:
            for xy in xys[j]:
                x, y = xy
                if (i>>x) & 1 != y:
                    ok = False
                    break
        if not ok:
            break
    if ok:
        ans = max(ans, digitsum(i))
print(ans)

### FIXED CODE ###

n = int(input())
xys = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        xys[i].append((x-1, y))

def digitsum(x, base=2):
    ret = 0
    while x>0:
        ret += x % base
        x = x // base
    return ret

ans = 0
for i in range(1<<n):
    ok = True
    for j in range(n):
        # if jth person may be honest, verify testimony of him.
        if (i>>j) & 1 == 1:
            for xy in xys[j]:
                x, y = xy
                if (i>>x) & 1 != y:
                    ok = False
                    break
        if not ok:
            break
    if ok:
        ans = max(ans, digitsum(i))
print(ans)
### BUGGY CODE ###

# coding: utf-8

# import numpy as np

"""
20191119
24分ギブアップ
質問

20191120
12分
"""


def main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())

    dp = [[0 for _ in range(W+1)] for _ in range(N)]

    for n in range(N):
        for w in range(W+1):
            if w >= ws[n]:
                dp[n][w] = max(dp[n-1][w-ws[n]]+vs[n], dp[n-1][w])  # use or not use
            else:
                dp[n][w] = dp[n-1][w]  # not use

    return max(dp[-1])


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


### FIXED CODE ###

# coding: utf-8

# import numpy as np

"""
20191119
24分ギブアップ
質問

20191120
12分
"""


def main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())

    dp = [[0 for _ in range(W+1)] for _ in range(N)]

    for n in range(N):
        for w in range(W+1):
            if w >= ws[n]:
                dp[n][w] = max(dp[n-1][w-ws[n]]+vs[n], dp[n-1][w])  # use or not use
            else:
                dp[n][w] = dp[n-1][w]  # not use

    return max(dp[-1])


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

N= int(input())
A = list(map(int, input().split()))
C=0
for i in range(N):
    k=A.count(i+1)
    C += k * (k - 1) / 2
for i in range(N):
    print(int(C-(A.count(A[i]))+1))

### FIXED CODE ###

import math
import collections

def cmb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
N = int(input())
M = input().split()

total = 0
count = collections.Counter(M)

for i in count.values():
    if i >= 2:
        total += cmb(i, 2)
    
for j in M:
    print(total - (count[j]-1))
### BUGGY CODE ###

n = int(input())
s = list(input())

r = [i for i, x in enumerate(s) if x == 'R']
g = [i for i, x in enumerate(s) if x == 'G']
b = [i for i, x in enumerate(s) if x == 'B']

c = 0

for k in r:
    for j in g:
        for i in b:
            a = []
            a.append(k)
            a.append(j)
            a.append(i)
            a.sort()
            if a[1] - a[0] != a[2] - a[1]:
                c += 1

print(c)

### FIXED CODE ###

n = int(input())
s = list(input())

r = s.count('R')
g = s.count('G')
b = s.count('B')

# 1つ目の条件を満たす組の数
ans = r * g * b

# 2つ目の条件を満たす組の数
c = 0
for i in range(n):
    for j in range(i+1,n):
        k = 2 * j -i
        if k > n-1:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            c += 1

print(ans - c)
### BUGGY CODE ###

import itertools
from collections import Counter
N, K = map(int, input().split())
MOD = 10**9 + 7
pluse = 10**10
n = []
comb_list = []
for i in range(N+1):
    n.append(pluse+i)
for i in range(K,N+2):
    tmp = list(itertools.combinations(n,i))
    for j in range(len(tmp)):
        comb_list.append(sum(tmp[j]))
# print(comb_list)
counter = Counter(comb_list)
print(len(counter.values())%MOD)


### FIXED CODE ###

N,K = map(int,input().split())
mod = 10**9 + 7
ans = 0
for i in range(K,N+2):
    M = i*(2*N-i+1)//2
    m = i*(i-1)//2
    ans += (M - m + 1)
print(ans % mod)
### BUGGY CODE ###

import sys
import numpy as np
import itertools
readline = sys.stdin.readline

n = int(readline())
a = list(map(int, readline().split()))

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

ans = np.mod(ans, 1e+9 + 7)

print(f"{ans:.0f}")

### FIXED CODE ###

def main():
    import sys
    readline = sys.stdin.readline

    mod = 10**9 + 7

    n = int(readline())
    A = list(map(int, readline().split()))

    sumA = sum(A) % mod
    ans = 0

    for i in A:
        sumA -= i
        ans += i * sumA
        ans %= mod

    ans %= mod
    print(ans)


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

txt = input()
n = (int)(input())
count = 0
for i in range(n):
  temp = input()
  if temp[0] == '1':
    count += 1
  else:
    sec, moji = (int)(temp.split(" ")[1]), temp.split(" ")[2]
    if (sec + count) % 2 == 1:
      txt = moji + txt
    else:
      txt += moji
if count % 2 == 1:
  txt = txt[::-1]
print(txt) 

### FIXED CODE ###

txt = input()
n = (int)(input())
count = 0
sentou = ""
saigo = ""
for i in range(n):
  temp = input()
  if temp[0] == '1':
    count += 1
  else:
    sec, moji = (int)(temp.split(" ")[1]), temp.split(" ")[2]
    if (sec + count) % 2 == 1:
      sentou = moji + sentou
    else:
      saigo += moji
if count % 2 == 1:
  txt = saigo[::-1] + txt[::-1] + sentou[::-1]
else:
  txt = sentou + txt + saigo
print(txt)
### BUGGY CODE ###

from collections import Counter
import sys

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


def f(c1, c2, c3, s):
    if dp[c1][c2][c3] != -1:
        return dp[c1][c2][c3]

    res = n
    if c1 != 0:
        res += f(c1 - 1, c2, c3, s - 1) * c1
    if c2 != 0:
        res += f(c1 + 1, c2 - 1, c3, s) * c2
    if c3 != 0:
        res += f(c1, c2 + 1, c3 - 1, s) * c3
    res /= s
    dp[c1][c2][c3] = res
    return res


n = int(input())
a = tuple(map(int, input().split()))

dp = tuple(
    tuple(
        [-1] * (n + 1) for _ in range(n + 1)
    ) for _ in range(n + 1))
dp[0][0][0] = 0
# dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

c = Counter(a)
c1 = c[1]
c2 = c[2]
c3 = c[3]

print(f(c1, c2, c3, c1 + c2 + c3))

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p


### FIXED CODE ###

def main():
    from collections import Counter

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              / (r1 + r2 + r3)

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした
# resの加算を複数回に分けると
# 三項演算子より遅くなる
# 再帰関数を辞めた
### BUGGY CODE ###

N=int(input())
M=0
for i in range(1,N+1):
    j=(i+1)%(N+1)
    if j==0:
        j=1
    # print(i,j,i%j)
    M+=i%j
print(M)

### FIXED CODE ###

N=int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

import bisect
from operator import itemgetter
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W = IL()
grid = [[i for i in S()] for i in range(H)]
cntH = [[0 for i in range(W)] for i in range(H)]
cntW = [[0 for i in range(W)] for i in range(H)]

for h in range(H):
  cnt = 0
  for w in range(W):
    if grid[h][w] == "#":
      cnt = 0
    else:
      cnt += 1
      cntW[h][w] = cnt

for h in range(H-1,-1,-1):
  cnt = 0
  for w in range(W-1,-1,-1):
    if grid[h][w] == "#":
      cnt = 0
    elif cnt == 0:
      cnt = cntW[h][w]
    else:
      cntW[h][w] = cnt

for w in range(W):
  cnt = 0
  for h in range(H):
    if grid[h][w] == "#":
      cnt = 0
    else:
      cnt += 1
      cntH[h][w] = cnt

for w in range(W-1,-1,-1):
  cnt = 0
  for h in range(H-1,-1,-1):
    if grid[h][w] == "#":
      cnt = 0
    elif cnt == 0:
      cnt = cntH[h][w]
    else:
      cntH[h][w] = cnt

ans = 0
for h in range(H):
  for w in range(W):
    ans = max(ans,cntW[h][w]+cntH[h][w])

print(ans-1)

### FIXED CODE ###

H,W = list(map(int,input().split()))
grid = [[i for i in input()] for i in range(H)]
cntH = [[0 for i in range(W)] for i in range(H)]
cntW = [[0 for i in range(W)] for i in range(H)]

for h in range(H):
  cnt = 0
  for w in range(W):
    if grid[h][w] == "#":
      cnt = 0
    else:
      cnt += 1
      cntW[h][w] = cnt

for h in range(H-1,-1,-1):
  cnt = 0
  for w in range(W-1,-1,-1):
    if grid[h][w] == "#":
      cnt = 0
    elif cnt == 0:
      cnt = cntW[h][w]
    else:
      cntW[h][w] = cnt

for w in range(W):
  cnt = 0
  for h in range(H):
    if grid[h][w] == "#":
      cnt = 0
    else:
      cnt += 1
      cntH[h][w] = cnt

for w in range(W-1,-1,-1):
  cnt = 0
  for h in range(H-1,-1,-1):
    if grid[h][w] == "#":
      cnt = 0
    elif cnt == 0:
      cnt = cntH[h][w]
    else:
      cntH[h][w] = cnt

ans = 0
for h in range(H):
  for w in range(W):
    ans = max(ans,cntW[h][w]+cntH[h][w])

print(ans-1)
### BUGGY CODE ###

# 2つの部分列に分ける
def eqcut(start, end):
    target = (cumA[start - 1] + cumA[end]) / 2  # start = 0のときcumA[-1] = 0

    ok = start
    ng = end + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if cumA[mid] <= target:
            ok = mid
        else:
            ng = mid
    # okかok+1
    if ok == end:
        return ok
    else:
        diff1 = abs( (cumA[end] - cumA[ok]) - (cumA[ok] - cumA[start - 1]))
        diff2 = abs( (cumA[end] - cumA[ok + 1]) - (cumA[ok + 1] - cumA[start - 1]))
        if diff1 <= diff2:
            return ok
        else:
            return ok + 1
            

N = int(input())
A = [int(x) for x in input().split()]

cumA = [A[0]] + [0] * N  # 累積和  cumA[-1] = 0となるように最後にダミー
for i in range(1, N):
    cumA[i] = cumA[i - 1] + A[i]

S = [0, 0, 0, 0]
B = [0, 0]
ans = cumA[N - 1]
# 3本の境界線のうち中央を探す
for i in range(1, N - 2):
    B[0] = eqcut(0, i)  # A[0], ..., A[i]を要素の総和が最小となる2つの部分列に分ける
    S[0] = cumA[B[0]]
    S[1] = cumA[i] - cumA[B[0]]

    B[1] = eqcut(i + 1, N - 1)
    S[2] = cumA[B[1]] - cumA[i]
    S[3] = cumA[N - 1] - cumA[B[1]]

    ans = min(ans, max(S) - min(S))

print(ans)

### FIXED CODE ###

# 2つの部分列に分ける
def eqcut(start, end):
    target = (cumA[start - 1] + cumA[end]) / 2  # start = 0のときcumA[-1] = 0

    ok = start
    ng = end + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if cumA[mid] <= target:
            ok = mid
        else:
            ng = mid
    # okかok+1
    if ok == end:
        return ok
    else:
        diff1 = abs( (cumA[end] - cumA[ok]) - (cumA[ok] - cumA[start - 1]))
        diff2 = abs( (cumA[end] - cumA[ok + 1]) - (cumA[ok + 1] - cumA[start - 1]))
        if diff1 <= diff2:
            return ok
        else:
            return ok + 1
            

N = int(input())
A = [int(x) for x in input().split()]

cumA = [A[0]] + [0] * N  # 累積和  cumA[-1] = 0となるように最後にダミー
for i in range(1, N):
    cumA[i] = cumA[i - 1] + A[i]

S = [0, 0, 0, 0]
B = [0, 0]
ans = cumA[N - 1]
# 3本の境界線のうち中央を探す
for i in range(1, N - 2):
    B[0] = eqcut(0, i)  # A[0], ..., A[i]を要素の総和が最小となる2つの部分列に分ける
    S[0] = cumA[B[0]]
    S[1] = cumA[i] - cumA[B[0]]

    B[1] = eqcut(i + 1, N - 1)
    S[2] = cumA[B[1]] - cumA[i]
    S[3] = cumA[N - 1] - cumA[B[1]]

    ans = min(ans, max(S) - min(S))

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

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

def main():
	s = raw_input()
	s2 = raw_input()
	x, y = [int(x) for x in s2.split()]
	# print s, x, y

	xt, yt = [], []
	d, step = 0, 0
	for c in s:
		if c == 'T':
			if d == 0:
				xt.append(step)
			else:
				yt.append(step)
			step = 0
			d = 1 - d
		else:
			step += 1
	if step > 0:
		if d == 0:
			xt.append(step)
		else:
			yt.append(step)

	x -= xt[0]
	xt = xt[1:]
	xd, yd = [0], [0]
	for t in xt:
		xd2 = []
		for i in xd:
			xd2.append(i + t)
			xd2.append(i - t)
		xd = xd2
	for t in yt:
		yd2 = []
		for i in yd:
			yd2.append(i + t)
			yd2.append(i - t)
		yd = yd2

	if x in xd and y in yd:
		print 'Yes'
	else:
		print 'No'


if __name__ == '__main__':
	main()

### FIXED CODE ###

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

def main():
	s = raw_input()
	s2 = raw_input()
	x, y = [int(x) for x in s2.split()]
	# print s, x, y

	xt, yt = [], []
	d, step = 0, 0
	for c in s:
		if c == 'T':
			if d == 0:
				xt.append(step)
			else:
				yt.append(step)
			step = 0
			d = 1 - d
		else:
			step += 1
	if step > 0:
		if d == 0:
			xt.append(step)
		else:
			yt.append(step)

	x -= xt[0]
	xt = xt[1:]
	xd, yd = set([0]), set([0])
	for t in xt:
		xd2 = set()
		for i in xd:
			xd2.add(i + t)
			xd2.add(i - t)
		xd = xd2
	for t in yt:
		yd2 = set()
		for i in yd:
			yd2.add(i + t)
			yd2.add(i - t)
		yd = yd2

	if x in xd and y in yd:
		print 'Yes'
	else:
		print 'No'


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

# ABC 156 D
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nms = lambda: map(str, input().split())
nl = lambda: list(map(int, input().split()))
# def factorial_mod(n, mod):
#     a = 1
#     for i in range(1, n + 1):
#         a *= i
#         a %= mod
#     return a
# def comb_mod(n, k, mod):
#     if k > n or k < 0:
#         return 0
#     fact_n = factorial_mod(n, mod)
#     fact_k = factorial_mod(k, mod)
#     fact_n_k = factorial_mod(n - k, mod)
#     return (fact_n * pow(fact_k, mod - 2, mod) * pow(fact_n_k, mod - 2, mod)) % mod
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
def spow(x, n,mod):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x%mod
        x = x*x%mod
        n = n >> 1 #ビットシフト
    return ans
n,a,b=nm()
MOD = 10**9 + 7
cn=spow(2,n,MOD)
ca=cmb(n,a)
cb=cmb(n,b)
# t=1
# for i in range(n):
#     t*=2%MOD
#     print(t)
# cn=(2**n)%MOD
print((cn-ca-cb-1)%MOD)
# print(ca)
# print(cb)
# ca=comb_mod(n, a, MOD)
# cb=comb_mod(n, b, MOD)
# cn=n*(n+1)*(2*n+1)//12-n*(n+1)//2
# # cn=cn%MOD
# # ca=ca%MOD
# # cb=cb%MOD
# print((cn-ca-cb))

### FIXED CODE ###

# D - Bouquet
def comb(n,k,mod):
    a = 1
    b = 1
    for i in range(k):
        a = a * (n-i) % mod
        b = b * (i+1) % mod
    return a * pow(b, mod-2, mod) % mod
n,a,b=map(int,input().split())
mod=10**9+7
c_n=pow(2,n,mod)-1
c_a=comb(n,a,mod)
c_b=comb(n,b,mod)
print((c_n-c_a-c_b)%mod)
### BUGGY CODE ###

s = list(input())
q = int(input())
q1 = [list(map(str, input().split())) for _ in range(q)]

f = 1
tail1 = []
head1 = []
for i in q1:
    if i[0] == "1":
        f *= -1
    else:
        j,x,s1 = i
        if (x == "1" and f == 1) or (x == "2" and f == -1):
            head1 = [s1] + head1
        else:
            tail1 = tail1 + [s1]

s2 = (head1 + s + tail1)[::f]

print("".join(s2))

### FIXED CODE ###

from collections import deque
 
S = input()
L = deque([])
for c in S:
    L.append(c)
Q = int(input())
flag = 1
for _ in range(Q):
    q = list(input().split())
    if q[0] == "1":
        flag *= -1
    else:
        F = q[1]
        if F == "1":
            if flag == 1:
                L.appendleft(q[2])
            else:
                L.append(q[2])
        else:
            if flag == 1:
                L.append(q[2])
            else:
                L.appendleft(q[2])
if flag == 1:
    print("".join(map(str, L)))
else:
    L.reverse()
    print("".join(map(str, L)))
### BUGGY CODE ###

a = int(input())
i = list(map(int, input().split()))

ans = 1
flag = 0
for x in range(len(i)):
    ans = ans * i[x]
    if ans > 1000000000000000000:
        flag = 1
    if i[x] == 0:
        flag = 2

if flag == 1:
    print(-1)
elif flag == 2:
    print(0)
else:
    print(ans)

### FIXED CODE ###

a = int(input())
i = list(map(int, input().split()))

ans = 1
flag = 0

if i.count(0) > 0:
    print(0)
    flag = 1

if flag == 0:
    for x in range(len(i)):
        ans = ans * i[x]
        if ans > 1000000000000000000:
            flag = 1
            break

    if flag == 1:
        print(-1)
    elif flag == 2:
        print(0)
    else:
        print(ans)
### BUGGY CODE ###

N = int(input())
A = {}
for i in range(N):
    A[i] = list(map(lambda x: int(x)-1, input().split()))

days = 0
games_amount = 0
for i in range(N*(N-1)//2):
    games = 0
    not_played = set(range(N))
    for j in range(N):
        if len(A[j]) == 0 or j not in not_played or A[j][0] not in not_played:
            continue
        if A[A[j][0]][0] == j:
            t1 = A[j].pop(0)
            not_played.remove(t1)
            not_played.remove(A[t1].pop(0))
            games += 1
            games_amount += 1
        if games*2 >= N:
            break
    if games == 0:
        print(-1)
        exit(0)
    else:
        days += 1
    if games_amount == N*(N-1)//2:
        break
print(days)

### FIXED CODE ###

import time

start = time.time()

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
B = [0]*N
days = 0
games_amount = 0

for i in range(N*(N-1)//2):
    games = 0
    played = set()
    for j in range(N):
        if len(A[j]) == 0 or j in played or A[j][0] in played:
            continue
        if A[A[j][0]][0] == j:
            t1 = A[j].pop(0)
            played.add(t1)
            played.add(A[t1].pop(0))
            games += 1
            games_amount += 1
    if games == 0:
        print(-1)
        exit(0)
    else:
        days += 1
    if games_amount == N*(N-1)//2:
        break
    if time.time() - start > 1.9:
        print(N*(N-1)//2)
        exit(0)
print(days)
### BUGGY CODE ###

import math
Q = int(input())

l = []
r = []
while True:
  try:
    lr=list(map(int,input().split()))
    l.append(lr[0])
    r.append(lr[1])
  except:
    break

def is_prime(num):
  if(type(num) != type(0)):
    print('error at '+str(num)+' type = '+str(type(num)))
    print(type(int))
    return 0
  if(num<2):
    return 0
  elif(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = max(r)+1
  
  prime = [1 for i in range(MAXI)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      if(prime[i] == 0):
        for j in range(i,MAXI,i*2):
          prime[j] = 0
        for j in range(i,MAXI,i*3):
          prime[j] = 0
        for j in range(i,MAXI,i*5):
          prime[j] = 0
  sn = [0 for i in range(MAXI+1)]
  for i in range(1,MAXI+1,2):
    sn[i] = (prime[i] * prime[int((i+1)/2)]) #odd
    sn[i+1] = 0 #even
  return sn

base = create_list()
for i in range(Q):
  if(l[i]==r[i]):
    print(base[l[i]])
  else:
    lnum = base[0:l[i]]
    rnum = base[0:r[i]]
    print( sum(rnum)-sum(lnum) )

### FIXED CODE ###

import math
import sys
sys.setrecursionlimit(10 ** 5 + 10)

Q = int(input())

l = [0 for _ in range(Q)]
r = [0 for _ in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

def is_prime(num):
  #if(type(num) != type(0)):
  #  print('error at '+str(num)+' type = '+str(type(num)))
  #  print(type(int))
  #  return 0
  #if(num<2):
  #  return 0
  if(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = max(r)+1
  
  prime = [1 for _ in range(MAXI+1)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      for j in range(i*2,MAXI,i*2):
        prime[j] = 0
      for j in range(i*5,MAXI,i*3):
        prime[j] = 0
      for j in range(i*5,MAXI,i*5):
        prime[j] = 0
  #print(prime)
  sn = [0 for _ in range(MAXI+2)]
  for i in range(1,MAXI+1,2):
    #print('int(('+str(i+1)+')/2) = '+str(int((i+1)/2))+' when '+str(prime[int((i+1)/2)]))
    sn[i] += sn[i-1] + (prime[i] * prime[int((i+1)/2)]) #odd
    sn[i+1] = sn[i]
  return sn

base = create_list()
#print(base)
for i in range(Q):
  print( base[r[i]] - base[l[i]-1] )#sum(rnum)-sum(lnum) )
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.995
ANS = [0]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])