Harryxun/stf_run huggingface dataset:
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 
# sys.stdin = open('input')
 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp()
    q = []
    for i in range(nq):
        l, r = inp()
        q.append((l, r, i))
    q.sort(key=lambda e:e[-2])
    mp = [-1] * (n+5)
    now = -1
    fw = Fenwick(n)
    ans = [0] * nq
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
 
            if mp[da[now]]!=-1:
                fw.add(mp[da[now]], -1)
            try:
                mp[da[now]] = now
            except:
                pass
            fw.add(now, 1)
        ans[idx] = fw.sum(l, r)

    print '\n'.join(map(str, ans))


            

 
 
 
 
my_main()

### FIXED CODE ###

from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 
# sys.stdin = open('input')
 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp()
    q = []
    for i in range(nq):
        l, r = inp()
        q.append((l, r, i))
    q.sort(key=lambda e:e[-2])
    mp = [-1] * (n+5)
    now = -1
    fw = Fenwick(n)
    ans = [0] * nq
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
            try:
                if mp[da[now]]!=-1:
                    fw.add(mp[da[now]], -1)
                mp[da[now]] = now
            except:
                pass
            fw.add(now, 1)
        ans[idx] = fw.sum(l, r)

    print '\n'.join(map(str, ans))


            

 
 
 
 
my_main()
N = int(input())
li =  [ int(it) -1 for it in input().split() ] 

from functools import lru_cache
MOD = 1000000007
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
@lru_cache(maxsize=None)
def modinv(a):
    (inv, q, gcd_val) = egcd(a, MOD)
    return inv % MOD
@lru_cache(maxsize=None)
def factorial(k):
  if (k<=1):
    return 1
  return (factorial(k-1)*k)%MOD
@lru_cache(maxsize=None)
def combination(n,m):
  return (factorial(n)*modinv(factorial(m))*modinv(factorial(n-m)))%MOD

#print ( factorial(5),factorial(3) )
#print ( combination(5,3) )

import collections as col
c = col.Counter( li ).items()
a = [ it for it in c if it[1] == 2][0][0]
p1 = li.index(a)
p2 = li[p1+1:].index(a) + 1 + p1
#print ( p1 , p2 )
H = p1 + (N-p2)
#print ( H )

li=[]
for i in range(1,N+2):
  a =  (combination(N+1,i) - (combination(H,i-1)if (i-1)<=H else 0))%MOD
  li.append(a)
print ( "\n".join( map(str,li) ) )
  

### FIXED CODE ###

N = int(input())
li =  [ int(it) -1 for it in input().split() ] 

import sys
sys.setrecursionlimit(10000000)

from functools import lru_cache
MOD = 1000000007
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
@lru_cache(maxsize=None)
def modinv(a):
    (inv, q, gcd_val) = egcd(a, MOD)
    return inv % MOD

fac_li = [0]*( 1000009 )
if True:
  s = 1
  for i in range(1,1000001):
    s = (s*i)%MOD
    fac_li[i] = s
def factorial(k):
  if (k<=1):
    return 1
  return fac_li[k]
@lru_cache(maxsize=None)
def combination(n,m):
  return (factorial(n)*modinv(factorial(m))*modinv(factorial(n-m)))%MOD

#print ( factorial(5),factorial(3) )
#print ( combination(5,3) )

import collections as col
c = col.Counter( li ).items()
a = [ it for it in c if it[1] == 2][0][0]
p1 = li.index(a)
p2 = li[p1+1:].index(a) + 1 + p1
#print ( p1 , p2 )
H = p1 + (N-p2)
#print ( H )

li=[]
for i in range(1,N+2):
  a =  (combination(N+1,i) - (combination(H,i-1)if (i-1)<=H else 0))%MOD
  li.append(a)
print ( "\n".join( map(str,li) ) )
import sys

n=int(input())

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

c=[0]*(max(a)+1)

for i in range(len(a)):
  c[a[i]]+=1

  if c[a[i]]>1:
    print("NO")
    sys.exit()

print("YES")


### FIXED CODE ###

import sys

n=int(input())

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

a.sort()

for i in range(len(a)-1):
  if a[i]==a[i+1]:
    print("NO")
    sys.exit()

print("YES")
a = int(input())
b = int(input())
c = int(input())
x = int(input())
cnt = 0
ma = x // a
mb = x // b
mc = x // c
for i500 in range(ma+1):
  for i100 in range(mb+1):
    for i50 in range(mc+a):
      if 500*i500 + 100*i100 + 50*i50 == x:
        cnt += 1
print(cnt)

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
x = int(input())
cnt = 0
ma = x // 500
mb = x // 100
mc = x // 50
na = min([a, ma])
nb = min([b, mb])
nc = min([c, mc])
for i500 in range(na+1):
  for i100 in range(nb+1):
      current = x-500*i500-100*i100
      if current >= 0 and current <= 50*nc:
          cnt += 1
          #print(i500,i100,cnt)
print(cnt)
# A V
# B W
# T
A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

if (V-W)*T >= B-A and (B-A) % (V-W) == 0:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

# A V
# B W
# T
A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

if (V-W)*T >= abs(B-A):
    print('YES')
else:
    print('NO')
res=[]
s=True
while s:
    s=input()
    if s:
        a,b = [int(x) for x in s.split()]
        res.append(a+b)

import math
for n in res:
    print(int(math.log(n,10))+1)

### FIXED CODE ###

res=[]

while 1:
    try:
        s=input()
        a,b = [int(x) for x in s.split()]
        res.append(a+b)
    except:
        for n in res:
            print(len(str(n)))
        break
# https://atcoder.jp/contests/abc089/tasks/abc089_d

# queryがたくさんある系
# query一つにつきO(1)ぐらいで応答しないと行けない→前処理の必要あり

# あるマスについてはD倍したマスだけ把握しておけばいいんじゃない？
'''
D=2
1 4 3
2 5 7
8 9 6
'''
# だったらstart=1,2において、移動のスコアの累積和を入れていく
# Qに回答時は、L%D番目のstartの累積和において、L//Dにおいて累積和の差を求めれば良い
# ピッタリDだった場合に面倒なので-0.5して置くのは良いかもしれない

from collections import defaultdict
from itertools import accumulate
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def get_cost(i, j, x, y):
    return abs(x - i) + abs(y - j)


H, W, D = read_ints()
A = read_matrix(H)
ruiseki = defaultdict(lambda: [])
num_to_co = {}

for i, a in enumerate(A):
    for j, aa in enumerate(a):
        num_to_co[aa] = (i, j)

for num in range(1, D + 1):
    pre_i, pre_j = num_to_co[num]
    pre_num = num
    ruiseki[num].append(0)
    while W * H >= pre_num + D:
        now_num = pre_num + D
        i, j = num_to_co[now_num]
        cost = get_cost(pre_i, pre_j, i, j)
        ruiseki[num].append(cost)
        # 必要なもの、前のi,j今のi,j 今の番号
        # 更新するもの 前のi,j←今のi,j 今の番号を次の番号に
        pre_i, pre_j = i, j
        pre_num = now_num

    ruiseki[num] = list(accumulate(ruiseki[num]))
# print(ruiseki)

# Qに答える番だ
Q = int(input())
for _ in range(Q):
    L, R = read_ints()
    tmp = ruiseki[L % D if L % D != 0 else (L // D)]
    # print(tmp)
    # print((R - 1) // D, (L - 1) // D)
    print(tmp[(R - 1) // D] - tmp[(L - 1) // D])


### FIXED CODE ###

# https://atcoder.jp/contests/abc089/tasks/abc089_d

# queryがたくさんある系
# query一つにつきO(1)ぐらいで応答しないと行けない→前処理の必要あり

# あるマスについてはD倍したマスだけ把握しておけばいいんじゃない？
'''
D=2
1 4 3
2 5 7
8 9 6
'''
# だったらstart=1,2において、移動のスコアの累積和を入れていく
# Qに回答時は、L%D番目のstartの累積和において、L//Dにおいて累積和の差を求めれば良い
# ピッタリDだった場合に面倒なので-0.5して置くのは良いかもしれない

from collections import defaultdict
from itertools import accumulate
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def get_cost(i, j, x, y):
    return abs(x - i) + abs(y - j)


H, W, D = read_ints()
A = read_matrix(H)
ruiseki = defaultdict(lambda: [])
num_to_co = {}

for i, a in enumerate(A):
    for j, aa in enumerate(a):
        num_to_co[aa] = (i, j)

for num in range(1, D + 1):
    pre_i, pre_j = num_to_co[num]
    pre_num = num
    ruiseki[num].append(0)
    while W * H >= pre_num + D:
        now_num = pre_num + D
        i, j = num_to_co[now_num]
        cost = get_cost(pre_i, pre_j, i, j)
        ruiseki[num].append(cost)
        # 必要なもの、前のi,j今のi,j 今の番号
        # 更新するもの 前のi,j←今のi,j 今の番号を次の番号に
        pre_i, pre_j = i, j
        pre_num = now_num

    ruiseki[num] = list(accumulate(ruiseki[num]))
# print(ruiseki)

# Qに答える番だ
Q = int(input())
for _ in range(Q):
    L, R = read_ints()
    tmp = ruiseki[L % D if L % D != 0 else D]
    # print(tmp)
    # print((R - 1) // D, (L - 1) // D)
    print(tmp[(R - 1) // D] - tmp[(L - 1) // D])
n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
def gcd(a, b):
    if b ==0:
        return a
    else:
        return gcd(b,a%b)

def lcm(a, b):
    # print(gcd(a,b))
    return a * b/gcd(a, b)


mk = 1
for i in a:
    mk = lcm(mk, i)


k = 0
for i in a:
    k = (k +  mk / i) %MOD
print(int(k %MOD))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
def gcd(a, b):
    if b ==0:
        return a
    else:
        return gcd(b,a%b)

mk = 1
for i in a:
    mk = mk * i//gcd(mk, i)

k = 0
for j in a:
    k +=  mk // j
print(k %MOD)
# -*- coding: utf-8 -*-
A = int(input())
B = int(input())

if (A > 8) or (B > 8):
    print (":(")
else:
     print ("Yay!")

### FIXED CODE ###

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

if (A > 8) or (B > 8):
    print (":(")
else:
    print ("Yay!")
import math

def lcm(x, y):
    return (x*y)//math.gcd(x,y)

A,B = map(int,input().split())

print(lcm(A,B))


### FIXED CODE ###

from fractions import gcd

def lcm(x, y):
    return (x*y)//gcd(x,y)

A,B = map(int,input().split())

print(lcm(A,B))
s = int(input())
while s >0:
  s = s-4
  if s%7 == 0:
    print('Yes')
    break
    
if s<=0:
  print('No')

### FIXED CODE ###

N,K = map(int,input().split())
if N%K == 0:
  print(0)
  
else:
  print(1)
#coding: utf-8
N,Y=map(int,input().split(" "))
for x in range(N+1):
  for y in range(N+1-x):
	z=N-x-y
    if 10000*x+5000*y+1000*z==Y:
      print(str(x)," ",str(y)," ",str(z))
      exit()
print("-1 -1 -1")

### FIXED CODE ###

#coding: utf-8
N,Y=map(int,input().split(" "))
for x in range(N+1):
  for y in range(N+1-x):
    z=N-x-y
    if 10000*x+5000*y+1000*z==Y:
      print(str(x)," ",str(y)," ",str(z))
      exit()
print("-1 -1 -1")
N,L = map(int,input().split())

a = 10**6
b = 0
ans = 0
for i in range(1,N+1):
    if abs(L+i-1) < mina:
        mina = abs(L+i-1)
        minb = i
        
for i in range(1,N+1):
    if i != minb:
        ans += (L+i-1)

print(ans)




### FIXED CODE ###

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

a = 10**6
b = 0
ans = 0
for i in range(1,N+1):
    if abs(L+i-1) < a:
        a = abs(L+i-1)
        b = i

for i in range(1,N+1):
    if i != b:
        ans += (L+i-1)

print(ans)
N=int(input()) #縦2列
XY=[map(int, input().split()) for _ in range(N)]
X,Y=[list(i) for i in zip(*XY)]
ans="No"

for j in range(0,N-2):
    if X[j]==Y[j] and X[j+1]==Y[j+1] and X[j+2]==Y[j+2]:
        ans="Yes"
        break

print(ans)

### FIXED CODE ###

S=input()
s="s"
es="es"

if S[len(S)-1]==s:
    S=S+es
else:
    S=S+s

print(S)
import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7

if N==K:
  ans0 = 1
  for a in A[0:N]:
    ans0 *= a
    ans0 %= MOD
  print(ans0)
  exit()
A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 *= a
    ans1 %= MOD
  print(ans1)
  exit()

A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]

ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

while ansA>0:
  ansA-=MOD

B1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]

if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
#if not Bp:Bp.insert(0,B1[0])
#if not Bm:Bm.insert(0,B1[-1])
  
#print(Bp,Bm,B2)

B1.remove(Bp[-1])
B1.append(B2[0])
#print(B1)
ansB = 1
for a in B1[0:K]:
  ansB *= a
  ansB %= MOD

C1=A[0:K]
C1.remove(Bm[-1])
C1.append(B2[-1])

ansC = 1
for a in C1[0:K]:
  ansC *= a
  ansC %= MOD

print(max(ansB,ansC)%MOD)

### FIXED CODE ###

import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
if N==K:
  ans0 = 1
  for a in A[0:N]:
    ans0 *= a
    ans0 %= MOD
  print(ans0)
  exit()
A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 *= a
    ans1 %= MOD
  print(ans1)
  exit()
 
A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]
 
ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

while ansA>0:
  ansA-=MOD

B1=A[0:K]
C1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]
 
if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
#print(Bp,Bm,B2)
#print(Bp[-1],B2[0])
B1.remove(Bp[-1])
B1.append(min(B2[0],0))
#print(B1)
ansB = 1
for a in B1[0:K]:
  ansB *= a
  ansB %= MOD
#print(Bm[-1],B2[-1])
C1.remove(Bm[-1])
C1.append(max(B2[-1],0))
 
ansC = 1
for a in C1[0:K]:
  ansC *= a
  ansC %= MOD
#print(B1,C1)
#print(ansB,ansC)
BB1=[np.sign(i) for i in B1]
ansBB1 = BB1[0:K].count(-1)%2
BB2=[np.sign(i) for i in C1]
ansBB2 = BB2[0:K].count(-1)%2
#print(ansBB1,ansBB2)
if ansBB1==1:
  print(ansC)
  exit()
if ansBB2==1:
  print(ansB)
  exit()
#print(B2[0]/Bp[-1],B2[-1]/Bm[-1])
#print(Bp[-1]*B2[-1],Bm[0]*B2[0])

#print(abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0]))
#print(ansB,ansC)
if abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0])>=0:
  print(ansC)
else: print(ansB)
input_list = list(map(int, input().split()))
hp = input_list[0]
arts = input_list[1]
arts_list = list(map(int, input().split()))
if hp < sum(arts_list):
  print(Yes)
else:
  print(No)


### FIXED CODE ###

input_list = list(map(int, input().split()))
hp = input_list[0]
arts = input_list[1]
arts_list = list(map(int, input().split()))
if hp <= sum(arts_list):
  print("Yes")
else:
  print("No")
from collections import deque
import fractions
N=int(input())
s=deque(list(map(int,input().split())))
ans=1
for i in range(N):
  a=s.popleft()
  b=fractions.gcd(s[0],s[1])
  for j in range(2,N-2):
    b=fractions.gcd(b,s[j])
  ans=max(ans,b)
  s.append(a)
print(ans)

### FIXED CODE ###

import fractions
N=int(input())
l1=list(map(int,input().split()))
l2=[0]*(N+1)
l3=[0]*(N+1)
for i in range(N):
  l2[i+1]=fractions.gcd(l2[i],l1[i])
for j in range(N-1,0,-1):
  l3[j-1]=fractions.gcd(l3[j],l1[j])
ans=1
for k in range(N):
  ans=max(ans,fractions.gcd(l2[k],l3[k]))
print(ans)
a,b,c,d = map(int,input().split())
l = list(range(a,b+1))
ans = 0


### FIXED CODE ###

A,B,C,D = map(int,input().split())

def gcd(a,b):
  while b:
    a,b = b,a%b
  return a

def F(N,C,D):
  x = N
  x -= N//C
  x -= N//D
  lcm = C*D//gcd(C,D)
  x += N//lcm
  return x

answer = F(B,C,D) - F(A-1,C,D)
print(answer)
a, b, c, x, y = map(int, input().split())
print(min(a*x+b*y, 2*c*x + b*max(0,y-x), 2*c*y + a*max(0, x-y))

### FIXED CODE ###

a, b, c, x, y = map(int, input().split())
print(min(a*x+b*y, 2*c*x + b*max(0,y-x), 2*c*y + a*max(0, x-y)))
import math
from functools import reduce


def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    mul = lcm_list(a)

    if m > (mul // 2):
        ans = ((m - (mul // 2)) // mul) + 1
        print(int(ans))
    else:
        print(0)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
def div_ceil(x, y): return (x + y - 1) // y
 
N, M = map(int, input().split())
*A, = map(int, input().split())
A = list(set([a // 2 for a in A]))
L = A[0]
for a in A[1:]:
    L *= a // gcd(L, a)
for a in A:
    if (L // a) % 2 == 0:
        ans = 0
        break
else:
    ans = div_ceil(M // L, 2)
print(ans)
k = int( input())
s = list(str(input()))
n = int( input())
  
for i in range(len(s)):
    if s[i] != s[n+1]:
        s[i] = "*"
          
print(s)

### FIXED CODE ###

k = int( input())
s = list(str(input()))
n = int( input())
a = ""
  
for i in range(len(s)):
    if s[i] != s[n-1]:
        s[i] = "*"
    a+=(str(s[i]))
        
print(a)
N=int(input())

A=N[0]
B=N[1]
C=N[2]

print (C,A,B)

### FIXED CODE ###

A,B,C=map(int,input().split())

print (C,A,B)
c=int(input())
count=1
ans=10000000000000
k=c
a=[]
for i in range(1,int(c**(1/2))):
    if c%i==0:
        count*=i
        k=int(k/i)
        a.append(count+k)
print(min(a)-2)

### FIXED CODE ###

c=int(input())
count=1
ans=10000000000000
k=c
for i in range(1,int(c**(1/2)+100000)):
    if c%i==0:
        if ans>i+int(c/i):
            ans=i+int(c/i)
        else:
            continue
print(ans-2)
a = list(input())
b = list(input())
c = len(a)
d = len(b)

flag = False
for i in range(c-d+1):
    li = [0]*c
    for k in range(c):
        li[k] = a[k]
    for j in range(d):
        if b[j] == a[i+j] or a[i+j] == "?":
            flag = True
            li[i+j] = b[j]
        elif b[j] != a[i+j]:
            flag = False
            break
    else:
        continue
for i in range(c):
    if li[i] == "?":
        li[i] = "a"

if flag:
    print("".join(li))
else:
    print("UNRESTORABLE")

### FIXED CODE ###

a = list(input())
b = list(input())
c = len(a)
d = len(b)
if d > c:
    print("UNRESTORABLE")
    exit()
ans = []
   
for i in range(c-d+1):
    #print(a[i:i+d])
    flag = False
    for j in range(d):
        if a[i:i+d][j] == b[j] or a[i:i+d][j] == "?":
            flag = True
        else:
            flag = False
            break
    li = [] 
    if flag:
        #print(a[i:i+d])
        li = a[:i] + b + a[i+d:]
        for k in range(len(li)):
            if li[k] == "?":
                li[k] = "a"
        ans.append("".join(li))
if ans:
    ans.sort()
    print(ans[0])
else:
    print("UNRESTORABLE")
N = int(input())
A = list(map(int, input().split()))
dic1 = {}
dic2 = {}
for i in range(N):
  if A[i] in dic1:
    dic1[A[i]] += 1
    dic2[A[i]].append(i)
  else:
    dic1[A[i]] = 1
    dic2[A[i]].append(i)

for j in range(N):
  ans = 0
  for k, v in dic1.items():
    if j in dic2[k]:
      ans += ((v-1)*(v-2))//2
    else:
      ans += (v*(v-1))//2
  print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
dic1 = {}
dic2 = {}
for i in range(N):
  if A[i] in dic1:
    dic1[A[i]] += 1
  else:
    dic1[A[i]] = 1
ans = 0
for v in dic1.values():
  ans += (v*(v-1))//2
for j in range(N):
  w = dic1[A[j]]
  v = w-1
  comb = ans -(w*(w-1))//2 + (v*(v-1))//2
  print(comb)
from collections import deque
def main():
    n,m = map(int, input().split())
    lst = deque([i for i in range(1,n+1)])
    for i in range(1,m+1):
        a = lst.popleft()
        b = a + i
        lst.remove(b)
        print(str(a)+' '+str(b))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n,m = map(int, input().split())
    if n%2==0 and 2*(m+1)==n:
        if n%4:
            for i in range(1,n//4+1):
                print(i,n//2-i)
            j = n

            for i in range(n//2+1,n//2+n//4+1):
                print(i,j)
                j -= 1
        else:
            for i in range(1,n//4+1):
                print(i,n//2+1-i)
            j = n-1
            for i in range(n//2+1,n//2+n//4):
                print(i,j)
                j -= 1
    else:
        for i in range(1,m+1):
            print(i,n-i)
if __name__ == '__main__':
    main()
n,m = map(int,input().split())

print((1990*m + 100(n-m))*2**m )

### FIXED CODE ###

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

print((1900*m + 100*(n-m))*(2**m) )
number = input(x=:)

x = int(number)

print(x***)

### FIXED CODE ###

x = int(input())

print(x **3)
S = input()
T = input()

T.pop(len(T) - 1)

if S == T:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

S = input()
T = input()
     
if S == T[:-1]:
  print('Yes')
else:
  print('No')
A=[int(input()) for i in range(5)]
k=int(input())

for i in range(4):
	for i in range(i):
		if A[i]-A[j]>k:
			print(""":(""")
			exit()
print("Yay!")

### FIXED CODE ###

A=[int(input()) for _ in range(5)]
k=int(input())

for i in range(5):
  for j in range(i):
    if A[i]-A[j]>k:
      print(":(")
      exit()
print("Yay!")
import math
from decimal import Decimal

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

for i in range(1,N):
        T2, A2 = [int(x) for x in input().split()]
        print('i= ',i)
        n = max(math.ceil(Decimal(T)/Decimal(T2)),math.ceil(Decimal(A)/Decimal(A2))
        print('n= ',n)
        T = T2*n
        A = A2*n
        print('T= ',T)
        print('A= ',A)

print(T + A)

### FIXED CODE ###

import math
from decimal import Decimal

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

for i in range(1,N):
        T2, A2 = [Decimal(x) for x in input().split()]
        n = Decimal(max(math.ceil(T/T2),math.ceil(A/A2)))
        T = T2 * n
        A = A2 * n

print(T+A)
x,y = map(int, input().split())

if 2*x <= y and y <= 4*x:
  if y % 2 == 0:
    print('Yes')
  else:
    print('No')
else:
  print('No')


### FIXED CODE ###

a,b,c,d,e = map(int, input().split())
print(15-a-b-c-d-e)
for _ in  A:
    if _ % 2 == 0:
        if _ % 3 == 0 or _ % 5 == 0:
            ans *= 1
        else:
            ans *= 0

if ans == 1:
    print('APPROVED')
else:
    print('DENIED')

### FIXED CODE ###

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

for _ in  A:
    if _ % 2 == 0:
        if _ % 3 == 0 or _ % 5 == 0:
            ans *= 1
        else:
            ans *= 0

if ans == 1:
    print('APPROVED')
else:
    print('DENIED')