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

import sys
input = sys.stdin.readline

B = int(1E8)

def main():

    H, W = map(int, input().split())
    
    l = 0
    q = []
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.append(B*h+w)
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append(B*(h-1) + w)
            if h != H-1:
                Next[h][w].append(B*(h+1) + w)
            if w != 0:
                Next[h][w].append(B*h + w-1)
            if w != W-1:
                Next[h][w].append(B*h + w+1)

    c = -1
    for _ in range(H+W+2):
        qq = []
        if l == 0:
            break
        nl = 0
        for hw in q:
            h, w = hw//B, hw%B
            for nhw in Next[h][w]:
                nh, nw = nhw//B, nhw%B
                if not checked[nh][nw]:
                    qq.append(B*nh + nw)
                    checked[nh][nw] = True
                    nl += 1
        q = qq
        l = nl
        c += 1

    print(c)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

B = int(1E8)

def main():

    H, W = map(int, input().split())
    
    l = 0
    q = []
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.append(B*h+w)
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append(B*(h-1) + w)
            if h != H-1:
                Next[h][w].append(B*(h+1) + w)
            if w != 0:
                Next[h][w].append(B*h + w-1)
            if w != W-1:
                Next[h][w].append(B*h + w+1)

    c = -1
    for _ in range(H+W+2):
        qq = []
        if len(q) == 0:
            break
        for hw in q:
            h, w = hw//B, hw%B
            for nhw in Next[h][w]:
                nh, nw = nhw//B, nhw%B
                if not checked[nh][nw]:
                    qq.append(B*nh + nw)
                    checked[nh][nw] = True
        q = qq
        c += 1

    print(c)


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

S = str(input())
Q = int(input())

for _ in range(Q):
    query = list(map(str, input().split()))

    if query[0] == "1":
        S = S[::-1]
    else:
        if query[1] == "1":
            S = query[2] + S
        else:
            S += query[2]
print(S)


### FIXED CODE ###

S = str(input())
Q = int(input())

topFlg = True

leftStr = ""
rightStr = ""

for _ in range(Q):
    query = list(map(str, input().split()))
    if query[0] == "1":
        topFlg = not (topFlg)
    else:
        if query[1] == "1":
            if topFlg:
                leftStr = query[2] + leftStr
            else:
                rightStr += query[2]
        else:
            if topFlg:
                rightStr += query[2]
            else:
                leftStr = query[2] + leftStr

print(leftStr + S +
      rightStr if topFlg else rightStr[::-1] + S[::-1] + leftStr[::-1])
### BUGGY CODE ###

N, M = map(int, input().split())
a = [0 for i in range(M)]
b = [0 for i in range(M)]
c = [0 for i in range(M)]
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
distance = [-10**20 for i in range(N)]
distance[0] = 0
for i in range(1,N):
    for j in range(M):
        u = a[j]-1; v = b[j]-1
        if distance[v] < distance[u] + c[j]:
            distance[v] = distance[u] + c[j]
negative = [False for i in range(N)]
for i in range(N):
    for j in range(M):
        u = a[j]-1; v = b[j]-1
        if distance[v] < distance[u] + c[j]:
            distance[v] = distance[u] + c[j]
            negative[v] = True
        if negative[u]:
            negative[v] = True
if negative[N-1]:
    print("inf")
else:
    print(distance[N-1])


### FIXED CODE ###

N, M = map(int, input().split())
a = [0 for i in range(M)]
b = [0 for i in range(M)]
c = [0 for i in range(M)]
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
distance = [-10**20 for i in range(N)]
distance[0] = 0
for i in range(1,N):
    for j in range(M):
        u = a[j]-1; v = b[j]-1
        if distance[v] < distance[u] + c[j]:
            distance[v] = distance[u] + c[j]
negative = [False for i in range(N)]
for i in range(N):
    for j in range(M):
        u = a[j]-1; v = b[j]-1
        if distance[v] < distance[u] + c[j]:
            distance[v] = distance[u] + c[j]
            negative[v] = True
        if negative[u]:
            negative[v] = True
if negative[N-1]:
    print("inf")
else:
    print(distance[N-1])
### BUGGY CODE ###

def main():
    import sys #追加
    sys.setrecursionlimit(500*500) #追加
    n = int(input())

    x = []
    l = []
    tls = []
    for i in range(n):
        tmp = list(map(int, input().split()))
        x.append(tmp[0])
        l.append(tmp[1])
    x, l = zip(*sorted(zip(x, l)))

    m = {}
    def solve(prev, idx):
        if idx == n:
            return 0
        key = (prev, idx)
        if key in m:
            return m[key]
        res_use = 0
        res_nouse = 0
        if idx < n - 1:
            if x[idx] + l[idx] >= x[idx+1] + l[idx+1]: 
                return solve(prev, idx+1)
        if x[idx] - l[idx] >= prev or prev == 0:
            res_use = 1
            res_use += solve(x[idx] + l[idx], idx + 1)
        res_nouse += solve(prev, idx + 1)

        ans = max(res_use, res_nouse)
        m[key] = ans
        return ans
    print(solve(0, 0))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    x = []
    l = []
    for i in range(n):
        tmp = list(map(int, input().split()))
        x.append(tmp[0] - tmp[1])
        l.append(tmp[0] + tmp[1])
    x, l = zip(*sorted(zip(x, l)))
    maxcount = 0
    preve = 0
    idx = 0
    while idx < n:
        tmps = x[idx]
        tmpe = l[idx]
        if preve == 0:
            maxcount += 1
            preve = tmpe
        elif tmps >= preve:
            maxcount += 1
            preve = tmpe
        elif tmpe < preve:
            preve = tmpe
        idx += 1
    print(maxcount)
    return

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

import random
N = int(input())
X = list(input())


def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


# X = ['']*N
# for i in range(N):
#     X[i] = str(random.randint(0, 1))
# print("".join(X))
C = X.count("1")

dp = [0]*N
dp[0] = 0
for i in range(1, N):
    k = i % popcount(i)
    dp[i] = 1 + dp[k]


# def solve(n, d):


for i in range(N):
    if X[i] == "0":
        X[i] = '1'
        print(dp[int((''.join(X)), 2) % (C+1)] + 1)
        #tmp = dp[int((''.join(X)), 2) % (C+1)] + 1
        X[i] = '0'
    else:
        if C == 1:
            print(0)
            continue
        X[i] = '0'
        print(dp[int((''.join(X)), 2) % (C-1)] + 1)
        #tmp = dp[int((''.join(X)), 2) % (C-1)] + 1
        X[i] = '1'


# print(dp)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    X = input().decode()
    K = int(X, 2)
    X = list(X)

    def popcount(x):
        # 2bitごとの組に分け、立っているビット数を2bitで表現する
        x = x - ((x >> 1) & 0x5555555555555555)

        # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
        x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

        x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
        x = x + (x >> 8)  # 16bitごと
        x = x + (x >> 16)  # 32bitごと
        x = x + (x >> 32)  # 64bitごと = 全部の合計
        return x & 0x0000007f

    # X = ['']*N
    # for i in range(N):
    #     X[i] = str(random.randint(0, 1))
    # print("".join(X))
    C = X.count("1")
    dpL = [0]*N
    dpR = [0]*N
    tmp = 1
    dpL[0] = 1 % (C+1)
    L = K % (C+1)

    if C == 1:
        R = 0
    else:
        R = K % (C-1)
        dpR[0] = 1 % (C-1)

    for i in range(1, N):
        dpL[i] = dpL[i-1]*2 % (C+1)
        if C > 1:
            dpR[i] = dpR[i-1]*2 % (C-1)

    dp = [0]*N
    dp[0] = 0
    for i in range(1, N):
        k = i % popcount(i)
        dp[i] = 1 + dp[k]

    # def solve(n, d):

    for i in range(N):
        if X[i] == "0":
            print(dp[(L + dpL[N-i-1]) % (C+1)] + 1)
        else:
            if C == 1:
                print(0)
                continue
            X[i] = '0'
            print(dp[(R - dpR[N-i-1]) % (C-1)] + 1)
            #tmp = dp[int((''.join(X)), 2) % (C-1)] + 1
            X[i] = '1'


main()
# print(dp)
### BUGGY CODE ###

from operator import mul
import collections
N = int(input())
A = list(map(int, input().split()))
cnt = collections.Counter(A)
Q = int(input())
ans = []
for _ in range(Q):
    b, c = map(int, input().split())
    if b in cnt:
        cnt[c] += cnt[b]
        del cnt[b]
    k = list(cnt.keys())
    v = list(cnt.values())
    print(sum(map(mul, k, v)))

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
cnt = collections.Counter(A)
Q = int(input())
ans = []
s = sum(A)
for _ in range(Q):
    b, c = map(int, input().split())
    n = cnt[b]
    if b in cnt:
        cnt[c] += cnt[b]
        del cnt[b]
    s += (c-b)*n
    print(s)
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
n = int(input())
A = []
ans = 0
nodes = set()
adjacent_list = defaultdict(list)
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in range(1, len(tmp)):
        l, g = min(i, tmp[j] - 1), max(i, tmp[j] - 1 )
        pre_l, pre_g = min(i, pre), max(i, pre) 
        adjacent_list[pre_l * n + pre_g].append(l * n + g)
        nodes.add(pre_l * n + pre_g)
        nodes.add(l * n + g)
        pre = tmp[j] - 1
nodes = list(nodes)
#まず、閉路検
seen = defaultdict(bool)
visited = defaultdict(bool)
def check(node):
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if len(adjacent_list[node]) == 0:
        return 1
    if node in finish:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = max(tmp, finish[node])
    return finish[node]
finished = set()
for i in nodes:
    check(i)
finish = defaultdict(int)
for i in nodes:
    dfs_path(i)
print(max(max(finish.values()), 1))

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n = int(input())
A = []
M = [[-1 for _ in range(n)] for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        M[i][j] = cnt
        M[j][i] = cnt
        cnt += 1
ans = 0
nodes = []
adjacent_list = [[] for i in range(n*(n-1)//2)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in tmp[1:]:
        adjacent_list[M[i][pre]].append(M[i][j-1])
        pre = j - 1
#まず、閉路検
seen = defaultdict(lambda: False)
visited = defaultdict(lambda: False)
def check(node):
    if visited[node]:
        return
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if not adjacent_list[node]:
        return 1
    if finish[node]:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = tmp
    return finish[node]
finished = set()
finish = [0 for i in range(n*(n-1)//2)]
for i in range(n*(n-1)//2):
    check(i)
    dfs_path(i)
print(max(max(finish), 1))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(set)
start={i for i in range(N)}
for i in range(N+M-1):
    a,b=map(int,input().split())
    start-={b-1}
    OUT[a-1]|={(i,b-1)}
    IN[b-1]|={i}
P=[0]*N
while len(start)>0:
    now=start.pop()
    for b,nex in OUT[now]:
        IN[nex].remove(b)
        if not IN[nex]:
            start|={nex}
            P[nex]=now+1
for p in P:
    print(p)

### FIXED CODE ###

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(int)
for i in range(N+M-1):
    a,b=map(int,input().split())
    OUT[a-1]|={b-1}
    IN[b-1]+=1
P=[0]*N
start={i for i in range(N) if IN[i]==0}
while len(start)>0:
    now=start.pop()
    for nex in OUT[now]:
        IN[nex]-=1
        if IN[nex]==0:
            start|={nex}
            P[nex]=now+1
[print(p) for p in P]
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=[]
SA=sum(A)
SB=sum(B)
S=SA-SB
cnt=0
if SB>SA:
    print(-1)
    exit()
for a,b in zip(A,B):
    if a>b:
        C.append(a-b)
    elif a==b:
        cnt+=1
for c in sorted(set(C)):
    if S>=C.count(c)*c:
        cnt+=C.count(c)
        S-=C.count(c)*c
    else:
        cnt+=S//c
        S=0
    if S==0:
        break
print(N-cnt)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=[]
SA=sum(A)
SB=sum(B)
S=SA-SB
cnt=0
ns=0
if SB>SA:
    print(-1)
    exit()
for a,b in zip(A,B):
    if a>b:
        C.append(a-b)
    elif a<b:
        ns+=b-a
        cnt+=1
C.sort(reverse=True)
for i in range(len(C)):
    if ns>0:
        cnt+=1
        ns-=C[i]
    else:break
print(cnt)
### BUGGY CODE ###

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

s = input()

count = []

for i in range(0, q) :
    l, r = map(int, input().split())
    count.append(str(s[l-1:r].count('AC')))

print('\n'.join(count))

### FIXED CODE ###

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

s = input()

count = [0] * n

for i in range(n) :
    if s[i-1] + s[i] == 'AC' :
        count[i] = count[i-1] + 1
    else :
        count[i] = count[i-1]

for j in range(0, q) :
    l, r = map(int, input().split())
    print(count[r-1] - count[l-1])
### BUGGY CODE ###

MOD = 10**9 + 7

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

ans = 0
for d in range(60):
    sumXOR = 0
    num0, num1 = 0, 0
    for A in As:
        if (A>>(59-d))&1:
            num1 += 1
        else:
            num0 += 1
#    print('d:', d, '/ num0:', num0, '/ num1:', num1)
    sumXOR += (num0 * num1) % MOD
    sumXOR %= MOD
    ans *= 2
    ans += sumXOR
    ans %= MOD

print(ans)


### FIXED CODE ###

MOD = 10**9 + 7

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

ans = 0
for d in range(60):
    sumXOR = 0
    num0, num1 = 0, 0
    for A in As:
        if (A>>(59-d))&1:
            num1 += 1
        else:
            num0 += 1
#    print('d:', d, '/ num0:', num0, '/ num1:', num1)
    sumXOR += (num0 * num1) % MOD
    sumXOR %= MOD
    ans *= 2
    ans += sumXOR
    ans %= MOD

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

K = int(input())

mod_ini = 7%K
mod = 0
cnt = 0

while True:
    if K%2 == 0:
        print(-1)
        break
    
    cnt += 1
    mod = (mod*10 + 7)%K
    #print(mod)
    
    if mod == 0:
        print(cnt)
        break
    elif mod == mod_ini and cnt != 1:
        print(-1)
        break
    

### FIXED CODE ###

K = input()
K_1 = int(K[-1])
K = int(K) 

mod_ini = 7%K
mod = 0
cnt = 0

while True:
    if K%2 == 0 or K_1 == 5:
        print(-1)
        break
    
    cnt += 1
    mod = (mod*10 + 7)%K
    #print(mod)
    
    if mod == 0:
        print(cnt)
        break
    elif mod == mod_ini and cnt != 1:
        print(-1)
        break
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    si = input()
    s.append(si)
    
s.sort()
sset = set(s)
ns = len(sset)
cou = []
pri = []
pre = 0

for i in range(ns):
    c = s.count(s[pre])
    cou.append(c)
    pre += c
    pri.append(s[pre-1])
    
M = max(cou)
for i in range(ns):
    if cou[i] == M:
        print(pri[i])

### FIXED CODE ###

import collections

n = int(input())
s = []
for i in range(n):
    si = input()
    s.append(si)
    
s.sort()
counted = collections.Counter(s)
M = max(counted.values())

ms = [k for k, v in counted.items() if v == M]
ms.sort()

for i in range(len(ms)):
    print(ms[i])
### BUGGY CODE ###

s = input()
k = int(input())
ans = ""
alpha = "abcdefghijklmnopqrstuvwxyz"
l = len(alpha)
for i in range(len(s)-1):
    if l - alpha.index(s[i]) <= k:
        k -= l - alpha.index(s[i])
        ans += "a"
    else:
        ans += s[i]
ans += alpha[(alpha.index(s[-1]) + k + l**100) % l]
print(ans)

### FIXED CODE ###

s = input()
k = int(input())
ans = ""
l = 26
for i in range(len(s)-1):
    if l - ord(s[i]) + 97 <= k and s[i] != "a":
        k -= l - ord(s[i]) + 97
        ans += "a"
    else:
        ans += s[i]
ans += (chr(((ord(s[-1]) - 97) + k + l) % l + 97))
print(ans)
### BUGGY CODE ###

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

import sys
import math

def main():
    n = int(input())
    root_n=math.ceil(math.sqrt(n))
    ans=[0]*n
    count=0
    for i in range(1,n+1):
        for x in range(1,root_n):
            if x**2 >= i:
                break
            for y in range(1,root_n):
                for z in range(1,root_n):
                    if x**2+y**2+z**2+x*y+y*z+z*x==i:
                        count+=1
        print(count)
        count=0

if __name__ == "__main__":
    main()

### FIXED CODE ###

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

import sys
import math

def main():
    n = int(input())
    root_n=math.ceil(math.sqrt(n))
    ans=[0]*n
    count=0

    for x in range(1,root_n):
        for y in range(1,root_n):
            for z in range(1,root_n):
                tmp=x**2+y**2+z**2+x*y+y*z+z*x
                if tmp<n+1:
                    ans[tmp-1]+=1
    for i in ans:
        print(i)

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

N = int(raw_input())
A = map(int, raw_input().split())
A = map(lambda x: format(x, '060b'), A)
MOD = 10**9 + 7

count = dict()
for i in range(60):
    zeros = len([a[i] for a in A if a[i] == '0'])
    ones = N - zeros
    count[i] = zeros*ones

ans = 0
for i, v in count.items():
    ans = (ans + count[i]*((1<<(59-i)) % MOD)) % MOD

print ans


### FIXED CODE ###

import numpy as np

N = int(raw_input())
A = np.array(map(int, raw_input().split()))
# A = map(lambda x: format(x, '060b'), A)
MOD = 10**9 + 7

count = dict()
for i in range(60):
    # zeros = len([a[i] for a in A if a[i] == '0'])
    zeros = np.count_nonzero((A>>i)&1)
    ones = N - zeros
    count[i] = zeros*ones

mod_val = dict()
curr = 1
for i in range(60):
    mod_val[i] = curr % MOD
    curr = (2*curr) % MOD

ans = 0
for i in count:
    ans = (ans + count[i]*mod_val[i]) % MOD

print ans
### BUGGY CODE ###

import itertools

N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]

ans = float('inf')
for Lp in itertools.permutations(L):
    Lac = tuple(itertools.accumulate(([0] + list(Lp))))
    for a in range(1, N - 1):
        for b in range(a + 1, N):
            for c in range(b + 1, N + 1):
                A_MP = 10 * (a - 1) + abs(Lac[a] - Lac[0] - A)
                B_MP = 10 * (b - a - 1) + abs(Lac[b] - Lac[a] - B)
                C_MP = 10 * (c - b - 1) + abs(Lac[c] - Lac[b] - C)
                ans = min(ans, A_MP + B_MP + C_MP)
print(ans)


### FIXED CODE ###

import itertools

N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]

ans = float('inf')
for Lp in itertools.permutations(L):
    Lac = tuple(itertools.accumulate(([0] + list(Lp))))
    for a in range(1, N - 1):
        for b in range(a + 1, N):
            for c in range(b + 1, N + 1):
                A_MP = 10 * (a - 1) + abs(Lac[a] - Lac[0] - A)
                B_MP = 10 * (b - a - 1) + abs(Lac[b] - Lac[a] - B)
                C_MP = 10 * (c - b - 1) + abs(Lac[c] - Lac[b] - C)
                ans = min(ans, A_MP + B_MP + C_MP)
print(ans)
### BUGGY CODE ###

from collections import defaultdict
import sys
def input(): return sys.stdin.readline().rstrip()
N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0 for i in range(Q)]
que = []
for i in range(Q):
    l, r = map(int, input().split())
    que.append((i, l, r))

Que = que.copy()

Que.sort(key=lambda x: x[-1])
point_data = defaultdict(list)

before_node = [-1 for i in range(N+1)]
for i, v in enumerate(C):
    if point_data[v]:
        before_node[i+1] = point_data[v][-1]
    point_data[v].append(i+1)

# BIT 木


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def Sum(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)

    def get(self, i, j):
        return self.Sum(j)-self.Sum(i-1)


ftree = BIT(N)
for i in range(Q):
    querie, l, r = Que[i]
    if i == 0:
        for j in range(1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    else:
        for j in range(Que[i-1][-1]+1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    ans[querie] = ftree.get(l, r)
    
for i in range(Q):
    print(ans[i])

### FIXED CODE ###

from collections import defaultdict
import sys
def input(): return sys.stdin.readline().rstrip()
N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0 for i in range(Q)]
que = []
for i in range(Q):
    l, r = map(int, input().split())
    que.append((i, l, r))

Que = que.copy()

Que.sort(key=lambda x: x[-1])
point_data = defaultdict(list)

before_node = [-1 for i in range(N+1)]
for i, v in enumerate(C):
    if point_data[v]:
        before_node[i+1] = point_data[v][-1]
    point_data[v].append(i+1)

# BIT 木


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def Sum(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)

    def get(self, i, j):
        return self.Sum(j)-self.Sum(i-1)


ftree = BIT(N)
for i in range(Q):
    querie, l, r = Que[i]
    if i == 0:
        for j in range(1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    else:
        for j in range(Que[i-1][-1]+1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    ans[querie] = ftree.get(l, r)
    
for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

from collections import Counter
n = int(input())
x = list(map(int, input().split()))
a = []
b = []
for i in range(n):
    a.append(i+1+x[i])
    b.append(i+1-x[i])
ans = 0
a, b = Counter(a), Counter(b)
for i in range(min(b), max(a)+1):
    ans += a[i]*b[i]
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
x = list(map(int, input().split()))
a = []
b = []
for i in range(n):
    a.append(i+1+x[i])
    b.append(i+1-x[i])
ans = 0
a, b = Counter(a), Counter(b)
for i in range(min(a), max(b)+1):
    ans += a[i]*b[i]
print(ans)
### BUGGY CODE ###

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

p = 0

for a in range(1, n+1):
    for b in range(1, n+1):
        for c in range(1, n+1):
            if (a+b)%k == 0 and (b+c)%k == 0 and (c+a)%k == 0:
                p += 1
            else:
                pass
              
print( p )

### FIXED CODE ###

n, k = map( int, input().split() )
ans = int((n//k)**3)

if k%2 == 1:
    print(ans)
else:
    ans += int(((n-k//2)//k+1)**3)
    print(ans)