Harryxun/stf_run huggingface dataset:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10000)

H, W = map(int, input().rstrip().split(' '))

field = []
for _ in range(H):
    temp_field = []
    for s in input():
        if s == '.':
            temp_field.append(0)
        else:
            temp_field.append(1)
    field.append(temp_field)
    
dp = [[-1] * W for _ in range(H)]

def rec(i, j):
    if field[i][j] == 1:
        return 0
    
    if dp[i][j] != -1:
        return dp[i][j]
        
    dp[i][j] = H + W
        
    min_dist = H + W
    if i > 0:
        min_dist = min(min_dist, rec(i-1, j) + 1)
    if i < H - 1:
        min_dist = min(min_dist, rec(i+1, j) + 1)
    if j > 0:
        min_dist = min(min_dist, rec(i, j-1) + 1)
    if j < W - 1:
        min_dist = min(min_dist, rec(i, j+1) + 1)
        
    dp[i][j] = min_dist
    
    return min_dist
    
    
for i in range(H):
    for j in range(W):
        rec(i, j)
     
print(max([max(temp_dp) for temp_dp in dp]))

### FIXED CODE ###

# coding: utf-8
# Your code here!

from collections import deque

H, W = map(int, input().rstrip().split(' '))

field = [[0] * W for _ in range(H)]
d = deque()
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            field[i][j] = 1
            d.append([i, j, 0])

max_dist = 0
while len(d) > 0:
    cur_h, cur_w, dist = d.popleft()
    for i, (dh, dw) in enumerate([[0, 1], [0, -1], [1, 0], [-1, 0]]):
        if (cur_h + dh) >= 0 and (cur_h + dh) < H and (cur_w + dw) >= 0 and (cur_w + dw) < W:
            if field[cur_h+dh][cur_w+dw] == 0:
                field[cur_h+dh][cur_w+dw] = 1
                d.append([cur_h+dh, cur_w+dw, dist+1])
                max_dist = max(max_dist, dist+1)

print(max_dist)
n, k = map(int, input().split())

num = list(map(int, input().split()))
t = [-1] * n
count = 0
s = 1

while t[s - 1] == -1:
  if count == k:
    break

  t[s - 1] = count
  count += 1
  s = num[s - 1]
else:
  z = (k - t[s - 1]) % (count - t[s - 1])
  print(t.index(t[s - 1] + z + 1)


### FIXED CODE ###

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

t_zero = [-1] * N

t = 0
a = 1

while t_zero[a-1] == -1:
  if t == K:
    break
  t_zero[a-1] = t
  t += 1
  a = A[a-1]
else:
  k = (K - t_zero[a-1]) % (t - t_zero[a-1])
  a = t_zero.index(t_zero[a-1] + k) + 1
print(a)
x = raw_input()
print(x ** 3)

### FIXED CODE ###

x = int(input())
print(x ** 3)
# -*- coding: utf-8 -*-
N, L = map(int,input().split())

taste = []
for i in range(1,N + 1):
    taste.append(L + i - 1)

SUM = sum(taste)

DIF = abs(SUM - (SUM - taste[0]))
ans = SUM - taste[0]
for i in range(1,N + 1):
    x = SUM - taste[i]
    if abs(SUM - x) < DIF:
        DIF = abs(SUM - x)
        ans = x
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
N, L = map(int,input().split())

taste = []
for i in range(1,N + 1):
    taste.append(L + i - 1)

SUM = sum(taste)

DIF = abs(SUM - (SUM - taste[0]))
ans = SUM - taste[0]
for i in range(1,N):
    x = SUM - taste[i]
    if abs(SUM - x) < DIF:
        DIF = abs(SUM - x)
        ans = x
print(ans)
import sys
from collections import deque
sys.setrecursionlimit(10000000)
readline = sys.stdin.buffer.readline
n = int(readline())

g = [[] for _ in range(n+1)] #隣接リスト
for i in range(n-1):
    a,b = map(int,readline().split())
    g[a].append(b)
    g[b].append(a)

color = [0] * (n+1) #color[i]:点iの色(1 or -1)。但し塗られていないときは0とする

def f(v,c):
    #頂点vに隣接する頂点全てを塗るあるいは判定する
    color[v] = c
    for i in range(len(g[v])):
        if color[ g[v][i] ] == 0:
            f(g[v][i],-c)
ans = [0]*(n+1)
t0 = deque([])
t1 = deque([])
t2 = deque([])
for i in range(1,n+1):
    if i%3==1:
        t1.append(i)
    elif i%3==2:
        t2.append(i)
    else:
        t0.append(i)
res = f(i,1)
black = 0
for i in color[1:]:
    if i == 1:
        black += 1

if black <= n//3:
    for i in range(1,n+1):
        if color[i] == 1:
            ans[i] = t0.pop()
        else:
            if t1:
                ans[i] = t1.pop()
            elif t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
else:
    for i in range(1,n+1):
        if color[i] == 1:
            if t1:
                ans[i] = t1.pop()
            else:
                ans[i] = t0.pop()
        else:
            if t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
print(*ans[1:])

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(1000000)
readline = sys.stdin.buffer.readline
n = int(readline())

g = [[] for _ in range(n+1)] #隣接リスト
for i in range(n-1):
    a,b = map(int,readline().split())
    g[a].append(b)
    g[b].append(a)

colors = [0] * (n+1)
 
colors[1] = 1
 
todo = []
for to in g[1]:
    todo.append([to, -1])
 
while todo:
    node, color = todo.pop()
 
    if colors[node] != 0:
        continue
 
    colors[node] = color
    new_color = -color
    for to in g[node]:
        if colors[to] != 0:
            continue
        todo.append([to, new_color])
ans = [0]*(n+1)
t0 = deque([])
t1 = deque([])
t2 = deque([])
for i in range(1,n+1):
    if i%3==1:
        t1.append(i)
    elif i%3==2:
        t2.append(i)
    else:
        t0.append(i)
black = 0
for i in colors[1:]:
    if i == 1:
        black += 1

if black <= n//3:
    for i in range(1,n+1):
        if colors[i] == 1:
            ans[i] = t0.pop()
        else:
            if t1:
                ans[i] = t1.pop()
            elif t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
elif black >= n-n//3:
    for i in range(1,n+1):
        if colors[i] == -1:
            ans[i] = t0.pop()
        else:
            if t1:
                ans[i] = t1.pop()
            elif t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
else:
    for i in range(1,n+1):
        if colors[i] == 1:
            if t1:
                ans[i] = t1.pop()
            else:
                ans[i] = t0.pop()
        else:
            if t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
print(*ans[1:])
import math
I = input().split()
A = int(I[0])
B = int(I[1])
N = int(I[2])
def fl(x):
    return math.floor((A*x)/B) - A*math.floor(x/B)

An = fl(N)

if  B == 1 :
    An = int(0)

if B < N :
    for i in range(B,N) :
        if i >= B+1 and fl(i) <= fl(i-1) :
            An = fl(i-1)
            break
elif B == N :
    An = fl(N-1)

print(str(An))

### FIXED CODE ###

I = [input() for i in range(2)]
K = int(I[0])
S = I[1].split()
A = int(S[0])
B = int(S[1])

na = A//K
nb = B//K

la = A%K
lb = B%K

#print(na)
#print(nb)

if na < nb or la == 0 or lb == 0 :
    ans = 'OK'
else:
    ans = 'NG'

print(ans)
import sys

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

    A.sort(reversed=True)

    res=0
    res+=A[0]
    res+=A[1]*(N-2)
    print(res)

if __name__=="__main__":
    main()

### FIXED CODE ###

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

    A.sort(reverse=True)

    res=A[0]

    counter=1

    while counter<=N-2:
        index = (counter + 1) // 2
        res+=A[index]
        counter+=1

    print(res)

if __name__=="__main__":
    main()
n, a = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(x)
dp = [[[0 for k in range(n * x_max + 1)] for j in range(n + 1)] for i in range(n + 1)]
dp[0][0][0] = 1
for i in range(1, n + 1):
    for j in range(n + 1):
        for k in range(x[i - 1]):
            dp[i][j][k] = dp[i - 1][j][k]
        if j > 0:
            for k in range(x[i - 1], n * x_max + 1):
                dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - x[i - 1]]
ans = 0
for j in range(1, n + 1):
    ans += dp[-1][j][j * a]
print(ans)


### FIXED CODE ###

n, a = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(x)
x_sum = sum(x)
ans = 0
if x_max >= a:
    dp = [[0 for j in range(2 * x_sum + 1)] for i in range(2)]
    dp[0][x_sum] = 1
    for i in range(1, n + 1):
        idx = i % 2
        y = x[i - 1] - a
        for j in range(2 * x_sum + 1):
            if 0 <= j - y <= 2 * x_sum:
                dp[idx][j] = dp[1 - idx][j] + dp[1 - idx][j - y]
            else:
                dp[idx][j] = dp[1 - idx][j]
    ans = dp[n % 2][x_sum] - 1
print(ans)
n, m = (int(x) for x in input().split())
x = [int(x) for x in input().split()]
if m == 1: print(0)
else:
    x.sort()
    dis = [abs(x[i+1] - x[i]) for i in range(m-1)]
    dis.sort()
    ans = dis[::-1]
    for _ in range(n-1): ans.pop(0)
    print(sum(ans))

### FIXED CODE ###

n, m = (int(x) for x in input().split())
x = [int(x) for x in input().split()]
if n >= m:
    print(0)
else:
    x.sort()
    dis = [abs(x[i+1] - x[i]) for i in range(m-1)]
    dis.sort()
    ans = dis[::-1]
    for _ in range(n-1): ans.pop(0)
    print(sum(ans))
n, k=map(int,input())
h=list(map(int,input()))
cnt=0
for i in h:
  if i>=k:
    cnt+=1
print(cnt)

### FIXED CODE ###

n, k=map(int,input().split())
h=list(map(int,input().split()))
cnt=0
for i in h:
  if i>=k:
    cnt+=1
print(cnt)
N, M = map(int, input().split())
H = list(map(int, input().split()))
a = []
[a.append(i) for i in range(1,N+1)]
for i in range(M):
  ai, bi = map(int, input().split())
  if H[ai+1] < H[bi+1] :
    a.remove(ai)
  else:
    a.remove(bi)
print(len(a))    
  

### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
a = [True] * N
for i in range(M):
  ai, bi = map(int, input().split())
  if H[ai-1] <= H[bi-1] :
    a[ai-1] = False
  if H[ai-1] >= H[bi-1]:
    a[bi-1] = False
print(sum(a))
n = int(input())
a = list(map(int, input().split(' ')))
q = int(input())
M = list(map(int, input().split(' ')))
minA = min(a)
sumA = sum(a)

def solve(i, m):
    if m==0 :
        return True
    if i>=n:
        return False
    res = solve(i+1, m) or solve(i+1, m-a[i])
    return res

for j in M:
    if j < minA or m>sumA:
        print('no')
    if solve(0, j):
        print('yes')
    else:
        print('no')



### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(' ')))
q = int(input())
M = list(map(int, input().split(' ')))
minA = min(a)
sumA = 0
for i in a:
    sumA += i


def solve(i, m):
    if m==0 :
        return True
    if i>=n:
        return False
    res = solve(i+1, m) or solve(i+1, m-a[i])
    return res

for j in M:
    if j < minA or j > sumA:
        print('no')
    else:
        if solve(0, j):
            print('yes')
        else:
            print('no')
a, b, k = [ int(v) for v in input().split() ]

for i in range(k):
  if i % 2 == 0:
  	a = a // 2
    b += a // 2
  else:
    a += b // 2
    b = b // 2
print(a,b)

### FIXED CODE ###


a, b, k = [ int(v) for v in input().split() ]
	
for i in range(k):
	if i % 2 == 0:
		b += a // 2
		a = a // 2
		
	else:
		a += b // 2
		b = b // 2
print(a,b)
N, K = map(int, input().split())
a = abs(N%K)
print(min(a, abs(a-K))

### FIXED CODE ###

N, K = map(int, input().split())
a = abs(N%K)
print(min(a, abs(a-K)))
a, b = list(map(int, input().split))
ans = 0;
sum = a;
while sum < b:
  sum += (a-1)
  ans++
print(ans)

### FIXED CODE ###

a, b = list(map(int, input().split()))
ans = 0;
sum = 1;
while sum < b:
  sum += (a-1)
  ans = ans + 1
print(ans)
n=int(input())
s=input()
k=int(input())
num = 0
for i in s:
  print(i)
  if i == s[k]:
    num +=1
  else:
    s = s.replace(s[num],'*')
    num +=1

### FIXED CODE ###

n=int(input())
s=input()
k=int(input())
num = 0
for i in s:
  if i == s[k-1]:
    num +=1
  else:
    s = s.replace(s[num],'*')
    num +=1
print(s)
import functools
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)

def gcd(nums):
    return functools.reduce(euclid, nums)



n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]

a.sort()

sa=[]

for i in range(1,n):
    sa.append(a[i]-a[i-1])



print(gcd(sa))



### FIXED CODE ###

import functools
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)

def gcd(nums):
    if len(nums)==1:
        return nums[0]
    return functools.reduce(euclid, nums)



n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
a.append(k)
a.sort()

sa=[]

for i in range(1,n+1):
    sa.append(a[i]-a[i-1])



print(gcd(sa))
S = input()
kei = 0
k = []
l = []
if S[0] == '<':
  k.append(0)
for i in range(len(S)-1):
  if S[i] == '>' and S[i+1] == '<':
    k.append(i+1)
  elif S[i] == '<' and S[i+1] == '>':
    l.append(i+1)
if S[len(S)] == '>':
  k.append(len(S)+1)
def summ(m):
  s = 0
  if m != 0:
    for j in range(1,m+1):
      s += j
  return s
for p in range(len(k)-1):
  if k[p+1] - l[p] > l[p] - k[p]:
    kei += summ(k[p+1] - l[p]) + summ(l[p]-k[p] - 1)
  else:
    kei += summ(k[p+1] - l[p] - 1) + summ(l[p]-k[p])
print(kei)   
  
  
  
  
  
  
  
  

### FIXED CODE ###

s = input()
N = len(s) + 1
l = [0]*N #からのリストN個
for i in range(N-1):
  if s[i] == '<':
    l[i+1] = l[i] + 1
for k in range(N-2,-1,-1):#後ろから逆順で一ずつ降る
  if s[k] == '>':
    l[k] = max(l[k], l[k+1] + 1)
print(sum(l))
a,b,c=map(int,input().split())

if a==b:
  if b==c:
    print("No")
  if b!=c:
    printf("Yes")
    
if a!=b:
  if a==c or b==c:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

a,b,c = input().strip().split()

if a==b:
  if b==c:
    print("No")
  else:
    print("Yes")
    
else:
  if a==c or b==c:
    print("Yes")
  else:
    print("No")
n = int(input())
a = list(map(int,input().split()))
s = sum(a)
a.sort()
b = 0
for i in a:
  b |= b<<i
  b |= 1<<i
  
def all_bit_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f
  

l = all_bit_count(b)
for i in range((l+1)//2):
  t = b&(-b)
  b ^= t
  
print(t.bit_length()-1)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
s = sum(a)
a.sort()
b = 1
for i in a:
  b |= b<<i
  
b &= 2**(s+1)-2**((s-1)//2)
while True:
  t = b&(-b)
  #print(i,t,b)
  if (s+1)//2 <= t.bit_length()-1 <= s:
    print(t.bit_length()-1)
    break
  b ^= t
n, m, x = map(int, input().split())
a = list(map(int, input().split()))
print(min(sum(a[:a.index(x)+1]), sum(a[a.index(x)+1:])))


### FIXED CODE ###

n, m, x = map(int, input().split())
a = list(map(int, input().split()))
for i,j in enumerate(a):
  if j > x:
    cnt = i
    break
print(min(cnt, m-cnt))
N = int(input())

s = 0
sN = str(N)
for i in range(len(sN)):
  s += sN[i]

if N % s == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = int(input())

s = 0
sN = str(N)
for i in range(len(sN)):
  s += int(sN[i])

if N % s == 0:
  print("Yes")
else:
  print("No")
from scipy.misc import comb

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

res = pow(2,n,10**9+7)
res -= 1


res -= comb(n, a, exact=True)
res %= 10**9+7

res -= comb(n, b, exact=True)
res %= 10**9+7

print(res)

### FIXED CODE ###

n,a,b = map(int,input().split())
mod = 10**9+7

def C(n, r, mod):
    x=y=1
    for i in range(r):
        x *= n; y *= r
        x %= mod; y %= mod
        n -= 1; r -= 1
    return x * pow(y, mod - 2, mod) % mod


res = pow(2,n,mod) - 1


comb_a = C(n,a,mod)
comb_b = C(n,b,mod)

print((res-(comb_a+comb_b))%mod)
count = 0
  n = input()

  for i in range(n-1):
    com, str = map(str, raw_input().split())
    if com == 'insert':
      dic[count] = str
      count += 1
    elif com == 'find':
      for j in range(count-1):
        if dic[j] == str:
          print 'yes'
          break
        elif j == count-1:
          print 'no'
          break

### FIXED CODE ###

n = input()
dic = set()
 
for i in range(n):
  com, st = map(str, raw_input().split())
  if com == 'insert':
    dic.add(st)
  elif com == 'find':
    if st in dic:
      print 'yes'
    else:
      print 'no'
import sys
import numpy as np

N, M = list(map(int, sys.stdin.readline().strip().split(" ")))
A = list(map(int, sys.stdin.readline().strip().split(" ")))
B = []
C = []

for _ in range(M):
    b, c = list(map(int, sys.stdin.readline().strip().split(" ")))
    B.append(b)
    C.append(c)

A = sorted(A)
arg_list = list(reversed(np.argsort(C)))
B = np.array(B)[arg_list]
C = np.array(C)[arg_list]

index = 0
count = 0
flag = False
for b, c in zip(B, C):
    for _ in range(b):
        if A[index] >= c:
            flag = True
            break
        A[index] = c
        index += 1
    if flag:
        break

print(sum(A))


### FIXED CODE ###

import sys
import numpy as np

N, M = list(map(int, sys.stdin.readline().strip().split(" ")))
A = list(map(int, sys.stdin.readline().strip().split(" ")))
B = []
C = []

for _ in range(M):
    b, c = list(map(int, sys.stdin.readline().strip().split(" ")))
    B.append(b)
    C.append(c)

A = sorted(A)
arg_list = list(reversed(np.argsort(C)))
B = np.array(B)[arg_list]
C = np.array(C)[arg_list]

index = 0
count = 0
flag = False
for b, c in zip(B, C):
    for _ in range(b):
        if index == N:
            flag = True
            break
        if A[index] >= c:
            flag = True
            break
        A[index] = c
        index += 1
    if flag:
        break

print(sum(A))
n,w = map(int,input().split())
info = [[0,0]]+[list(map(int,input().split())) for i in range(n)]
v = 0
for i in range(n+1):
  v += info[i][1]
n = n+1
## dp[i][j]:i番目までのアイテムを詰めたときに総価値jになるときの最小重さ
dp = [[float("inf")]*(v) for i in range(n)]

for i in range(n):
  dp[i][0] = 0

for i in range(1,n):
  for j in range(1,v):
    if j-info[i][1]>=0:
      dp[i][j] = min(dp[i-1][j],dp[i-1][j-info[i][1]]+info[i][0])
    else:
      dp[i][j] = dp[i-1][j]

for j in range(v):
  if dp[n-1][j] <= w:
    ans = j
print(ans)

### FIXED CODE ###

n,w = map(int,input().split())
info = [[0,0]]+[list(map(int,input().split())) for i in range(n)]

## dp[i][j]:i番目までのアイテムを重さjのナップサックに詰めるときの最大価値
dp = [[0]*(w+1) for i in range(n+1)]
for i in range(n+1):
  for j in range(w+1):
    if j-info[i][0]>=0:
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-info[i][0]]+info[i][1])
    else:
      dp[i][j] = dp[i-1][j]

print(dp[n][w])
N,K=map(int,input().split())

import math
sums = 0
for i in range(1,N+1):
    num=int(math.log(K//i,2)+1)
#     if num>int(num):
#         num=int(num)+1
    if i>K-1:
        sums +=(1/N)
    else:
        sums += 1/(N * math.pow(2,num))

print(sums)

### FIXED CODE ###

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

import math
sums = 0
for i in range(1,N+1):
    num=int(math.log(K/i,2)+1)
    
    if i>K-1:
        sums +=(1/N)
    else:
        if i*2**(num)>=K>i*2**(num-1):
            sums += 1/(N * math.pow(2,num))
        else:
            sums += 1/(N * math.pow(2,num-1))

print(sums)
n = input()

if n == 1:
  print ("Hello World")
else:
  a = input()
  b = input()
  a = int(a)
  b = int(b)
  c = a + b
  print (c)

### FIXED CODE ###

n = input()
n = int(n)

if n == 1:
  print ("Hello World")
else:
  a = input()
  b = input()
  a = int(a)
  b = int(b)
  c = a + b
  print (c)
X, Y, Z, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A = sorted([int(x) for x in A], reverse=True)
B = sorted([int(x) for x in B], reverse=True)
C = sorted([int(x) for x in C], reverse=True)

res = []
memo = []
i, j, k = 0, 0, 0
while len(res) < K:
  if (i, j, k) not in memo:
  	res.append(A[i]+B[j]+C[k])
    memo.append((i,j,k))
  if i+1 < X and (i+1, j, k) not in memo:
  	res.append(A[i+1]+B[j]+C[k])
    memo.append((i+1, j, k))
  if j+1 < Y and (i, j+1, k) not in memo:
  	res.append(A[i]+B[j+1]+C[k])
    memo.append((i, j+1, k))
  if k+1 < Z and (i, j, k+1) not in memo:
  	res.append(A[i]+B[j]+C[k+1])
    memo.append((i, j, k+1))
  if i < X:
    i += 1
  if j < Y:
    j += 1
  if k < Z:
    k += 1
res = sorted(res, reverse=True)[:K]
for i in res:
  print(i)

### FIXED CODE ###

from heapq import *

X, Y, Z, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A = sorted([int(x) for x in A], reverse=True)
B = sorted([int(x) for x in B], reverse=True)
C = sorted([int(x) for x in C], reverse=True)

res = []
memo = []
ans = []
heappush(res, (-A[0]-B[0]-C[0], 0, 0, 0))
while len(ans) < K:
  e, i, j, k = heappop(res)
  ans.append(-e)
  if i+1 < X and [i+1, j, k] not in memo:
    heappush(res, (-A[i+1]-B[j]-C[k], i+1, j, k))
    memo.append([i+1, j, k])
  if j+1 < Y and [i, j+1, k] not in memo:
    heappush(res, (-A[i]-B[j+1]-C[k], i, j+1, k))
    memo.append([i, j+1, k])
  if k+1 < Z and [i, j, k+1] not in memo:
    heappush(res, (-A[i]-B[j]-C[k+1], i, j, k+1))
    memo.append([i, j, k+1])

for i in ans:
  print(i)
r, c = map(int, input().split())
mat = []
for i in range(r):
 mat.append(list(map(int, input().split())))

for x in range(r):
 rsum = 0
 for y in range(c):
  rsum += mat[x][y]
 mat[x].append(rsum)

for x in range(c):
 csum = 0
 for y in range(r):
  csum = mat[y][x]
 mat[r].append(csum)

for x in range(r+1):
 for y in range(c):
  print("{0} ".format(mat[x][y]), end = '')
 print(mat[x][y+1])
  

### FIXED CODE ###

r, c = map(int, input().split())
mat =[]

for x in range(r):
 mat.append(list(map(int, input().split())))

tsum = 0

for x in range(r):
 rsum = 0
 for y in range(c):
  rsum += mat[x][y]
  tsum == mat[x][y]
 mat[x].append(rsum)

mat.append([])

for x in range(c):
 csum = 0
 for y in range(r):
  csum += mat[y][x]
  tsum += mat[y][x]
 mat[r].append(csum)



for x in range(r):
 for y in range(c):
  print("{0} ".format(mat[x][y]), end = '')
 print(mat[x][c])

for x in range(c):
 print("{0} ".format(mat[r][x]), end='')
print(tsum)
from collections import defaultdict
from bisect import bisect_right

""" Binary Indexed Tree """
class BIT:

    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)

    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x

    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

    # x < sum(index) となる最小の index を返す
    def upper_bound(self, x):
        l, r = -1, self.N
        while l+1 < r:
            m = (l+r)//2
            y = self.sum(m)
            if x < y:
                r = m
            else:
                l = m
        return r

    # x <= sum(index) となる最小の index を返す
    def lower_bound(self, x):
        l, r = -1, self.N
        while l+1 < r:
            m = (l+r)//2
            y = self.sum(m)
            if y < x:
                l = m
            else:
                r = m
        return r

N, Q = map(int, input().split())
c = list(map(int, input().split()))
rl = [None] * Q
for i in range(Q):
    l, r = map(int, input().split())
    rl[i] = (r, l, i)
rl.sort()
bit = BIT(N+2)
ans = [None] * Q
last_idx = [-1] * N
j = 0
for r, l, i in rl:
    while j < r:
        if last_idx[c[j]] == -1:
            last_idx[c[j]] = j
        else:
            bit.add(last_idx[c[j]]+1, -1)
            last_idx[c[j]] = j
        bit.add(j+1, 1)
        j += 1
    ans[i] = bit.sum(r) - bit.sum(l-1)
print(*ans, sep='\n')
            

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    bit = [0] * (N+1)

    def add(x, a):
        while x <= N:
            bit[x] += a
            x += x & -x

    def sum(x):
        ret = 0
        while x != 0:
            ret += bit[x]
            x -= x & -x
        return ret

    c = list(map(int, input().split()))
    lr = [None] * Q
    for i in range(Q):
        l, r = map(int, input().split())
        lr[i] = (i, l, r)
    lr.sort(key=lambda x: x[2])
    ans = [None] * Q
    last_idx = [-1] * (N+1)
    j = 0
    for i, l, r in lr:
        while j < r:
            if last_idx[c[j]] == -1:
                last_idx[c[j]] = j
            else:
                add(last_idx[c[j]]+1, -1)
                last_idx[c[j]] = j
            add(j+1, 1)
            j += 1
        ans[i] = sum(r) - sum(l-1)
    for a in ans:
        print(a)
            
if __name__ == "__main__":
    main()