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

n,m = map(int,input().split())
count_ac = 0
count_wa = 0
l = [('','')]*m
memo_n = []
import collections
idx = 0
for i in range(m):
    t = tuple(input().split())
    l[i] = t
    if t[1] == 'AC' and t[0] not in memo_n:
        memo_n.append(t[0])
        count_ac += 1
        c = collections.Counter(l[idx:i])
        # count_wa += l.count((t[0],'WA'))
        count_wa += c[(t[0],'WA')]

print(str(count_ac) + " " + str(count_wa))

### FIXED CODE ###

n,m = map(int,input().split())
ac = [0]*n
wa = [0]*n
for i in range(m):
    p,s = input().split()
    p = int(p)
    if ac[p-1]:
        continue
    if s == 'AC':
        ac[p-1] = 1
    else:
        wa[p-1] += 1
count_ac = 0
count_wa = 0
for i in range(n):
    count_ac += ac[i]
    if ac[i]:
        count_wa += wa[i]
print(str(count_ac) + " " + str(count_wa))
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from math import floor
def main():
    a, b, n = map(int, input().split())
    r = 0
    for i1 in range(1, n + 1):
        t = floor(a * i1 / b) - a * floor(i1 / b)
        r = max(r, t)
    print(r)
if __name__ == '__main__':
    main()

### FIXED CODE ###

from math import floor
def main():
    a, b, n= map(int, input().split())
    x = min(n, b - 1)
    r = floor((a * x) / b) - a * floor(x / b)
    print(r)

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

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

n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))

memo = {}


def step(now):
    if (memo.get(now) != None):
        return memo.get(now)
    if (now in a):
        return 0
    # print(now)
    if (now == 0):
        return 1
    if (now < 0):
        return 0
    # print(now)
    memo.update({now: step(now-1)+step(now-2)})
    return memo.get(now)


print(step(n) % 1000000007)

### FIXED CODE ###

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

n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))
a=set(a)

memo = [0]*(n+1)
memo[0]=1
if not(1 in a):
    memo[1]=1

for i in range(2,n+1):
    #print(i)
    if i in a:
        continue
    #print(memo[i-1],memo[i-2])
    memo[i]=memo[i-2]+memo[i-1]
            

#print(memo)
print(memo[n]% 1000000007)
### BUGGY CODE ###

if __name__ == '__main__':
    n, k = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [float('inf') for _ in range(10**5 + 1000)]

    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            if i + j < len(h):
                dp[i + j] = min(dp[i] + abs(h[i] - h[i + j]), dp[i + j])

    print(dp[n - 1])


### FIXED CODE ###

if __name__ == '__main__':
    n, k = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [float('inf') for _ in range(10**5 + 1000)]

    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            if i + j < len(h):
                dp[i + j] = min(dp[i] + abs(h[i] - h[i + j]), dp[i + j])

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

import sys
from operator import itemgetter
input = sys.stdin.readline

_s = input()


def chker(s):
    slist = []
    i = 1
    while len(s) >= i:
        if s[i - 1:i + 1] == '><':
            slist.append(s[:i])
            s = s[i:]
            i = 1
        else:
            i += 1

    slist.append(s)

    minisum = 0
    for item in slist:
        l, r = item.count('<'), item.count('>')
        l, r = (l, r) if l > r else (r, l)
        minisum += l * (l + 1) / 2 + r * (r - 1) / 2

    print(int(minisum))


chker(_s)


### FIXED CODE ###

import sys
from operator import itemgetter
input = sys.stdin.readline

_s = input()


def chker(s):
    l, r, minisum = 0, 0, 0
    if s[0] == '<':
        l += 1
    elif s[0] == '>':
        r += 1
    for i in range(1, len(s)):
        if s[i - 1] == '>' and s[i] == '<':
            l, r = (l, r) if l > r else (r, l)
            minisum += l * (l + 1) / 2 + r * (r - 1) / 2
            l, r = 1, 0
        else:
            if s[i] == '<':
                l += 1
            elif s[i] == '>':
                r += 1

    l, r = (l, r) if l > r else (r, l)
    minisum += l * (l + 1) / 2 + r * (r - 1) / 2

    print(int(minisum))


chker(_s)
### BUGGY CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[u].append(v)
s,t = inm()
s -= 1
t -= 1

reach2 = [ [] for i in range(n) ]
m2done = [ False for i in range(n) ]
reach3 = [ [] for i in range(n) ]
m3done = [ False for i in range(n) ]

def mark(f):
    x = []
    if not m2done[f]:
        y = []
        for v1 in dst[f]:
            for v2 in dst[v1]:
                y.append(v2)
        reach2[f] = y
        m2done[f] = True

    for v2 in reach2[f]:
                for v3 in dst[v2]:
                    if v3 == f:
                        continue
                    x.append(v3)
    reach3[f] = list(set(x))
    m3done[f] = True

dist = [-1] * n
dist[s] = 0
q = deque([(s,0)])
nodedone = [False for i in range(n)]
while len(q)>0:
    v,d = q.popleft()
    if not m3done[v]:
        mark(v)
    for nxt in reach3[v]:
        if dist[nxt] > -1 or nodedone[nxt]:
            continue
        nodedone[nxt] = True
        if nxt==t:
            print(d+1)
            exit()
        dist[nxt] = d+1
        q.append((nxt,d+1))
print(-1)


### FIXED CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n*3) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[u].append(v+n)
    dst[u+n].append(v+n*2)
    dst[u+n*2].append(v)
s,t = inm()
s -= 1
t -= 1
ddprint(dst)

dist = [-1] * (n*3)
dist[s] = 0
q = deque([s])
while len(q)>0:
    v = q.popleft()
    #ddprint('v='+str(v))
    for nxt in dst[v]:
        #ddprint('nxt='+str(nxt))
        if nxt==t:
            print((dist[v]+1)//3)
            exit()
        if dist[nxt] > -1:
            continue
        dist[nxt] = dist[v]+1
        q.append(nxt)
    #ddprint(dist)
    #ddprint(q)
print(-1)
### BUGGY CODE ###

def chmin(a, b):
  if (a > b):
    return b

  return a

def chmax(a, b):
  if (a < b):
    a = b
    return True

  return False

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

dp = [10**9] * N

for n in range(N):
  if n == 0:
    dp[n] = 0
    continue
  if n == 1:
    dp[n] = abs(li[n] - li[n-1])
    continue

  for k in range(1, K+1):
    if k > n:
      break

    dp[n] = chmin(dp[n], dp[n-k] + abs(li[n] - li[n-k]))

print(dp[-1])

### FIXED CODE ###

def chmin(a, b):
  if (a > b):
    return b

  return a

def chmax(a, b):
  if (a < b):
    a = b
    return True

  return False

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

dp = [10**9] * N

for n in range(N):
  if n == 0:
    dp[n] = 0
    continue
  if n == 1:
    dp[n] = abs(li[n] - li[n-1])
    continue

  for k in range(1, K+1):
    if k > n:
      break

    dp[n] = chmin(dp[n], dp[n-k] + abs(li[n] - li[n-k]))

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

import heapq
import sys
input = sys.stdin.buffer.readline

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    F = list(map(int,input().split()))
    if sum(A) <= K:
        print(0)

    else:
        A.sort()
        F.sort(reverse=True)
    
        score = []
        for i in range(N):
            score.append((-A[i]*F[i],F[i]))
        heapq.heapify(score)
        for i in range(K):
            cost,diff = heapq.heappop(score)
            cost += diff
            heapq.heappush(score,(cost,diff))
        
        mscore,diff = heapq.heappop(score)
        print(-mscore)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    f = list(map(int,input().split()))
    a.sort()
    f.sort(reverse=True)

    if sum(a) <= K:
        print(0)
    else:
        a = np.array(a)
        f = np.array(f)
        left,right = 0,max(a)*max(f)
        while right-left > 1:
            mid = (left+right)//2
            pra = a-mid//f
            pra[pra<0] = 0
            if np.sum(pra) > K:
                left = mid
            else:
                right = mid
        print(right)

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

from sys import stdin
nii=lambda:map(int,stdin.readline().split())

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

l=[]
for i in range(m):
  b,c=nii()
  l+=[c]*b
l=sorted(l,reverse=True)
l_len=len(l)
if l_len<n:
 l+=[0]*(n-l_len)

ans=0
for i in range(n):
  ans+=max(a[i],l[i])
print(ans)

### FIXED CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())

n,m=map(int,input().split())
a=sorted(list(nii()))
l=[list(nii()) for i in range(m)]
l=sorted(l,key=lambda x:x[1],reverse=True)

man=[]
num=0
for b,c in l:
  man+=[c]*b
  num+=b
  if num>n:
    break

ans=0
for i in range(n):
  if i<num:
    ans+=max(a[i],man[i])
  else:
    ans+=a[i]
print(ans)
### BUGGY CODE ###

import os
import string
import sys
from collections import Counter
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)

lefts = [{c: 0 for c in string.ascii_lowercase} for _ in range(N)]
rights = [{c: 0 for c in string.ascii_lowercase} for _ in range(N)]
for i in range(1, N):
    for c in string.ascii_lowercase:
        lefts[i][c] = lefts[i - 1][c]
    lefts[i][S[i - 1]] += 1
for i in reversed(range(N - 1)):
    for c in string.ascii_lowercase:
        rights[i][c] = rights[i + 1][c]
    rights[i][S[i + 1]] += 1
total = Counter(S)


def dump(counter):
    for c in sorted(counter.keys()):
        if counter[c] > 0:
            print(c, counter[c])
    print()


@lru_cache(maxsize=None)
def count_palindrome(l, r):
    if r <= l:
        assert False
    if l + 1 == r:
        return 1
    counts = total.copy()
    for c in string.ascii_lowercase:
        counts[c] -= lefts[l][c]
        counts[c] -= rights[r - 1][c]
    odds = 0
    for c in counts.values():
        odds += c % 2
    if odds <= 1:
        return 1

    ret = INF
    for i in range(l + 1, r):
        # i で split するときの両側の数
        cnt = count_palindrome(l, i) + count_palindrome(i, r)
        ret = min(cnt, ret)
    return ret


ans = count_palindrome(0, N)
print(ans)


### FIXED CODE ###

import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


# 解説
S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)

cs = [0] * N
h = 0
for i, c in enumerate(S):
    h ^= 1 << (ord(c) - ord('a'))
    cs[i] = h


def dump(h):
    import numpy as np
    print(np.binary_repr(h, 26))


def dumpdp(dp):
    for k in dp.keys():
        if dp[k] < INF:
            dump(k)
            print(dp[k])
    print()


# dp[h]: それまでのハッシュが h である位置以前の分割方法の最小値
dp = defaultdict(lambda: INF)
dp[0] = 0
dp[cs[0]] = 1
for i in range(1, N):
    # print(S[i - 1])
    # dumpdp(dp)

    h = cs[i]
    if h == 0:
        continue
    d = 1
    while d < (1 << 26):
        # i から h^d の位置までまとめて 1 つ切り出せる
        dp[h] = min(dp[h], dp[h ^ d] + 1)
        d <<= 1

if cs[-1] == 0:
    print(1)
else:
    print(dp[cs[-1]])
### BUGGY CODE ###

# -*- conding:utf-8 -*-


from collections import deque

q_list = deque()
n = int(input())
for i in range(n):
    tmp = input().split()
    if tmp[0] == "find":
        if tmp[1] in q_list:
            print("yes")
        else:
            print ("no")
    else:
        q_list.append(tmp[1])

### FIXED CODE ###

# -*- conding:utf-8 -*-


se = set()
n = int(input())
tmp = [input().split() for i in range(n)]


for i in tmp:
    cmd, v = i
    if cmd == "find":
        if v in se:
            print("yes")
        else:
            print ("no")
    else:
        se.add(v)
### BUGGY CODE ###

n = int(input())
li = []
lis = []
for i in range(n):
	a = int(input())
	lis.append(a)
	li.append(a)
co = 0
cou = 0
for i in range(n-1):
	if lis.index(n-(i+1)) > lis.index(n-i):
		lis.remove(n-(i+1))
		lis.insert(0,n-(i+1))
		co += 1

for k in range(n-1):
	if li.index(k+2) < li.index(k+1):
		li.remove(k+2)
		li.append(k+2)
		cou += 1
print(min(co,cou))

### FIXED CODE ###

n = int(input())
lis = [int(input()) for i in range(n)]
li = [-1 for i in range(n)]
for i in range(n):
    li[lis[i]-1] = i
cnt = 0
ans = n-1
for i in range(n-1):
    if li[i] < li[i+1]:
        cnt += 1
    else:
        ans = min(ans,n-1-cnt)
        cnt = 0
ans = min(ans,n-1-cnt)
print(ans)
### BUGGY CODE ###

import numpy as np
_, m = list(map(int, input().split()))
a = np.array(list(map(int, input().split())))

for i in range(m):
    a[np.argmax(a)] /=2

print(int(np.floor(a).sum()))

### FIXED CODE ###

import heapq
h = []
N, M = map(int, input().split())
As = list(map(int, input().split()))
for i in As:
    heapq.heappush(h, -i)
for _ in range(M):
    i = heapq.heappop(h)
    i = -1 * (-i // 2)
    heapq.heappush(h, i)
 
print(sum([-1 * heapq.heappop(h) for i in range(len(h))]))
### BUGGY CODE ###

first_input = input().split(' ')

s_length = int(first_input[0])
num_of_Q = int(first_input[1])

input_string = input()

for q in range(num_of_Q):
    l_r = input().split(' ')
    l = int(l_r[0])
    r = int(l_r[1])

    sub_str = input_string[l-1:r]
    num_of_ac = sub_str.count('AC')

    print(num_of_ac)

### FIXED CODE ###

first_input = input().split(' ')

s_length = int(first_input[0])
num_of_Q = int(first_input[1])

input_string = input()

seq = [0]*s_length
count = 0

for s in range(s_length):
    if s > 0 and input_string[s-1:s+1] == 'AC':
        count += 1
    seq[s] = count

for q in range(num_of_Q):
    l_r = input().split(' ')
    l = int(l_r[0])
    r = int(l_r[1])

    print(seq[r-1] - seq[l-1])
### BUGGY CODE ###

n = int(input())
s = input()
_ = input()
l = list(map(int, input().split()))
for k in l:
  d,m,dm,dmc = 0,0,0,0
  for i in range(n):
    if i > k-1:
      j = i-k
      if s[j] == 'D':
        d -= 1
        dm -= m
      elif s[j] == 'M':
        m -= 1
    if s[i] == 'D':
      d += 1
    elif s[i] == 'M':
      m += 1
      dm += d
    elif s[i] == 'C':
      dmc += dm
  print(dmc)

### FIXED CODE ###

def num(s,n,k):
  d,m,dm,dmc = 0,0,0,0
  for i in range(n,n*2):
    x,y = s[i],s[i-k]
    if y == 68:
      d -= 1
      dm -= m
    elif y == 77:
      m -= 1
    if x == 68:
      d += 1
    elif x == 77:
      m += 1
      dm += d
    elif x == 67:
      dmc += dm
  return dmc

def main():
  n = int(input())
  s = [0]*n + list(map(ord, list(input())))
  _ = input()
  l = list(map(int, input().split()))
  for k in l:
    print(num(s,n,k))

main()
### BUGGY CODE ###

#!/home/matsumotokazuho/.pyenv/shims/pypy
# import math
# from copy import deepcopy
# from operator import itemgetter
# from collections import defaultdict
# from collections import Counter
# from collections import deque
# import pprint
import itertools
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H, W = map(int, input().split())
Board = [list(input().rstrip()) for _ in range(H)]

# q = deque()
q = []
# for i, j in itertools.product(range(H), range(W)):
for i in range(H):
    for j in range(W):
        if Board[i][j] == '#':
            # Board[i][j] = 0
            q.append((i, j))

ans = 0
# while q:
for i in itertools.count():
    qq = []
    ans += 1
    for yx in q:
        for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            y = yx[0] + d[0]
            x = yx[1] + d[1]
            # y, x = [i+j for i, j in zip(yx, d)]
            if y < 0 or H - 1 < y or x < 0 or W - 1 < x:
                pass
            elif Board[y][x] == '.':
                # Board[y][x] = Board[q[0][0]][q[0][1]] + 1
                Board[y][x] = '#'
                qq.append((y, x))
    q = qq
    if not q:
        break

# ans = max(list(itertools.chain.from_iterable(Board)))
# ans = max(itertools.chain.from_iterable(Board))
# pprint.pprint(Board)
print(ans-1)


### FIXED CODE ###

#!/home/matsumotokazuho/.pyenv/shims/pypy
# import math
# from copy import deepcopy
# from operator import itemgetter
# from collections import defaultdict
# from collections import Counter
# from collections import deque
# import pprint
# import itertools
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H, W = map(int, input().split())
Board = [list(input().rstrip()) for _ in range(H)]

# q = deque()
q = []
# for i, j in itertools.product(range(H), range(W)):
for i in range(H):
    for j in range(W):
        if Board[i][j] == '#':
            # Board[i][j] = 0
            q.append((i, j))

ans = 0
while q:
    qq = []
    ans += 1
    for yx in q:
        for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            y = yx[0] + d[0]
            x = yx[1] + d[1]
            # y, x = [i+j for i, j in zip(yx, d)]
            if y < 0 or H - 1 < y or x < 0 or W - 1 < x:
                pass
            elif Board[y][x] == '.':
                # Board[y][x] = Board[q[0][0]][q[0][1]] + 1
                Board[y][x] = '#'
                qq.append((y, x))
    q = qq

# ans = max(list(itertools.chain.from_iterable(Board)))
# ans = max(itertools.chain.from_iterable(Board))
# pprint.pprint(Board)
print(ans-1)
### BUGGY CODE ###


def main():
    n,m = map(int,input().split())
    MOD = 10**9 + 7

    fact = [1]
    for i in range(m):
        fact.append(fact[-1]*(i+1)%MOD)

    ｍPn = fact[m] * pow(fact[m-n],MOD-2,MOD) % MOD

    a = pow(mPn,2,MOD)
    b = 0
    for i in range(1,n+1):
        nCr = fact[n] * pow(fact[i],MOD-2,MOD) % MOD * pow(fact[n-i],MOD-2,MOD) % MOD
        b += (-1)**(i) * nCr * fact[m-i] % MOD * pow(fact[m-n],MOD-2,MOD) % MOD
        b %= MOD
    ans = a + b * mPn
    print(ans%MOD)


main()




### FIXED CODE ###


def main():
    n,m = map(int,input().split())
    MOD = 10**9 + 7

    fact = [1]
    fact_inv = [1]
    for i in range(m):
        fact.append(fact[-1]*(i+1)%MOD)
    fact_inv = [1] * (m+1)
    fact_inv[m] = pow(fact[m],MOD-2,MOD)
    for i in range(m):
        fact_inv[m-i-1] = fact_inv[m-i] * (m-i) % MOD
    # print(fact_inv)


    ｍPn = fact[m] * pow(fact[m-n],MOD-2,MOD) % MOD

    a = pow(mPn,2,MOD)
    b = 0
    for i in range(1,n+1):
        nCr = fact[n] * fact_inv[i] % MOD * fact_inv[n-i] % MOD
        b += (-1)**(i%2) * nCr * fact[m-i] % MOD * fact_inv[m-n] % MOD
        b %= MOD
    ans = a + b * mPn
    print(ans%MOD)


main()
### BUGGY CODE ###

from operator import itemgetter

def main():
    n = int(input())
    keys = []
    for i in xrange(n):
        keys.append(map(int,raw_input().split())+[i])

    T = Tree()
    T.recursive_add_Node(keys,0)

    q = int(input())
    for i in xrange(q):
        sx, tx, sy, ty = map(int,raw_input().split())
        nums = []
        find(T.root,[sx,sy],[tx,ty],0,nums)
        nums.sort()
        for i in nums:
            print i
        print ""
        

def find(z,s,t,d,nums):
    if(s[0]<=z.key[0]<=t[0])and(s[1]<=z.key[1]<=t[1]):
        nums.append(z.num)

    d += 1
    xy = d%2
    if (z.left != None)and(z.key[xy]>=s[xy]):
        find(z.left,s,t,d,nums)
    if (z.right != None)and(z.key[xy]<=t[xy]):
        find(z.right,s,t,d,nums)


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

    def add_Node(self,k,n):
        y = None
        x = self.root
        d = 0
        xy = 0
        while(x != None):
            d += 1
            xy = d%2
            y = x
            if x.key[xy] > k[xy]:
                x = x.left
            else:
                x = x.right
        
        z = Node(k,n)
        z.parent = y
        z.depth  = d

        if y == None:
            self.root = z
        elif y.key[xy] > k[xy]:
            y.left = z
        else:
            y.right = z
        
    def recursive_add_Node(self,keys,depth):
        keys.sort(key=itemgetter(depth%2))
        id_mean = len(keys)/2
        self.add_Node(keys[id_mean][:2],keys[id_mean][2])
       
        if id_mean != 0:
            self.recursive_add_Node(keys[:id_mean],depth+1)
        if id_mean+1 != len(keys):
            self.recursive_add_Node(keys[id_mean+1:],depth+1)

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


if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin,stdout
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline
 
def main():
    n = int(input())
    keys = map(lambda i: map(int,readline().split())+[i], xrange(n))
    keys.sort()

    root = int(math.sqrt(len(keys)))
 
    low = [x for x, y, i in keys[::root]]
    high = [x for x, y, i in keys[root - 1::root]] + [float('inf')]
 
    keys = [sorted(keys[i:i+root], key=itemgetter(1)) for i in range(0,len(keys),root)]
    keys_y = map(lambda k:[y for x,y,i in k], keys)

    q = int(input())
    for i in xrange(q):
        sx,tx,sy,ty = map(int,readline().split())
        
        nums = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            y = keys_y[i]
            for j in range(bisect_left(y, sy), bisect_right(y, ty)):
                if sx <= keys[i][j][0] <= tx:
                    nums.append(keys[i][j][2])
        if nums:
            nums.sort()
            map(lambda n:stdout.write("{}\n".format(n)), nums)
        print("")

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

n = int(input())
ls = list(map(int, input().split(' ')))
ans = 1
if ls[0] != 0:
    ans = 0
m = max(set(ls))
d = {i: ls.count(i) for i in range(m+1)}
for i in range(1, m+1):
    ans = (ans * (d[i-1] ** d[i]) % 998244353) % 998244353
print(ans)


### FIXED CODE ###

n = int(input())
ls = list(map(int, input().split(' ')))
m = max(set(ls))
d = {}
for l in ls:
    d[l] = d.get(l, 0) + 1
ans = 0 if (ls[0] != 0 or d.get(0) >= 2) else 1
for i in range(1, m+1):
    if i not in d:
        ans = 0
    ans = (ans * (d.get(i-1, 0) ** d.get(i, 0))) % 998244353 
print(ans)
### BUGGY CODE ###

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

ans = set()

for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            iss = s[i : i + 1]
            js = s[j : j + 1]
            ks = s[k : k + 1]
            ans.add(iss + js + ks)

print(len(ans))

### FIXED CODE ###

N = int(input())
S = input()

ans = 0

for i in range(10):
    a = S.find(str(i))
    if -1 == a:
        continue
    for j in range(10):
        b = S.find(str(j), a + 1)
        if -1 == b:
            continue
        for k in range(10):
            c = S.find(str(k), b + 1)
            if -1 == c:
                continue
            ans += 1
            # print(''.join(map(str, [i, j, k])))

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

s = list(input())
ans=0
cach=-1
while True:
    if s==[]:
        break
    else:
        tmp=s.pop(0)

    if tmp != cach:
        ans +=1
        cach=tmp
    else:
        if s!=[]:
            tmp+=s.pop(0)
            ans +=1
            cach=tmp

print(ans)


### FIXED CODE ###

from collections import deque
s = deque(list(input()))   # deque オブジェクトを取得

ans=0
cach=-1
while True:
    if s==deque([]):
        break
    else:
        tmp=s.popleft()

    if tmp != cach:
        ans +=1
        cach=tmp
    else:
        if s!=deque([]):
            tmp+=s.popleft()
            ans +=1
            cach=tmp

print(ans)