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

from itertools import product


def get_magic_movable_list(movable_list, candidate_list):
    return [(h, w) for h, w in candidate_list if any((t_h, t_w) in movable_list for t_h, t_w in product([h-2, h-1, h, h+1, h+2], [w-2, w-1, w, w+1, w+2]))]


def get_movable_list(h, w, movable_list, candidate_list):
    movable_list.append((h, w))
    candidate_list.remove((h, w))
    targets = [(h+1, w), (h-1, w), (h, w+1), (h, w-1)]
    for h, w in targets:
        if (h, w) in candidate_list:
            movable_list, candidate_list = get_movable_list(h, w, movable_list, candidate_list)
    return movable_list, candidate_list

H, W = map(int, input().split())
s_h, s_w = [i-1 for i in map(int, input().split())]
d_h, d_w = [i-1 for i in map(int, input().split())]
s = [list(input()) for i in range(H)]

candidate_list = [(h, w) for h in range(H) for w in range(W) if s[h][w] == '.']
movable_list, candidate_list = get_movable_list(s_h, s_w, [], candidate_list)
i = 0

while True:
    if (d_h, d_w) in movable_list:
        break
    magic_movable_list = get_magic_movable_list(movable_list, candidate_list)

    if not magic_movable_list:
        i = -1
        break

    i += 1

    for h, w in magic_movable_list:
        if (h, w) in candidate_list:
  	        movable_list, candidate_list = get_movable_list(h, w, movable_list, candidate_list)

print(i)

### FIXED CODE ###

from collections import deque
 
 
walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
        (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
        (0, -2), (0, -1), (0, 1), (0, 2),
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2),]
 
 
def get_warped(walked, map_):
    warped = deque()
    while walked:
        h, w = walked.popleft()
        for i, j in warp:
            h2 = h + i
            w2 = w + j
            if -1 < h2 < H and -1 < w2 < W and map_[h2][w2] == '.':
                warped.append((h2, w2))
                map_[h2][w2] = map_[h][w] + 1
    return warped, map_
 
 
def get_walked(candidate, map_):
    walked = deque()
    while candidate:
        h, w = candidate.popleft()
        walked.append((h, w))
        for i, j in walk:
            h2 = h + i
            w2 = w + j
            if -1 < h2 < H and -1 < w2 < W and map_[h2][w2] == '.':
                candidate.append((h2, w2))
                map_[h2][w2] = map_[h][w]
    return walked, map_
 
H, W = map(int, input().split())
s_h, s_w = [i-1 for i in map(int, input().split())]
d_h, d_w = [i-1 for i in map(int, input().split())]
map_ = [list(input()) for i in range(H)]
 
candidate = deque([(s_h, s_w)])
map_[s_h][s_w] = 0
 
while candidate:
    walked, map_ = get_walked(candidate, map_)
    candidate, map_ = get_warped(walked, map_)
 
for h in range(H):
    for w in range(W):
        if map_[h][w] == '.':
            map_[h][w] = -1
 
print(map_[d_h][d_w])
### BUGGY CODE ###

s=input()
q=int(input())
cnt1=0
for i in range(q):
    query=list(input().split())
    if int(query[0])==1:
        cnt1+=1
    else:
        if (int(query[1])+cnt1)%2==0:
            s=s+query[2]
        else:
            s=query[2]+s
if cnt1%2==0:
    print(s)
else:
    s2=""
    for i in range(len(s)):
        s2=s2+s[-1-i]
    print(s2)


### FIXED CODE ###

s=input()
q=int(input())
cnt1=0
s_mae=[]
s_ushiro=[]
for i in range(q):
    query=list(input().split())
    if int(query[0])==1:
        cnt1+=1
    else:
        if (int(query[1])+cnt1)%2==0:
            s_ushiro.append(query[2])
        else:
            s_mae.append(query[2])
s1=""
for i in range(len(s_mae)):
    s1=s1+s_mae[-1-i]
s2="".join(s_ushiro)
ans=s1+s+s2
if cnt1%2==0:
    print(ans)
else:
    ans2=""
    for i in range(len(ans)):
        ans2=ans2+ans[-1-i]
    print(ans2)
### BUGGY CODE ###

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

D = defaultdict(int)
for a in A:
    for i in range(61):
        D[1 << i] += bool(a & (1 << i))

ans = 0
for key, value in D.items():
    ans += ((key * value) % MOD) * (N - value) % MOD
    ans %= MOD

print(ans % MOD)


### FIXED CODE ###

def main():
    def accumulate(array):
        for i in range(len(array) - 1):
            array[i + 1] += array[i]
        return array

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

    X = [[0] * N for i in range(61)]
    for i, a in enumerate(A):
        for j in range(61):
            if (1 << j) & a:
                X[j][i] = 1

    for i in range(61):
        X[i] = accumulate(X[i])


    ans = 0
    for i, a in enumerate(A):
        for j in range(61):
            x = X[j][-1] - X[j][i]
            if (1 << j) & a:
                ans += ((1 << j) % MOD) * ((N - i - 1) - x)
                ans %= MOD

            else:
                ans += ((1 << j) % MOD) * x
                ans %= MOD


    print(ans % MOD)


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

def getZ_index(input_list):
    for index, i in enumerate(reversed(input_list)):
        if i == 'Z':
            return len(input_list) - index
    return 0


lis = list(input())
max_num = 0
for index, i in enumerate(lis):
    if i == 'A':
        if 'Z' in lis[index: len(lis)]:
            max_num = max(max_num, getZ_index(
                lis[index: len(lis)]))
print(max_num)


### FIXED CODE ###

s = list(input())
print(len(s) - list(reversed(s)).index('Z') - s.index('A'))
### BUGGY CODE ###

import sys
from collections import deque

input = sys.stdin.readline


def bfs(H, W, dist, black_induces):
    queue = deque(black_induces)
    while queue:
        h, w = queue.popleft()
        for y, x in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
            hh, ww = h + y, w + x
            if not (0 <= hh < H and 0 <= ww < W):
                continue
            if dist[hh][ww] == -1:
                dist[hh][ww] = dist[h][w] + 1
                queue.append((hh, ww))


def main():
    H, W = map(int, input().split())
    dist = [[] for _ in range(H)]
    black_induces = []
    for i in range(H):
        A = input().rstrip()
        for j, s in enumerate(A):
            if s == "#":
                dist[i].append(0)
                black_induces.append((i, j))
            else:
                dist[i].append(-1)

    bfs(H, W, dist, black_induces)

    ans = max(max(d) for d in dist)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.readline


def bfs(H, W, A, dist):
    queue = deque([])
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                dist[h][w] = 0
                queue.append((h, w))
    while queue:
        h, w = queue.popleft()
        for y, x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            next_h, next_w = h + y, w + x
            if dist[next_h][next_w] == -1:
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append((next_h, next_w))


def main():
    H, W = map(int, input().split())
    A = [None] * (H + 2)
    A[0] = A[-1] = "." * (W + 2)
    for i in range(1, H + 1):
        A[i] = "".join([".", input().rstrip(), "."])

    dist = [[0] + [-1] * W + [0] for _ in range(H + 2)]
    dist[0] = dist[-1] = [0] * (W + 2)
    bfs(H + 2, W + 2, A, dist)

    ans = max(map(max, dist))
    print(ans)


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

X, Y, Z, K = map(int, input().split())

A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))


import itertools
val_list = []


A_list = sorted(A_list, reverse=True)
B_list = sorted(B_list, reverse=True)
C_list = sorted(C_list, reverse=True)

#print(A_list)
#print(B_list)
#print(C_list)

for a, b, c in itertools.product(range(len(A_list)), range(len(B_list)), range(len(C_list))):
    if (a+1) * (b+1) * (c+1) > K:
        continue
        
    val_list.append(A_list[a] + B_list[b] + C_list[c])

val_list = sorted(val_list, reverse=True)
for i in range(K):
    print(val_list[i])

    


            


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())

A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))

val_list = []


A_list = sorted(A_list, reverse=True)
B_list = sorted(B_list, reverse=True)
C_list = sorted(C_list, reverse=True)

#print(A_list)
#print(B_list)
#print(C_list)

for a in range(len(A_list)):
    if a + 1 > K:
        break
    for b in range(len(B_list)):
        if b + 1 > K:
            break
        if (a+1) * (b+1) > K:
            break
            
        for c in range(len(C_list)):
            if c + 1 > K:
                break
            if (a+1) * (b+1) * (c+1) > K:
                break
        
            val_list.append(A_list[a] + B_list[b] + C_list[c])

val_list = sorted(val_list, reverse=True)
for i in range(K):
    print(val_list[i])
### BUGGY CODE ###

def is_even(num):
    return num % 2 == 0
def goback(M, x):
    k = M // 2
    if M == 0:
        return L - x[0]
    elif M == 1:
        return 2 * (L - x[1]) + x[0]
    elif is_even(M):
        return 2 * sum(x[0:k]) - 2 * sum(x[M - k + 1:M + 1]) - x[M - k] + L * (2 * k + 1)
    else:
        return 2 * sum(x[0:k]) + x[k] - 2 * sum(x[M - k:M + 1]) + L * 2 * (k + 1)

L, N = (int(i) for i in input().split())
points = []
ans = []
for i in range(0, N):
    points.append(int(input()))

for i in range(0, N):
    ans.append((goback(i, points)))

revpoints = [L - p for p in points[::-1]]
for i in range(0, N):
    ans.append((goback(i, revpoints)))

print(max(ans))

### FIXED CODE ###

def is_even(num):
    return num % 2 == 0
def goback(M, x, Sx):
    k = M // 2
    if M == 0:
        return L - x[0]
    elif M == 1:
        return 2 * (L - x[1]) + x[0]
    elif is_even(M):
        return 2 * Sx[k - 1] - 2 * (Sx[M] - Sx[M - k]) - x[M - k] + L * (2 * k + 1)
    else:
        return 2 * Sx[k - 1] + x[k] - 2 * (Sx[M] - Sx[M - k - 1]) + L * 2 * (k + 1)

L, N = (int(i) for i in input().split())
ans = 0

pl = []
for i in range(N):
    pl.append(int(input()))
sumpl = [pl[0]]
for i in range(1, N):
    sumpl.append(sumpl[i - 1] + pl[i])
for i in range(0, N):
    ans = max(ans, goback(i, pl, sumpl))

revpl = [L - p for p in pl[::-1]]
sumrevpl = [revpl[0]]
for i in range(1, N):
    sumrevpl.append(sumrevpl[i - 1] + revpl[i])
for i in range(0, N):
    ans = max(ans, goback(i, revpl, sumrevpl))

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

n,m=map(int,input().split())
a=[]
mod=10**9+7
for i in range(m):
  b=int(input())
  a.append(b)
block=[0,1]
for i in range(1,n+1):
  if i in a:
    block=block[1:]+[0]
  else:
    block=block[1:]+[sum(block)%mod]
print(block[-1])

### FIXED CODE ###

n,m=map(int,input().split())
mod=10**9+7
a = [int(input()) for i in range(m)]
block=[0,1]
x=[True for i in range(n)]
for j in a:
  x[j-1]=False

for i in range(1,n+1):
  if x[i-1]==False:
    block=block[1:]+[0]
  else:
    block=block[1:]+[sum(block)%mod]
print(block[-1])
### BUGGY CODE ###

n=int(input())
a_list=list(map(int,input().split()))
ans=[0]*n
for i in range(n-1):
    ans[i]=a_list.count(i+1)
for l in ans:
    print(l)

### FIXED CODE ###

import collections
n=int(input())
a_list=list(map(int,input().split()))
ans=[0]*n
c = collections.Counter(a_list)
#print(c)
for i in range(n-1):
    print(c[i+1])
print("0")
### BUGGY CODE ###

N,M = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(M)]

ab.sort()
data = []
for a,b in ab:
  if a == 1:
    data.append(b)
  else:
    break

for i in range(M-1,-1,-1):
  a = ab[i][0]
  if a in data and ab[i][1] == N:
    print("POSSIBLE")
    break
  elif a==1:
    print("IMPOSSIBLE")
    break

### FIXED CODE ###

import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()

data = [0]*N
for i in range(M):
  a,b = IL()
  if a == 1:
    if data[b]==1:
      print("POSSIBLE")
      break
    else:
      data[b]=1
  if b == N:
    if data[a]==1:
      print("POSSIBLE")
      break
    else:
      data[a]=1
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

from typing import List


def main():
    n = int(input())
    m = xyz(n)
    for i in m:
        print(i)


def f(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


def xyz(n: int) -> List[int]:
    rs = []
    for i in range(1, n + 1):
        r = 0
        for x in range(1, i - 4):
            for y in range(x, i - 4):
                for z in range(y, i - 4):
                    if f(x, y, z) > i:
                        break
                    elif f(x, y, z) == i:
                        if x == y == z:
                            r += 1
                        elif x == y or y == z or z == x:
                            r += 3
                        else:
                            r += 6
        rs.append(r)

    return rs


if __name__ == '__main__':
    main()


### FIXED CODE ###

from typing import List


def main():
    n = int(input())
    m = xyz(n)
    for i in m:
        print(i)


def f(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


def xyz(n: int) -> List[int]:
    result = [0] * n
    for x in range(1, 100):
        for y in range(1, 100):
            for z in range(1, 100):
                m = f(x, y, z)
                if m > n:
                    break
                result[m - 1] += 1

    return result


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

import sys

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

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    bb = list(map(int, input().split()))
    ans = 0
    for k in range(56):
        t = 1 << k
        am = list(map(lambda x: x % (t * 2), aa))
        bm = list(map(lambda x: x % (t * 2), bb))
        #am.sort()
        bm.sort()
        cnt = n ** 2
        for a in am:
            i = 0
            while i < n and a + bm[i] < t:
                i += 1
            cnt -= i
            while i < n and a + bm[i] < 2 * t:
                i += 1
            cnt += i
            while i < n and a + bm[i] < 3 * t:
                i += 1
            cnt -= i
        if cnt % 2:
            ans += t
    print(ans)

main()


### FIXED CODE ###

import sys
import numpy as np

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

def main():
    n = int(input())
    aa = np.array(list(map(int, input().split())), dtype="i8")
    bb = np.array(list(map(int, input().split())), dtype="i8")
    ans = 0
    for k in range(29):
        t = 1 << k
        t2 = t << 1
        am = aa % t2
        bm = bb % t2
        # am.sort(reverse=True)
        bm.sort()
        # print(am)
        # print(bm)
        cnt = n % 2
        for tk in range(t, t * 4, t):
            cnt += np.sum(np.searchsorted(bm, tk - am))
        if cnt % 2:
            ans += t
    print(ans)

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, w = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]

dp = [[0] * (w + 1) for _ in range(n + 1)]

for i, (wi, vi) in enumerate(items):
    for j in range(w + 1):
        if j >= wi:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - wi] + vi)
        else:
            dp[i + 1][j] = dp[i][j]

print(dp[n][w])


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, w = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]

dp = [[0] * (w + 1) for _ in range(n + 1)]

for i, (wi, vi) in enumerate(items):
    for j in range(w + 1):
        if j >= wi:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - wi] + vi)
        else:
            dp[i + 1][j] = dp[i][j]

print(dp[n][w])
### BUGGY CODE ###

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

import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
A = LIST()

# 部分和DPを変形させて、その値になるのに使われた値の集合を持っておく
dp = defaultdict(set)
dp[0].add(0)
for i in range(N):
    for j in range(K-1, -1, -1):
        if len(dp[j]):
            dp[j+A[i]] |= dp[j]
            dp[j+A[i]].add(A[i])

ans = 0
for i in range(N):
    for k, s in dp.items():
        # A[i]減らしたらK未満になる状況で、一度でもA[i]が使われていれば必要
        if k >= K and k-A[i] < K and A[i] in s:
            break
    else:
        # 該当するどの集合でも、一度も使われていなければ不要
        ans += 1
print(ans)


### FIXED CODE ###

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

import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    # 部分和DP
    dp = np.zeros((N+1, K), dtype=np.bool)
    dp[0,0] = 1
    for i in range(N):
        # まとめて遷移
        dp[i+1] |= dp[i]
        if i != omit and A[i] < K:
            dp[i+1,A[i]:] |= dp[i,:K-A[i]]
    # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
    for j in range(max(0, K-A[omit]), K):
        if dp[N,j]:
            return True
    # なければ不要
    return False

A.sort()
print(bisearch_min(-1, N, check))
### BUGGY CODE ###

n, p = map(int, input().split())
m = int(p**(1/n) + 10)

for i in range(1, m)[::-1]:
    if p%(i**n) == 0:
        print(i)
        exit()

### FIXED CODE ###

n, p = map(int, input().split())
l = []
ans = 1

for i in range(2, int(p**0.5) + 2):
    if p%i == 0:
        cnt = 0
        while p%i == 0:
            p /= i
            cnt += 1
        l.append([i, cnt])

if p != 1:
    l.append([p, 1])

for i, j in l:
    while j >= n:
        ans *= i
        j -= n

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

def main():
    n = int(input())
    S = input()
    q = int(input())
    for _ in range(q):
        t, i, c = input().split()
        if t == '1':
            S = S[:int(i)-1] + c + S[int(i):] 
        else:
            print(len(set(S[int(i)-1:int(c)])))
        
if __name__ == "__main__":
    main()   

### FIXED CODE ###

def main():
    n = int(input())
    a = ord("a")
    orda = lambda x: ord(x)-a
    s = list(map(orda, list(input())))
    q = int(input())
    bits = [BIT(n) for _ in range(26)]
    for i, si in enumerate(s, 1):
        bits[si].add(i, 1)
    for _ in range(q):
        t, i, c = input().split()
        i = int(i)
        if t == "1":
            bits[s[i-1]].add(i, -1)
            bits[ord(c)-a].add(i, 1)
            s[i-1] = ord(c)-a
        else:
            c = int(c)
            cnt = 0
            for bit in bits:
                is_in = bit.sum_(c) - bit.sum_(i-1)
                if is_in:
                    cnt += 1
            print(cnt)
            
            
class BIT:
    __slots__ = ["length", "data"]
    def __init__(self, length):
        self.data = [0]*(length+1)
        self.length = length
    
    def add(self, i, x):
        while i < self.length+1:
            self.data[i] += x
            i += i&-i
    
    def sum_(self, i):
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i&-i
        return x


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

n = int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
d = [int(i) for i in input().split()] # 配列で数字

m = int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
t = [int(i) for i in input().split()]

def bs(nums, target):
    l = 0
    r = len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            r = mid - 1
        else:
            l = mid + 1
    return -1

if n < m:
    print('NO')
else:
    d.sort()
    for p in t:
        r = bs(d, p)
        if r == -1:
            print('NO')
            break
        else:
            del d[r]
    else:
        print('YES')

### FIXED CODE ###

n = int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
d = [int(i) for i in input().split()] # 配列で数字

m = int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
t = [int(i) for i in input().split()]

def bs(nums, target):
    l = 0
    r = len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            r = mid - 1
        else:
            l = mid + 1
    return -1

if n < m:
    print('NO')
else:
    d.sort()
    t.sort()
    i = j = 0
    while i < n and j < m:
        if d[i] == t[j]:
            i += 1
            j += 1
        else:
            i += 1
    if j == m:
        print('YES')
    else:
        print('NO')
### BUGGY CODE ###

a, b = map(int, input().split())
ans = 1
B = b + 1

for i in range(a, B):
    ans *= i

if ans > 0:
    print("Positive")
elif ans < 0:
    print("Negative")
elif ans == 0:
    print("Zero")

### FIXED CODE ###

a, b = map(int, input().split())
zero = (a == 0 | b == 0) | (a < 0 and 0 < b) | (b < 0 and 0 < a)
negative_a = (a < 0 and 0 < b) and (a + b + 1) % 2 != 0
negative_b = (a < 0 | b < 0) and (a + b + 1) % 2 != 0
if zero:
    print("Zero")
elif negative_a | negative_b:
    print("Negative")
else:
    print("Positive")
### BUGGY CODE ###


N, M, Q = map(int, input().split())
A = [[0] * N for _ in range(N)]
for _ in range(M):
    l, m = map(int, input().split())
    A[l - 1][m - 1] += 1

questions = []
for _ in range(Q):
    p, q = map(int, input().split())
    questions.append((p - 1, q - 1))


D = []
for l in range(N):
    s = 0
    d = []
    for r in range(N):
        s += A[l][r]
        d.append(s)
    D.append(d)

for question in questions:
    print(sum([D[i][question[1]]
               for i in range(question[0], question[1] + 1)]))


### FIXED CODE ###

N, M, Q = map(int, input().split())
A = [[0] * N for _ in range(N)]
for _ in range(M):
    l, m = map(int, input().split())
    A[l - 1][m - 1] += 1

questions = []
for _ in range(Q):
    p, q = map(int, input().split())
    questions.append((p - 1, q - 1))


D = []
for l in range(N):
    s = 0
    d = []
    for r in range(N):
        s += A[l][r]
        d.append(s)
    D.append(d)

T = []
for r in range(N):
    s = 0
    t = [0]
    for l in range(N):
        s += D[l][r]
        t.append(s)
    T.append(t)

for question in questions:
    print(T[question[1]][N] - T[question[1]][question[0]])
### BUGGY CODE ###

s,n=input(),int(input())
ss=[s[i:i+j+1] for i in range(len(s)) for j in range(5)]
ss.sort()
print(sorted(set(ss), key=ss.index)[n-1])

### FIXED CODE ###

s=input()
n=int(input())
ss=[]
for i in range(len(s)):
  for j in range(5):
    ss.append(s[i:i+j+1])
ss.sort()

kk=1
for i in range(len(ss)):
  if kk==n:
    print(ss[i])
    break
  if ss[i]!=ss[i+1]:
    kk+=1