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

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

F = [0]*(n+2) # [l,r+1): 1<=[l]<[r+1]<=n+1
for _ in range(k):
    l, r = map(int, input().split())
    F[l] += 1
    F[r+1] += -1

# print(F)
S = []
for i in range(n+1): # i:[0, n]
    if F[i] > 0: S.append(i)
    F[i+1] += F[i]

# print(F)
# print(n,k)
# print(S)

MOD = 998244353
dp = [0]*(n+1)  # [0,n]
dp[1] = 1

for i in range(1, n+1): # i:[1,n]
    for s in S:
        if i + s <= n:
            # print('s {} i {} n {}'.format(s,i,n))
            dp[i + s] += dp[i]

# print(dp)

print((dp[n] + MOD) % MOD)


### FIXED CODE ###

n, k = map(int, input().split())
LR = []
for _ in range(k):
    l, r = map(int, input().split())
    LR.append([l, r+1])

MOD = 998244353
dp = [0]*(n+1)  # [0,n]
dp[0] = 1
dp[1] = -1

for i in range(n): # i:[0,n-1]
    if i > 0: dp[i] += dp[i-1]
    for j in range(k):
        l, r = LR[j]
        if i+l < n:
            dp[i+l] += dp[i]
            dp[i+l] %= MOD
        if i+r < n:
            dp[i+r] -= dp[i]
            dp[i+r] %= MOD

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

import sys
input = sys.stdin.readline


n,m=map(int,input().split())
l=[[0,0] for _ in range(m)]
p=[[] for _ in range(n)]

for i in range(m):
        l[i][0],l[i][1]=map(int,input().split())
        p[l[i][0]-1].append(l[i][1])
for i in range(n):
        p[i].sort()
for i in range(m):
        for j in range(len(p[l[i][0]-1])):
                if p[l[i][0]-1][j]==l[i][1]:
                        c=j+1
                        print(str(l[i][0]).zfill(6)+str(c).zfill(6))
                        break

### FIXED CODE ###

import sys
input = sys.stdin.readline


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

for i in range(m):
        a,b=map(int,input().split())
        p[a-1].append([b,i])

for i in range(n):
        p[i].sort()
ans=[""]*m
for i in range(n):
        for j in range(len(p[i])):
                ans[p[i][j][1]]=str(i+1).zfill(6)+str(j+1).zfill(6)

for i in range(m):
        print(ans[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Apr  4 14:43:20 2019

@author: fumito
"""

def create_sub(lr,S):
    sub = S[int(lr[0])-1:int(lr[1])]
    return sub

def trans(sub):
    trans_list = []
    for i in sub:
        if i == "A":
            trans_list.append(0)
        elif i == 'C':
            trans_list.append(1)
        else:
            trans_list.append(2)
    return trans_list

def count(trans):
    count = 0
    flg = 0
    for j in trans:
        if j ==0:
            flg = 1 
        elif j == 1:
            if flg == 1:
                count += 1
                flg = 0
            else:
                flg = 0
        else:
            flg = 0
    return count


if __name__ == "__main__":
    N,Q = map(int,input().split())
    S = str(input())
    lr = [input().split() for i in range(Q)]
    
    ans = []
    for i in range(Q):
        Sub = create_sub(lr[i],S)
        Trans = trans(Sub)
        Count = count(Trans)
        ans.append(Count)
    for j in ans:
        print(j)


### FIXED CODE ###

N,Q = map(int,input().split())
S = str(input())
l,r = [0]*Q,[0]*Q
for i in range(Q):
    l[i],r[i] = map(int,input().split())
    
count_list = []
count = 0
count_list.append(0)
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C":
        count += 1
        count_list.append(count)
    else:
        count_list.append(count)
    
for j in range(Q):
    print(count_list[r[j]-1]-count_list[l[j]-1])
### BUGGY CODE ###

N = int (input ())
z = 1
while True:
  if N < (2+z)**2-(1+z+z):
    break
  else:
    z += 1
z -= 1
n = 1
while n < N+1:
  p = 0
  for X in range (z+1):
    for Y in range (z+1):
      for Z in range (z+1):
        if n == (X+Y+Z)**2-(X*Y+Y*Z+Z*X):
          if X > 0 and Y > 0 and Z > 0:
            p += 1
  print (p)
  n += 1

### FIXED CODE ###

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

N, M = map(int, input().split())
x = M//N
max = 1
for i in range(1, x+1):
    mod = M - (N-1)*i
    if mod%i == 0:
        if max < i:
            max = i
print(max)

### FIXED CODE ###

N, M = map(int, input().split())
x = M//N
max = 1
for i in range(x, 0, -1):
    mod = M - (N-1)*i
    if mod%i == 0:
        max = i
        break
print(max)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc077/tasks/arc084_a

"""
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
input = stdin.readline


def main(args):
    N = int(input())
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    A.sort()
    B.sort()
    C.sort()

    lut_A = {}
    for a in A:
        j = bisect_right(B, a)
        lut_A[a] = j

    lut_B = [0] * N
    for i, b in enumerate(B):
        j = bisect_right(C, b)
        lut_B[i] = N-j

    ans = 0

    for a in A:
        i = lut_A[a]
        ans += sum(lut_B[i:])

    print(ans)



if __name__ == '__main__':
    main(sys.argv[1:])
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc077/tasks/arc084_a

"""
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
input = stdin.readline


def main(args):
    N = int(input())
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    A.sort()
    B.sort()
    C.sort()

    lut_A = {}
    lut_C = {}
    for b in B:
        i = bisect_left(A, b)
        lut_A[b] = i
        j = bisect_right(C, b)
        lut_C[b] = N - j


    ans = 0
    for b in B:
        i = lut_A[b]
        j = lut_C[b]
        ans += i * j

    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

from itertools import combinations

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

for ai, aj in combinations(A, 2):
    if ai != aj:
        continue
    else:
        print('NO')
        break
else:
    print('YES')


### FIXED CODE ###

import numpy as np

N = int(input())
A = tuple(map(int, input().split()))
A = np.array(A)
A = np.sort(A)

for i in range(N):
    if (i > 0 and A[i-1] == A[i]) or (i < N-1 and A[i] == A[i+1]):
        print('NO')
        break
else:
    print('YES')
### BUGGY CODE ###

from collections import deque as dq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ab = []
c = []
inf = 10 ** 10
for i in range(M):
  ab.append(list(map(int, input().split())))
  c.append(list(map(int, input().split())))
dp = [[inf] * M for _ in range(2 ** 12)]
cc = []
for i in range(M):
  temp = 0
  for k in range(ab[i][1]):
    t = 2 ** (c[i][k] - 1)
    temp = temp | t
  cc.append(temp)
def less(a, b):
  if a > b:
    return b
  else:
    return a
#print(ab, c)
Q = dq([])
Q.append((0, 0))
vis = set()
while len(Q):
  q = Q.popleft()
  i, j = q[0], q[1]
  if j >= M:
    continue
  if q in vis:
    continue
  vis.add(q)
  temp = i ^ 0
  temp2 = cc[j]
  if j > 0:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = less(dp[temp][j - 1] + ab[j][0], dp[temp | temp2][j])
    dp[temp][j] = less(dp[temp][j], dp[temp][j - 1])
    dp[temp2][j] = less(ab[j][0], dp[temp2][j])
    Q.append((temp | temp2, j + 1))
    Q.append((temp, j + 1))
    Q.append((temp2, j + 1))
  else:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = less(ab[j][0], dp[temp | temp2][j])
    Q.append((temp | temp2, j + 1))
if dp[2 ** N - 1][-1] == inf:
  print(-1)
else:
  print(dp[2 ** N - 1][-1])



### FIXED CODE ###

from collections import deque as dq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ab = []
c = []
inf = 2 << 31
for i in range(M):
  ab.append(list(map(int, input().split())))
  c.append(list(map(int, input().split())))
dp = [[inf] * M for _ in range(2 ** 12)]
cc = []
for i in range(M):
  temp = 0
  for k in range(ab[i][1]):
    t = 2 ** (c[i][k] - 1)
    temp = temp | t
  cc.append(temp)
def less(a, b):
  if a > b:
    return b
  else:
    return a
#print(ab, c)
Q = dq([])
Q.append((0, 0))
vis = [[0] * M for _ in range(2 ** 12)]
while len(Q):
  q = Q.popleft()
  i, j = q[0], q[1]
  if j >= M:
    continue
  if vis[i][j] == 1:
    continue
  vis[i][j] = 1
  temp = i ^ 0
  temp2 = cc[j]
  if j > 0:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = less(dp[temp][j - 1] + ab[j][0], dp[temp | temp2][j])
    dp[temp][j] = less(dp[temp][j], dp[temp][j - 1])
    dp[temp2][j] = less(ab[j][0], dp[temp2][j])
    Q.append((temp | temp2, j + 1))
    Q.append((temp, j + 1))
    Q.append((temp2, j + 1))
  else:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = less(ab[j][0], dp[temp | temp2][j])
    Q.append((temp | temp2, j + 1))
if dp[2 ** N - 1][-1] == inf:
  print(-1)
else:
  print(dp[2 ** N - 1][-1])
### BUGGY CODE ###

#!/usr/bin/env pypy3

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    C = list(map(int, input().split()))
    P = [i-1 for i in P]
    ans = -1e19

    for si in range(N):
        index = si
        cycle =[]
        total = 0
        while True:
            index = P[index]
            cycle.append(C[index])
            total = total + C[index]
            if index == si:
                break
        cycle_length = len(cycle)
        count = 0
        for i in range(cycle_length):
            count  = count + cycle[i]
            if i+1 > K:
                break
            num = count
            if total > 0:
                cnt = (K - (i+1)) // cycle_length
                num = num + cnt*total
            ans = max(ans, num)
    print(ans)


main()


### FIXED CODE ###

#!/usr/bin/env pypy3

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    C = list(map(int, input().split()))
    P = [i-1 for i in P]
    ans = -1e19

    for si in range(N):
        index = si
        cycle =[]
        total = 0
        while True:
            index = P[index]
            cycle.append(C[index])
            total = total + C[index]
            if index == si:
                break
        cycle_length = len(cycle)
        count = 0
        for i in range(cycle_length):
            count  = count + cycle[i]
            if i+1 > K:
                break
            num = count
            if total > 0:
                cnt = (K - (i+1)) // cycle_length
                num = num + cnt*total
            ans = max(ans, num)
    print(ans)


main()
### BUGGY CODE ###


#スタック、キューを使う
from collections import deque

N,M = map(int,input().split())

G = [ set() for row in range(N)]

for i in range(M):
    A,B = map(int,input().split())
    G[A-1].add(B-1)
    G[B-1].add(A-1)

for i in range(N):
    G[i] = list(G[i])

#1グループに所属する最大数
ans = 0

#友達グループの数
count = 0

#各頂点の状態を色で表す WHITE:未訪問 GRAY:訪問中 BLACK:訪問完了
color = ['WHITE' for i in range(N)]

#訪問途中の頂点を退避しておくスタック
S = deque()

#次の要素を取り出す
def next(u):    
    #G[u]に格納されているまだ未訪問のノードを返す
    for i in range(len(G[u])):
        if color[G[u][i]] == 'WHITE':
            return G[u][i]
    return -1

def dfs(u):
    #始点uをスタックに追加
    S.append(u)
    color[u] = 'GRAY'
    global count
    count += 1
    #dequeは空のとき偽を返す
    while S:
        u = S[-1]    #スタックの頂点をuに格納
        v = next(u)
        #uに未訪問の隣接ノードがある
        if v != -1:
            color[v] = 'GRAY'
            count += 1
            S.append(v)
        else:
            S.pop()
            color[u]='BLACK'

#未訪問のuを始点として深さ優先探索
for i in range(N):
    count = 0
    if color[i] == 'WHITE':
        dfs(i)
        if count >= ans:
            ans = count

print(ans)


### FIXED CODE ###

"""
UnionFindにはいろいろな実装があるが, 本問ではparents配列にノード数を保持する実装だと非常に簡単に解ける. 
以下のようにしてノード数を保持する.
自身が子のとき, 親ノード番号を格納する.
自身が根のとき, ノード数を負の数で格納する.
つまり,　負の数のときは自身が根であり, その絶対値がその木のノード数を表す.
初期化時は、すべてのノードを−1で初期化する.
"""

N,M = map(int,input().split())

#UnionFind木の実装
#-1で初期化し、併合のたびに-1していく
par = [-1] * N  #親
rank = [0] * N #木の深さ

#木の根を求める
def find(x):
    #par[x]が負のとき(自分が代表のとき)、自身を返す
    if par[x] < 0:
        return x
    else:
        return find(par[x])

#xとyの属する集合を併合
def unite(x,y):
    x = find(x)
    y = find(y)
    #もとから同じ集合のときは何もしない
    if (x == y):
        return
    #x側を常に小さくする
    if par[x] > par[y]:
            x, y = y, x
    
    #x側に併合する、その際xの代表にノード数を加算する
    par[x] += par[y]
    par[y] = x
    

#xとyが同じ集合に属するかどうか
def same(x,y):
    return find(x) == find(y)

for i in range(M):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    unite(x,y)


ans = min(par)

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

N, M, P = map(int, input().split())
from collections import deque
edge1 = [[] for _ in range(N)]
edge2 = [[] for _ in range(N)]
for i in range(M):
    a,b,c= map(int, input().split())
    edge1[a-1].append([b-1,P-c])
    edge2[b-1].append([a-1,P-c])
edges1 = []
d = deque([0])
visited1 = {}
while len(d):
    v = d.popleft()
    for u,w in edge1[v]:
        if (w,v,u) not in visited1:
            visited1[(w,v,u)]=True
            edges1.append([w,v,u])
            d.append(u)
edges2 = []
d = deque([N-1])
visited2 = {}
while len(d):
    v = d.popleft()
    for u,w in edge2[v]:
        if (w,u,v) not in visited2:
            visited2[(w,u,v)]=True
            edges2.append([w,u,v])
            d.append(u)
new_edge = []
for e in edges1:
    if e in edges2:
        new_edge.append(e)
d = [float('inf')]*N
d[0] = 0
n = 0
while True:
    n += 1
    update = False
    for w,v,u in new_edge:
        if d[u]>d[v]+w:
            d[u] = d[v]+w
            update = True
    if update == False:
        break
    if n==N and update==True:
        print(-1)
        exit()
print(max(0,-d[-1]))

### FIXED CODE ###

N, M, P = map(int, input().split())
from collections import deque,defaultdict
edge1 = [[] for _ in range(N)]
edge2 = [[] for _ in range(N)]
for i in range(M):
    a,b,c= map(int, input().split())
    edge1[a-1].append([b-1,P-c])
    edge2[b-1].append([a-1,P-c])
edges1 = set()
d = deque([0])
visited1 = defaultdict(lambda: False)
while len(d):
    v = d.popleft()
    for u,w in edge1[v]:
        if visited1[w*10**8+v*10**4+u] == False:
            visited1[w*10**8+v*10**4+u] = True
            edges1.add(w*10**8+v*10**4+u)
            d.append(u)
edges2 = set()
d = deque([N-1])
visited2 = defaultdict(lambda: False)
while len(d):
    v = d.popleft()
    for u,w in edge2[v]:
        if visited2[w*10**8+u*10**4+v] == False:
            visited2[w*10**8+u*10**4+v] = True
            edges2.add(w*10**8+u*10**4+v)
            d.append(u)
new_edge = list(edges1&edges2)
d = [10**10]*N
d[0] = 0
n = 0
while True:
    n += 1
    update = False
    for e in new_edge:
        w = e//10**8
        v = e%10**8//10**4
        u = e%10**4
        if d[u]>d[v]+w:
            d[u] = d[v]+w
            update = True
    if update == False:
        break
    if n==N and update==True:
        print(-1)
        exit()
print(max(0,-d[-1]))
### BUGGY CODE ###

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

e_p = []
for i in range(n):
    e_p.append(0.5*p[i]+0.5)

max = 0
for i in range(n-k+1):
    s = sum(e_p[i:i+k])
    if s > max:
        max = s

print(max)


### FIXED CODE ###

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

e_p = []
for i in range(n):
    e_p.append(0.5*p[i]+0.5)


ans = []
s = sum(e_p[:k])
ans.append(s)
for i in range(1,n-k+1):
    s -= e_p[i-1]
    s += e_p[i+k-1]
    ans.append(s)
print(max(ans))
### BUGGY CODE ###

def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    K = list(map(int, input().split()))
    d_list = [0] * N
    m_list = [0] * N
    c_list = [0] * N
    M_list = [0] * N
    for index, s in enumerate(S):
        if s == 'D':
            d_list[index] += 1
        elif s == 'M':
            m_list[index] += d_list[index - 1]
            M_list[index] += 1
        elif s == 'C':
            c_list[index] += m_list[index - 1]
        d_list[index] += d_list[index - 1]
        m_list[index] += m_list[index - 1]
        c_list[index] += c_list[index - 1]
        M_list[index] += M_list[index - 1]



    for k in K:
        d = d_list[k - 1]
        m = m_list[k - 1]
        c = c_list[k - 1]
        M = M_list[k - 1]

        for index, x in enumerate(S[k:]):
            if S[index] == 'D':
                m -= M
                d -= 1
            elif S[index] == 'M':
                M -= 1

            if x == 'D':
                d += 1
            elif x == 'M':
                m += d
                M += 1
            elif x == 'C':
                c += m            
        print (c)                


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    K = tuple(map(int, input().split()))
    d_list = [0] * N
    m_list = [0] * N
    c_list = [0] * N
    M_list = [0] * N
    for index, s in enumerate(S):
        if s == 'D':
            d_list[index] += 1
        elif s == 'M':
            m_list[index] += d_list[index - 1]
            M_list[index] += 1
        elif s == 'C':
            c_list[index] += m_list[index - 1]
        d_list[index] += d_list[index - 1]
        m_list[index] += m_list[index - 1]
        c_list[index] += c_list[index - 1]
        M_list[index] += M_list[index - 1]



    for k in K:
        d = d_list[k - 1]
        m = m_list[k - 1]
        c = c_list[k - 1]
        M = M_list[k - 1]

        for index, x in enumerate(S[k:]):
            if S[index] == 'D':
                m -= M
                d -= 1
            elif S[index] == 'M':
                M -= 1

            if x == 'D':
                d += 1
            elif x == 'M':
                m += d
                M += 1
            elif x == 'C':
                c += m            
        print (c)                


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

import numpy as np

in_list = []
for i in range(2):
    in_list.append(input())
N,S = in_list
N = int(N)
res = 0
find_ind = []
for i in ['R','G','B']:
    find = (np.array(list(S)) == i)
    find_ind.append(find.argsort()[::-1][:sum(find)])
    # print(len(find_ind[-1]))

find_ind = np.array(find_ind)
rg_diff = find_ind[0] - find_ind[1].reshape(len(find_ind[1]),1)
rg_diff = np.abs(rg_diff)
# print(rg_diff)
gb_diff = find_ind[1] - find_ind[2].reshape(len(find_ind[2]),1)
gb_diff = np.abs(gb_diff)
gb_diff = gb_diff.T
# print(gb_diff)
br_diff = find_ind[2] - find_ind[0].reshape(len(find_ind[0]),1)
br_diff = np.abs(br_diff)

# print(br_diff)

res = 0
# print(len(gb_diff), len(rg_diff))
for i in range(len(find_ind[1])):
    res += np.sum((rg_diff[i] - gb_diff[i].reshape(len(gb_diff[i]),1)) == 0)
for i in range(len(find_ind[0])):
    res += np.sum((rg_diff[:,i] - br_diff[i].reshape(len(br_diff[i]),1)) == 0)
br_diff = br_diff.T
for i in range(len(find_ind[2])):
    res += np.sum((gb_diff[:,i] - br_diff[i].reshape(len(br_diff[i]),1)) == 0)


print(len(find_ind[0])*len(find_ind[1])*len(find_ind[2])-res)



### FIXED CODE ###

import numpy as np
in_list = []
for i in range(2):
    in_list.append(input())
N,S = in_list
N = int(N)

res = 0
for i in range(N-2):
    n = 1
    while True:
        j = i+n
        k = j+n
        if k > N-1: break
        res += (S[i] != S[j] and S[j] != S[k] and S[k] != S[i])
        n += 1
    
    
rgb = S.count("R") * S.count("G") * S.count("B")
print(rgb - res)
### BUGGY CODE ###

n, m = map(int, input().split())
info = sorted([list(map(int, input().split())) for _ in range(m)])

q = []
t = m
for i in range(m):
	if info[i][0] == 1:
		q.append(info[i][1])
	else:
		t = i
		break

for j in range(t, m):
	if info[j][0] in q:
		if info[j][1] == n:
			print("POSSIBLE")
			break
else:
	print("IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())
side1 = set()
side2 = set()

for i in range(m):
	a, b = map(int, input().split())

	if a == 1:
		side1.add(b)
	
	elif b == n:
		side2.add(a)

print(("" if side1 & side2 else "IM") + "POSSIBLE")
### BUGGY CODE ###

import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i].append(i+1)
    g[i+1].append(i)
g[x-1].append(y-1)
g[y-1].append(x-1)

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)

ans = [0]*n
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    # que = queue.Queue()
    # que.put(start)
    q = deque([start])
    while q:
        # v = que.get()
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v]+1
                # que.put(nv)
                q.append(nv)
    for i in dist:
        ans[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
# for i in range(1,n):
#     # print(int(np.count_nonzero(d==i)/2))
#     print(int(ans[i]/2))
print(' '.join(str(i//2) for i in ans[1:]))


### FIXED CODE ###

def main():
    from collections import deque
    n,x,y=map(int,input().split())
    e=[[]for _ in range(n)]
    for i in range(n-1):
        e[i]+=i+1,
        e[i+1]+=i,
    e[x-1]+=y-1,
    e[y-1]+=x-1,
    a=[0]*n
    for s in range(n):
        d=[-1]*n
        d[s]=0
        q=deque([s])
        add,pop=q.append,q.popleft
        while q:
            v=pop()
            for w in e[v]:
                if d[w]<0:
                    d[w]=d[v]+1
                    add(w)
        for i in d:a[i]+=1
    print(' '.join(str(i//2)for i in a[1:]))
main()
### BUGGY CODE ###

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

inv_A = 0
for i in range(0,N):
  for j in range(0,N):
    if i<j and A[i] > A[j]:
      inv_A += 1

inv_sorted_A = 0
for i in range(0,N):
  for j in range(0,N):
    if i<j and sorted_A[i] < sorted_A[j]:
      inv_sorted_A += 1

count = inv_A
for i in range(1,K):
  count += (inv_sorted_A * i) % 1000000007 + inv_A % 1000000007

print(count)  

### FIXED CODE ###

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

inv_A = 0
for i in range(0,N):
  for j in range(0,N):
    if i<j and A[i] > A[j]:
      inv_A += 1

inv_sorted_A = 0
for i in range(0,N):
  for j in range(0,N):
    if i<j and sorted_A[i] < sorted_A[j]:
      inv_sorted_A += 1

if K == 1:
  print(inv_A)
else:  
  count = inv_sorted_A * K * (K-1) // 2  + inv_A * K 
  print(count % 1000000007)
### BUGGY CODE ###

N,K = map(int,input().split())
ans = 0
for a in range(1,N+1):
    for b in range(1,N+1):
        for c in range(1,N+1):
            if ((a+b) % K == 0) and ((a+c) % K == 0) and ((b+c) % K == 0):
                ans += 1
            else:
                continue
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
if K % 2 != 0:
    case1 = len([n for n in range(1,N+1) if n % K ==0])
    print(case1 ** 3)
else:
    case1 = len([n for n in range(1,N+1) if n % K ==0])
    case2 = len([n for n in range(1,N+1) if n % K == K //2])
    print(case1**3 + case2**3)
### BUGGY CODE ###

n,k = map(int,input().split())
p_list = list(map(int,input().split()))
ans = 0
save = 0
sum = 0
for i in range(n-k+1):
    dum = 0
    for j in range(k):
        dum += p_list[i+j]
    if dum > ans:
        save = i
        ans = dum
for i in range(save,save+k):
    sum += p_list[i]*0.5 + 0.5
print(sum)

### FIXED CODE ###

n,k = map(int,input().split())
p_list = list(map(int,input().split()))
ans = 0
save = 0
sum = 0
ans_o = 0
ans_check = 0
for j in range(k):
    ans_check += p_list[0 + j]
    ans_o += p_list[0 + j]
for i in range(1,n-k+1):
    ans = ans_o-p_list[i-1]+p_list[i+k-1]
#    print(ans)
    if ans > ans_check:
        save = i
        ans_check = ans
    ans_o = ans
    #print(save)

for i in range(save,save+k):
    sum += p_list[i]*0.5 + 0.5
print(sum)
### BUGGY CODE ###

import fractions

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

x = fractions.gcd(a,b)
ans = []

i = 2
y = int(x**0.5)
while True:
    if x%i == 0:
        x //= i
        ans.append(i)
    elif x == 1:
        break
    else:
        i += 1

print(len(set(ans))+1)

### FIXED CODE ###

import fractions

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

x = fractions.gcd(a,b)
ans = []

i = 2
y = int(x**0.5)
for j in range(10000000):
    if x%i == 0:
        x //= i
        ans.append(i)
        i = 2
        y = int(x**0.5)
    elif i == y:
        ans.append(x)
        break
    else:
        i += 1

print(len(set(ans))+1)