生物学家终于发明了修复 DNA 的技术，能够将包含各种遗传疾病的DNA片段进行修复。
为了简单起见，DNA 看作是一个由
A、G、C、T
构成的字符串。
修复技术就是通过改变字符串中的一些字符，从而消除字符串中包含的致病片段。
例如，我们可以通过改变两个字符，将 DNA 片段 AAGCAG 变为
AGGCAC，从而使得 DNA 片段中不再包含致病片段
AAG、AGC、CAG，以达到修复该DNA片段的目的。
需注意，被修复的 DNA 片段中，仍然只能包含字符
A、G、C、T。
请你帮助生物学家修复给定的 DNA 片段，并且修复过程中改变的字符数量要尽可能的少。
你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包 \(A\) 依赖软件包 \(B\)，那么安装软件包 \(A\) 以前，必须先安装软件包 \(B\)。同时，如果想要卸载软件包 \(B\)，则必须卸载软件包 \(A\)。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除 \(0\) 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而 \(0\) 号软件包不依赖任何一个软件包。依赖关系不存在环（若有 \(m \ (m \geq 2)\) 个软件包\(A_1, A_2, A_3, \ldots ,A_m\)，其中 \(A_1\) 依赖 \(A_2\)，\(A_2\) 依赖 \(A_3\)，\(A_3\) 依赖 \(A_4\)，……，\(A_{m−1}\) 依赖 \(A_m\)，而 \(A_m\) 依赖 \(A_1\)，则称这 \(m\) 个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为 \(0\)。
对于所有数据，\(n \leq 100000, \ q \leq 100000\)。
树链剖分是一个很常见的处理树上问题的算法，但之前一直没学 /kk，现在终于把这个坑补了。
这里只讲了重链剖分，不涉及其他剖分方式。
树链剖分是一种把树上问题转化为序列问题的算法。它可以将树上的一条路径所经过的点用序列中的若干条区间表示。
首先我们需要知道几个概念：重儿子、轻儿子、重边、轻边。我们定义对于一个节点 \(u\) 的儿子为 \(v\)，我们定义以 \(v\) 为根的子树中节点最多的子树所对应的 \(v\) 为重儿子，其余的 \(v\) 为轻儿子。父亲连向重儿子的边为重边，父亲连向轻儿子的边为轻边。如果同时有多个以 \(v\) 为根的子树节点数相同且最大，则选取任意一个 \(v\) 为重儿子，其余为轻儿子。这样对于每个非叶节点，我们都有一个重儿子和一个重边。
有 \(n (n \le 10^5)\) 个雪花。每个雪花是 \(6\) 个数组成的一个环。若两个环经过旋转（也可不旋转）后环上数字相等，则两个雪花相同。若两个环顺时针和逆时针数字相同则两个环也相同。判断是否有相同的雪花。
在这一轮的星际战争中，我方在宇宙中建立了 \(n\) 个据点，以 \(m\) 个单向虫洞连接。我们把终点为据点 \(u\) 的所有虫洞归为据点 \(u\) 的虫洞。
战火纷飞之中这些虫洞很难长久存在，敌人的打击随时可能到来。这些打击中的有效打击可以分为两类：
注意：摧毁只会导致虫洞不可用，而不会消除它的存在。
为了抗击敌人并维护各部队和各据点之间的联系，我方发展出了两种特种部队负责修复虫洞：
考虑到敌人打击的特点，我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复，处于可用状态，那么这个据点也是可用的。
我方掌握了一种苛刻的空间特性，利用这一特性我方战舰可以沿着虫洞瞬移到敌方阵营，实现精确打击。
为了把握发动反攻的最佳时机，指挥部必须关注战场上的所有变化，为了寻找一个能够进行反攻的时刻。总指挥认为：
总司令为你下达命令，要求你根据战场上实时反馈的信息，迅速告诉他当前的时刻是否能够进行一次反攻。
对于所有数据保证：\(1 \le n \le 5 \times {10}^5\)，\(1 \le m \le 5 \times {10}^5\)，\(1 \le q \le 5 \times {10}^5\)。
小 L 和小 Q 在玩一个策略游戏。
有一个长度为 \(n\) 的数组 \(A\) 和一个长度为 \(m\) 的数组 \(B\)，在此基础上定义一个大小为 \(n \times m\) 的矩阵 \(C\)，满足 \(C_{i j} = A_i \times B_j\)。所有下标均从 \(1\) 开始。
游戏一共会进行 \(q\) 轮，在每一轮游戏中，会事先给出 \(4\) 个参数 \(l_1, r_1, l_2, r_2\)，满足 \(1 \le l_1 \le r_1 \le n\)、\(1 \le l_2 \le r_2 \le m\)。
游戏中，小 L 先选择一个 \(l_1 \sim r_1\) 之间的下标 \(x\)，然后小 Q 选择一个 \(l_2 \sim r_2\) 之间的下标 \(y\)。定义这一轮游戏中二人的得分是 \(C_{x y}\)。
小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。
请问：按照二人的最优策略，每轮游戏的得分分别是多少？
对于所有数据，\(1 \le n, m, q \le {10}^5\)，\(-{10}^9 \le A_i, B_i \le {10}^9\)。对于每轮游戏而言，\(1 \le l_1 \le r_1 \le n\)，\(1 \le l_2 \le r_2 \le m\)。
小熊的地图上有 \(n\) 个点，其中编号为 \(1\) 的是它的家、编号为 \(2, 3, \ldots, n\) 的都是景点。部分点对之间有双向直达的公交线路。如果点 \(x\) 与 \(z_1\)、\(z_1\) 与 \(z_2\)、……、\(z_{k - 1}\) 与 \(z_k\)、\(z_k\) 与 \(y\) 之间均有直达的线路，那么我们称 \(x\) 与 \(y\) 之间的行程可转车 \(k\) 次通达；特别地，如果点 \(x\) 与 \(y\) 之间有直达的线路，则称可转车 \(0\) 次通达。
很快就要放假了，小熊计划从家出发去 \(4\) 个不同的景点游玩，完成 \(5\) 段行程后回家：家 \(\to\) 景点 A \(\to\) 景点 B \(\to\) 景点 C \(\to\) 景点 D \(\to\) 家且每段行程最多转车 \(k\) 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点 A \(\to\) 景点 B 的这段行程中，转车时经过的点可以是家、也可以是景点 C，还可以是景点 D \(\to\) 家这段行程转车时经过的点。
假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。
对于所有数据，保证 \(5 \le n \le 2500\)，\(1 \le m \le 10000\)，\(0 \le k \le 100\)，所有景点的分数 \(1 \le s_i \le {10}^{18}\)。保证至少存在一组符合要求的行程。
你有一个只含 \(0\) 和 \(1\) 的 \(n\) 位序列，你需要将这个序列排序。对于这个序列，你每次可以随机地选择两个数进行交换，求将这个序列排好序所交换次数的期望 \(\mod 998244353\)。
小 H 最近在研究随机算法。随机算法往往需要通过调用随机数生成函数（例如 Pascal 中的 \(\texttt{random}\) 和 C/C++ 中的 \(\texttt{rand}\)）来获得随机性。事实上，随机数生成函数也不是真正的「随机」，其一般都是按某个算法计算得来的。
比如，下面这个二次多项式递推算法就是一个常用算法：
算法选定非负整数 \(x_0,a,b,c,d\)，并采用如下公式递推进行计算。 \[\forall i \geq 1,\ x_i=(ax_{i-1}^2+bx_{i-1}+c)\bmod d\] 这样可以得到一个任意长度的非负整数 数列 \(\{x_i\}_{i \geq 1}\)。一般说来，我们认为这个 数列 是随机的。
利用随机序列 \(\{x_i\}_{i \geq 1}\)，我们还可以采用如下算法产生一个从 \(1\) 到 \(K\) 的 随机排列 \(\{T_i\}^K_{i \geq 1}\)：
此外，小 H 在这 \(K\) 次交换的基础上，又 额外 进行了 \(Q\) 次交换工作，对于第 \(i\) 次交换，小 H 会选定两个额外下标 \(u_i\) 和 \(v_i\)，并交换 \(T_{u_i}\) 和 \(T_{v_i}\) 的值。
为了检验这个随机生成算法的实用性，小 H 设计了如下问题：
小 H 有一个 \(N\) 行 \(M\) 列的棋盘，她首先按照上述过程，通过 \(N\times M+Q\) 次交换操作，生成一个 \(1 \sim N \times M\) 的随机排列 \(\{T_i\}^{N \times M}_{i \geq 1}\)，然后将这 \(N \times M\) 个数逐行逐列依次填入这个棋盘：也就是第 \(i\) 行第 \(j\) 列的格子上所填入的数应为 \(T_{(i-1)M+j}\)。
接着小 H 希望从棋盘的左上角，也就是第一行第一列的格子出发，每次向右走或向下走，在不走出棋盘的前提下，走到棋盘的右下角，也就是第 \(N\) 行第 \(M\) 列的格子。
小 H 把所经过格子上的数字都记录了下来，并 从小到大排序，这样，对于任何一条合法的移动路径，小 H 都可以得到一个长度为 \(N+M-1\) 的升序序列，我们称之为 路径序列。
小 H 想知道，她可能得到的 字典序最小 的 路径序列 应该是怎样的呢？
