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

import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


def my_popcount(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c


def f(x, cur):
    #print(x, cur)
    if x == 0:
        return cur
    return f(x%my_popcount(x), cur+1)

N = int(input())
X = input()

Xint = int(X, 2)
popcountX = X.count("1")
#print("test", Xint, popcountX)
plus = Xint%(popcountX+1)
minus = 0
if popcountX != 1:
    minus = Xint%(popcountX-1)

for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((plus + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((minus - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
X = input()
Xint = int(X, 2)
Xcount = X.count("1")

"""
0010
1010 10(mod2) -> 0
i = n-1の時だけ +1
0011 -> 3 -> 1->0
0110 -> 6(mod2) -> 0
"""

if Xcount == 1:
    for i in range(N):
        if X[i] == "1":
            print(0)
        elif i == N-1:
            print(2)
        else:
            print(1)
    exit()

Modplus, Modminus = Xint%(Xcount+1), Xint%(Xcount-1)

def f(x):
    if x == 0:
        return 0
    return f(x%bin(x).count("1"))+1

for i in range(N):
    if X[i] == "1":
        print(1+f((Modminus-pow(2, N-1-i, Xcount-1))%(Xcount-1)))
    else:
        print(1+f((Modplus+pow(2, N-1-i, Xcount+1))%(Xcount+1)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def toggle(i):
  if (i == '1'):
    return '0'
  else:
    return '1'


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 1)
for i in range(1, 2 * 10 ** 5 + 1):
  ans[i] = solve(i, 0)
for i in range(n):  
  if(x[i] == '0'):
    print(solve2(X + 2 ** (n-i-1), u))
  else:
    print(solve2(X - 2 ** (n-i-1), d))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (n == 1 and x == '1'):
  print(0)
  exit()

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 4)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
if(d != 0):
  _d = (2 * 10 ** 5) // d
  D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
Us[0] = 1 % u
if(d != 0):
  Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i - 1] * 2) % u
  if(d != 0):
    Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(x[i] == '0'):
    print(solve2(U + Us[n-i-1], u))
  else:
    if (d == 0):
      print(0)
    else:
      print(solve2(D - Ds[n-i-1], d))
### BUGGY CODE ###

N = int(input())
words = {}
for i in range(N):
  name = input()
  if name not in words:
    words[name] = 1
  elif name in words:
    words[name] += 1
    
res_name = []
for i in words.keys():
  if words[i] == max(words.values()):
    res_name.append(i)
res_name = sorted(res_name)
for i in res_name:
  print(i)

### FIXED CODE ###

N = int(input())
words = {}
for i in range(N):
  name = input()
  if name not in words:
    words[name] = 1
  elif name in words:
    words[name] += 1
    
res_name = []
Max = max(words.values())
for i in words.keys():
  if words[i] == Max:
    res_name.append(i)
res_name = sorted(res_name)
for i in res_name:
  print(i)
### BUGGY CODE ###

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

A.append(0)

B = []
f = True
for i in range(N):
    if f:
        if A[i] < A[i+1]:
            B.append(A[i])
            f = False
    else:
        if A[i] > A[i+1]:
            B.append(A[i])
            f = True


if len(B) == 0:
    print(1000)
else:
    res = 1000
    xx = len(B)//2+1
    B = [0]+B+[10**10]
    for i in range(2**xx):
        en = 1000
        ka = 0
        for j in range(xx):
            if (i>>j)&1:
                en += ka*B[j*2]
                ka = 0
                ka = en//B[j*2+1]
                en = en%B[j*2+1]
        else:
            res = max(en, res)

    print(res)

### FIXED CODE ###

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

kabu = 0
en = 1000

for i in range(N):
    a, b = divmod(en, A[i])
    kabu += a
    en = b
    if A[i+1] < A[i]:
        en += kabu*A[i]
        kabu = 0

print(en)
### BUGGY CODE ###

n=int(input())
S=input()
dictR=[]
dictG=[]
dictB=[]
r=0
g=0
b=0
r=S.count("R")
g=S.count("G")
b=S.count("B")
sum=r*g*b
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            si=S[i]
            sj=S[j]
            sk=S[k]
            if k-j!=j-i or (si==sj or sj==sk or si==sk):
                sum+=1



print(sum-(n*(n-1)*(n-2)//6))

### FIXED CODE ###

n=int(input())
S=input()
R={}
G={}
B={}
r=0
g=0
b=0
for i in range(n):
    if S[i] == 'R':
        R[i] = None
    elif S[i] == 'G':
        G[i] = None
    else:
        B[i] = None
cnt=len(R)*len(G)*len(B)
for b in B:
    for g in G:
        if (b+g)/2 in R:
            cnt-=1
for b in B:
    for r in R:
        if (b+r)/2 in G:
            cnt-=1
for r in R:
    for g in G:
        if (r+g)/2 in B:
            cnt-=1
print(cnt)
### BUGGY CODE ###

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

def restword(a,b):
    w=[a,b]
    if('R' not in w):
        return 'R'
    elif('G' not in w):
        return 'G'
    else:
        return 'B'

ans=0
for i in range(n):
    for j in range(i+1,n):
        if(s[i]!=s[j]):
            sk=s[j+1:]
            rest_k=restword(s[i], s[j])
            ans_k=sk.count(rest_k)
            if(j+j-i < n and s[j+j-i]==rest_k):
                ans_k-=1
            ans+=ans_k
        else:
            continue

print(ans)

### FIXED CODE ###

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

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

ans=r*g*b
for i in range(n):
    for j in range(i+1,n):
        k=j+(j-i)
        if(k<n and s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]):
#            print(i,j,k)
            ans-=1
print(ans)
### BUGGY CODE ###

def gcd2(a, b):
    if b == 0:
        return a
    
    return gcd2(b, a % b)

def gcd3(a, b, c):
    return gcd2(gcd2(a, b), c)

if __name__ == "__main__":
    k = int(input())
    
    ans = 0

    for a in range(1, k + 1):
        for b in range(1, k + 1):
            for c in range(1, k + 1):
                ans += gcd3(a, b, c)
    
    print(ans)

### FIXED CODE ###

def gcd2(a, b):
    if b == 0:
        return a
    
    return gcd2(b, a % b)

def gcd3(a, b, c):
    return gcd2(gcd2(a, b), c)

if __name__ == "__main__":
    k = int(input())
    
    ans = 0

    for a in range(1, k + 1):
        for b in range(1, a + 1):
            for c in range(1, b + 1):
                if a == b and b == c and c == a:
                    ans += gcd3(a, b, c)
                elif a == b or b == c or c == a:
                    ans += gcd3(a, b, c) * 3
                else:
                    ans += gcd3(a, b, c) * 6
    
    print(ans)
### BUGGY CODE ###

import numpy as np
N,K,Q=map(int,input().split())
l=np.ones(N)*K
for i in range(Q):
    a=int(input())-1
    one=np.ones(N)
    one[a]=0
    l=l-one
for i in range(N):
    if l[i]>0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

N = 5
ARR = [6, 9, 4, 2, 11]
#
# N = 2
# ARR = [100, 0]

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


def calculate(n, arr):
    s1 = max(arr)

    if n % 2 == 0:
        mid1, mid2 = s1 // 2, s1 // 2
    else:
        mid1, mid2 = s1 // 2, s1 // 2 + 1

    offset = 0
    find = False
    while find == False:
        find = (mid1 - offset) in arr
        if find == True:
            return s1, mid1 - offset
        find = (mid2 + offset) in arr
        if find == True:
            return s1, mid2 - offset
        offset = offset + 1


n, a = calculate(N, ARR)
print(n, a)


### FIXED CODE ###

import bisect

N = 5
ARR = [6, 9, 4, 2, 11]


N = 2
ARR = [100, 0]

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


def calculate(n, arr):
    arr = sorted(arr)

    mid = arr[n - 1] / 2

    a1 = bisect.bisect_left(arr, mid)

    s1 = abs(arr[a1 - 1] - (arr[n - 1] / 2))
    s2 = abs(arr[a1] - (arr[n - 1] / 2))

    if s1 > s2:
        return arr[n - 1],arr[a1]
    else:
        return arr[n-1],arr[a1-1]


n, a = calculate(N, ARR)
print(n, a)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce


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


def solve():
    MOD = 10 ** 9 + 7
    N, *A = map(int, open(0).read().split())
    
    lcm_num = reduce(lcm, A)
    ans = 0
    for a in A:
        ans += lcm_num // a
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

from fractions import gcd


def solve():
    N, *A = map(int, open(0).read().split())
    MOD = 10 ** 9 + 7

    lcm = 1
    for a in A:
        lcm = a * lcm // gcd(a, lcm)

    ans = [lcm // a for a in A]
    print(sum(ans) % MOD)


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

import sys, io, os, re
import bisect
from pprint import pprint
from math import sin, cos, pi, radians, sqrt
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce

def array1(n): return [0] * n
def array2(n, m): return [[0] * m for x in range(n)]
def array3(n, m, l): return [[[0] * l for y in xrange(m)] for x in xrange(n)]

a = sys.stdin.readline().strip()
arr = map(int, sys.stdin.readline().strip().split())
mod = 10**18
x = reduce(lambda x, y: (x*y) if x*y <= mod else -1, arr)

print(x)

### FIXED CODE ###

import sys, io, os, re
import bisect
from pprint import pprint
from math import sin, cos, pi, radians, sqrt
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce

def array1(n): return [0] * n
def array2(n, m): return [[0] * m for x in range(n)]
def array3(n, m, l): return [[[0] * l for y in xrange(m)] for x in xrange(n)]

a = sys.stdin.readline().strip()
arr = list(map(int, sys.stdin.readline().strip().split()))
mod = 10**18

ans = arr[0]
for i in range(1, len(arr)):
    ans *= arr[i]
    if ans > mod:
        ans = -1
        break

if 0 in arr:
    ans = 0

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

L,R = map(int,input().split())
 
ans = 2019
m = []
for i in range(L,R+1):
	m.append(i%2019)

for i in range(len(m)):
	for j in range(i+1,len(m)):
		tmp = (m[i]*m[j])%2019
		if ans> tmp:
			ans = tmp
		if tmp == 0:
			break				
print(ans)

### FIXED CODE ###

L,R = map(int,input().split())
 
ans = 2019
m = []
l = R-L+1
if l < 2019:
	for i in range(L,R+1):
		m.append(i%2019)
else:
	for i in range(L,L+2019):
		m.append(i%2019)

for i in range(len(m)):
	for j in range(i+1,len(m)):
		tmp = (m[i]*m[j])%2019
		if ans> tmp:
			ans = tmp
		if tmp == 0:
			break				
print(ans)
### BUGGY CODE ###

import sys

class binarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right

        if y is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def printBT(self):
        print inorderTreeWalk(self.root)
        print preorderTreeWalk(self.root)

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def inorderTreeWalk(node):
    if node:
        return inorderTreeWalk(node.left) + " " + str(node.key) + inorderTreeWalk(node.right)
    return ""

def preorderTreeWalk(node):
    if node:
        return " " + str(node.key) + preorderTreeWalk(node.left) + preorderTreeWalk(node.right)
    return ""

if __name__ == "__main__":
    lines = sys.stdin.readlines()

    bt = binarySearchTree()
    for i in range(1, int(lines[0]) + 1):
        if lines[i][0] == "i":
            bt.insert(int(lines[i].split()[1]))
        else:
            bt.printBT()

### FIXED CODE ###

import sys

class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None

def insert(z):
    global root
    y = None
    x = root
    while x is not None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def inorderTreeWalk(node):
    global In
    if node:
        inorderTreeWalk(node.left)
        In.append(str(node.key))
        inorderTreeWalk(node.right)

def preorderTreeWalk(node):
    global Pre
    if node:
        Pre.append(str(node.key))
        preorderTreeWalk(node.left)
        preorderTreeWalk(node.right)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]

    root = None
    for line in lines:
        if line[0] == "i":
            insert(Node(int(line.split()[1])))
        else:
            In = []
            Pre = []
            inorderTreeWalk(root)
            print " " + " ".join(map(str, In))
            preorderTreeWalk(root)
            print " " + " ".join(map(str, Pre))
### BUGGY CODE ###

N = int(input().split()[0])
aa = input().split()
bb = []

for i in range(1, N+1):
    num = aa.index(str(i))
    bb.append(num + 1)

print(*bb)


### FIXED CODE ###

N = int(input().split()[0])
aa = input().split()
bb = [0]*N

for i in range(0, N):
    bb[int(aa[i]) - 1] = i + 1

print(*bb)
### BUGGY CODE ###

def main():
        N,Q = map(int,input().split())
        ab = [list(map(int,input().split())) for _ in range(N - 1)]
        px = [list(map(int,input().split())) for _ in range(Q)]
        ab.sort()
        px.sort()
        plus = [0 for _ in range(N)]

        for p,x in px:
                plus[p - 1] += x 

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        for p in plus:
                print(p)

if __name__ == '__main__':
        main()

### FIXED CODE ###

def main():
        N,Q = map(int,input().split())
        ab = [list(map(int,input().split())) for _ in range(N - 1)]
        px = [list(map(int,input().split())) for _ in range(Q)]
        ab.sort()
        # px.sort()
        plus = [0 for _ in range(N)]

        for p,x in px:
                plus[p - 1] += x 

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        for p in plus:
                print(p)

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

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [0]*(N+1)
dp[0] = 1
for i in range(1,N+1):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
print(dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
A = set([int(input()) for _ in range(M)])
dp = [0]*(N+1)
dp[0] = 1
for i in range(1,N+1):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
print(dp[N])
### BUGGY CODE ###

N,K,Q=map(int,input().split())
A = []
def minus(n):
    return n-1
for _ in range(Q):
    A.append(int(input()))#縦入力
Nlist = []
for i in range(N):
    Nlist.append(K)
for j in range(0,Q):
    Nlist = list(map(minus,Nlist))
    Nlist[A[j]-1] += 1
for k in range(0,N):
    if Nlist[k]>=1:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K,Q=map(int,input().split())
A = []
for _ in range(Q):
    A.append(int(input()))#縦入力
Nlist = []
for i in range(N):
    Nlist.append(K-Q)
for j in range(0,Q):
    Nlist[A[j]-1] += 1
for k in range(0,N):
    if Nlist[k]>=1:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
l = []
for i in range(n):
    if i < n-1:
        if s[i] == "A" and s[i+1] == "C":
            l.append("a")
        else:
            l.append(s[i])
    else:
        l.append(s[i])
ans = 0
for i in range(q):
    print(l[lr[i][0]-1:lr[i][1]-1].count("a"))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
t = [0] * (n+1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2] == "AC" else 0)
for i in range(q):
    print(t[lr[i][1]-1] - t[lr[i][0]-1])
### BUGGY CODE ###

tmp = input().split()
N = int(tmp[0])

ListG = []

for i in range(N):
    Si = input().split()
    p = Si in ListG
    if not p :
        ListG.append(Si)
    
print(len(ListG))

### FIXED CODE ###

tmp = input().split()
N = int(tmp[0])

ListG = []

for i in range(N):
    ListG.append(input().split())

ListG.sort()
p = 1
for i in range(N-1):
    if ListG[i] == ListG[i+1]:
        continue
    else:
        p = p +1

print(p)
### BUGGY CODE ###

n,a,b = list(map(int,input().split()))
mod = 10**9 + 7
ans = (pow(2,n) - 1)% mod
numerator = 1
denominator = 1

for i in range(1,n+1):
    numerator = (numerator*(n-i+1))%mod
    denominator = (denominator*i)%mod
    if i == a or i == b:
        ans -= (numerator*pow(denominator,mod-2,mod))%mod
        if i == b:
            break

print(ans%mod)

### FIXED CODE ###

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

ans = (pow(2,n,mod) - 1) %mod
numerator = 1%mod
denominator = 1%mod
for i in range(1,b+1):
    numerator = (numerator*(n+1-i))%mod
    denominator = (denominator*pow(i,mod-2,mod))%mod
    if i == a or i == b:
        ans = (ans - (numerator*denominator))%mod

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

a,b,c,d = map(int,input().split())

ans = 0

if c % d == 0:
    for i in range(a, b+1):
        if i % c !=0:
            ans += 1
elif d % c == 0:
    for i in range(a, b+1):
        if i % d !=0:
            ans += 1
else:
    for i in range(a, b+1):
        if (i % d !=0) and (i % c !=0):
            ans += 1

print(ans)

### FIXED CODE ###

import fractions

a,b,c,d = map(int,input().split())

ans = 0

if c % d == 0:
    print((b - a + 1) - ((b)//d - (a-1)//d))
elif d % c == 0:
    print((b - a + 1) - ((b)//c - (a-1)//c))
else:
    tot = c * d // fractions.gcd(c, d)
    tmp = ((b) // d - (a-1) // d) + ((b)//c - (a-1)//c) - ((b) // tot - (a-1) // tot)
    print(int((b - a + 1) - tmp))
### BUGGY CODE ###

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

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

ans = 0
for i in range(60):
    B = [(A[j]>>i)&1 for j in range(N)]
    c = B.count(0)
    ans += c*(N-c)*(2**i%MOD)%MOD

print(ans%MOD)

### FIXED CODE ###

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

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
B = [0]*60
C = [0]*60

for i in range(60):
    for j in range(N):
        if (A[j]>>i)&1 == 0:
            C[i] += 1
        else:
            B[i] += 1

ans = 0
for i in range(60):
    ans += B[i]*C[i]*2**i%MOD
print(ans%MOD)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = []
for i in range(Q):
    A.append(int(input()))
for i in range(N):
    ans = K - Q + A.count(i+1)
    # print(ans)
    if ans > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

N, K, Q = map(int, input().split())
P = [0] * N

for i in range(Q):
    P[int(input())-1] += 1
for i in range(N):
    ans = K - Q + P[i]
    # print(ans)
    if ans > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

idx = 0
for _ in range(m):
    b,c = map(int, input().split())
    a += [c]*b
    idx += b
a.sort()
print(sum(a[idx:]))

### FIXED CODE ###

from heapq import heappop, heappush


n,m = map(int,input().split())
A = list(map(int,input().split()))
pq = []
ans = 0

for a in A:
    heappush(pq, [-a, 1])
    
for _ in range(m):
    b,c = map(int,input().split())
    heappush(pq, [-c, b])

for i in range(n):
    c,b = heappop(pq)
    c = -c
    ans += c
    if b > 1:
        b -= 1
        heappush(pq, [-c, b])
        
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
H=[int(x) for x in input().split()]
INF=10**10

dp=[INF for x in range(N)]
dp[0]=0

for i in range(N):
    for j in range(1,K+1):
        if i+j < N:
            dp[i+j]=min(dp[i+j],dp[i]+abs(H[i]-H[i+j]))
        else:
            break

print(dp[N-1])

### FIXED CODE ###

N,K=map(int,input().split())
H=[int(x) for x in input().split()]
INF=10**10

dp=[INF for x in range(N)]
dp[0]=0

for i in range(N):
    for j in range(1,K+1):
        if i+j < N:
            dp[i+j]=min(dp[i+j],dp[i]+abs(H[i]-H[i+j]))
        else:
            break

print(dp[N-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
c = 0

for i in range(0,n):
  if a[i] == min(a[0:i+1]):
   c+=1
print(c)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
c = 0

x=a[0]

for i in range(0,n):
  if x >= a[i]:
#    print(a[i])
    x=a[i]
    c+=1
print(c)
### BUGGY CODE ###

h,w=map(int,input().split())
S=[["#"]+list(input())+["#"] for _ in range(h)]
S.insert(0,["#"]*(w+2))
S.append(["#"]*(w+2))

C=[[[0]*4 for _ in range(w+2)] for _ in range(h+2)]
for i in range(1,h+1):
    for n, flag in enumerate((1, -1)):
        for j in range(1,w+1)[::flag]:
            if S[i][j]!="#":C[i][j][n] +=C[i][j-flag][n]+1
for i in range(1,w+1):
    for n, flag in enumerate((1, -1)):
        for j in range(1,h+1)[::flag]:
            if S[j][i]!="#":C[j][i][n+2] +=C[j-flag][i][n+2]+1

print(max([sum(C[i][j])-3 for i in range(1,h+1) for j in range(1,w+1)]))

### FIXED CODE ###

import numpy as np
h,w=map(int,input().split())
S=np.array([list(input()) for _ in range(h)])
S=np.where(S==".",1,0)

left,right,up,down=[np.zeros((h,w),dtype=np.int64) for _ in range(4)]
for i in range(w):
    left[:,i]=(left[:,i-1]+1)*S[:,i]
    right[:,-i-1]=(right[:,-i]+1)*S[:,-i-1]
for i in range(h):
    up[i]=(up[i-1]+1)*S[i]
    down[-i-1]=(down[-i]+1)*S[-i-1]

print(int(np.max(left+right+up+down)-3))
### BUGGY CODE ###

n,m=map(int,input().split())
lst=[]
for i in range(m):
    lst.append(list(map(int,input().split())))

ipponme=[]

for i in lst:
    if i[0]==1:
        ipponme.append(i[1])

for i in ipponme:
    for j in lst:
        if j[0]==i and j[1]==n:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

### FIXED CODE ###

n,m=map(int,input().split())
lst=[]
for i in range(m):
    lst.append(list(map(int,input().split())))

front=[]
back=[]

for i in lst:
    if i[0]==1:
        front.append(i[1])

for i in lst:
    if i[1]==n:
        back.append(i[0])
front=set(front)
back=set(back)
print("POSSIBLE" if len(front&back)>=1 else "IMPOSSIBLE")