def gcd(a, b):
  if b == 0:
    reutrn a
  a, b = b, a % b
  return gcd(a, b)

def exgcd(a, b):
  if b == 0:
    return 1, 0
  else:
    x, y = exgcd(b, a % b)
    return y, (x - a // b * y)

def CRT(k, a, r):
  n = 1; ans = 0
  for i in range(1, k + 1):
    n = n * r[i]
  for i in range(1, k + 1):
    m = n // r[i]
    b, y = exgcd(m, r[i]) # b * m mod r[i] = 1
    while b < 0:
      b += r[i]
    ans = (ans + a[i] * m * b) % n
    return (ans % n + n) % n

r = [0, 3, 5, 7]
a = [0, 2, 3, 2]
print(CRT(3, a, r))

def isPrime(n):
	prime = [True] * n
  for i in range(2, n + 1):
    if prime[i]:
      for i in range(i * 2, n + 1, i):
        prime[i] = False
  return [i for i in range(2, n) if prime[i]]

def buildGraph(numCourses: int, prerequisites: List[List[int]]) -> List[List[int]]:
  # 图中共有 numCourses 个节点
  graph = [[] for _ in range(numCourses)]
  for edge in prerequisites:
    from_, to_ = edge[1], edge[0]
    # 添加一条从 from 指向 to 的有向边
    # 如果是无向图，则再反向添加一次
    graph[from_].append(to_)
  return graph

# 记录被遍历过的节点
visited = []
# 记录从起点到当前节点的路径
onPath = []

def traverse(graph, s):
  if visited[s]:
    return
  # 经过节点 s，标记为已遍历
  visited[s] = True
  # 做选择：标记节点 s 在路径上
  onPath[s] = True
  for neighbor in graph.neighbors(s):
    traverse(graph, neighbor)
  # 撤销选择：节点 s 离开路径
  onPath[s] = False

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
  graph = self.buildGraph(numCourses, prerequisites)
  self.visited = [False] * numCourses
  self.onPath = [False] * numCourses
  self.hasCycle = False
  for i in range(numCourses):
    self.traverse(graph, i)
  return not self.hasCycle

def traverse(self, graph, s):
  if self.onPath[s]:
    self.hasCycle = True
  if self.visited[s] or self.hasCycle:
    return
  self.visited[s] = True
  self.onPath[s] = True
  for t in graph[s]:
    self.traverse(graph, t)
  self.onPath[s] = False

def buildGraph(self, numCourses, prerequisites):
  # 代码见前文

def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
  # 记录后序遍历结果
  postorder = []
  # 记录是否存在环
  hasCycle = False
  visited = [False] * numCourses
  onPath = [False] * numCourses

  # 建图函数
  def buildGraph(numCourses, prerequisites):
    # 代码见前文
    pass

  # 图遍历函数
  def traverse(graph, s):
    if onPath[s]:
      # 发现环
      hasCycle = True
    if visited[s] or hasCycle:
      return
    # 前序遍历位置
    onPath[s] = True
    visited[s] = True
    for t in graph[s]:
      traverse(graph, t)
    # 后序遍历位置
    postorder.append(s)
    onPath[s] = False

  graph = buildGraph(numCourses, prerequisites)
  # 遍历图
  for i in range(numCourses):
    traverse(graph, i)
  # 有环图无法进行拓扑排序
  if hasCycle[0]:
    return []
  # 逆后序遍历结果即为拓扑排序结果
  return postorder[::-1]

def __init__(self):
  # 记录图是否符合二分图性质
  self.ok = True
  # 记录图中节点的颜色，False和True代表两种不同颜色
  self.color = []
  # 记录图中节点是否被访问过
  self.visited = []

# 主函数，输入邻接表，判断是否是二分图
def isBipartite(self, graph: List[List[int]]) -> bool:
  n = len(graph)
  self.color = [False] * n
  self.visited = [False] * n
  # 因为图不一定是联通的，可能存在多个子图
  # 所以要把每个节点都作为起点进行一次遍历
  # 如果发现任何一个子图不是二分图，整幅图都不算二分图
  for v in range(n):
    if not self.visited[v]:
      self.traverse(graph, v)
      if not self.ok:
        break
  return self.ok

# DFS 遍历框架
def traverse(self, graph: List[List[int]], v: int) -> None:
  # 如果已经确定不是二分图了，就不用浪费时间再递归遍历了
  if not self.ok:
    return

  self.visited[v] = True
  for w in graph[v]:
    if not self.visited[w]:
      # 相邻节点 w 没有被访问过
      # 那么应该给节点 w 涂上和节点 v 不同的颜色
      self.color[w] = not self.color[v]
      # 继续遍历 w
      self.traverse(graph, w)
    else:
      # 相邻节点 w 已经被访问过
      # 根据 v 和 w 的颜色判断是否是二分图
      if self.color[w] == self.color[v]:
        # 若相同，则此图不是二分图
        self.ok = False
        return

import heapq
class Prim:
  # 核心数据结构，存储「横切边」的优先级队列
  def __init__(self, graph: List[List[int]]):
    self.graph = graph
    self.pq = []  # PriorityQueue<int[]> 的实现
    self.inMST = [False] * len(graph)  # 类似 visited 数组的作用，记录哪些节点已经成为最小生成树的一部分
    self.weightSum = 0  # 记录最小生成树的权重和

    self.inMST[0] = True  # 随便从一个点开始切分都可以，我们不妨从节点 0 开始
    self.cut(0)

    # 不断进行切分，向最小生成树中添加边
    while self.pq:
        # 按照边的权重从小到大排序
      edge = heapq.heappop(self.pq)
      to = edge[1]  # 表示相邻节点
      weight = edge[2]  # 表示这条边的权重
      if self.inMST[to]:  # 节点 to 已经在最小生成树中，跳过。否则这条边会产生环
        continue
      self.weightSum += weight  # 将边 edge 加入最小生成树
      self.inMST[to] = True
      self.cut(to)  # 节点 to 加入后，进行新一轮切分，会产生更多横切边

  # 将 s 的横切边加入优先队列
  def cut(self, s):
    for edge in self.graph[s]:  # 遍历 s 的邻边
      to = edge[1]  # 相邻的节点
      if self.inMST[to]:  # 相邻接点 to 已经在最小生成树中，跳过
        continue
      heapq.heappush(self.pq, edge)  # 加入横切边队列

  # 最小生成树的权重和
  def weightSum(self) -> int:
    return self.weightSum

  # 判断最小生成树是否包含图中的所有节点
  def allConnected(self) -> bool:
    for i in range(len(self.inMST)):
      if not self.inMST[i]:
        return False
    return True

import heapq
from typing import List
# 假设 graph 是一个邻接矩阵，graph[i][j] 是从节点 i 到节点 j 的距离
def dijkstra(start: int, graph: List[List[int]]) -> List[int]:
  V = len(graph)
  distTo = [float('inf')] * V
  distTo[start] = 0
  pq = [(0, start)]  # 使用元组 (distance, node)，以便按照 distance 进行排序
  while pq:
    (dist, curNodeID) = heapq.heappop(pq)
    if dist > distTo[curNodeID]:
      continue
    for weight, nextNodeID in graph[curNodeID]:
      if weight is not None:  # 如果两个节点之间有边
        distToNextNode = distTo[curNodeID] + weight
        if distTo[nextNodeID] > distToNextNode:
          distTo[nextNodeID] = distToNextNode
          heapq.heappush(pq, (distToNextNode, nextNodeID))
  return distTo