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

import sys
input = sys.stdin.readline
from collections import *

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

    def acc(self, i):
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

N, Q = map(int, input().split())
c = list(map(int, input().split()))
prev = [-1]*N
ys = defaultdict(list)

for i in range(N):
    if prev[c[i]-1]!=-1:
        ys[prev[c[i]-1]].append(i)
    
    prev[c[i]-1] = i

que = defaultdict(list)

for i in range(Q):
    l, r = map(int, input().split())
    que[l-1].append((i, r-1))
    
idx = 0
bit = BIT(N)
ans = []

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    for i, r in que[x]:
        ans.append((i, r-x+1-bit.acc(r+1)))
    
ans.sort(key=lambda t: t[0])

for ans_i in ans:
    print(ans_i[1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import *

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

    def acc(self, i):
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

N, Q = map(int, input().split())
c = list(map(int, input().split()))
prev = [-1]*N
ys = defaultdict(list)

for i in range(N):
    if prev[c[i]-1]!=-1:
        ys[prev[c[i]-1]].append(i)
    
    prev[c[i]-1] = i

que = defaultdict(list)

for i in range(Q):
    l, r = map(int, input().split())
    que[l-1].append((i, r-1))
    
idx = 0
bit = BIT(N)
ans = [-1]*Q

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    for i, r in que[x]:
        ans[i] = r-x+1-bit.acc(r+1)

for ans_i in ans:
    print(ans_i)
### BUGGY CODE ###

N = int(input())
arr = [0]*(N+2)
 
for x in range(1,151):
    for y in range(1,151):
        for z in range(1,151):
            n = x**2 + y**2 + z**2 + x*y + y*z + x*z 
            if n <= N :
                arr[n] += 1
 
for i in range(1,N+1):
    print(arr[i])

### FIXED CODE ###

N = int(input())
arr = [0]*(N+2)
 
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            n = x**2 + y**2 + z**2 + x*y + x*z + y*z
            if n <= N :
                arr[n] += 1
 
for i in range(1,N+1):
    print(arr[i])
### BUGGY CODE ###

from collections import defaultdict as dd
h, w, m = map(int, input().split())

#dic[row, col] -> set(ids)
h_dic = dd(set)
w_dic = dd(set)
spot = set()

for i in range(m):
    h_c, w_c = map(int, input().split())
    h_dic[h_c].add(i)
    w_dic[w_c].add(i)
    spot.add((h_c, w_c))
#print(h_dic, w_dic)

#H_lis -> [i, num_spot(int)]
H_lis = []
for key, val in h_dic.items():
    H_lis.append([key, len(val)])
W_lis = []
for key, val in w_dic.items():
    W_lis.append([key, len(val)])
H_lis.sort(key=lambda x: x[1], reverse=True)
W_lis.sort(key=lambda x: x[1], reverse=True)

#print(H_lis, W_lis)
max_h_num = H_lis[0][1]
#print(max_h)
max_w_num = W_lis[0][1]

ans = 0
max_h_lis = [val[0] for val in H_lis if val[1] == max_h_num]
max_w_lis = [val[0] for val in W_lis if val[1] == max_w_num]
for i in max_h_lis:
    for j in max_w_lis:
        count = max_h_num + max_w_num
        if (i, j) in spot:
            count -= 1
        ans = max(ans, count)
print(ans)

"""    
max_counter = 0
for i in h_dic.keys():
    for j in w_dic.keys():
        counter = len(h_dic[i] | w_dic[j])
        #print(i, j, h_dic[i] | w_dic[j],counter)
        max_counter = max(max_counter, counter)
print(max_counter)

"""

### FIXED CODE ###

from sys import exit
from collections import defaultdict as dd
h, w, m = map(int, input().split())

#dic[row, col] -> set(ids)
h_dic = dd(int)
w_dic = dd(int)
spot = set()

for i in range(m):
    h_c, w_c = map(int, input().split())
    h_dic[h_c] += 1
    w_dic[w_c] += 1
    spot.add((h_c, w_c))
#print(h_dic, w_dic)

#H_lis -> [i, num_spot(int)]
max_h_num = 0
for key, val in h_dic.items():
    max_h_num = max(max_h_num, val)
max_w_num = 0
W_lis = []
for key, val in w_dic.items():
    max_w_num = max(max_w_num, val)


#print(H_lis, W_lis)
#print(max_h)

ans = 0
max_h_lis = [key for key in h_dic if h_dic[key] == max_h_num]
max_w_lis = [key for key in w_dic if w_dic[key] == max_w_num]
for i in max_h_lis:
    for j in max_w_lis:
        if (i, j) not in spot:
            print(max_h_num + max_w_num)
            exit()
else:
    print(max_h_num + max_w_num - 1)

"""    
max_counter = 0
for i in h_dic.keys():
    for j in w_dic.keys():
        counter = len(h_dic[i] | w_dic[j])
        #print(i, j, h_dic[i] | w_dic[j],counter)
        max_counter = max(max_counter, counter)
print(max_counter)

"""
### BUGGY CODE ###

MOD = 998244353
N, K = map(int, input().split())
L = []
R = []
for k in range(K):
    l, r = map(int, input().split())
    L += [l]
    R += [r]
# memo = [[0 for i in range(N+2)] for k in range(K)]
memo = [0 for i in range(N+2)]
memo[1] = 1
memo[2] = -1
cusum = 0
for i in range(1, N+1):
    cusum += memo[i]
    # print(cusum)
    for k in range(K):
        l, r = L[k], R[k]
        # for j in range(i+l, min(i+r+1, N+1)):
        #     memo[j] += memo[i]
        memo[min(i+l, N+1)] += cusum
        memo[min(i+r+1, N+1)] -= cusum
    # print(memo)
# for i in range(1, N+1):
#     for k in range(K):
#         memo[k][i+1] += memo[k][i]
print(cusum % MOD)

### FIXED CODE ###

MOD = 998244353
N, K = map(int, input().split())
L = []
R = []
for k in range(K):
    l, r = map(int, input().split())
    L += [l]
    R += [r]
# memo = [[0 for i in range(N+2)] for k in range(K)]
memo = [0 for i in range(N+2)]
memo[1] = 1
memo[2] = -1
cusum = 0
for i in range(1, N+1):
    cusum = (cusum + memo[i]) % MOD
    # print(cusum)
    for k in range(K):
        l, r = L[k], R[k]
        # for j in range(i+l, min(i+r+1, N+1)):
        #     memo[j] += memo[i]
        memo[min(i+l, N+1)] += cusum
        memo[min(i+r+1, N+1)] -= cusum
    # print(memo)
# for i in range(1, N+1):
#     for k in range(K):
#         memo[k][i+1] += memo[k][i]
print(cusum % MOD)
### BUGGY CODE ###

# 初期入力

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set =set(A)
count =set()
for i in range(N-1):
    for j in range(i+1,N):
        if A[j] %A[i] ==0:
            count.add(A[j])
ans =len(A_set - count)
print(ans)

### FIXED CODE ###


2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

	

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)
### BUGGY CODE ###

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

def check(L):
  for i in range(N - (L * 2) + 1):
    if S[i:i+L] in S[i+L:]:
      return True
  return False

left = 0
right = N // 2 + 1
while right - left > 1:
  mid = left + (right - left) // 2
  if check(mid):
    left = mid
  else:
    right = mid
print(left)

### FIXED CODE ###

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

def check(L):
  a = set()
  for i in range(N - (L * 2) + 1):
    a.add(S[i:i+L])
    if S[i+L:i+L+L] in a:
      return True
  return False

left = 0
right = N // 2 + 1
while right - left > 1:
  mid = left + (right - left) // 2
  if check(mid):
    left = mid
  else:
    right = mid
print(left)
### BUGGY CODE ###

H, W = map(int, input().split())
ch, cw =  map(int, input().split())
gh, gw =  map(int, input().split())
 
f = [[s=="." for s in input()] for h in range(H)]
ans = [[-1 for w in range(W)]for h in range(H)]
 
nextQ = [(ch-1)*1000 + cw-1]
ans[ch-1][cw-1] = 0
while len(nextQ)>0:
  Q = list(nextQ)
  nextQ = set()
  i = 0
  while i<len(Q):
    nh = Q[i]
    i += 1
    nw = nh%1000
    nh = nh//1000
    for dh in range(0-min(nh,2), 3):
      if nh+dh>=H:
        break
      for dw in range(0-min(nw,2), 3):
        if nw + dw>=W:
          break
        if dh==0 and dw==0:
          continue
        if dh*dw==0 and (abs(dh)==1 or abs(dw)==1):
          if ans[nh+dh][nw+dw]==-1:
            if f[nh+dh][nw+dw]:
              Q.append((nh+dh)*1000 + nw+dw)
              ans[nh+dh][nw+dw]=ans[nh][nw]
            else:
              ans[nh+dh][nw+dw]=-2
          elif ans[nh+dh][nw+dw]>ans[nh][nw]:
            Q.append((nh+dh)*1000 + nw+dw)
            nextQ -= {(nh+dh)*1000 + nw+dw}
            ans[nh+dh][nw+dw]=ans[nh][nw]
        else:
          if ans[nh+dh][nw+dw]==-1:
            if f[nh+dh][nw+dw]:
              nextQ.add((nh+dh)*1000 + nw+dw)
              ans[nh+dh][nw+dw]=ans[nh][nw]+1
            else:
              ans[nh+dh][nw+dw]=-2
print(ans[gh-1][gw-1])

### FIXED CODE ###

H, W = map(int, input().split())
ch, cw =  map(int, input().split())
gh, gw =  map(int, input().split())

f = [[s=="." for s in input()] for h in range(H)]
ans = [[-1 for w in range(W)]for h in range(H)]

nextQ = [(ch-1)*1000 + cw-1]
ans[ch-1][cw-1] = 0
while len(nextQ)>0:
  Q = list(nextQ)
  nextQ = set()
  visited = set()
  while len(Q):
    nh = Q.pop(0)
    nw = nh%1000
    nh = nh//1000
    for dh in range(0-min(nh,2), 3):
      if nh+dh>=H:
        break
      for dw in range(0-min(nw,2), 3):
        if nw + dw>=W:
          break
        if dh==0 and dw==0:
          continue
        if dh*dw==0 and (abs(dh)==1 or abs(dw)==1):
          if ans[nh+dh][nw+dw]==-1:
            if f[nh+dh][nw+dw]:
              Q.append((nh+dh)*1000 + nw+dw)
              visited.add((nh+dh)*1000 + nw+dw)
              ans[nh+dh][nw+dw]=ans[nh][nw]
            else:
              ans[nh+dh][nw+dw]=-2
          elif ans[nh+dh][nw+dw]>ans[nh][nw]:
            Q.append((nh+dh)*1000 + nw+dw)
            visited.add((nh+dh)*1000 + nw+dw)
            ans[nh+dh][nw+dw]=ans[nh][nw]
        else:
          if ans[nh+dh][nw+dw]==-1:
            if f[nh+dh][nw+dw]:
              nextQ.add((nh+dh)*1000 + nw+dw)
              ans[nh+dh][nw+dw]=ans[nh][nw]+1
            else:
              ans[nh+dh][nw+dw]=-2
          elif ans[nh+dh][nw+dw]>ans[nh][nw]:
            nextQ.add((nh+dh)*1000 + nw+dw)
            ans[nh+dh][nw+dw]=ans[nh][nw]+1
  nextQ -= visited
print(ans[gh-1][gw-1])
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self):
    self.edges = set()
    self.distance = 1


def main():
  N = int(input())
  nodes = [Node() for _ in range(N)]

  if N == 0:
    print('Second', flush=True)
    return
  elif N == 1:
    print('First', flush=True)
    return

  for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].edges.add(nodes[b - 1])
    nodes[b - 1].edges.add(nodes[a - 1])

  leaves = [n for n in nodes if len(n.edges) == 1]

  while True:
    leaf = leaves.pop(0)
    parent = leaf.edges.pop()

    if len(parent.edges) == 1:
      size = leaf.distance + parent.distance
      break

    parent.distance = max(parent.distance, leaf.distance + 1)
    parent.edges.remove(leaf)

    if len(parent.edges) == 1:
      leaves.append(parent)

  if size % 3 == 2:
    print('Second', flush=True)
  else:
    print('First', flush=True)


if __name__ == '__main__':
  main()



### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import collections


class Node(object):

  def __init__(self):
    self.edges = set()
    self.distance = 1


def main():
  N = int(input())
  nodes = [Node() for _ in range(N)]

  if N == 0:
    print('Second', flush=True)
    return
  elif N == 1:
    print('First', flush=True)
    return

  for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].edges.add(nodes[b - 1])
    nodes[b - 1].edges.add(nodes[a - 1])

  leaves = collections.deque(n for n in nodes if len(n.edges) == 1)

  while True:
    leaf = leaves.popleft()
    parent = leaf.edges.pop()

    if len(parent.edges) == 1:
      size = leaf.distance + parent.distance
      break

    parent.distance = max(parent.distance, leaf.distance + 1)
    parent.edges.remove(leaf)

    if len(parent.edges) == 1:
      leaves.append(parent)

  if size % 3 == 2:
    print('Second', flush=True)
  else:
    print('First', flush=True)


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

N, Q = map(int, input().split())
S = input()
ans = []
import re
# for i in range(Q):
#     l, r = map(int, input().split())
#     ans.append(len(re.findall("AC", S[l-1:r])))
# for i in ans:
#     print(i)
# TLE
index = []
for i in range(N):
    if S[i:].find("AC") != -1:
        index.append(S[i:].find("AC") + i)
index = list(set(index))
import numpy as np
for i in range(Q):
    l, r = map(int, input().split())
    # l-1 ~ rまで
    ans.append(sum(l-1<=x and x<=r-2 for x in index))
for i in ans:
    print(i)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
C = [0] * len(S)
for i, c in enumerate(S):
    if i != 0 and c == 'C' and S[i-1] == 'A':
        C[i] += 1
    C[i] += C[i - 1]
ans = []
for i in range(Q):
    l, r = map(int, input().split())
    ans.append(C[r-1] - C[l-1])
for i in ans:
    print(i)
### BUGGY CODE ###

from bisect import*
def main():
    root=[[],[]]
    def search_higher(key):
        ptr0,ptr1=root
        ret=None
        while ptr1:
            i=bisect(ptr0,key)
            if i!=len(ptr0):ret=ptr0[i]
            ptr0,ptr1=ptr1[i]
        i=bisect(ptr0,key)
        if i!=len(ptr0):ret=ptr0[i]
        return ret
    def search_lower(key):
        ptr0,ptr1=root
        ret=None
        while ptr1:
            i=bisect_left(ptr0,key)
            if i!=0:ret=ptr0[i-1]
            ptr0,ptr1=ptr1[i]
        i=bisect_left(ptr0,key)
        if i!=0:ret=ptr0[i-1]
        return ret
    def insert_rec(ptr,key):
        ptr0,ptr1=ptr
        b_size=600
        if not ptr[1]:
            insort(ptr0,key)
            if len(ptr0)==b_size*2-1:
                ret=[ptr0[:b_size],[]]
                ptr[0]=ptr0[b_size:]
                return ret
        else:
            i=bisect(ptr0,key)
            tmp=insert_rec(ptr1[i],key)
            if tmp:
                ptr0.insert(i,tmp[0].pop())
                ptr1.insert(i,tmp)
                if len(ptr1)==b_size*2:
                    ret=[ptr0[:b_size],ptr1[:b_size]]
                    ptr[0],ptr[1]=ptr0[b_size:],ptr1[b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root[0],root[1]=[tmp[0].pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

# 初期入力
N = int(input())
L = list(map(int, input().split()))

#3本選ぶ組み合わせ
from itertools import combinations
count =0
for t in combinations(L, 3):
    if max(t)*2 < sum(t): #最大の1辺＊２＜3辺の合計なら三角形作れる
        count +=1
print(count)

### FIXED CODE ###

import bisect

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

count  =0
L.sort()
for i in range(0, N - 1):
  for j in range(i + 1, N):
    index = bisect.bisect_left(L, L[i] + L[j]) #AC:約2.9秒
    count += max(0, index - j - 1)

"""
    失敗:回答は出るがTLE:ランダム配列1000本で約6.2秒
    index = bisect.bisect_left(L[j+1:],L[i] + L[j]) #TLEの原因?
    count += index
"""
print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B=[]
C=[]
for i in range(N):
    B.append(A[i]-1)
for i in range(N):
    C.append(A[i]+1)
mx=0
for i in range(max(C)+1):
    cnt=0
    for j in range(N):
        if i==A[j]:
            cnt+=1
        elif i==B[j]:
            cnt+=1
        elif i==C[j]:
            cnt+=1
    mx=max(mx,cnt)
print(mx)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B=[]
C=[]
for i in range(N):
    B.append(A[i]-1)
for i in range(N):
    C.append(A[i]+1)
D=[]
D=A+B+C
mx=0
E=[0]*10**6
for i in D:
    E[i]+=1
    
print(max(E))
### BUGGY CODE ###

n=int(input())
a=[]
for _ in range(n):
    num=int(input())
    if num not in a:
        a.append(num)
    else:
        a.remove(num)
print(len(a))

### FIXED CODE ###

n=int(input())
a={}
for _ in range(n):
    num=int(input())
    if num not in a:
        a[num]=1
    else:
        a[num]+=1
all_count=0
for _, count in a.items():
    if count%2==1:
        all_count+=1
print(all_count)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
game = {}

for i in range(1, n+1):
    game[i] = deque((map(int, input().split())))

count = 0
final = n*(n-1)//2
for day in range(1, 900000):
    finish = [0]*(n+1)
    possible = False
    for me in range(1, n+1):
        if finish[me] == 1 or game[me] == deque([]):
            continue

        you = game[me][0]
        if finish[you] == 1:
            continue
        else:
            if game[you][0] == me:
                finish[game[you].popleft()] = 1
                finish[game[me].popleft()] = 1
                possible = True
                count += 1
            else:
                continue

    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
game = {}

for i in range(1, n+1):
    game[i] = deque((map(int, input().split())))

count = 0
final = n*(n-1)//2
done = []

finish = [0] * (n + 1)
for me in range(1, n + 1):
    if finish[me] == 1 or game[me] == deque([]):
        continue

    you = game[me][0]
    if finish[you] == 1:
        continue
    else:
        if game[you][0] == me:
            done.append(you)
            done.append(me)
            finish[game[you].popleft()] = 1
            finish[game[me].popleft()] = 1
            possible = True
            count += 1
        else:
            continue

for day in range(2, 1000000):
    finish = [0]*(n+1)
    possible = False
    new_done = []
    for me in done:
        if finish[me] == 1 or game[me] == deque([]):
            continue

        you = game[me][0]
        if finish[you] == 1:
            continue
        else:
            if game[you][0] == me:
                finish[game[you].popleft()] = 1
                finish[game[me].popleft()] = 1
                new_done.append(me)
                new_done.append(you)
                possible = True
                count += 1
            else:
                continue
    done = new_done
    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
if n == 1:
    print("Yes")
else:
    l1 = l[1:]+[0]
    d = [i-j for (i,j) in zip(l1, l)][:-1]
    t = [i for i in d if i <= -2]
    if len(t) >= 1:
        print("No")
    else:
        if -1 not in d:
            print("Yes")
        else:
            num = d.count(-1)
            p = d.index(-1)
            if num == 1:
                print("Yes")
            else:
                d = d[p+1:]
                for i in range(num-1):
                    p = d.index(-1)
                    d1 = d[:p]
                    if sum(d1) <= 0:
                        pass
                    else:
                        d = d[p+1:]
                if len(d) == 0 or -1 not in d:
                    print("Yes")
                else:
                    print("No")

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
if n == 1:
    print("Yes")
else:
    l1 = l[1:]+[0]
    d = [i-j for (i,j) in zip(l1, l)][:-1]
    t = [i for i in d if i <= -2]
    if len(t) >= 1:
        print("No")
    else:
        if -1 not in d or d.count(-1)==1:
            print("Yes")
        else:
            p = d.index(-1)
            d = d[p+1:]
            s = ''.join(map(str, d))
            spl = s.split("-1") 
            if "" in spl[:-1]:
                print("No")
            else:
                if spl[-1] == "":
                    spl = [s for s in spl if s != '']
                    y = [int(i) for i in spl]
                    if 0 not in y:
                        print("Yes")
                    else:
                        print("No")
                else:
                    y = [int(i) for i in spl]
                    if 0 in y[:-1]:
                        print("No")
                    else:
                        print("Yes")
### BUGGY CODE ###

N, M = map(int,input().split())
ab = sorted([list(map(int,input().split())) for _ in range(M)])
c = []
for a, b in ab:
    if a == 1:
        c.append(b)
    if b == N:
        if a in c:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")


### FIXED CODE ###

N, M = map(int, input().split())
A = set()
B = set()

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.add(b)
    elif b == N:
        B.add(a)

if A & B:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

N, K, Q = map(int,input().split())
a = []
b = [0] * N
for i in range(Q):
    A = int(input())
    a.append(A)

for i in a:
    for j in range(1,N + 1):
        if i == j:
            b[j - 1] += 1
for i in b:
    if i > Q - K:
        print('Yes')
    else:
        print('No')






### FIXED CODE ###

N, K, Q = map(int,input().split())
a = []
b = [0] * N
for i in range(Q):
    A = int(input())
    a.append(A)

for i in a:
    b[i - 1] += 1
for i in b:
    if i > Q - K:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from itertools import combinations
from fractions import gcd

ans=0
aaa=0

a,b=map(int,input().split())
c=gcd(a,b)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
s=make_divisors(c)
#print(s)
for i in s:
    aaa=0
    if i>=3:
        for j in range(2,i):
            #print(i,j)
            if i%j==0:
                aaa=1
                break
            else:
                aab=0
    if aaa==0:
        ans+=1
print(ans)
    


### FIXED CODE ###

from itertools import combinations
from fractions import gcd

#coding:utf8
import random

def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True
ans=0

a,b=map(int,input().split())
c=gcd(a,b)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
s=make_divisors(c)
for i in s:
    ans=ans+is_prime3(i)
print(ans+1)