物资运输

题号：NC204613
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

抗疫一线，物资的运输和分配工作十分重要。尤其是疫情严重地区，合理分配资源更加重要。

我们简化城市物资运输网络，假设一共有 $N$ 个医院。

对于第 $i$ 家医院，有以下几条联通的路径：

所有边都是双向边。现在为了预估物资运输的能力，你需要知道中心物资点到每个医院的最大流。

输入数据共三行，第一行为医院个数 $N$ 。( $2 \leq N \leq 10^6$ )

第二行包括三个整数 $a_1, p_a, q_a$ 。为了简化输入， $\{a_n\}$ 由以下递推式生成： $a_i = p_aa_{i - 1} \pmod{q_a}$ ，含义如题目描述所述。( $a_1,p_a,q_a$ 均在 int 范围内且均为正数)

第三行包括三个整数 $b_1, p_b, q_b$ 。为了简化输入， $\{b_n\}$ 由以下递推式生成： $b_i = p_bb_{i - 1} \pmod{q_b}$ ，含义如题目描述所述。( $b_1,p_b,q_b$ 均在 int 范围内且均为正数)

由于输出较多，你只需要输出中心物资点到每个医院的最大流的和。

示例1

复制

5
7 2 13
5 3 11

复制

假设中心物资点为 $0$ 号节点， $1$ 到 $N$ 号医院为 $1$ 到 $N$ 号节点，城市网络图如下。

从中心物资点到每一个医院的最大流分别为 $20,9,7,8,20$ ，其和为 $20+9+7+8+20=64$ 。