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

# エラトステネスの篩
N = int(input())


def make_prime_table(N):
    sieve = [0] * (N + 1)
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, N + 1):
        if sieve[i] != 0:
            continue
        sieve[i] = i
        for j in range(i * i, N + 1, i):
            if sieve[j] == 0:
                sieve[j] = i
    return sieve


def f(X):
    t = []
    a = X
    while a != 1:
        if len(t) != 0 and t[-1][0] == prime_table[a]:
            t[-1][1] += 1
        else:
            t.append([prime_table[a], 1])
        a //= prime_table[a]
    result = 1
    for _, n in t:
        result *= n + 1
    return result


prime_table = make_prime_table(N)
result = 0
for K in range(1, N + 1):
    result += K * f(K)
print(result)


### FIXED CODE ###

# エラトステネスの篩
N = int(input())

sieve = [0] * (N + 1)
sieve[0] = -1
sieve[1] = -1
for i in range(2, N + 1):
    if sieve[i] != 0:
        continue
    sieve[i] = i
    for j in range(i * i, N + 1, i):
        if sieve[j] == 0:
            sieve[j] = i


def f(K):
    t = []
    a = K
    while a != 1:
        if len(t) != 0 and t[-1][0] == sieve[a]:
            t[-1][1] += 1
        else:
            t.append([sieve[a], 1])
        a //= sieve[a]
    result = 1
    for _, n in t:
        result *= (n + 1)
    return result


result = 0
for K in range(1, N + 1):
    result += K * f(K)
print(result)
### BUGGY CODE ###

S = list(input())
T = list(input())
slen = []
tlen = []
ans = "Yes"

while len(S) > 0:
    tempS = S[0]
    slen.append(S.count(tempS))
    while tempS in S:
        S.remove(tempS)
    
    
while len(T) > 0:
    tempT = T[0]
    tlen.append(T.count(tempT))
    while tempT in T:
        T.remove(tempT)
    
slen.sort()
tlen.sort()

print(["No", "Yes"][slen == tlen])

### FIXED CODE ###

from collections import Counter

S = Counter(list(input()))
T = Counter(list(input()))
s,t = list(S.values()),list(T.values())
print(["No", "Yes"][Counter(s) == Counter(t)])
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
for i in A:
    i = int(i)

def h(n,A):
    res = float('inf')
    for i in range(len(A)):
        temp1 = sum(A[:i])
        temp2 = sum(A[i:])
        res = min(res,abs(temp1-temp2))
    print(res)
h(n,A)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
for i in A:
    i = int(i)

def h(n,A):
    res = float('inf')
    f = []
    b = []
    t = 0
    for i in range(len(A)):
        t+=A[i]
        f.append(t)
    t = 0
    for i in range(len(A)-1,-1,-1):
        t += A[i]
        b.append(t)
    b.reverse()
    for i in range(len(A)-1):
        temp1 = f[i]
        temp2 = b[i+1]
        res = min(res,abs(temp1-temp2))
        
    #print(f)
    #print(b)
    print(res)
    
    
    
h(n,A)
### BUGGY CODE ###

S = input()
n = len(S)

A=[]
for i in range(len(S)):
  A.append(int(S[i:])%2019)

B=set(A)
b=0
for i in B:
  if i!=0:
    a = A.count(i)
    b += a*(a-1)/2
  else:
    b += 1

print(int(b))

### FIXED CODE ###

S = input()[::-1]
n = len(S)

cnt = [0] * 2019
cnt[0] = 1
m = 0
d = 1
for i in S:
  m += int(i) * d
  m %= 2019
  cnt[m] += 1
  d *= 10
  d %= 2019

ans=0
for i in cnt:
  ans += int(i*(i-1)/2)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
dic = [None]*(301**3)
dic[0] = 0
def dfs(uno,dos,tres):
  if uno < 0 or dos < 0 or tres < 0:
    return 0
  v = uno + dos*301 + tres*90601
  if dic[v] is not None:
    return dic[v]
  t = uno + dos + tres
  res = n
  res += uno*dfs(uno-1,dos,tres)
  res += dos*dfs(uno+1,dos-1,tres)
  res += tres*dfs(uno,dos+1,tres-1)
  res /= t
  dic[v] = res
  return res
print(dfs(a.count(1),a.count(2),a.count(3)))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
uno = a.count(1)
dos = a.count(2)
tres = n - uno - dos
dp = [[[0]*(n+1) for _ in range(dos+tres+1)] for j in range(tres+1)]
for k in range(tres+1):
  for j in range(dos+tres-k+1):
    for i in range(n+1-j-k):
      if i+j+k == 0: continue
      v = i+j+k
      res = n
      if i: res += i * dp[k][j][i-1]
      if j: res += j * dp[k][j-1][i+1]
      if k: res += k * dp[k-1][j+1][i]
      dp[k][j][i] = res / v
print(dp[tres][dos][uno])
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
ans = [K]*N
for i in range(1, Q+1):
    ans = list(map(lambda x: x-1, ans))
    ans[A[i-1]-1] += 1    
for k in ans:
    if k <= 0:
        print('No')
    else:
         print('Yes')

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
ans = [K-Q]*N
for i in range(1,Q+1):
    ans[A[i-1]-1] += 1    
for k in ans:
    if k <= 0:
        print('No')
    else:
         print('Yes')
### BUGGY CODE ###

A, B, Q = map(int, input().split())
s = [-10**11] + [int(input()) for i in range(A)] + [10**11]
t = [-10**11] + [int(input()) for i in range(B)] + [10**11]

def nibutans(x, l, r):
	if r - l <= 1:
		return max(r, l)
	nibu = (r + l) // 2
	return nibutans(x, nibu, r) if x > s[nibu] else nibutans(x, l, nibu)

def nibutant(x, l, r):
	if r - l <= 1:
		return max(r, l)
	nibu = (r + l) // 2
	return nibutant(x, nibu, r) if x > t[nibu] else nibutant(x, l, nibu)

for i in range(Q):
	x = int(input())
	sr, tr = nibutans(x, 0, A + 1), nibutant(x, 0, B + 1)
	ans = 10**17
	for S in [s[sr - 1], s[sr]]:
		for T in [t[tr - 1], t[tr]]:
			d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
#			print(str(ans) + ' ' + str(d1) + ' ' + str(d2))
			ans = min(ans, d1, d2)
	print(ans)


### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
s = [-10**11] + [int(input()) for i in range(A)] + [10**11]
t = [-10**11] + [int(input()) for i in range(B)] + [10**11]

'''
def nibutans(x, l, r):
	if r - l <= 1:
		return max(r, l)
	nibu = (r + l) // 2
	return nibutans(x, nibu, r) if x > s[nibu] else nibutans(x, l, nibu)

def nibutant(x, l, r):
	if r - l <= 1:
		return max(r, l)
	nibu = (r + l) // 2
	return nibutant(x, nibu, r) if x > t[nibu] else nibutant(x, l, nibu)

for i in range(Q):
	x = int(input())
	sr, tr = nibutans(x, 0, A + 1), nibutant(x, 0, B + 1)
	ans = 10**17
	for S in [s[sr - 1], s[sr]]:
		for T in [t[tr - 1], t[tr]]:
			d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
#			print(str(ans) + ' ' + str(d1) + ' ' + str(d2))
			ans = min(ans, d1, d2)
	print(ans)
'''
for q in range(Q):
	x = int(input())
	b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
	res = 10**13
	for S in [s[b - 1], s[b]]:
		for T in [t[d - 1], t[d]]:
			d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
			res = min(res, d1, d2)
	print(res)
### BUGGY CODE ###


def resolve():
    MOD = 998244353
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    dp = [[0] * (S + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(S + 1):
            dp[i + 1][j] += 2 * dp[i][j]
            dp[i + 1][j] %= MOD
            if j + A[i] <= S:
                dp[i + 1][j + A[i]] += dp[i][j]
                dp[i + 1][j + A[i]] %= MOD
    print(dp[N][S])


if __name__ == "__main__":
    resolve()

### FIXED CODE ###


def resolve():
    MOD = 998244353
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    dp = [[0] * (S + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(S + 1):
            dp[i + 1][j] += 2 * dp[i][j]
            dp[i + 1][j] %= MOD
            if j + A[i] <= S:
                dp[i + 1][j + A[i]] += dp[i][j]
                dp[i + 1][j + A[i]] %= MOD
    print(dp[N][S])


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

s = input()
cnt = 0
while '10' in s:
    ind = s.find('10')
    s = str(s[0:ind]) + str(s[ind + 2:len(s)])
    #print(s)
    cnt = cnt + 2

while '01' in s:
    ind = s.find('01')
    # print(ind)
    s = str(s[0:ind]) + str(s[ind + 2:len(s)])
    #print(s)
    cnt = cnt + 2

print(cnt)

### FIXED CODE ###

s = input()
cnt = 0

l = list(s)
a = l.count('0')
b = l.count('1')

# print(a)
# print(b)

print(min(a,b) * 2)
exit()
while '10' in s:
    ind = s.find('10')
    temp = []
    temp.append(str(s[0:ind]))
    temp.append(str(s[ind + 2:len(s)]))
    #print(s)
    s = "".join(temp)
    cnt = cnt + 2

while '01' in s:
    ind = s.find('01')
    # print(ind)
    temp = []
    temp.append(str(s[0:ind]))
    temp.append(str(s[ind + 2:len(s)]))
    s = "".join(temp)
    #print(s)
    cnt = cnt + 2

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

n = int(input())
A = list(map(int, input().split()))
M = 10 ** 9 + 7
ans = 0
for i in range(n-1):
    ans += A[i] * (sum(A[i+1:]))
    ans %= M
ans %= M
print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
M = 10 ** 9 + 7
ans = 0
B = [A[0]]
for j in range(1,n):
    B.append(A[j]+B[j-1])
for i in range(n-1):
    ans += A[i] * (B[-1]-B[i])
    ans %= M
ans %= M
print(ans)
### BUGGY CODE ###

import numpy as np

N, M = map(int, input().split(' '))

data = []
for m in range(M):
    data.append(list(map(int, input().split(' '))))

npdata = np.array(data)

cnt = 0
for n in range(1, N+1):
  if M == len(npdata[(npdata[:,0]<=n)&(n<=npdata[:,1])]):
  	cnt += 1
print(cnt)

### FIXED CODE ###

N, M = map(int, input().split(' '))
 
data = []
l = 1
r = 10**5
for m in range(M):
    li, ri = map(int, input().split(' '))
    if li > l:
      l = li
    if ri < r:
      r = ri
 
if l<= N <= r:
  cnt = (N - l) + 1
elif l > r:
  cnt = 0
elif r < N:
  cnt = (r - l) + 1
else:
  cnt = 0
 
print(cnt)
### BUGGY CODE ###

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

for i in range(len(X)):
    Y = X[:i] + X[i+1:]
    Y.sort()
    print(Y[int(N/2)-1])

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = sorted(X)

for i in range(len(X)):
    candi = Y[int(N/2)-1]
    if X[i] <= candi:
        print(Y[int(N/2)])
    else:
        print(candi)
### BUGGY CODE ###

def solve():
    MOD = 10**9+7
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N+1)]
    dp[0][0] = 1

    for i in range(N):
        if S[i] == '?':
            for j in range(10):
                for k in range(13):
                    dp[i+1][(k*10+j)%13] += dp[i][k]
        else:
            num = int(S[i])
            for j in range(13):
                dp[i+1][(j*10+num)%13] += dp[i][j]
    print(dp[N][5]%MOD)


if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys

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


def solve():
    MOD = 10 ** 9 + 7
    S = rl().rstrip()
    
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N + 1)]
    dp[0][0] = 1
    
    for i in range(N):
        if S[i] == '?':
            for j in range(10):
                for k in range(13):
                    dp[i + 1][(k * 10 + j) % 13] += dp[i][k] % MOD
        else:
            num = int(S[i])
            for j in range(13):
                dp[i + 1][(j * 10 + num) % 13] += dp[i][j] % MOD
    print(dp[N][5] % MOD)


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

from math import log
X=int(input())

def ok(B):
    i=1
    B=abs(B)
    while i**5<B:
        i+=1
    return i



A=0
while True:
    B_5=A**5-X
    r = ok(B_5)
    if r==abs(B_5):
        print(A,r*(-1 if B_5<0 else 1))
        break
    A+=1


### FIXED CODE ###

X=int(input())

def ok(B):
    i=1
    B=abs(B)
    while i**5<B:
        i+=1
    return i**5==B

def get(B):
    f = B/abs(B)
    i=1
    B=abs(B)
    while i**5<B:
        i+=1
    return int(i*f)



A_cand=[]
i=0
while i**5<=10**10:
    A_cand.append(i)
    i+=1

#print(A_cand)
for a in range(300):
    B_5=a**5-X
    if ok(B_5):
        r=get(B_5)
        print(a,r)
        exit()
        break
for a in A_cand:
    a*=-1
    B_5=a**5-X
    if ok(B_5):
        r=get(B_5)
        print(a,r)
        exit()
print(0/0)
### BUGGY CODE ###

from collections import deque
import math
import sys

input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

field = []
for _ in range(h):
    field.append(list(input()))
visited = [[False for _ in range(w)] for _ in range(h)]
costs = [[99999999 for _ in range(w)] for _ in range(h)]


q = deque([(x1, y1)])
costs[x1][y1] = 0

while q:
    x, y = q.popleft()
    if visited[x][y]:
        continue
    visited[x][y] = True
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for i in range(1, k + 1):
            px, py = x + dx * i, y + dy * i
            if not(0 <= px < h and 0 <= py < w) or field[px][py] == '@' or visited[px][py]:
                break
            if costs[px][py] > costs[x][y] + 1:
                costs[px][py] = costs[x][y] + 1
                q.append((px, py))

print(-1 if costs[x2][y2] == 99999999 else costs[x2][y2])


### FIXED CODE ###

from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

h, w, k = map(int, readline().split())
x1, y1, x2, y2 = map(int, readline().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

field = [readline() for _ in range(h)]
costs = [[-1] * w for _ in range(h)]

q = deque([(x1, y1)])
costs[x1][y1] = 0

while q:
    x, y = q.popleft()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for i in range(1, k + 1):
            px, py = x + dx * i, y + dy * i
            if not(0 <= px < h and 0 <= py < w) or field[px][py] == '@':
                break
            if 0 <= costs[px][py] < costs[x][y] + 1:
                break
            if costs[px][py] == -1:
                q.append((px, py))
            costs[px][py] = costs[x][y] + 1

print(costs[x2][y2])
### BUGGY CODE ###

# ａ⁵－ｂ⁵＝(ａ－ｂ)(ａ⁴＋ａ³ｂ＋ａ²ｂ²＋ａｂ³＋ｂ⁴)
import sys
# X = int(input())
# a = 1
# for i in range(1, 10**9):
#     a = i**5
#     if a-X > 0:
#         b = 1
#         while True:
#             if a-X == b**5:
#                 print(i, b)
#                 sys.exit()
#             elif a-X > b:
#                 b += 1
#             else:
#                 break
#     elif a-X < 0:
#         b = -1
#         while True:
#             if a-X == b**5:
#                 print(i, b)
#                 sys.exit()
#             elif a-X < b:
#                 b -= 1
#             else:
#                 break
#     else:
#         print(i, 0)
#         break

from itertools import combinations
X = int(input())
num = X
fact = []
i = 2
# 素因数分解
while num > 1:
    if num%i == 0:
        num //= i
        fact.append(i)
    else:
        i += 1

for i in range(len(fact)+1):
    for item in combinations(fact, i):
        a = 0
        b = -1
        for num in item:
            b *= num
        while a**5 - b**5 >= X:
            if a**5 - b**5 == X:
                print(a, b)
                sys.exit()
            else:
                a += 1
                b += 1



### FIXED CODE ###

from sys import exit
X = int(input())
p = [0]*122
for i in range(122):
    p[i] = pow(i , 5)
for i in range(122):
    a = p[i]
    for j in range(i):
        if a-p[j] == X:
            print(i, j)
            exit()
    for j in range(i, 122):
        if a+p[j] == X:
            print(i, -1*j)
            exit()
### BUGGY CODE ###

n=int(input())
paper=[]
for i in range(n):
	a=input()
	if a in paper:
		paper.remove(a)
	else :
		paper.append(a)
print(len(paper))

### FIXED CODE ###

import collections
n = int(input())
list = []
count = 0
for i in range(n):
    a = int(input())
    list.append(a)
ans = collections.Counter(list)
for j in ans.values():
    if j % 2 == 1:
        count += 1
print(count)
### BUGGY CODE ###

a, b, k = map(int, input().split())
x = [i for i in range(a, b+1)]
if len(x) <= 2 * k:
  print(*[str(i) + '\n' for i in x])
else:
  ans = x[:k] + x[-k:]

  print(*[str(i)+'\n' for i in ans] )

### FIXED CODE ###

a, b, k = map(int, input().split())

if (b-a +1) <= 2 * k:
  for i in range(a,b+1):
    print(i)
else:
  for i in range(a, a+k):
    print(i)
  for i in range(b-k+1, b+1):
    print(i)
### BUGGY CODE ###

import itertools
N = int(input())
A = list(map(int,input().split()))
Acc = list(itertools.accumulate(A))
ans = 0
for i, j in itertools.combinations(Acc, 2):
    if i == j:
        ans += 1
for i in Acc:
    if i == 0:
        ans += 1
print(ans)

### FIXED CODE ###

import itertools
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
Acc = list(itertools.accumulate(A))
ans = 0
for i in Counter([0]+Acc).values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

cnt = 0

k = int(input())
"""
def bt(l):
    if cnt == k:
        print("".join(map(str,l)))
    else:
        if len(l) == 1:
            if l[0] == 9:
                bt([1,0])
"""
def islunlun(l):
    for x in range(1,len(l)):
        if abs(ord(l[x])-ord(l[x-1])) > 1:
            return False
    return True

cnt = 0
x = 1
while True:
    if islunlun(str(x)):
        cnt += 1
    if cnt == k:
        print(x)
        exit(0)
    x += 1

### FIXED CODE ###

import sys

sys.setrecursionlimit(100010)
k = int(input())


def islunlun(l):
    for x in range(1,len(l)):
        if abs(ord(l[x])-ord(l[x-1])) > 1:
            return False
    return True

s = set()
mx = 3234566667
def generate(l):
    val = None
    if l == []:
        val = 0
    else:
        val = int("".join(list(map(str,l))))
    #print(l, val)
    if mx < val:
        return
    else:
        if l != []:
            s.add(val)
    if len(l) == 0:
        for x in range(1,10):
            l.append(x)
            generate(l.copy())
            l.pop(len(l)-1)
    else:
        #print(max(0, l[len(l) - 1] - 1), min(9,l[len(l)-1]+1)+1)
        for x in range(max(0,l[len(l)-1]-1), min(9,l[len(l)-1]+1)+1):
            l.append(x)
            generate(l)
            l.pop(len(l)-1)

"""def bt(l):
    for x in range(10):
        l.append()"""

generate([])
l = []
for x in s:
    l.append(x)
l.sort()
print(l[k-1])
### BUGGY CODE ###

mod = 10**9 + 7

s = input()[::-1]
n = len(s)
DP = [[0]*3 for i in range(n+1)]

htn_cnt = 0
for i, c in enumerate(list(s)):
    for j in range(3):
        if c == "?":
            DP[i+1][j] = 3*DP[i][j] % mod
        else:
            DP[i+1][j] = DP[i][j] % mod
    if c == "C" or c == "?":
        DP[i+1][0] = (DP[i+1][0] + 3**htn_cnt) % mod
    if c == "B" or c == "?":
        DP[i+1][1] = (DP[i+1][1] + DP[i][0]) % mod
    if c == "A" or c == "?":
        DP[i+1][2] = (DP[i+1][2] + DP[i][1]) % mod
    if c == "?":
        htn_cnt += 1
print(DP[n][2] % mod)

### FIXED CODE ###

import numpy as np
mod = 10**9 + 7

s = input()[::-1]
#s = "?"*(10**5)
n = len(s)
DP = [[0]*3 for i in range(n+1)]

power_three = 1

for i, c in enumerate(list(s)):
    for j in range(3):
        if c == "?":
            DP[i+1][j] = 3*DP[i][j] % mod
        else:
            DP[i+1][j] = DP[i][j] % mod
    if c == "C" or c == "?":
        DP[i+1][0] = (DP[i+1][0] + power_three) % mod
    if c == "B" or c == "?":
        DP[i+1][1] = (DP[i+1][1] + DP[i][0]) % mod
    if c == "A" or c == "?":
        DP[i+1][2] = (DP[i+1][2] + DP[i][1]) % mod
    if c == "?":
        power_three = 3*power_three % mod
print(DP[n][2] % mod)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
#####segfunc######                                                              
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
n,q=map(int,input().split())
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
c=list(map(int,input().split()))
lr=[]
for i in range(q):
    lr.append(list(map(int,input().split())) + [i])
lr.sort(key=lambda x: x[1])
ans=[0]*q
ll=0
lastc=[-1]*(n+1)
for l,r,ind in lr:
    l-=1
    r-=1
    while ll<=r:
        if lastc[c[ll]]==-1:
            lastc[c[ll]]=ll
            update(ll,1)
        else:
            update(lastc[c[ll]],0)
            lastc[c[ll]]=ll
            update(lastc[c[ll]],1)
        ll+=1
    ans[ind]=query(l,r+1)
for i in ans:
    print(i)

### FIXED CODE ###

import sys
input=sys.stdin.readline
#####segfunc######                                                              
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
n,q=map(int,input().split())
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
c=list(map(int,input().split()))
lr=[]
for i in range(q):
    lr.append(list(map(int,input().split())) + [i])
lr.sort(key=lambda x: x[1])
ans=[0]*q
ll=0
lastc=[-1]*(n+1)
for l,r,ind in lr:
    l-=1
    r-=1
    while ll<=r:
        if lastc[c[ll]]==-1:
            lastc[c[ll]]=ll
            update(ll,1)
        else:
            update(lastc[c[ll]],0)
            lastc[c[ll]]=ll
            update(lastc[c[ll]],1)
        ll+=1
    ans[ind]=query(l,r+1)
for i in ans:
    print(i)
### BUGGY CODE ###

N, K = map(int, input().split())
S = input()

l = []
for i in range(N):
  if i == 0 or S[i - 1] != S[i]:
    l.append(1)
  else:
    l[-1] += 1

if S.count("1") == N or S.count("0") == N:
  print(N)
else:
  ans = 0
  for i in range(len(l)):
    cnt = 0
    if S[0] == "0" and i == 0:
      for j in range(K * 2):
        cnt += l[j]
        if j == len(l) - 1:
          break
    elif S[0] == "0" and i % 2 == 1 or S[0] == "1" and i % 2 == 0:
      for j in range(i, i + K * 2 + 1):
        cnt += l[j]
        if j == len(l) - 1:
          break  
    ans = max(ans, cnt)
  print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
S = input()

nums = []
now = 1
cnt = 0
for i in range(N):
  if S[i] == str(now):
    cnt += 1
  else:
    nums.append(cnt)
    now = 1 - now
    cnt = 1
if cnt != 0:
  nums.append(cnt)

if len(nums) % 2 == 0:
  nums.append(0)

add = 2 * K + 1

sums = [0 for _ in range(len(nums) + 1)]
for i in range(len(nums)):
  sums[i + 1] = sums[i] + nums[i]

ans = 0
for i in range(len(nums)):
  if i % 2 == 1:
    continue
  
  left = i
  right = min(i + add, len(nums))
  tmp = sums[right] - sums[left]

  ans = max(tmp, ans)

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

N = int(input())
C=list(input())
L=0
R=0
X=0
for i in range(N):
  L=i
  if L==N-1-R:
    break
  if C[i]=='W':
    for ii in range(N-L-R):
      if C[N-1-R-ii]=='R':
        C[L]='R'
        C[N-1-R-ii]='W'
        X+=1
        R+=ii+1
        if L==N-1-R:
          break
        break
print(X)

### FIXED CODE ###

N = int(input())
C=list(input())
type=set(C)
L=0
R=0
RR=0
X=0
if 'R' in type and 'W' in type:
    for i in range(N):
      L=i
      R=RR
      if L>=N-1-R:
        break
      if C[i]=='W':
          for ii in range(N-L-R):
            if C[N-1-R-ii]=='R':
              C[L]='R'
              C[N-1-R-ii]='W'
              X+=1
              break
            RR+=1
            if L>=N-1-R:
              break
print(X)