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

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def query(n: int):
    print(n)
    res = input()
    if res == "Vacant":
        sys.exit()
    return res


def main():
    n = input_int()
    record = [None] * n
    # 方針：
    # 2分探索で探す
    # 初期状態を見つける
    left = 0
    right = n - 1
    record[left] = query(left)
    record[right] = query(right)

    while True:
        mid = (left + right) // 2
        record[mid] = query(mid)
        if (left - mid) % 2 == 1:
            # 差が奇数で性別が一致する場合は空白が間に存在する
            if record[left] == record[mid]:
                right = mid
            else:
                left = mid
        else:
            # 差が偶数で性別が一致する場合は空白が間に存在しない
            if record[left] == record[mid]:
                left = mid
            else:
                right = mid

    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def query(n: int):
    print(n, flush=True)
    res = input().rstrip()[0]
    if res == "V":
        sys.exit()
    return res


def main():
    n = input_int()
    record = [None] * n
    # 方針：
    # 2分探索で探す
    # 初期状態を見つける
    left = 0
    right = n - 1
    record[left] = query(left)
    record[right] = query(right)

    for i in range(18):
        mid = (left + right) // 2
        record[mid] = query(mid)
        if (mid - left) % 2 == 1:
            # 差が奇数で性別が一致する場合は空白が間に存在する
            if record[left] == record[mid]:
                right = mid
            else:
                left = mid
        else:
            # 差が偶数で性別が一致する場合は空白が間に存在しない
            if record[left] == record[mid]:
                left = mid
            else:
                right = mid

    return


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

import bisect

n = int(input())
arr = list(map(int,input().split()))

arr.sort()
ans = 0
for i in range(n):
    for j in range(i+1,n):
        a,b = arr[i],arr[j]

        cmin = abs(a-b)
        cmax = a+b

        l = bisect.bisect_left(arr,cmin+1,lo=j+1)
        r = bisect.bisect_right(arr,cmax-1,lo=j+1)
        # print(cmin,l,cmax,r)
        if r-l > 0:
            ans += r-l

print(ans)


### FIXED CODE ###

import bisect

n = int(input())
arr = list(map(int,input().split()))

arr.sort()
ans = 0
for i in range(n):
    for j in range(i+1,n):
        a,b = arr[i],arr[j]

        cmin = abs(a-b)
        cmax = a+b

        l = bisect.bisect_left(arr,cmin+1,lo=j+1)
        r = bisect.bisect_right(arr,cmax-1,lo=j+1)
        # print(cmin,l,cmax,r)
        if r-l > 0:
            ans += r-l

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

n = int(input())
sum = 0

def gcd(a, b, c):
    smaller = min(min(a, b), c)
    for i in range(1, smaller + 1):
        if (a % i == 0) and (b % i == 0) and (c % i == 0):
            gcd = i
    return gcd

for i in range (1, n + 1):
    for j in range (1, n + 1):
        for k in range(1, n + 1):
            sum += gcd(i, j, k)
print(sum)

### FIXED CODE ###

n = int(input())
sum = 0

def gcd(a, b):
    if a < 1 or b < 1 :
        if a > 0:
            return a
        return b
    remainder = 0
    if a % b == 0 :
        return b
    remainder = a % b
    a = b
    b = remainder
    return gcd(a, b)

for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            sum += gcd(gcd(i, j), k)
print(sum)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
s = []
for i in l:
    if (i in s):
        print("NO")
        exit(0)
    s.append(i)
print("YES")


### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
s = set()
for i in l:
    if (i in s):
        print("NO")
        exit(0)
    s.add(i)
print("YES")
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
idx = 0
s=sum(p[:k])
e=0

for i in range(1,n-k+1):
    if p[i-1] < p[i+k-1]:
        s1 = sum(p[i:i+k])
        if s1 > s:
            idx = i
            s = s1


l = [(1 + p1)*(p1//2 + 0.5*(p1%2))/p1 for p1 in p[idx:idx+k]]

print(sum(l))


### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
l=[sum(p[:k])]

for i in range(n-k):
    l1=l[i] - p[i] + p[i+k]
    l.append(l1)

print((max(l)+k)/2)
### BUGGY CODE ###

import numpy as np

h, w = map(int, input().split(' '))
d = [[float('inf') for _ in range(w)] for _ in range(h)]

a = []
que = []
for i in range(h):
    aa = input()
    a.append(aa)
    for j, aaa in enumerate(aa):
        if aaa == '#':
            d[i][j] = 0
            que.append((i, j))

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

while len(que) > 0:
    y, x = que.pop(0)

    for dy, dx in move:
        ny = y + dy
        nx = x + dx

        if (ny >= 0 and ny < h) and (nx >= 0 and nx < w) and a[ny][nx] == '.' and d[ny][nx] == float('inf'):
            que.append((ny, nx))
            d[ny][nx] = d[y][x] + 1

print(np.max(d))


### FIXED CODE ###

import numpy as np


def solve():
    h, w = map(int, input().split(' '))
    max_value = h + w
    values = []
    for i in range(h):
        values.append([0 if i == '#' else max_value for i in list(input())])
    values = np.array(values)

    for x in range(w - 1):
        values[:, x+1] = np.minimum(values[:, x] + 1, values[:, x+1])
    for x in range(w - 1, 0 , -1):
        values[:, x-1] = np.minimum(values[:, x-1], values[:, x] + 1)
    for x in range(h - 1):
        values[x+1, :] = np.minimum(values[x, :] + 1,values[x+1, :])
    for x in range(h - 1, 0, -1):
        values[x-1, :] = np.minimum(values[x, :] + 1, values[x-1, :])
    print(np.max(values))


solve()
### BUGGY CODE ###

a = input().split()
N = int(a[0])
W = int(a[1])
wv_list = []
for i in range(N):
    b = input().split()
    w = int(b[0])
    v = int(b[1])

    wv_list.append([w, v])

n_list = [0 for i in range(W + 1)]

if wv_list[0][0] <= W:
    n_list[wv_list[0][0]] = wv_list[0][1]
import copy
for i in range(1, N):
    n_list1=copy.deepcopy(n_list)
    for j in range(W):
        s = j + wv_list[i][0]
        if s <= W:
            n_list[s] = max(n_list1[j] + wv_list[i][1], n_list[s])

        n_list[j] = max(n_list1[j], n_list[j])

print(max(n_list))


### FIXED CODE ###

a= input().split()
N = int(a[0])
W = int(a[1])
wv_list = []
max_value = 0

#価値と重さのやつをリストにしてる
for i in range(N):
  b = input().split()
  w = int(b[0])
  v = int(b[1])
  max_value += v

  wv_list.append([w, v])

#初期化
#とりあえず、全部最大になるように
inf=float('inf')
n_list = [[inf for i in range(max_value + 1)] for j in range(N)]

#最初のアイテムに関して、重みを適切な価値のところにいれている
n_list[0][wv_list[0][1]] = wv_list[0][0]

for i in range(1, N):
  # 今まで全く選んでなかった場合に、i番目のアイテムを選んだ時
  n_list[i][wv_list[i][1]] = wv_list[i][0]
  for j in range(max_value):

    s = j + wv_list[i][1]
    #アイテムを選んだらこうなりますよってのを更新
    if s <= max_value:
      n_list[i][s] = min(n_list[i - 1][j] + wv_list[i][0], n_list[i][s])

    #選ばんかったらこうなりますよってのを更新？
    n_list[i][j] = min(n_list[i - 1][j], n_list[i][j])
  
for i in range(1, max_value):

  if n_list[-1][-i] <= W:
    print(max_value - i + 1)
    break
### BUGGY CODE ###

# C - Sum of gcd of Tuples (Easy)

import math

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 += math.gcd(a, math.gcd(b, c))

print(ans)

### FIXED CODE ###

# C - Sum of gcd of Tuples (Easy)

import math

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 += math.gcd(a, math.gcd(b, c))

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

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N = I()
u,v,w = Line(N-1)

c = []
for i in range(N-1):
  c.append([u[i]-1, v[i]-1, w[i]])
  c.append([v[i]-1, u[i]-1, w[i]])

from heapq import heappop, heappush
inf=float('inf')
d=[inf for i in range(N)]
d[0]=0
prev=[None]*N
p=dict()
for i,j,k in c: p[i]=p.get(i,[])+[(j,k)]

q=[]
heappush(q,(d[0],0))
while q:
  du, u = heappop(q)
  if d[u]<du: continue
  for v,weight in p.get(u,[]):
    alt=du+weight
    if d[v]>alt:
      d[v]=alt
      prev[v]=u
      heappush(q, (alt,v))

for i in range(N):
  if d[i]%2==0:
    print('0')
  else:
    print('1')

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N = I()
u,v,w = Line(N-1)

c = [[] for _ in range(N)]
for i in range(N-1):
  c[u[i]-1].append([v[i]-1, w[i]])
  c[v[i]-1].append([u[i]-1, w[i]])

d=[-1]*N
v=0
check_visited = [False]*N
check_visited[v] = True
S = [v]
d[v]=0
while S:
  v1 = S.pop()
  for i in c[v1]:
    if check_visited[i[0]] == False:
      check_visited[i[0]] = True
      d[i[0]] = d[v1] + i[1]
      S.append(i[0])

for i in range(N):
  if d[i]%2==0:
    print('0')
  else:
    print('1')
### BUGGY CODE ###

'''
Created on 2020/08/26

@author: harurun
'''
def main():
  import math
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N,P=map(int,pin().split())
  t=int(math.sqrt(P))+1
  if N==1:
    print(P)
    return 
  while t>0:
    s=P
    for i in range(N):
      if s%t!=0:
        break
      s=s//t
    else:
      print(t)
      return
    t-=1
  print(1)
  return 

main()

### FIXED CODE ###

'''
Created on 2020/08/26

@author: harurun
'''
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

def main():
  import math
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  N,P=map(int,pin().split())
  l=factorize(P)
  d=list(set(l))
  ans=1
  for i in d:
    t=l.count(i)
    if t>=N:
      ans*=i**(int(t/N))
  print(ans)
  return

main()
### BUGGY CODE ###

from heapq import heappush,heappop

N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    table[u-1].append([a,v-1])
    table[v-1].append([a,u-1])
    rtable[u-1].append([b,v-1])
    rtable[v-1].append([b,u-1])
dij=[]
heappush(dij,[0,s-1])
val=[10**16]*N
val[s-1]=0
while dij:
    q,x=heappop(dij)
    if val[x]<q:
        continue
    for d,y in table[x]:
        if val[y]>val[x]+d:
            val[y]=val[x]+d
            heappush(dij,[val[y],y])
rdij=[]
heappush(rdij,[0,t-1])
rval=[10**16]*N
rval[t-1]=0
while rdij:
    q,x=heappop(rdij)
    if rval[x]<q:
        continue
    for d,y in rtable[x]:
        if rval[y]>rval[x]+d:
            rval[y]=rval[x]+d
            heappush(rdij,[rval[y],y])
score=[0]*N
mod=pow(10,15)
for i in range(N):
    score[i]=mod-(val[i]+rval[i])
amax=[mod]*N
amax[-1]=score[-1]
for i in range(N-2,-1,-1):
    amax[i]=max(amax[i+1],score[i])
for i in range(N):
    print(amax[i])

### FIXED CODE ###

from heapq import heappush,heappop
from collections import deque
N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    table[u-1].append([a,v-1])
    table[v-1].append([a,u-1])
    rtable[u-1].append([b,v-1])
    rtable[v-1].append([b,u-1])
dij=[]
heappush(dij,[0,s-1])
val=[10**16]*N
val[s-1]=0
while dij:
    q,x=heappop(dij)
    if val[x]<q:
        continue
    for d,y in table[x]:
        if val[y]>val[x]+d:
            val[y]=val[x]+d
            heappush(dij,[val[y],y])
rdij=[]
heappush(rdij,[0,t-1])
rval=[10**16]*N
rval[t-1]=0
while rdij:
    q,x=heappop(rdij)
    if rval[x]<q:
        continue
    for d,y in rtable[x]:
        if rval[y]>rval[x]+d:
            rval[y]=rval[x]+d
            heappush(rdij,[rval[y],y])
ans=deque()
t=val[N-1]+rval[N-1]
mod=pow(10,15)
ans.append(mod-t)
for i in range(N-2,-1,-1):
    t=min(t,val[i]+rval[i])
    ans.appendleft(mod-t)
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

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

ex = []
for x in p:
    ex.append(1/x * (sum(list(range(1, x+1)))))

ans = 0
for i in range(n-k+1):
    ans = max(ans, sum(ex[i:i+k]))

print(ans)

### FIXED CODE ###

def main():

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

    ex = [0]
    for x in p:
        ex.append(ex[-1] + (x+1)/2)

    ans = 0
    for i in range(k, n+1):
        ans = max(ans, ex[i] - ex[i-k])

    print(ans)

main()
### BUGGY CODE ###

import re
N, Q = map(int, input().split())
S = input()
l = []
r = []
for i in range(Q):
    li, ri = map(int, input().split())
    l += [li]
    r += [ri]

for ind in range(Q):
    substr = S[max(0, l[ind]-1) : min(r[ind], N)]
    print(len(re.findall("AC", substr)))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
l = []
r = []
for i in range(Q):
    li, ri = map(int, input().split())
    l += [li]
    r += [ri]

S_tf = [0]*(N+1)
for ind in range(N):
    S_tf[ind + 1] = S_tf[ind] + (1 if S[ind:ind+2] == "AC" else 0)
for ind in range(Q):
    print(S_tf[max(0, r[ind]-1)] - S_tf[min(l[ind]-1, N)])
### BUGGY CODE ###

N = int(input())
A = [None]
A[1:] = list(map(int,input().split()))

csum = [0 for _ in range(N+1)]
cxor = [0 for _ in range(N+1)]
for i in range(1,N+1):
    csum[i] = csum[i-1] + A[i]
    cxor[i] = cxor[i-1] ^ A[i]
ans = N
for l in range(1,N):
    for r in range(l+1,N+1):
        rsum = csum[r] - csum[l-1]
        rxor = cxor[r] ^ cxor[l-1]
        if rsum == rxor:
            ans += 1
print(ans)


### FIXED CODE ###

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

    if N == 1:
        return 1

    ans = N
    l = 0
    r = 0
    s = A[l]
    while l < N-1:
        if r+1 < N:
            if s & A[r+1] == 0:
                r += 1
                s |= A[r]
                ans += r - l
                continue
        if l == r:
            l += 1
            r += 1
            s = A[l]
        else:
            s &= ~A[l]
            l += 1
    return ans

print(solve())

#  1  2  4  8  1
#  l  r              (1,2)
#  l     r           (1,4)(2,4)
#  l        r        (1,8)(2,8)(4,8)
#     l     r
#     l        r     (2,1)(4,1)(8,1)
### BUGGY CODE ###

N=input()
A=input().split()
if(sorted(set(A), key=A.index)==A):
  print("YES")
else:
  print("NO")


### FIXED CODE ###

N=input()
A=input().split()
def has_duplicates(seq):
    return len(seq) != len(set(seq))
if has_duplicates(A):
  print("NO")
else:
  print("YES")
### BUGGY CODE ###

N = int(input())
a = input().split()
sum = 0
sum_sunuke = 0

def sum_list(L):
  sum = 0
  for i in range(len(L)):
   sum += L[i]
  return sum

for i in range(N):
  a[i] = int(a[i])
  sum += a[i]

for i in range(N-1):
  #print(a[:i+1])
  #print(a[i+1:])
  if(i == 0):
   min = abs(2*sum_list(a[:i+1])-sum)
  else:
   tmp = abs(2*sum_list(a[:i+1])-sum)
   if(min > tmp):
      min = tmp
  #print(min)
print(min)
 

### FIXED CODE ###

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

min_dif = float('inf')
s1 = 0
for i in range(N):
  if(i != N-1):
   s1 += A[i]
   s2 = sum_all - s1
   tmp_dif = abs(s1 - s2)
   min_dif = min(min_dif,tmp_dif)
print(min_dif)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

tmp = ""

for i in range(n):
    tmp = a[i]
    for j in range (i+1, n):
        if (tmp ==  a[j]):
            print("NO")
            exit()
        else:
            continue

print("YES")


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

a = sorted(a)
tmp = ""

for i in range(n-1):
    if (a[i] == a[i+1]):
        print("NO")
        exit()
    else:
        continue

print("YES")
### BUGGY CODE ###

def WalkingTakahashi():
    
    data = list(map(int,input().split()))
    
    position = data[0]
    
    for i in range(data[1]):
        
        if abs(position + data[2]) < abs(position - data[2]):
            position = position + data[2]
            
        else:
            position = position - data[2]
            
    print(abs(position))
        
if __name__ == '__main__':
    WalkingTakahashi()




### FIXED CODE ###

def WalkingTakahashi():
    
    data = list(map(int,input().split()))
    
    position = abs(data[0])
    
    m = min(data[1], position//data[2])
    
    position = position - data[2]*m
    
    data[1] = data[1] - m
    
    data[1] %= 2
    
    position = position - data[2]*data[1]
    
    print(abs(position))
    
if __name__ == '__main__':
    WalkingTakahashi()
### BUGGY CODE ###

from functools import reduce
from operator import mul

def main():
  N,M = map(int,input().split())
  if N == M:
    L = [i for i in range(1,N + 1)]
    ans = (reduce(mul,L) ** 2) * 2  % (10 ** 9 + 7)
    print(ans)
  elif N + 1 == M or M + 1 == N: 
    L1 = [i for i in range(1,N + 1)]
    L2 = [i for i in range(1,M + 1)]
    ans = (reduce(mul,L1)) * (reduce(mul,L2)) % (10 ** 9 + 7)
    print(ans)
  else:
    print(0)
main()

### FIXED CODE ###

import sys
from functools import reduce,lru_cache
import math
from operator import mul

def main():
  #sys.setrecursionlimit(10 ** 5 + 1)
  N,M = map(int,input().split())
  
  @lru_cache(maxsize = None)
  def recur(n):
    if n == 0:
      return 1
    else:
      m = n * recur(n - 1)
      return m
      
  if N == M:
    L = [i for i in range(1,N + 1)]
    #ans = (reduce(mul,L) ** 2) * 2  % (10 ** 9 + 7)
    ans = (math.factorial(M) ** 2) * 2 % ((10 ** 9) + 7)
    print(ans)
  elif abs(M - N) == 1: 
    ans = math.factorial(N) * math.factorial(M) % ((10 ** 9) + 7)
    print(ans)
    
  else:
    print(0)
    
main()
### BUGGY CODE ###

import sys


def main():
    input = sys.stdin.readline
    N = int(input())

    robots = dict()
    x_list = []
    duplicates = dict()

    for i in range(N):
        x, l = map(int, input().split())
        x_list.append(x)
        robots[x] = l
        duplicates[x] = 0

    x_list.sort()
    n_duplicates = 0

    for i, x in enumerate(x_list):
        arm = robots[x]
        for y in x_list[i:]:
            if x == y:
                continue
            if x+arm > y-robots[y]:
                duplicates[x] += 1
                duplicates[y] += 1
                n_duplicates += 2

    n_d_list = sorted(duplicates.values(), reverse=True)
    count = 0
    for d in n_d_list:
        if n_duplicates < 1:
            break
        n_duplicates -= 2 * d
        count += 1

    print(N - count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.readline
    N = int(input())

    robots = list()

    for i in range(N):
        x, arm = map(int, input().split())
        right = x+arm
        robots.append([x, right])

    robots.sort(key=lambda x: x[1])
    count = 0
    last_r = -10**10
    for x, r in robots:
        l = x - (r - x)
        if l < last_r:
            count += 1
        else:
            last_r = r

    print(N - count)


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

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

from collections import Counter
n = int(input())
prime_list = prime_factorize(n)
if n == 1:
    print(1)
    exit()

cnt = Counter(prime_list)
cnt_values = list(cnt.values())
value_list = [range(i + 1) for i in cnt_values]
iter_list = list(value_list[0])
iter_list = [[i] for i in iter_list]
for v_list in value_list[1:]:
    tmp = []
    for v in v_list:
        for i in iter_list:
            tmp.append(i + [v])
    iter_list = tmp
    
key_list = list(cnt.keys())
ans = n - 1
mod = 2 * n
for i_list in iter_list:
    tmp = 1
    for key, value in zip(key_list, i_list):
        tmp = tmp * pow(key, value)
    if tmp == 1:
        continue
    for i in range(1, n // tmp + 1):
        if (tmp * i) * ((tmp * i) - 1) % mod == 0:
            ans = min(ans, (tmp * i) - 1)
        if (tmp * i) * ((tmp * i) + 1) % mod == 0:
            ans = min(ans, tmp * i)
print(ans)    

### FIXED CODE ###

import math

def gcd_ext(a, b):
    x, y, lastx, lasty = 0, 1, 1, 0
    while b != 0:
        q = a // b
        a, b = b, a % b
        x, y, lastx, lasty = lastx - q * x, lasty - q * y, x, y
    return (lastx, lasty)

n = int(input())
divisor_list = []
n *= 2
for x in range(2, int(n ** 0.5) + 1):
    if n % x == 0:
        divisor_list.append([x, n // x])
ans = n - 1
for m1, m2 in divisor_list:
    if math.gcd(m1, m2) != 1:
        continue
    p, q = gcd_ext(m1, m2)
    tmp = (-1 * m1 * p) % (m1 * m2)
    ans = min(tmp, ans)
    tmp = (-1 * m2 * q) % (m1 * m2)
    ans = min(tmp, ans)
print(ans)
### BUGGY CODE ###

n = int(input())
red = [list(map(int,input().split())) for _ in range(n)]
blue = [list(map(int,input().split())) for _ in range(n)]
red_count = []
import copy

for i in range(n):
  index_list = []
  for j in range(n):
    if blue[j][0]>red[i][0] and blue[j][1]>red[i][1]:
      index_list.append(j)
  red_count.append(index_list)
red_count.sort(key=lambda x: len(x))

def redcounter(count,i,red_count):
  if i == len(red_count)-1 and red_count[i]:
    return count+1
  elif  i == len(red_count)-1:
    return count
  
  if red_count[i]:
    for index in range(len(red_count[i])): ## removeするindex
      remove_index = red_count[i][index]
      red_count_copy = copy.deepcopy(red_count)
      c = count
      for j in range(i+1,len(red_count_copy)): ## removeしていく
        if remove_index in red_count_copy[j]:
          red_count_copy[j].remove(remove_index)
      c = max(count,redcounter(c,i+1,red_count_copy))
    return c+1
  else:
    return redcounter(count,i+1,red_count)
   
print(redcounter(0,0,red_count))
  


    

### FIXED CODE ###

n = int(input())
lired = [list(map(int,input().split())) for _ in range(n)]
liblue = [list(map(int,input().split())) for _ in range(n)]
lired = sorted(lired,key = lambda x:-x[1])
liblue = sorted(liblue,key = lambda x:x[0])
li = list(range(n))
count = 0

for i in range(n):
  for j in li:
    if lired[i][0] < liblue[j][0] and lired[i][1] < liblue[j][1]:
      count += 1
      li.remove(j)
      break
print(count)