title: 【模板】多项式幂函数（加强版）

background:
[普通版传送门](https://www.luogu.com.cn/problem/P5245)

模板题，无背景。

description:
给定一个 $n-1$ 次多项式 $A(x)$，求一个在 $\bmod\ x^n$ 意义下的多项式 $B(x)$，使得 $B(x) \equiv (A(x))^k \ (\bmod\ x^n)$。

多项式的系数在 $\bmod\ 998244353$ 的意义下进行运算。

inputFormat:
第一行两个整数 $n,k$。

接下来 $n$ 个整数，依次表示 $A(x)$ 的系数 $a_0, a_1,...,a_{n-1}$。

outputFormat: 输出 $n$ 个整数，依次表示 $B(x)$ 的前 $n$ 项系数 $b_0, b_1,...,b_{n-1}$ 在模 $998244353$ 意义下的最小自然数值。


title: [LnOI2019SP] 快速多项式变换(FPT)

type: P

description:
这是一道构造题。

诗乃在心中想了一个$n+1$项的多项式$f(x)$。第$i$项次数为$i$，系数为$a_i$：

$$f(x)=a_0+a_1x+a_2x^2+a_3x^3+ \cdots +a_nx^n$$

给定$m$以及$f(m)$的值（即当$x=m$时此多项式的值），请构造多项式，满足任意$0 \leq a_i < m$且$a_i$为非负整数。

设你构造的多项式项数为$n$，则必须满足$1 ≤ n ≤ 100$且最高项系数不为零。

inputFormat: 两个整数，$m$、$f(m)$。

outputFormat:
第一行输出正整数$n$，表示多项式的项数。

第二行依次输出$n$个非负整数（$a_0$至$a_{n-1}$），每个非负整数之间用**一个**空格隔开。

hint:
对于20%的数据， $ 2 ≤ m ≤ 5. $

对于100%的数据，
 $ 2 ≤ m,f(m) ≤ 10^{18}.$

所有数据的时间限制为 $1000ms$，空间限制为 $256MB$，可开启O2优化。


title: [LnOI2019] 东京夏日相会

background:
![avartar](https://cdn.luogu.com.cn/upload/pic/52827.png)

「听说有烟火大会在下周举办呢」

「诶？ 那种人多的地方我不太喜欢呢」

「啊， 那我还是问问别人好了╭(╯^╰)╮」

「唔， 好像还是很有趣呢。我说不定会去吧(⊙﹏⊙)b」

description:
当然上面发生的事情和Abbi没有任何一点关系。作为一只长(zhang)了脖子的单身鹿，Abbi只能在家拿着“望远镜”孤独地在远处欣赏烟火大会。

![avartar](https://cdn.luogu.com.cn/upload/pic/52828.png)

~~啥？什么狙击枪？这是望远镜啊！（认真）~~

为了看到夜空中所有的烟花，Abbi需要调整“望远镜”的放大倍数与位置。夜空可近似地看成一个平面，其中第$i$朵烟花可以近似地看作一个圆心为$(x_i,y_i)$，半径为$r_i$的圆。

Abbi的望远镜视野可以近似地看作一个圆。因为调整放大倍数很累，因此Abbi希望在满足所有烟花都**完整**地出现在视野中的同时，视野的半径尽可能小。请你求出视野的圆心坐标与半径。

inputFormat:
第一行一个整数$n$，表示有$n$朵烟花。

第二行~第$n+1$行，每行三个实数$x_i$、$y_i$和$r_i$，表示每朵烟花的圆心坐标与半径。

outputFormat: 第一行三个实数，$X$、$Y$、$R$，分别表示望远镜视野的圆心坐标与半径。你的答案中半径与标准答案的误差不得超过$0.01$，圆心坐标与标准答案的误差不得超过$0.04$。


title: [LnOI2019] 第二代图灵机

background:
1989年，Abbi提出了一种抽象的计算模型 —— 第二代图灵机 (The 2nd Generation Turing Machine）。

所谓的第二代图灵机就是指一个抽象的机器，它有一条长度为$n$的纸带，纸带分成了$n$个小方格，每个方格有不同的**颜色**和不同的**数字**。

![avatar](https://cdn.luogu.com.cn/upload/pic/52955.png)

description:
第二代图灵的基本思想是用机器来模拟鹿们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：

1. 在纸带上的一格写数字.
2. 在纸带上的一段区间着色.

为了测试第二代图灵机的性能，Abbi提出了一种用于判定机器是否具有智能的试验方法，即图灵试验。

1. 求$[l,r]$中包含所有(一共$c$种)颜色，数字和最小的子区间的数字和。
2. 求$[l,r]$中没有重复颜色，数字和最大的子区间的数字和。

你需要为第二代图灵机编写算法，使他能通过所有的图灵试验。为保证试验的正确性，所有数据都是随机生成的。

inputFormat:
第一行输入两个正整数$n,m,c$，分表表示纸带长度，操作次数和颜色总数。

第二行$n$个非负整数，表示每个格子上的初始数字$a_i$。

第三行$n$个非负整数，表示每个格子上的颜色编号$b_i$。

接下来$m$行，对应每一次操作。

操作一格式：$1\quad x\quad y$，表示将第$x$位的数字改为$y$，保证$1≤y≤10000$.

操作二格式：$2\quad l\quad r\quad y$，表示将区间$[l,r]$的颜色全部改为$y$，保证$1≤y≤c$.

操作三格式：$3\quad l\quad r$，表示询问区间$[l,r]$中包含所有(一共$c$种)颜色，数字和最小的子区间的数字和。

操作四格式：$4\quad l\quad r$，表示询问区间$[l,r]$中没有重复颜色，数字和最大的子区间的数字和。

outputFormat:
对于操作三和操作四，输出一个整数，表示最小或最大的数字和。

对于操作三，若不存在满足条件的子区间，请输出$-1$。

hint:
![avatar](https://cdn.luogu.com.cn/upload/pic/53113.png)

**由于数据规模较大，建议用以下方法读入一个正整数。**

```cpp
void read(int &x){
	char ch;
	while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
```

tags: 珂朵莉树,颜色段均摊,ODT


title: 序列

description:
构建一个N个点的有向图G，初始没有任何边。接下来构建一个长度为E的边的序列A，序列中每条边都是满足1≤s,t≤N且s≠t的有向边(s,t)，且序列中的边互不相同。按照顺序把这些边加入到G中，每次加入后计算当前图的强连通分量个数并记录下来，得到一个新的长度为E的正整数序列B。如果两个边的序列得到的B相同则称它们本质相同。

请问有多少种本质不同的边的序列，你只要求出答案对$10^9+7$取模后的结果。

inputFormat: 输入一行，一个正整数N表示有向图G的点数。

outputFormat: 输出一行N×(N-1)个由空格隔开的整数，第i个数表示当E=i时的答案。

hint:
Subtask 1 (5pts)：N≤5。

Subtask 2 (10pts)：N≤10。

Subtask 3 (15pts)：N≤20。

Subtask 4 (15pts)：N≤30。

Subtask 5 (15pts)：N≤50。

Subtask 6 (20pts)：N≤100。

Subtask 7 (20pts)：无特殊限制

对于全部数据：1≤N≤400。

前6个子任务限时1s，第7个3.5s。

## 代码长度限制：10kb 超过这个限制赛后将会被标记为无效。


title: [Cnoi2019] 青染之心

background: 这里原本有着一个史诗般的可歌可泣的背景故事，可是这里空太小，写不下。

description:
Cirno 初始有一个空的物品序列，一个大小为 $V$ 的背包，现在你有 $q$ 个操作，分为两种：

- `add x y`：表示加入一种体积为 $x$, 价值为 $y$ 的物品到序列末尾。
- `erase`：表示删除序列末尾的物品。

在每个操作结束以后，你需要求出：

假设序列中的每种物品都有无穷多个，Cirno的背包可以装下的物品最大价值和。

inputFormat:
第一行，两个整数，$q$，$V$ 分别表示操作数和背包大小。

以下 $q$ 行，每行一个操作。

outputFormat: $q$ 行，每行表示每次操作后的答案。


title: [Cnoi2019] 人形演舞

background: 由于出题人都退役了, 所以题目背景咕咕咕~了.

description:
Cirno 与 Marisa 之间有一个博弈:

首先给定 一个 **可重正整数集合** $V$, 所有的数字都是在 $[1, m]$ 之间。

每次一个人可以选取 $x \in V, y \in [1, x]$, 且 $ x \oplus y \in [0, x)$ , 然后把  $x$ 变为 $x \oplus y$。

$\oplus$ 表示按位异或。

当一个人不能操作时, 则视作失败。

假定 Cirno 和 Marisa 都使用最优策略。

现在 Cirno 想知道自己先手时获胜的方案数对 $998244353$ 取模后是多少。

inputFormat: 一行，两个整数 $|V|, m$

outputFormat: 一行，表示答案.


title: [Cnoi2019] 最终幻想

background: 理论上来说，压轴的应该是一道数据结构题，可是它咕咕咕~了.

description:
你有一个 $n$ 维超球, 求使用 $k$ 个 $n-1$ 维超平面可以将这个 $n$ 维超球划分成多少个 $n$ 维块。

答案对 $998244353$ 取模。

inputFormat: 输入两个数 $n$, $k$.

outputFormat: 一行，表示答案。

hint:
Subtask1( 21pts ) : $n \le 10^6$

Subtask2( 7pts )   : $k \le n$

Subtask3( 72pts ) : 无特殊限制

对于 100% 的数据 $n, k \in [1,998244353)$

~~其实可以出高精度范围的，但是出题人咕咕咕~了。~~


title: [Cnoi2019] 数学作业

background:
幻想乡，春节，万家灯火。

Kamishirasawa Keine 老师自然不会放过这么好的机会，，，布置作业。

description:
现在 Cirno 手上有着 $T$ 天的作业，每天的作业可以用一个二元组 $( n, V )$ 表示，其中 $n$ 表示集合的大小， $V$ 表示大小为 $n$ 的集合. 现在，Cirno 需要求出的是 $V$ 的所有子集的异或和的和，答案对 $998\,244\,353$ 取模。

形式化地：

$$
\text{ans}\equiv \sum_{S \subseteq V} \mathop{\bigoplus}\limits_{ s \in S } s \pmod {998\,244\,353}
$$

inputFormat:
第一行，一个整数 $T$。

以下 $T$ 行，每行一个二元组 $( n, V )$。

outputFormat: $T$ 行，每行一个整数，表示答案。

hint:
- Subtask 1（17pts）：$ T, n \le 8 $；
- Subtask 2（22pts）：$ T, n \le 100 $；
- Subtask 3（61pts）：$ T, n \le 3\times10^6 $。

对于 $100\%$ 的数据，$ \sum |V| \le 3 \times 10^6, 0 \le p \le 10^9$。


title: [Cnoi2019] 雪松树之约

background: 由于 Cirno 突然犯懒, 所以背景故事咕咕咕了。

description:
Cirno 定义了一种图：圆柱网络 $G( L, x )$ 。

$G(L, x)$ 表示一个有 $L \times x$ 个节点的图。

其中每个节点用一个整数二元组 $( a, b )$ 表示 $( 1 \le a \le L, 1 \le b \le x )$。

对于 $ \forall i \in (1,L], \ j \in (0,x]$ , 节点 $(i, j)$ 与节点 $(i - 1, j)$ 之间有一条边。

对于 $ \forall i \in [1,L], \ j \in (0,x)$ , 节点 $(i, j)$ 与节点 $(i, j +1)$ 之间有一条边。

对于 $ \forall i \in [1,L]$ 节点 $(i, x)$ 与 节点 $(i, 1)$ 之间有一条边。

现在 Cirno 想知道 $G( L, x )$ 的 **独立集** 的个数。

由于你不会高精度，所以你需要将答案对 $998244353$ 取模。

inputFormat: 一行，两个整数，$L$，$x$。

outputFormat: 一行，一个整数，表示 $G(L,x)$ 的独立集的个数对 $998244353$ 取模后的结果。

hint:
对于 前 $10\%$ 的数据 $ L, x \le 8 $。

对于 前 $30\%$ 的数据 $ x \le 8 $。

对于 前 $50\%$ 的数据 $ x \le 11 $。

对于 $100\%$ 的数据 $0 < L \le 10^{18}, 0 <x \le 17 $。

本题采用捆绑测试。

下图 是 $G( 3, 4 )$ 的示例图。

![](https://cdn.luogu.com.cn/upload/pic/56163.png)


title: 【模板】动态图连通性

background: 这是 [LOJ #122](https://loj.ac/problem/122) 的一个非官方、**不维护**的镜像，原始出题人是 EtaoinWu ，在本站的原始上传者未知。这个镜像题的数据不保证是最新的，因此推荐到 LOJ 进行练习。

description:
这是一道模板题。

你要维护一张无向简单图（即没有自环，没有重边的无向图）。你被要求加入删除一条边及查询两个点是否连通。

$0.$：加入一条边。保证它不存在。
$1.$：删除一条边。保证它存在。
$2.$：查询两个点是否联通。

为了保证做法的在线性，本题采用了特殊方式的读入。

假设你维护了一个变量 $\text{last}$，初始值为 $0$ 。

对于每个读入的节点 $x$，实际上询问、修改的节点编号是 $x \text{ xor } \text{last}$，其中 $\text{xor}$ 是二进制异或操作。

对于每次解码之后查询 $u,v$，如果它们联通，那么 $\text{last}$ 会被更新为 $u$；否则会被更新为 $v$。

inputFormat:
输入的第一行是两个数 $n,m$。

接下来 $m$ 行，每一行三个数 $\text{op},x,y$。$\text{op}$ 表示操作编号。

outputFormat: 对于每一个$op=2$ 的询问，输出一行 `Y` 或 `N` ，表示两个节点是否连通。

hint:
由于hack数据的加入，数据分布并非如下文所述。下面的仅供参考。

对于数据点 $1$，$n \leq 200,m \leq 200$

对于数据点 $2$，$n=5,m \leq 30$

对于数据点 $3$，$n=10,m \leq 1000$，其中查询的次数 $\geq 900$ 次。

对于数据点 $4$，$n=300,m \leq 50000$

对于数据点 $5$，$n=5000,m \leq 200000$，没有操作 $1$，其中约 $70 \%$ 是操作 $2$。

对于数据点 $6$，$n=5000,m \leq 200000$，没有操作 $1$，其中约 $70 \%$ 是操作 $0$。

对于数据点 $7$、$8$，$n=100,m \leq 500000$

对于数据点 $9$，$n=5000,m \leq 500000$，图是一棵树，其直径 $\leq 30$ 。

对于数据点 $10$， $n=5000,m \leq 500000$，图是一棵树，其每个点度数 $\leq 10$。

还有一些保证 $n \leq 5000,m \leq 500000$ 的附加数据。


title: [集训队互测 2016] 消失的源代码

background:
翻开古老的试题，发现题面已模糊不清。
选手们的源代码也已经消失。
只剩下编译后的可执行程序。
你找到了输入文件，希望重新生成输出文件。

description:
给出可执行程序 $\texttt{lost}$，和输入文件 $\texttt{input*.txt}$，对于每一个输入文件，求出它对应的输出文件。
$\texttt{lost}$ 的输入和输出是标准输入输出。可以在命令行中对输入输出进行重定向。
还下发了一个可执行程序 $\texttt{lost2}$，它从 $\texttt{input.txt}$ 中读入，输出到 $\texttt{output.txt}$。除此以外 $\texttt{lost2}$ 和 $\texttt{lost}$ 完全相同。可以根据习惯选用 $\texttt{lost}$ 或 $\texttt{lost2}$。
$\text{lost}$ 并不完美，当数据规模较大时，它或许不能成功运行，此时会直接输出 `invalid input!`

inputFormat:
第一行一个整数，表示数据类型。$\texttt{lost}$ 会根据数据类型，完成相应的计算。例如数据类型为 $0$ 时，$\texttt{lost}$会计算 $\texttt{A+B Problem}$ ( $\texttt{input0.txt}$、$\texttt{output0.txt}$ )。
第二行一个整数，表示数据组数。
接下来是每一组数据。输入格式由数据类型确定。
当数据规模不超过第一组数据时，保证 $\texttt{lost}$ 能够正常运行。
只有数据组数不超过一组时，保证 $\texttt{lost}$ 的输出正确。

outputFormat: 对于每组数据，输出一行。


title: [USACO19FEB] Cow Dating P

description:
由于目前可供奶牛们使用的约会网站并没有给 Farmer John 留下深刻印象，他决定推出一个基于新匹配算法的奶牛交友网站，该算法可基于公牛和母牛间的共同兴趣对公牛和母牛进行匹配。

Bessie 在寻找情人节 Barn Dance 的合作伙伴时，决定试用这个网站。在注册账户之后，FJ 的算法为他给出了一个长度为 $ N $（$1 \leq N \leq 10^6$） 的匹配列表，列表上每头公牛接受她舞蹈邀请的概率为 $ p $（$0 < p < 1$）。

Bessie 决定向列表中的一个连续区间内的奶牛发送邀请，但Bessie希望**恰好只有一个奶牛**接受邀请。请帮助 Bessie 求出**恰好只有一个奶牛**接受邀请的最大概率是多少。

inputFormat:
第一行输入一个整数 $ N $ 。

接下来 $ N $ 行，每行包含一个整数，它的含义是 $ p_i $ 乘以 $ 10^6 $ 后的结果。

outputFormat: 请输出**恰好只有一个奶牛**接受邀请的最大概率乘以 $ 10^6 $ 后向下取整后的结果。

hint:
样例的最优方案是向第二和第三只奶牛发送邀请。

子任务：对于 $ 25\% $ 的数据， $ N \leq 4000 $ 。


title: [USACO19FEB] Moorio Kart P

description:
Bessie 和 Farmer John 喜欢山羊卡丁车比赛。这个比赛非常类似于其他人喜欢的卡丁车比赛，除了卡丁车是由山羊拉动，以及赛道是由农田组成。农田由 $ N $ 个草地和 $ M $ 条道路组成，每条道路都连接着两个草地。

定义农场是两个或更多草地的一个集合，同一农场中的每个草地都可以沿着一系列**唯一**的道路到达农场中其他任意一个草地。

整个农田可能由多个农场组成，假设图中有 $ K $ 个农场。Bessie 希望通过添加长度为 $ X $ 的 $ K $ 条道路，连接所有 $ K $ 个农场来制作山羊卡丁车赛道。每个农场只应访问一次，并且每个农场内必须至少穿过一条道路。

为了让选手们对赛道更有兴趣，赛道的长度至少应该为 $ Y $ 。Bessie 希望知道所有这些有趣赛道的赛道长度总和。如果一个赛道中有两个农场直接相连，但另外一个赛道中这两个农场没有直接相连的话，这两个赛道就是不同的。

---

形式化题意：

给定 $K$ 个连通块的森林，边有边权。你需要加入 $K$ 条长为 $X$ 的边使得整张图变成一棵基环树。原来的每个连通块在环上至少有一条边，所有新加入的边都应该在环上。

求所有环长 $\ge Y$ 的合法方案的环长之和。

inputFormat:
第一行包括四个整数 $ N,M,X,Y $（$1 \leq N \leq 1500,1 \leq M \leq N-1,0 \leq X, Y \leq 2500$）。

接下来 $ M $ 行，每行包含三个整数： $ A_i,B_i,D_i $（$1 \leq A_i, B_i \leq N,0 \leq D_i \leq 2500$），代表 $ A_i $ 号草地和 $ B_i $ 号草地间有一条长度为 $ D_i $ 的道路。保证两个草地间最多只有一条道路直接相连，且不存在自环。

outputFormat: 输出有趣赛道的赛道长度总和 $\pmod {10^9+7}$ 后的结果。


title: [USACO19FEB] Mowing Mischief P

description:
Bessie 的表妹 Ella 和 Bella 正在参观农场。不幸的是，自从他们到达以来，他们一直在恶作剧。

在他们的最新计划中，他们决定尽可能多地割草。农场的草地是 $ T \times T $ 的正方形。左下角是 $ (0,0) $ ，右上角是 $ (T,T) $ 。因此，正方形包含 $ (T+1)^2 $ 个格点（具有整数坐标的点）。

Ella 和 Bella 计划从 $ (0,0) $ 开始并以每秒一个单位长度的速度运行到 $ (T,T) $ ，同时每只奶牛都握住非常锋利且非常有弹性的线的一端。任何被这根电线扫过的区域的草都会被切断。Ella 和 Bella 可能采取不同的路径，但她们只会向上或者向右移动，从一个格点移动到另一个格点。

Bessie 非常担心会切割太多的草，所以她发明了一个聪明的计划来限制 Ella 和 Bella 的路径。在整个草原上散布着 $ N $ 种花（ $ 1 \leq N \leq 2 \times 10^5 $ ），每种花都在一个特定的格点上。 Bessie 将从这些花中挑选一个子集 $ S $ ， $ S $ 集合中的花 Ella 和 Bella 都需要经过（Ella 和 Bella 的路径都必须经过 $ S $ 中的所有花朵）。

Ella 和 Bella 将会切割面积尽可能大的草，请帮助Bessie确定集合 $ S $ 使得在 $ S $ 集合尽可能大的情况下被切割的草的**面积**最小。

inputFormat:
输入第一行包括两个数 $ N,T $（$1 \leq T \leq 10^6$）。

接下来 $ N $ 行每行包含两个数 $ x_i,y_i $ ，代表一种花的位置。

保证 $ 1 \leq x_i,y_i \leq T-1 $，且不存在两朵花在同一条水平或竖直线上。

outputFormat: 输出一个整数，即被切割的草的**面积**的最小值。

hint:
选择 $ (10,3) $ 和 $ (13,11) $ 这两个位置上的花，可以使得被切割的草的面积最小。

子任务：对于 $ 20\% $ 的数据， $ N \leq 3200 $ 。


title: 最小mex生成树

background: 这是一道经典题。

description:
给定 $n$ 个点 $m$ 条边的无向连通图，边有边权。

设一个自然数集合 $S$ 的 $\text{mex}$ 为：最小的、没有出现在 $S$ 中的自然数。

现在你要求出一个这个图的生成树，使得其边权集合的 $\text{mex}$ 尽可能小。

inputFormat:
第一行输入两个正整数 $n,m$。

接下来 $m$ 行，每行 $3$ 个非负整数 $u,v,w$，表示 $u,v$ 之间有一条权值为 $w$ 的边。

outputFormat: 输出一行一个自然数，表示最小的 $\text{mex}$ 值。

hint:
【数据范围】
- 对于 $20\%$ 的数据，$1\le n \le 100$，$1\le m \le 200$。
- 对于 $50\%$ 的数据，$1\le n \le 2000$，$1\le m \le 3000$。
- 对于 $80\%$ 的数据，$1\le n \le 10^5$，$1\le m \le 2\times 10^5$。
- 对于 $100\%$ 的数据，$1\le n \le 10^6$，$1\le m \le 2\times 10^6,0\le w \le 10^5$。

输入数据规模较大，建议使用高效的读入方式。


title: [NOI Online #1 入门组] 魔法

description:
C 国由 $n$ 座城市与 $m$ 条有向道路组成，城市与道路都从 $1$ 开始编号，经过 $i$ 号道路需要 $t_i$ 的费用。

现在你要从 $1$ 号城市出发去 $n$ 号城市，你可以施展最多 $k$ 次魔法，使得通过下一条道路时，需要的费用变为原来的相反数，即费用从 $t_i$ 变为 $-t_i$。请你算一算，你至少要花费多少费用才能完成这次旅程。

注意：使用魔法只是改变一次的花费，而不改变一条道路自身的 $t_i$；最终的费用可以为负，并且一个城市可以经过多次（包括 $n$ 号城市）。

inputFormat:
输入的第一行有三个整数，分别代表城市数 $n$，道路数 $m$ 和魔法次数限制 $k$。

第 $2$ 到第 $(m + 1)$ 行，每行三个整数。第 $(i + 1)$ 行的整数 $u_i, v_i, t_i$ 表示存在一条从 $u_i$ 到 $v_i$ 的单向道路，经过它需要花费 $t_i$。

outputFormat: 输出一行一个整数表示最小的花费。


title: [ICPC2019 WF] First of Her Name

background:
### Warning: If you submit a malicious program, you will be banned.
### 警告：恶意提交本题将被封号。

description:
In the Royal Family, names are very important! As the Royal Historian you have been charged with analyzing the patterns in the names of the Royal Ladies in the realm.

There have been n Royal Ladies, for convenience numbered from 1 to $n$. The name of each Lady is anuppercase letter concatenated with the name of her mother. The exception is the Lady numbered 1, the
founder of the Royal Family, whose name is just a single uppercase letter.

For example, ENERYS could be the mother of AENERYS (as the name AENERYS consists of the single uppercase letter 'A' concatenated with ENERYS, which is her mother's name). Similarly, AENERYS could be the mother of DAENERYS and YAENERYS.

You are given the description of all the Royal Ladies. Your task is to determine, for certain interesting strings $s$, the number of Royal Ladies for whom s is a prefix of their name.

For example, consider Sample Input 1 below, with a Royal Line that goes straight from the founder S to AENERYS (through YS, RYS, ERYS, NERYS and ENERYS), with each Lady having exactly one daughter. Then AENERYS has two daughters—DAENERYS and YAENERYS, with the latter havingone daughter, RYAENERYS.

In such a family, RY is a prefix of the names of two ladies: RYS and RYAENERYS. E is a prefix of the names of ERYS and ENERYS. N is a prefix only of NERYS's name, while S is a prefix only of the nameof the founder, S. AY is not a prefix of any Royal Lady's name.

inputFormat:
The first line of input contains two integers $n$ and $k$, where $n$ $(1 \leq n \leq 10^6)$ is the total number of Royal Ladies and $k$ $(1 \leq k \leq 10^6)$ is the number of query strings.

Then follow n lines describing the Royal Ladies. The $i^{th}$ of these lines describes the Royal Lady numbered $i$, and contains an uppercase letter $c_i$ ('A'–'Z') and an integer $p_i$, where $c_i$ is the first letter of the name of Lady $i$, and $p_i$ $(p1 = 0$ and $1 \leq pi \lt i$ for $i \gt 1)$ is the number of her mother (or $0$, in the case
of the First Lady). All the names are unique.

The remaining $k$ lines each contain one nonempty query string, consisting only of uppercase letters. The sum of the lengths of the query strings is at most $10^6$.

outputFormat: Output $k$ lines, with the $i^{th}$ line containing the number of Royal Ladies who have the $i^{th}$ query string as a prefix of their name.

translation:
**题目描述**

众所周知，皇室家族的名字非常有讲究。而作为研究皇室的历史学家的你，最近接到了一个艰巨的任务——分析王国历史中所有皇室夫人的名字。

王国历史上有 $n$ 位皇室夫人，方便起见，我们将其从 $1$ 至 $n$ 编号。除了 $1$ 号夫人外，其余夫人的名字均为一个大写字母连接着她母亲的名字。而 $1$ 号夫人作为王国的首任王后，她的名字只有一个大写字母。

例如，由于 `AENERYS` 由 `A` 与 `ENERYS` 组成，因此 `ENERYS` 是 `AENERYS` 的母亲。相似地，`AENERYS` 是 `DAENERYS` 与 `YAENERYS` 的母亲。

你知道王国历史上所有皇室夫人的姓名与关系，而你需要完成的任务是，对于其他历史学家感兴趣的名字串 $s$，总共有多少位夫人的名字是以 $s$ 起始的。

例如在样例的皇室族谱中，`S` 至 `AENERYS` 的这一支（包含 `YS`、`RYS`、`ERYS`、`NERYS` 与 `ENERYS` 这几位夫人）均只有一位女儿。接下来 `AENERYS` 有两位女儿，分别是 `DAENERYS`，以及女儿是 `RYAENERYS` 的 `YAENERYS`。

在这个皇室家族内，有两位夫人的名字以 `RY` 起始，她们是 `RYS` 与 `RYAENERYS`。而 `ERYS` 与 `ENERYS` 均以 `E` 起始。名字以 `N` 起始的仅有一位夫人 `NERYS`。同样地，以 `S` 起始的仅有首位王后 `S`。而没有任何一位夫人的名字以 `AY` 起始。

**输入格式**

第一行有两个整数 $n,k$，分别代表王国历史上皇室夫人总数，以及其他历史学家感兴趣的名字串的个数。

接下来 $n$ 行描述所有皇室夫人的姓名与关系。第 $i+1$ 行描述第 $i$ 位夫人的资料 $c_i$ 与 $p_i$，其中字符 $c_i$ 表示她名字的首位字母，$p_i$ 为她母亲的编号。对于编号为 $1$ 的首位王后，$p_1=0$。所有夫人的名字均不重复。

接下来 $k$ 行，每行为一个大写字母构成的非空串，代表一个其他历史学家感兴趣的名字串。

**输出格式**

输出 $k$ 行，第 $i$ 行为一个整数，代表总共有多少位夫人的名字是以第 $i$ 个感兴趣的名字串起始的。

**数据范围**

$1\leq n\leq 10^6$，$1\leq k\leq 10^6$，$p_1=0$，特别地，对于 $1\lt i\leq n$，保证有 $1\leq p_i\lt i$。感兴趣的名字串总长不超过 $10^6$。

samples:
10 5
S 0
Y 1
R 2
E 3
N 4
E 5
A 6
D 7
Y 7
R 9
RY
E
N
S
AY

hint: Source: ICPC World Finals 2019.


title: [USACO19FEB] Cow Land G

background: Cow Land 是一个特殊的奶牛游乐园，奶牛们可以在那里漫步，吃美味的草，并参观不同的景点（尤其过山车特别受欢迎）。

description:
Cow Land 总共有 $ N $ 个不同的景点（ $ 2 \leq N \leq 10^5 $ ）。 一共有 $ n-1 $ 条道路连接任意两个景点，这意味着任意两个景点间只有一条简单路径。

每个景点 $ i $ 都有一个享受值 $ e_i $ ，这个值可能会改变。因为一些景点在早上更有吸引力，而其他景点在下午则更能吸引游客。

从景点 $ i $ 到景点 $ j $ 的奶牛们可以欣赏从景点 $ i $ 到景点 $ j $ 的路上的所有景观。这条路线的享受值为景点 $ i $ 到景点 $ j $ 的路上的所有景点（包括景点 $ i $ 和景点 $ j $ ）的享受值按位进行异或运算的结果。

请帮助奶牛确定他们前往 Cow Land 旅行时计划的路线的享受值。

inputFormat:
输入的第一行包含两个整数， $ N,Q $（$1 \leq Q \leq 10^5$）。

接下来一行包含 $ N $ 个整数，其中第 $ i $ 个整数 $ e_i $ 代表景点 $ i $ 的享受值。

接下来 $ N-1 $ 行，每行包含两个整数 $ a,b $ ，表示景点 $ a $ 和景点 $ b $ 之间有一条道路相连。

最后 $ Q $ 行，每行包含 3 个整数，表示一个操作，具体内容如下：

1. `1 i v`，表示将 $ e_i $ 修改为 $ v $ 。
2. `2 i j`，表示询问从景点 $ i $ 到景点 $ j $ 的路线的享受值为多少。

outputFormat: 对于每个 2 操作，输出对应查询的结果。

hint: 子任务：对于 $ 50\% $ 的数据，没有修改操作。


title: [USACO19FEB] Dishwashing G

background: Bessie 和 Elsie 正在帮助 Farmer John 洗碗，这是一个比人们想象的更复杂的过程。

description:
两头奶牛决定 Bessie 负责涂肥皂，Elsie 负责冲洗。

刚开始的时候，$N$ 个脏盘子（保证是从 $1$ 到 $N$ 的一个排列）堆在 Bessie 那里，而 Elsie 这边的堆是空的。而在她们俩之间，则有一张专门放涂过肥皂的盘子的桌子。

每个冲洗步骤需要执行以下两个操作之一：

- Bessie 从脏盘子堆顶取出一个盘子，涂上肥皂，然后放在桌子上。将这个盘子放在桌子上时，Bessie 只能放在现有的非空盘堆的顶端，或是在最右边新增一个盘堆。
- Elsie 从桌子最左边的盘堆的顶端拿起盘子，将它冲洗后放在干净的盘堆顶端。

她们希望干净的盘堆能按编号排序，编号最小的在底端，编号最大的在顶端。然而她们发现有的时候这并不可能做到。现在给定脏盘子的堆叠顺序，请你求出一个最大前缀，使得该前缀的所有盘子洗干净后，能按上面的要求堆叠。

inputFormat:
第一行一个整数 $N$（$1 \leq N \leq 10^5$）。

接下来 $N$ 行，每行一个整数，代表 Bessie 的脏盘子堆的堆叠顺序。输入的第一个盘子在堆的顶部。

outputFormat: 输出该序列的最大前缀长度，使得该前缀的所有盘子洗干净后，能按小号在下，大号在上的规则堆叠。


title: OwenOwl 不学车也不删库

background:
神 mcfx 和神 ComeIntoPower 没事就瞎编题目背景。OwenOwl 去问基佬 zcysky 他们这么做的原因，基佬 zcysky 却这样答复：

![](https://cdn.luogu.com.cn/upload/pic/54751.png)

OwenOwl 非常郁闷，于是他有一天找到了神 J，让神 J 造了 20010910 个指针把他们三个指到阿塞拜疆去陪 sunset 阿克了。

他们三个游览阿塞拜疆的时候，OwenOwl 就把车砸了，库恢复了。

但是因为神 mcfx 和神 ComeIntoPower 之前以 OwenOwl 这个 ID 出了太多毒瘤题，OwenOwl 早就风评被害了。为了证明毒瘤的是他俩，不是自己，OwenOwl 就出了道签到题。

description:
设 $p$ 是一个质数。

你有一个 $p^k$ 个点的无向完全图（任意两个点之间有一条无向边），点的标号是 $0$ 到 $p^k-1$。

现在你需要从中找出一些 $p$ 个点的完全图，使得原图中每条边属于且恰好属于其中一个完全图。

很显然你需要找出的完全图的个数是 $\frac{p^k(p^k-1)/2}{p(p-1)/2} $，可以发现这个式子一定是整数

inputFormat: 一行两个正整数 $p,k$。

outputFormat:
如果无解，输出一行 `NO`。

否则输出一行 `YES`，接下来输出 $\frac{p^k(p^k-1)/2}{p(p-1)/2} $ 行，每行 $p$ 个数表示你找出的这个完全图的点的编号。

按任意顺序输出任意一种方案即可。

hint:
对于 $10\%$ 的数据，$k \le 1$；

对于 $50\%$ 的数据，$k \le 2$；

另有 $20\%$ 的数据，$p = 2$；

对于 $100\%$ 的数据，$k$ 是正整数，$p$ 是质数，$2 \le p^k \le 2000$。

另外，保证输出总量不超过 2MB，但仍请注意控制输出所花费的时间。


title: [yLOI2019] 棠梨煎雪

background:
> 岁岁花藻檐下共将棠梨煎雪，
> 自总角至你我某日辗转天边。
> 天淡天青，宿雨沾襟，
> 一年一会信笺却只见寥寥数言。

——银临《棠梨煎雪》

description:
扶苏正在听《棠梨煎雪》的时候，@[spitfirekindergarten](https://www.luogu.org/space/show?uid=61795) 发来一道 [IOI2018 集训队作业题](http://uoj.ac/problem/425)：我切了这集训队题，辣鸡扶苏快过来做题。扶苏定睛一看，这不 s\* 题嘛，写了一发交上去才发现自己看错题目了。但是写完的代码不能浪费，于是就有了这道题。

歌词中的主人公与她的朋友一年会有一次互相写信给对方，一共通信了 $m$ 年。为了简化问题，我们认为她们每封信的内容都是一条二进制码，并且所有二进制码的长度都是 $n$。即每封信的内容都是一个长度为 $n$ 的字符串，这个字符串只含字符 ``0`` 或 ``1``。

这天她拿出了朋友写给她的所有信件，其中第 $i$ 年的写的信件编号为 $i$。由于信件保存时间过久，上面有一些字符已经模糊不清，我们将这样的位置记为 ``?``，``?`` 字符可以被解释为 ``0`` 或 ``1``。由于她的朋友也是人，符合人类的本质，所以朋友在一段连续的时间中书写的内容可能是相同的。现在她想问问你，对于一段连续的年份区间 $[l,r]$ 中的所有信件，假如朋友在这段时间展示了人类的本质，所写的是同一句话，那么这一句话一共有多少种可能的组成。也即一共有多少字符串 $S$，满足在这个区间内的所有信件的内容都可能是 $S$。

一个长度为 $n$ 的只含 ``0,1,?`` 的字符串 $A$ 可能是一个字符串 $B$ 当且仅当 $B$ 满足如下条件：

- $B$ 的长度也是 $n$ 。
- $B$ 中只含字符 ``0,1``。
- $A$ 中所有为 ``0`` 的位置在 $B$ 中也是 ``0``。
- $A$ 中所有为 ``1`` 的位置在 $B$ 中也是 ``1``。
- $A$ 中为 ``?`` 的位置在 $B$ 中可以为 ``0`` 也可以是 ``1``。

同时她可能会突然发现看错了某年的信的内容，于是她可能会把某一年的信的内容修改为一个别的只含 ``0``,``1``,``?`` 的长度为 $n$ 的字符串。

inputFormat:
每个输入文件中都有且仅有一组测试数据。

输入数据第一行为三个用空格隔开的整数，分别代表代表字符串长度 $n$，字符串个数 $m$ 和操作次数 $q$。

下面 $m$ 行，每行是一个长度为 $n$ 的字符串，第 $(i + 1)$ 行的字符串 $s_i$ 代表第 $i$ 年信的内容。

下面 $q$ 行，每行的第一个数字是操作编号 $opt$。

- 如果 $opt=0$，那么后面接两个整数 $[l,~r]$，代表一次查询操作。
- 如果 $opt=1$，那么后面接一个整数 $pos$，在一个空格后会有一个长度为 $n$ 的字符串 $t$，代表将第 $pos$ 个字符串修改为新的字符串 $t$。

outputFormat: 为了避免输出过大，请你输出一行一个数代表所有查询的答案异或和对 $0$ 取异或的结果。


title: [Ynoi2011] 成都七中

background:
上初中的时候就听说成都七中非常厉害，我当时文化课成绩还不错，于是也想去成都七中。

当时对高中的看法是什么样的我现在也无从得知了，但从模糊的感觉上大概是很憧憬的。

我初三的时候想办法联系到了cdqz的竞赛教练林老师，然后获得了周末来旁听OI讲课的许可。

还记得讲课的学长是集训队的于神，一开始就在给我们讲数据结构。cdqz明亮宽敞（当时的印象）的机房，和从未见过的beamer排版给我留下了深刻的印象。

第一节课是树状数组，完全没听懂，现在感觉这个东西其实不适合一开始就讲，因为结构理解起来挺麻烦的，也不像线段树那样有一个非常直观的分治结构，而且代码经过特化非常精简，很容易谔谔。

第二节课是线段树，这个听懂了一部分，感觉好神奇，但是讲到标记的部分我就无法理解了，讲完课写题，写了一个很长很丑的线段树，调了很久很久，半懂不懂地把题过了。

当时在做vijos上面的题，看到小白逛公园的感觉就像是AMX-1357看到鼠爷一样。

每天都有考试，考试的时候基本上啥都不会，只能写写暴力分骗分，每次评测的时候都看到学长们过了好多题，当时感觉非常羡慕。

和我一起去cdqz听课的有一位zms，他初二拿了普及组省第一，初三考提高组差点拿了一等奖，我一直以他为竞争对手，每次考试的时候都在和他比划比划成绩，但基本上都是我输。

【记得配图，内容：当时考试的成绩（大概找不到了），当时的PPT（大概找不到了），成都七中校门（这个有）】

由于这是Ynoi，不是出题人拿来写无趣的文字的地方，所以你需要做一个数据结构题：

description:
给你一棵 $n$ 个节点的树，每个节点有一种颜色，有 $m$ 次查询操作。

查询操作给定参数 $l\ r\ x$，需输出：

将树中编号在 $[l,r]$ 内的所有节点保留，$x$ 所在连通块中颜色种类数。

每次查询操作独立。

inputFormat:
第一行两个数 $n,m$。

第二行 $n$ 个数表示每个节点的颜色。

之后 $n-1$ 行，每行两个数 $x$ 和 $y$，表示 $x$ 和 $y$ 之间连有一条边。

之后 $m$ 行，每行三个数 $l\ r\ x$，表示一次查询操作。

outputFormat: 对每个查询操作，输出一行一个数表示答案。

hint:
Idea：nzhtl1477，Solution：nzhtl1477，Code：created_equal1，Data：nzhtl1477

对于 $100\%$ 的数据，所有出现过的数在 $[1,10^5]$ 之间，保证每次输入的 $l \le x \le r$。


title: [Ynoi2011] WBLT

background:
时间大概在学科夏令营那段时间：

当时信息组的其他几个还有新高二的同学都开始学splay了，每天听到zms和yjq（一个学长，很强）讨论splay，还戏称为"spaly"，就感觉很紧张，他们怎么学这么厉害的东西，我还完全不了解。

然后我上网查了查splay，看到几百行的代码，看到什么zig，zag，势能分析（所以说写的这么丑的博客为什么会排前几），就感觉这个东西无法理解，大概看了看也没看懂。

去问了问于神splay的功能是什么——“插入，删除，查询第k小”

反正天天也无聊，于是就想了想：

线段树可以查第k小，只需要让其叶子sorted即可。

所以线段树是不是也能做？

但是我们的线段树是一个静态的结构（当时的想法），这个东西要动态化才行，不然如何插入删除？

线段树维护了每个点的区间，这个东西是静态的，也就是问题所在，我们考虑如何动态化这个东西：

插入一个节点的时候，如果找到了插入位置，那么一定是一个叶子，我们可以给这个节点新建两个叶子的儿子。

可以发现这个插入位置后面的所有节点都进行了平移，于是我们可以考虑对这个进行打标记来维护，称为平移标记，每次push_down平移标记来实现动态化。

每次删除的时候可以使用其兄弟来代替被删除的节点，同理需要进行平移标记的维护。

查询的时候先push_down平移标记，然后考虑是否进入左儿子即可。

可以发现这样的结构在插入链式数据下复杂度会有问题，考虑如何平衡。

我当时第一个想到的是设定一个ratio，使得左右儿子的比例在ratio之内，否则暴力重构，写了写发现好像是对的，去问于神，然后他说这个就是“替罪羊树”......

诶所以我自己发明平衡树了？

这么看来平衡树很简单啊。

这么看来我很强啊（错觉）。

然后我就一直按这个思路想下去了，想了很多种奇怪的写法，比如不平衡的时候合并一下，或者按中点分裂什么的。

我乱写了一个策略，通过了平衡树模板题，但是当时写的非常复杂，因为我维护了父亲，而且写法未经过优化。

后来发现不需要所谓的平移标记，可以直接维护size，这样可以按相对位置二分下去，减少了很多代码量。

发现可以不存father，减少了很多代码量。

又发现这个树也是可以”旋转“的，我们将旋转定义为合并两个节点即可（所以我看到说什么”无旋treap不用旋转，和treap不一样“的言论都感觉很谔谔，因为本身就是等价操作，同一个东西写出来不一样而已）。

同时也是可以分裂的，这里我分裂定义为了经过 $O( logn )$ 次旋转使得根的左儿子的右儿子是我们需要的区间。

我发现我设计出的平衡树的确是可以支持所有操作的，复杂度也都是 $O( logn )$ ，而且个人认为这个很好写。

所以我发明平衡树了？

当时起了个名字“自平衡线段树”——“Self Balancing Segment Tree”，虽然后来查了很久发现其实是把两个OI界中未引入的东西结合在了一起，应该叫做“Weight Balanced Leafy Tree”

刚做出来的时候觉得这个是很重要的东西，于是对其他人都藏着掖着，生怕同学们学到我的技术，因为我当时也知道，省队就5个名额，同学都是我的竞争对手。

当时mhy听说我的平衡树很强，就问我能不能10分钟写出来，我接受了挑战，然后还真的写出来了，得到了集训队爷的认可+1

当时就对自己充满了自信，我都能发明这么强的一个数据结构，那进集训队保送清华北大还不是随手的事情吗（flag）。

【记得配图，WBLT的】

由于这是Ynoi，不是出题人拿来写装逼的文字的地方，所以你需要做一个数据结构题：

description:
给你一个长为 $n$ 的序列，有 $m$ 次查询操作。

每次查询操作给定参数 $l,r,b$，需输出最大的 $x$，使得存在一个 $a$，满足 $0\leq a<b$，使得 $a,a+b,a+2b,\ldots,a+(x-1)b$ 都在区间 $[l,r]$ 内至少出现过一次。

如果不存在 $[0,b-1]$ 内的数，则输出 $0$。

inputFormat:
第一行一个整数 $n$。

第二行 $n$ 个整数表示这个序列。

第三行一个整数 $m$。

之后 $m$ 行，每行三个整数 $l,r,b$，表示一次查询操作。

outputFormat: 对于每个查询操作，输出一行一个整数表示答案。

hint:
Idea：nzhtl1477，Solution：nzhtl1477，Code：ccz181078，Data：ccz181078&Forever_Pursuit

对于 $30\%$ 的数据，所有出现过的数在 $[0,1000]$ 之间。

对于另外 $30\%$ 的数据，$b \leq 1000$。

对于 $100\%$ 的数据，所有出现过的数在 $[0,10^5]$ 之间。


title: [ICPC2019 WF] Checks Post Facto

description:
Your university's board game club just hosted a Checkers tournament, and you were assigned to take notes on the games. Unfortunately, while walking home, you dropped all of your papers into a puddle! Disaster! Much of what you wrote is now unreadable; all you have left are some lists of moves played in the middle of various games. Is there some way you can reconstruct what happened in those games? You had better fix things fast, or they will demote you to Tic-Tac-Toe recordkeeper!

Checkers (or English Draughts) is a well-known board game with simple rules. It is played on the dark squares of an $8 \times 8$ checkerboard. There are two players, Black and White, who alternate turns moving their pieces (all of Black's pieces are black and all of White's pieces are white). Each piece occupies a single dark square, and can be either a normal $man$ or a promoted $king$. A turn consists of choosing one piece and moving it in one of two ways:

1. Shifting it diagonally to an unoccupied adjacent dark square, as shown in Figure C.1(a). This is called a $simple~move$. If the piece is a man, it can move only in the two diagonal directions towards the opposing side of the board (towards the bottom for Black, the top for White). If the piece is a king, it can move in all four diagonal directions.

2. Jumping over an adjacent enemy piece to an unoccupied square immediately on the other side, then removing ($capturing$) that piece. Men can jump only in the two directions described above, while kings can jump in all four. The player can then repeat this step, continuing to jump with the same piece as long as there are properly-positioned enemy pieces to capture. Such a sequence of one or more jumps is called a $jump~move$. Figure C.1(b) shows a jump move comprising three
jumps.

![](https://cdn.luogu.com.cn/upload/image_hosting/onoiijvu.png)

In Checkers, captures are forced moves. If a jump move is available at the start of a player's turn, they must jump, and cannot stop jumping with that piece until it has no more possible jumps. They are free to choose which piece to jump with, and where, if there are multiple possibilities. In Figure C.1(b), Black could not have made any other move.

If a man reaches the farthest row from its player (that is, a black man reaches the bottom row or a white man reaches the top row), it is removed from the board and replaced by a king of the same color (it is said to be $promoted$), and the turn ends. A piece cannot be promoted and then jump backwards as a new king in the same turn.

Given a list of moves, find a setup of pieces such that the moves can be legally played in sequence starting from that setup. This setup may not have black men on the bottom row or white men on the top row, since they would have been promoted to kings already. You need only ensure that the rules above are obeyed; you do not need to ensure that this setup is reachable in a real game of Checkers.

inputFormat:
The first line of input contains a character $c$ and an integer $n$, where $c$ is either `B` or `W`, indicates which player makes the first move (Black or White respectively) and $n$ ($1 \leq n \leq 100$) is the number of moves in the list. Then follow $n$ lines, each of which describes a move in the standard Checkers notation defined below.

The dark squares are identified by numbers $1 \sim 32$, as shown in Figure C.1(c). A simple move from square $a$ to square $b$ is written as `a-b`. A jump move starting at $a$ and jumping to $b_1, b_2, \dots , b_k$ is written as $a\text{x}b_1\text{x}b_2\text{x} \dots \text{x}b_k$.

There is always a valid solution for the given set of moves.

outputFormat: Output two boards side-by-side (separated by a space), giving the positions of all pieces on the board before (on the left) and after (on the right) the given moves. Use  `-` for light squares,  `.` for empty dark squares, lowercase `b` and `w` for black and white men, and uppercase `B` and `W` for black and white kings. If there is more than one valid solution, any one is acceptable.

translation:
游戏在一个 $8 \times 8$ 的方格棋盘的深色方格上进行。有两名玩家，黑方和白方，他们轮流移动他们的棋子（所有黑方的棋子都是黑色的，所有白方的棋子都是白色的）。每个棋子占据一个单独的深色方格，可以是**兵**或**王**。一个回合包括选择一个棋子并以以下两种方式之一移动它：

1. 将其**斜着**移动到一个相邻的未占用的深色方格，如图 (a) 所示。这被称为**简单移动**。兵只能沿向前的两种方向移动（对于黑方是朝下，对于白方是朝上）。如果棋子是王，它可以在所有四个斜方向移动。

2. 跳过对方的棋子到达空地，并吃掉对方的子。允许移动的方向与第一条相同。然后，玩家可以重复此步骤，继续使用相同的棋子跳。这样一个或多个跳的序列称为**跳跃移动**。图 (b) 展示了由三个跳跃组成的跳跃移动。

如果在玩家回合开始时有一个跳跃移动可用，他们必须进行跳跃，并且不能停止使用该棋子跳跃，直到它没有更多可能的跳跃。他们可以自由选择使用哪个棋子进行跳跃，以及在有多个可能性的情况下选择在哪里跳跃。在图 (b) 中，黑方不能进行任何其他移动。

如果一个兵达到其玩家的最远一行（即，一个黑子达到底行或一个白子达到顶行），它将变成同色的王（称为**晋升**），然后**回合结束**。这意味着一个兵不能在同一回合中被晋升然后以王的身份继续倒退跳跃。

给定一系列移动，请找到一个初始棋局，使得可以从该棋局开始按顺序合法进行这些移动。此棋局可能不能在底行有黑子或在顶行有白子，因为它们可能已经被晋升为王。你只需要确保上述规则被遵守；不需要确保这个棋局在实际跳棋游戏中是可达的。

### 输入格式

输入的第一行包含一个字符 $c$ 和一个整数 $n$，其中 $c$ 是 B 或 W，表示哪个玩家首先移动（分别为黑方或白方），$n$（$1 \leq n \leq 100$）是移动列表中的移动次数。然后是 $n$ 行，每行描述标准跳棋符号中定义的一步移动。

深色方格用数字 $1 \sim 32$ 标识，如图 (c) 所示。从方格 $a$ 到方格 $b$ 的简单移动写作 a-b。从 $a$ 开始跳到 $b_1, b_2, \dots , b_k$ 的跳跃移动写作 $a\text{x}b_1\text{x}b_2\text{x} \dots \text{x}b_k$。

对于给定的移动集合，总是存在至少一个答案。

### 输出格式

所有棋子在棋盘上的位置以两个并排的棋盘输出（用空格分隔），分别表示在给定的移动之前（左边）和之后（右边）的棋盘。

使用`-`表示浅色方格，`.`表示空的深色方格，小写的`b`和`w`表示黑色和白色兵，大写的`B`和`W`表示黑色和白色王。如果存在多个答案，则任何一个都可以接受。


title: [JSOI2013] 丢番图

background:
丢番图是亚历山大时期埃及著名的数学家。他是最早研究整数系数不定方程的数学家之一。

为了纪念他，这些方程一般被称作丢番图方程。最著名的丢番图方程之一是

$$x^n+y^n=z^n$$

费马提出，对于 $n>2$, $x,y,z$ 没有正整数解。这被称为“费马大定理”，它的证明直到最近才被安德鲁·怀尔斯（AndrewWiles）证明。

description:
考虑如下的丢番图方程：

$$\frac{1}{x}~+~\frac{1}{y}~=~\frac{1}{n}~,(x,y,n~\in~N^+)$$

小G对下面这个问题十分感兴趣：对于一个给定的正整数 $n$，有多少种本质不同的解满足上面的方程？例如 $n=4$，有三种本质不同 ($x~\leq~y$)的解：

> $\frac{1}{5}+\frac{1}{20}~=~\frac{1}{4}$
>
> $\frac{1}{6}+\frac{1}{12}~=~\frac{1}{4}$
>
> $\frac{1}{8}+\frac{1}{8}~=~\frac{1}{4}$

显然，对于更大的 $n$，没有意义去列举所有本质不同的解。你能否帮助小G快速地求出对于给定 $n$，满足上面方程的本质不同的解的个数？

inputFormat: 一行，仅一个整数 $n$。

outputFormat: 一行一个整数代表答案。

hint:
#### 数据规模与约定

对于全部的测试点，保证 $1\leq n \leq 10^{14}$。


title: [JSOI2013] 广告计划

background: 如今，在建筑的墙面上或者篱笆桩的表面上涂上一些广告，是一种新的吸引眼球的方法。

description:
现在，小G 运营的一家小公司，决定也试着这样做做广告。小G在他的篱笆桩上腾出了一些地方供广告使用。每一个篱笆桩都是一个水平的1\*1\*L的 4 棱柱，其中有一个 1\*L的面是可以做广告的。1\*L的面上划出了 L 个1\*1 的小正方形（更具体地说是连续L个水平排列的正方形），每个正方形内写上一个字母。 时间久了，广告做多了难免会出现一些比较麻烦的情况，比如计划改变或者制作出错，因此小 G 的仓库里面积累了好多没有用的，上面已经写上 L 个字母的篱笆桩。（所有的篱笆桩的大小都是一样的，他们唯一的区别仅仅在于上面写了什么字母）。 小G 决定对于这些篱笆桩进行重新利用，并且有了一些新的想法。

如果将这些篱笆桩竖直的叠放起来，并且依次从左往右，对于每一个篱笆桩顺次从上到下读出上面的字母，那么我们可以得到一些新的比较长的单词，如下图：

![qwq](https://cdn.luogu.com.cn/upload/pic/54049.png)

这些新的单词能满足小G的一些新的需要。当然，基于美学考虑，小G 是不允许你删改篱笆桩上已经写上的字母的。 我们更具体地描述这个过程。我们将 K个长度为 L的篱笆桩叠在一起，可以得到一个写有 K行L列共K*L个字母的面，每一个字母都在对应的唯一的格子里。

我们从左上角开始依次向下读出每一个字母可以得到一个字母的序列，比如上图中的这个例子，那么我们读出的结果就是“TOEIIZENITKN”。如果，这个串中有我们所需要的单词，那么显然我们只需要将一些格子刷白，就可以得到我们所需要的了。举个例子，比如小G想要给圣彼得堡的足球队泽尼特队做个广告，那么很显然只要按照上图中的做法就可以达到小G想要的效果了。

现在小G已经想好了要做怎样的广告，同时也提供给你了小G仓库中的篱笆桩的类型的描述，你可以认为每一种类型的篱笆桩都是有无数个的。现在小G 想知道至少需要多少个篱笆桩叠起来才可以做出小G想要的广告。

inputFormat:
第一行两个自然数，N和L。

接下来N 行，每行包含 L个小写字母，描述一种篱笆桩上写着的字母。保证不同类型的篱笆桩上的字母序列都是不一样的，每一种类型的篱笆桩都是有无数个。

最后一行是一个字符串s，表示小G 想好的广告词。

outputFormat: 第一行一个整数K，表示所需要的最少数量的篱笆桩（注意是数量，并不是种类数）。


title: [JSOI2013] 美丽家园

description:
现在富裕的家庭都有了自己的别墅，别墅的院子往往大家选择铺上黑白两色的地砖。如何铺地砖是很有学问的，因为这涉及到美学方面的问题。怎样铺是美的呢？先看下面两组：

![qwq](https://cdn.luogu.com.cn/upload/pic/54050.png)

Figure 1 中的就被人们认定为比较美丽的，而 Figure 2 中的铺法则是不美丽的了。因为人们认为，如果出现一块 2*2 的区域里，只有一种颜色，那这就是不美丽的，反之则是美丽的。

现在，小 G 的公司拿到了一个任务，一块 N*M 的院子必须铺上地砖。爱美之心人皆有之，主人家自然希望这块院子地砖的铺法是美丽的，所以他首先想让小 G 的公司拿出设计方案的总数来。

而且这户主人家似乎对 P这个数特别迷信，所以他希望得到的总方案数对P取模后的结果。

inputFormat: 仅有一行包含三个用空格隔开的正整数 $N,~M,~P$, 分别与题目描述中的数据对应。

outputFormat: 输出总方案数对 $P$ 取模后的结果。


title: [JSOI2013] 编程作业

description:
考虑到如下的两段代码，很容易发现他们其实是一样的。

#### 代码1

```cpp
int i, j;
i = 3;
j = i + 1;
```

#### 代码2

```
int a, i;
a = 3;
i = a + 1;
```

这是因为这两段代码之间唯一的差异，只是他们更换了一下变量名，比如第一段代码中的 `i` 变成了第二段的 `a`，第一段的 `j` 变成了第二段的 `i` 。而其他的常量，例如 `3`，`1` 或者其他的关键字和运算符，比如 `int`，`+` 和 `;`。都是没有发生变化的。

不过注意到如下的代码片段，我们并不能简单认为这是一样的，因为这不是一个简单的替换，而是可以导致不同运算结果的。
#### 代码3

```cpp
a = 3;
b = 3;
```

#### 代码4
```cpp
c = 3;
c = 3;
```

为了简化问题，我们用大写字母来表示所有的关键字、常量等非变量符合。

假如我们采用如下的替换表：

![qwq](https://cdn.luogu.com.cn/upload/pic/54051.png)

那么最开始给出的两段雷同代码就可以分别写成 `AiBjCiDECjDiFGC` 以及 `AaBiCaDECiDaFGC`。

或者简单的说，我们认为这两段代码是一样的。

现在请写一个程序，处理若干这样的代码雷同检测问题：给一个完整代码以及一个较短的代码片段，请求出，这个代码片段在完整代码中一共出现了多少次（代码片段出现的位置可以重叠）。

为了简单起见，我们认为程序中只会至多出现 a~z 这 26 个变量，同时也至
多只有 A~Z 这 26 个非变量符号。

inputFormat:
第一行包含一个整数 $Q$ 表示此数据中一共包含 $Q$ 个询问。

接下来 $2Q$ 行，每两行为一个询问。

每个询问中的第一行包含一个字符串 $S$，表示完整代码，第二行包含一个字符串 $T$，表示需要检测出现次数的代码片段。

outputFormat: 一共输出 $Q$ 行，每行一个整数，表示对应代码片段的出现次数。

samples:
3
AiBjCiDECjDiFGC
AaBiCaDECiDaFGC
cDEcDEbDE
aDEbDE
ccddef
aab

hint:
#### 样例说明
前两个样例均为题目中所举例的代码段。第三个样例中，在完整代码 S中与
代码片段T 一样的片段为：ccd和dde

#### 数据范围
$Q<=3,~|T|<=10^5,|S|<=10^6$


title: [JSOI2013] 密码

background: Will 有一个神秘盒，传说只要有人能解开神秘盒上的密码，就可以预知未来（比如知道这道题的标程是怎样的），你愿意来尝试一下么？

description:
对于一个 $m$ 位的十进制整数 $N~=~(\overline{n_1 n_2 n_3 \dots n_m})_{10}$，定义 $g(N)~=~\sum_{i = 1}^{m} n_i$。

定义集合 $S_N~=~\{x~|~x~>~0,~g(x)~\leq~N,x~\text{的十进制表示中任意位不为} 0\}$。

给定 $n$，求

$$f(n)~=~\sum_{x \in S_n} \sum_{y \in S_n \land x < y} x~\times~y$$

答案对 $10^6+3$ 取模。

inputFormat: 一行一个正整数 $n$。

outputFormat: 一行一个整数代表答案对 $10^6 + 3$ 取模的结果。


title: [JSOI2013] 旅行时的困惑

description:
Waldives 有 $N$ 个小岛。目前的交通系统中包含 $N-1$ 条快艇专线，每条快艇专线连接两个岛。这 $N-1$ 条快艇专线恰好形成了一棵树。

由于特殊的原因，所有 $N-1$ 条快艇专线都是单向的。这导致了很多岛屿之间
不能相互到达。因此，Waldives 政府希望新建一些公交线路，使得建设完毕后，任意两个小岛都可以互相到达。为了节约开支，政府希望建设最少的公交线路。

同时，出于规划考虑，每一条公交线路都有如下的要求：
> 1、每一条交通线路包含若干条连续的快艇专线，你可以认为一条公交线路
对应树上的一条路径，而其所包含的若干快艇专线则对应树上被这条路
径所覆盖的树边（也就是之前已经存在的某个快艇专线）；
>
> 2、显然一条交通线路只能覆盖树上任意一条边至多一次；
>
> 3、公交线路中所包含的每一个快艇专线都是有方向的，并且与其所覆盖的
树边的方向相反；
>
>4、不同的公交线路可以覆盖树上相同的点或者相同的边。

Waldives 的 $N$ 个岛屿分别从 $0$ 到 $N-1$ 编号。现在给出 Waldives 已有的快艇专线信息，请计算最少所需要新建的交通线路的数量。

inputFormat:
第一行包含一个整数 $N$。

接下来 $N-1$行，每行包含两个整数 $x,~y$。表示存在一条从岛屿 $x$ 开往岛屿 $y$ 的快艇专线。

outputFormat: 输出一行一个整数，表示需要建设的最少的交通线路数量。


title: [JSOI2013] 游戏中的学问

description:
大家应该都见过很多人手拉手围着篝火跳舞的场景吧？一般情况下，大家手拉手跳舞总是会围成一个大圈，每个人的左手拉着旁边朋友的右手，右手拉着另
一侧朋友的左手。

不过，如果每一个人都随机的拉住两个不同人的手，然后再慢慢散开，事情
就变得有趣多了——此时大家依旧会形成圈，不过却可能会形成多个独立的圈。
当然这里我们依然要求一个人的右手只能拉另一个人的左手，反之亦然。

班里一共有 $N$ 个同学，由 $1$ 到 $N$ 编号。Will想知道，究竟有多少种本质不
同的拉手方案，使得最终大家散开后恰好形成 $k$ 个圈呢？

给定两种方案，若存在一个人和他的一只手，满足在这两种方案中，拉着这
只手的人的编号不同，则这两种方案本质不同。

inputFormat: 输入一行包含三个正整数$N,~k,~P$

outputFormat:
输出文件的包含一行一个整数，表示本质不同的方案数对p的余数。保证p
一定是一个质数。


title: [JSOI2013] 超立方体

background:
超立方体是立方体在高维空间内的拓展（其在 2 维情况下退化为正方形，1 维情况下退化成线段）。在理论计算机科学领域里，超立方体往往可以和 2 进制编码联系到一起。对理论计算机科学颇有研究的 Will 自然也会对超立方体有着
自己的思考。

![qwq](https://cdn.luogu.com.cn/upload/pic/54052.png)

上图就是在 0～4 维空间内超立方体所对应的图形。显然我们可以把超立方体的每个顶点看成一个点，每一条棱看成一条边，这样就会得到一个无向图，我们称之为超立方图。

description:
D 维空间内的超立方图有 $2^D$ 个点，我们把这些点从 $0$ 到 $2^D-1$ 依次编号。

有一个有趣而重要的充要结论是：一定存在一种编号的方式，使得图中任意两个有边相连的顶点的编号的 2 进制码中，恰好有一位不同。

在2维和3维空间内这个结论可以这样形象的理解：对于 2 维空间，我们只要把这个正方形放到第一象限内，使得 4 个顶点的坐标按逆时针顺序依次为 $(0,0),(1,0),(1,1),(0,1)$，然后再把坐标看成 2 位 2 进制数，依次将这 4 个点编号为  0,1,3,2即可。

对于 3 维空间，同样我们可以将立方体的一个顶点与原点重合，并使得所有棱均平行于坐标轴，然后分别确定这 8 个点的坐标，最后把 3 维空间内的坐标看成一个 3 位 2 进制数即可。对于 D 维空间，以此类推。

现在对于一个 $N$ 个点 $M$ 条边的无向图（每个点从 $0$ 到 $N-1$ 编号），Will 希望知道这个图是否同构于一个超立方图。

inputFormat:
第一行包含一个整数 $Q$ 表示此数据中一共包含 $Q$ 个询问。

接下来 $Q$ 组询问，每一组询问的输入格式如下：

第一行包含两个整数 $N$ 和 $M$，接下来 $M$ 行，每行 2 个不同的整数 $x,y$，表示图中存在一条无向边连接编
号为 $x$ 和 $y$ 的点（$0 \le x,y < N$）

outputFormat:
1、如果询问中给定的图不同构于任何一个超立方图，输出 $-1$；

2、如果同构于某一个超立方图，那么请给图中这 $N$ 个点重新编号，并在这一行输出 $N$ 个用空格隔开的整数，表示原图中每个点新的编号，使得重新编号后，满足题目中所述的结论。

注意：输出文件的每一行，要么仅包含一个整数 $-1$，要么则应包含一个由 $0$ 到 $N-1$ 这 $N$ 个数组成的排列。如果有多组解输出任意一个均可。


title: [JSOI2013] 数字理论

description: 给定 $4$ 个正整数 $K,~S,~P,~D$，要求在十进制数中，寻找一个最小的 $K$ 位自然数 $x$，满足 $x$ 的各个数位之和为 $S$，并且 $x$ 乘以 $D$ 之后各个数位之和为 $P$。

inputFormat: 输入数据中包含一行四个整数，分别为 $K,~S,~P,~D$。

outputFormat: 输出一行一个整数，表示满足条件的最小自然数 $x$。如果不存在则输出$-1$。


title: [JSOI2013] 体育课

description:
体育课里一共有 N 个同学，学号分别为 1 到 N，JYY 的学号是 P。学号为 i 的同学的身高为 $h_i$。

JYY的体育老师 KFC 有一个特殊排队方法： KFC 先让班里的N 个同学按照学号从小到大的顺序，从左到右站成一排，然后从到队列的最左边（也就是第一个学生面前）开始，一直向右走动到第 N-1 个学生面前；接着 KFC 再回到第一个学生面前，继续开始向右走，就这样一共走动 N-1 次。每次当 KFC 走到第 i个学生面前时，KFC 会比较一下队列里第i 个学生和第i+1 个学生的身高，如果左边（第i 个）的学生比右边（第i+1）的学生高，那么KFC 就会交换这两个学生在队列里的位置。

最终，在 N-1 次走动全部结束之后，KFC 会选出队列最右边的一些学生去搬桌子。自然的，JYY希望能够站在尽量靠左的位置来增加自己踢足球的机会。 此外，JYY 还有一个绝招，那就是在 KFC 老师快走到自己面前的时候，开始蹲下来系鞋带！如果 JYY 蹲下来系鞋带了，那么在这一次走动中，好说话的KFC 老师就不会让 JYY和相邻的同学比较身高了， 自然也就不会让 JYY和相邻的同学交换位置。 （只有 JYY最聪明会蹲下来系鞋带，其他同学都只会老老实实的让KFC 老师比较身高）

蹲下来系鞋带是很耗费体力的。为了留着体力踢足球，JYY最多只能蹲下 K
次。

JYY想知道，按照怎样的下蹲策略可以使自己在队列里站的尽量靠左。

我们用一个长度为 N-1的字符串来表示一个策略：如果字符串的第 i 个字符
是“+”，则表示在第 i 次走动时 JYY蹲下来系鞋带；如果第 i 个字符是“-”，则表示JYY会老老实实的比较身高。

inputFormat:
第一行包含三个整数 N，P，K。
第二行包含 N 个整数，第 i 个整数表示 hi。

outputFormat:
第一行包含一个正整数，表示按照最优策略 JYY 可以排在的最
靠左的位置。
输出文件的第二行包含一个长度为 N-1 的字符串，表示最佳策略。
如果有多个最佳策略，JYY 希望知道字典序最大的策略。


title: [JSOI2013] 打地鼠

background:
JYY 特别喜欢到游戏厅玩打地鼠游戏——拿起两个锤子用力敲打不断冒出
来的地鼠。

打到不同的地鼠有不同的得分，JYY想知道怎样才能得到最高的分
数。

description:
游戏里一共会冒出来 $N$ 个地鼠，这些地鼠冒出来的位置都分布在一条直线
上。第 $i$ 个地鼠会在 $T_i$ 时刻在 $X_i$ 位置冒出来，打到第 $i$ 个地鼠的得分是 $P_i$。

当游戏开始时（也就是 0 时刻），JYY 左手的位置为 XLEFT，右手的位置为
XRIGHT。JYY的手的最大移动速度是 $V$（每单位时刻最多移动的距离为 V） 。

地鼠会在瞬间冒出来然后消失。如果在对应的时刻 JYY 的一只手恰好也在地鼠冒出来的位置，那么 JYY 就可以在瞬间完成击打动作并得到对应的分数,否则，JYY就只能错过这只地鼠了。

JYY两只手都拿着锤子，所以两只手是可以同时打地鼠的。

然而， 如果在游戏过程中 JYY的两只手交叉的话， JYY会感到很不舒服 （这
个动作确实很别扭，而且两只手可能会互相阻碍而影响移动速度） ，所以 JYY希
望在整个游戏过程中左手的位置 XLEFT永远严格小于右手的位置XRIGHT。JYY想知道，他最多能得多少分呢？

inputFormat:
第一行包含四个整数$N,~V,~XLEFT,~XRIGHT$；
接下来 $N$ 行，分别描述 $N$ 个可能出现的地鼠；
其中第 $i$ 行包含三个整数 $X_i$，$T_i$，$P_i$。
数据保证在同一个时刻不会有两个地鼠出现在同样的位置。

outputFormat: 输出一行一个整数，表示JYY最多能够得到的分数。


title: [JSOI2013] 公交系统

background:
几年前南京因为修地铁的缘故，很多公交车线路都被迫改变了。

JYY 为此很苦恼：试想一下，当你坐上一辆公交车，却发现这辆公交车驶向了与你记忆完全不同的方向。

于是 JYY 打算开发一套可以利用手机进行实时更新的公交信息应用， 所有安装了这款应用的手机都可以向数据库发送最新的公交线路更改情况，同时也可以通过应用向数据库查询自己所需要的信息。

description:
南京一共有 $n$ 个公交站点，分别从 $1$ 到 $n$ 编号。两个不同的站点 $x$ 和 $y$ 之间可能会有公交车直接运营（不经过别的站点直接从 $x$ 开到 $y$） ，我们将这种关系看作一条无向边（公交线路显然是双向的，我们既可以从 $x$ 坐公交车到 $y$，也可以从 $y$ 坐车到 $x$）。

任意时刻任何公交站点都至多只会连有 $2$ 条边，并且所有这些边是不会形成
环的（公交车很少会出现环线，所以这些公交线路应该形成一些不相交的链，链
的两端分别对应两个终点站）。

JYY 的 IOS 应用按照时间顺序一共收到了 $q$ 条交互信息，每一条交互信息
都是下列五种信息之一：

- `add x y z`，表示当前时刻，站点 $x$ 到站点 $y$ 之间有新增了一班公交车直接运营，并且在当前路况下，公交车所需要的运营时间为 $z$。
- `del x y`，表示由于某种原因，原本在站点 $x$ 和站点 $y$ 之间直接运营的公交车停运了。
- `change x y z`，表示由于路况情况改变，站点 $x$ 到站点 $y$ 之间直接运营的公交车当前的运营时间为 $z$。
- `reach x y`，表示某个用户询问从站点 $x$ 坐车能不能坐到站点 $y$。
- `dest x y`，表示某个用户从站点 $x$ 上车，坐上了当前正开往站点 $y$ 的公交车。该用户想知道，他到达 $y$ 后继续乘坐可乘坐的线路(已经乘坐过的线路不能重复乘坐)，最终能够到达的终点站是哪一站？从站点 $x$ 开始需要多久才能
开到终点站？

**在收到第一条信息之前，没有任何公交车在运营**。

由于用户难免会提交错误的信息，所以 JYY 希望他的软件对于错误的信息也
要能够做出合理的反应：

- 对于 `add` 信息，如果加入边 $(x,y)$ 之后，任何站点连接的边数均不超过 $2$ 并且图中没有环，JYY 则认为这个信息是正确的，并根据这个信息更新
数据库中的公交线路数据，否则JYY会无视这个错误信息。
- 对于 `del` 和 `change` 信息，如果站点 $x$ 和站点 $y$ 之间有公交车直接运营， JYY 则认为这条信息是正确的，并更新数据库，否则 JYY 则会无视这个错误
信息。
- 对于 `dest` 信息，如果站点 $x$ 不能到达站点 $y$，JYY 也会认为这一条询问信
息是错误的。

JYY 希望你能够帮助他完成这一个公交信息应用。

inputFormat:
输入数据的第一行包含两个整数，分别代表站点数 $n$ 和交互信息条数 $q$。

接下来 $q$ 行，每行对应一个 JYY 需要处理的信息，其格式见【题目描述】。

outputFormat:
输出 $q$ 行，每行都对应一个输入文件中的信息，具体内容如下：

- 如果输入的信息是错误的，输出 `ERROR`。
- 对于一个正确的 `add`，`del`，`change` 信息，输出 `OK`。
- 对于一个正确的 `dest` 信息，输出一行两个整数，分别为终点站的编号和开到终点站所需要的时间.
- 对于 `reach` 信息，如果用户询问的两个公交站点相互可达，输出 `YES`，否则输出 `NO`。

samples:
6 10
add 1 2 1
add 2 1 1
add 3 2 1
add 4 5 2
reach 4 6
dest 1 5
del 5 6
add 1 4 2
dest 2 3
dest 3 2

samples:
OK
ERROR
OK
OK
NO
ERROR
ERROR
OK
3 1
5 6

hint:
#### 数据规模与约定

对于 $100\%$ 的数据，保证：

- $2 \leq n \leq 10^5$，$2 \leq q \leq2×10^5$。
- $1 \leq x, y \leq n$，$x \neq y$，$1\leq z \leq10^4$。

---

#### 提示

请注意数据读入对程序效率造成的影响。


title: 多项式三角函数

description:
给定一个 $n-1$ 次多项式 $A(x)$，求一个 $\bmod{\:x^n}$ 下的多项式 $F(x)$，满足 $F(x)\equiv\sin{A(x)}$ 或 $F(x)\equiv\cos{A(x)}$。

所有运算在 $\bmod\ 998244353$ 意义下进行。

inputFormat:
第一行 **两个** 整数 $n,type$，若 $type=0$ 代表求 $\sin$，若 $type=1$ 代表求 $\cos$；

第二行 $n$ 个整数，依次表示多项式的系数 $a_0,a_1,\cdots,a_{n-1}$。

保证 $a_0=0$。

outputFormat: 输出一行 $n$ 个整数，表示答案多项式中的系数 $f_0,f_1,\cdots,f_{n-1}$。


title: 多项式反三角函数

description:
给定一个 $n-1$ 次多项式 $A(x)$，求一个 $\bmod{\:x^n}$ 下的多项式 $F(x)$，满足 $F(x)\equiv\text{asin}\:A(x)$ 或 $F(x)\equiv\text{atan}\:A(x)$。

所有运算在 $\bmod\ 998244353$ 意义下进行。

inputFormat:
第一行 **两个** 整数 $n,type$，若 $type=0$ 代表求 $\text{asin}$，若 $type=1$ 代表求 $\text{atan}$；

第二行 $n$ 个整数，依次表示多项式的系数 $a_0,a_1,\cdots,a_{n-1}$。

保证 $a_0=0$。


title: 总而言之神J要去练习篮球

background:
神J和神树大人正在开发一个睡眠程序，运行之后人们就能在梦里随机看到宇宙中的一角。当然大部分时候这一角都是黑的，所以人们总是觉得自己没有做梦。

神J留了个后门，只需要操控指针，就能钦定一个人的梦。于是神J天天操控神树大人梦里写代码。

神树大人很不满意，因为树必须天天睡觉。神树大人是神，早就知道神J在背后操控，所以他也留了个后门，只需要输入特殊命令，就能强迫神J睡觉，并在梦里做任何事情。

这天，神J突然发现自己身处一个大篮球场里，周围有许多学员在练习三人篮球赛。“你傻站在那干啥呢？”神树大人吹着哨子走了过来，“快去练习，都要举行肯德基三人篮球全国总决赛了，快去投进114514个球，再运球过1919810个人。zcy快过来监督他。”一个篮球突然出现在神J手里。于是神J就在zcy的监督下练习了一个下午的篮球。

description:
为了防止神J用篮球造出一个指针把自己指出去，神树大人钦定神J用篮球造一个矩阵。

这个矩阵无限大，行列从0开始标号，且$a[i][j]=i\ xor\ j$

![](https://cdn.luogu.com.cn/upload/pic/54403.png)

现在，对于一个左上角为$(lx,ly)$，右下角为$(rx,ry)$的子矩阵，$K(K\leq 10^9)$次随机从里面取$W\times H$的矩阵，问取出的矩阵完全一样的概率，对$10^9+7$取模。

inputFormat:
第一行一个数$Q$表示$Q$组询问

之后$Q$行每行7个数$lx,rx,ly,ry,W,H,K$

outputFormat: 输出答案对$10^9+7$取模。保证答案存在。

hint:
对于`1 2 1 2 1 1 2`这组询问

![](https://cdn.luogu.com.cn/upload/pic/54402.png)

可以取的矩阵有：0,3，各出现两次。

有如下情况：

第一次取到 3，第二次取到 0，一共4种方法

第一次取到 3，第二次取到 3，一共4种方法

第一次取到 0，第二次取到 0，一共4种方法

第一次取到 0，第二次取到 3，一共4种方法

一共16种方法，符合条件的有4+4=8种

所以答案为 8/16=500000004(mod 10^9+7)

##数据范围

对于所有的数据，$0\leq lx\leq rx\leq 10^9,0\leq ly\leq ry\leq 10^9,W\leq rx-lx+1,H\leq ry-ly+1,1\leq K\leq 10^9,Q\leq 10^3$

![](https://cdn.luogu.com.cn/upload/pic/54632.png)

空格为无特殊限制


title: 无论怎样神树大人都会删库跑路

background:
众所周知，神J（Joker）每隔几天就会去成都法中假装上课，实际上是去玩指针。神J可以趁别人不注意掏出指针把自己指到任何位置（生物标本柜里大变活人？），或者把两个人的指针交换一下（成都法中版《你的名字》？），或者对着OJ念系统命令使得OJ随机变慢（mcfx：怎么这CPU睿频后反而变慢了）。

神树大人很不满意，因为树必须站在原地，而且神树大人也不会指针。但是神树大人是神，于是他打算把这个宇宙的数据库删了跑路，这样无所事事的神J就只能和神树大人玩牌了。

description:
现在有个长为$T$的字符串$S$和$n$个小字符串$a_i$。

给定一个长为$m$的数组$R$，数组下标从1开始，初始有一个空字符串$X$，神树大人打算进行$Q$次操作，第$i$次操作会把小字符串$a_{R_{(i-1)\bmod m+1}}$丢到这个$X$的末尾。

每次操作后，神树大人会检查这个字符串$X$是否存在一个后缀使得任意排列后可以变成$S$。

问有多少次这个字符串$X$存在一个后缀使得**任意排列**后可以变成$S$（即所有字符出现次数相同）。

可惜的是，这个字符串字符大小高达$10^5$，所以你必须读入一个整数数组

inputFormat:
输入$n,T,Q$

接下来输入$T$个数表示字符串$S$

接下来输入$n$行，每行第一个数$len$表示长度，接下来输入$len$个数表示这个小字符串，输入的每个数都在$[0,10^5]$范围内。

接下来输入$m$

输入一行$m$个数，表示$R$。

outputFormat: 输出答案

hint:
样例1解释：

![](https://cdn.luogu.com.cn/upload/pic/54698.png)

##数据范围

对于所有数据，$n,T,m\leq 10^5,1\leq R_i\leq n,Q\leq 10^9$，所有小字符串的总长不超过$10^5$，所有字符$\in[0,10^5]$。

![](https://cdn.luogu.com.cn/upload/pic/54734.png)


title: 欧稳欧再次学车

background: 请自行脑补一张欧稳欧学车的图

description:
欧稳欧学车时经常用一辆橡树车练习。这辆橡树车共有 $N$ 个挡位，欧稳欧每秒可以把挡位增加或减少 $1$，初始时（$0$ 时刻）挡位为 $1$。

这辆车的转速范围是 $[L,R]$，初始时转速为 $L$。每次升挡时，转速会变成 $L$；降挡时，会变成 $R$。欧稳欧在每秒也可以踩油门，让转速增加 $X$，再对 $R$ 取 $\text{min}$。如果转速连续 $K$ 秒都 $=R$，那么这辆车的发动机会停止工作，在这 $K$ 秒结束的一瞬间停下（即使 $K$ 秒中经历了降档操作，仍然算这种情况）。

这些操作我们认为都是在每秒开头的一瞬间进行的，其中换挡操作比踩油门操作先进行。而这一秒内这辆车前进的距离是 转速$\times$挡位。

现在给出欧稳欧练习时的操作序列，你需要求出他一共前进的距离是多少。

inputFormat:
第一行六个整数 $T,N,L,R,X,K$，$T$ 表示总时间。

接下来 $T$ 行，每行两个整数 $x,y$，表示这一秒的操作。

其中 $x=0$ 表示升挡，$x=1$ 表示降挡，$x=2$ 表示挡位不变；$y=0$ 表示不踩油门，$y=1$ 表示踩油门。（不要问为什么没有刹车）

outputFormat:
一行一个整数，表示给定操作序列的前进距离。

如果欧稳欧在挡位为 $N$ 时升挡，或在挡位为 $1$ 时降挡，那么给定序列不合法，输出 $-1$。

hint:
对于样例一：

第一秒挡位为 $2$，转速为 $6$；
第二秒挡位为 $3$，转速为 $1$；
第三秒挡位为 $3$，转速为 $6$；
第四秒挡位为 $3$，转速为 $10$；
第五秒挡位为 $2$，转速为 $10$。

对于样例二，前进两秒之后发动机就停止了工作。

对于 $30\%$ 的数据，没有挡位操作（即保证 $x=2$）；

对于另外 $30\%$ 的数据，没有踩油门操作（即保证 $y=0$）；

对于全部数据，保证 $1\le T,N,L,R,X,K\le 10^6,L\le R$。


title: [SNOI2017] 一个简单的询问

description:
给你一个长度为 $N$ 的序列 $a_i$，$1\leq i\leq N$，和 $q$ 组询问，每组询问读入 $l_1,r_1,l_2,r_2$，需输出

$$
\sum\limits_{x=0}^\infty \text{get}(l_1,r_1,x)\times \text{get}(l_2,r_2,x)
$$

$ \text{get}(l,r,x)$ 表示计算区间 $[l,r]$ 中，数字 $x$ 出现了多少次。

inputFormat:
第一行，一个数字 $N$，表示序列长度。
第二行，$N$ 个数字，表示 $a_1\sim a_N$。
第三行，一个数字 $Q$，表示询问个数。
第 $4\sim Q+3$ 行，每行四个数字 $l_1,r_1,l_2,r_2$，表示询问。

outputFormat: 对于每组询问，输出一行一个数字，表示答案。

hint:
对于 $20\%$ 的数据，$1\leq N,Q\leq 1000$；
对于另外 $30\%$ 的数据，$1\leq a_i\leq 50$；
对于 $100\%$ 的数据，$N,Q\leq 50000$，$1\leq a_i\leq N$，$1\leq l_1\leq r_1\leq N$，$1\leq l_2\leq r_2\leq N$。

数据范围与原题相同，但测试数据由 LibreOJ 自制，并非原数据。

**注意：** 答案有可能超过 `int` 的最大值。


title: [LnOI2019SP] 龟速单项式变换(SMT)

background:
题目提供者：朝田诗乃

众所周知，这是一题签到题。

description:
有如下定义：若正整数序列 $a$ 中存在连续若干个正整数的和为 $m$ 的倍数，则这个正整数序列 $a$ 被称为“$m$ 序列”。

给定 $n$ 和 $m$，你需要知道长度为 $n$ 的任意正整数序列 $a$ 是否都是“$m$ 序列”。

inputFormat: 两个数，$n$ 和 $m$。

outputFormat: 如果成立输出 `YES` 否则输出 `NO`。

samples:
2 4
NO

hint:
样例解释：存在反例 $[1, 2]$。

Subtask 1 (50 pts)：$1 \le n, m \le 5$。

Subtask 2 (50 pts)：$1 \le n, m \le {10}^{18}$。


title: [LnOI2019] 脸滚键盘

background:
题目提供者：Okami

朝田诗乃：一个优秀的长脖子鹿是会数数字的位数的。

description:
长颈鹿Abbi喜欢用脸滚键盘，它每次滚键盘就会把一段子区间的值乘起来。

定义子区间为一个区间中的一个连续区间。

定义一段子区间的权值为每个元素权值之积。

定义一段区间的期望权值为任意选出一段子区间的权值的期望值。

给定 $n$ 个数字，分别表示权值 $a_i$ 。

共$q$次询问，对于一次询问 $l \ r$ 查询指定区间的期望权值。

inputFormat:
第一行，两个数$n$和$q$。

第二行$n$个数，第$n$个数表示序列初始值$a_i$

接下来$q$行，每行两个数$l \ \ r$，表示询问的区间。

outputFormat:
对于每次询问，输出指定区间的期望权值。

由于期望权值可以很大，**请输出期望权值模 $100000007$。**

不要问我除不尽怎么办了，看上面

还是不行的话请移步https://www.luogu.org/problem/P2613


title: 【模板】快速阶乘算法

background:
有一天，NaCly_Fish 无意间看到一种高效求阶乘模大质数的算法，但是她太菜，并不会写。
于是她就暴力造了数据，请您帮忙写出 std 吧。

什么，您问为什么不保证模数可以 NTT？
那样的话就可能被打表水过，或者答案就爆 int 了。

反正您是神仙，肯定能秒掉这题。

description:
给你正整数 $n$，和一个质数 $p$，你需要求出：
$$ n! \text{ mod } p$$
有 $T$ 组数据。

inputFormat:
第一行一个正整数 $T$，表示数据组数。
接下来 $T$  行，每行两个正整数 $n,p$，意义如题目描述。

outputFormat: 输出 $T$ 行，表示每组数据的答案。

hint:
### 数据范围：

对于 $10\%$ 的数据：$p = 998244353$
对于另外 $10\%$ 的数据：$p = 1004535809$
对于 $100\%$ 的数据：$1\le n < p \le 2^{31}-1$，$1 \le T \le 5$
保证 $p$ 为质数。

【提示】
请确保你的算法时间复杂度不高于 $\Theta(\sqrt n \log n)$，时限为 std 的十倍以上。


title: 秘籍-反复异或

description:
给定一个长为 $n$ 的序列，支持操作：

- `1 l r x`：将区间 $[l,r]$ 的所有元素加 $x$。
- `2 l r` ：查询区间 $[l,r]$ 中所有元素异或和的后 $m$ 个二进制位的值。

inputFormat:
第一行三个正整数 $n,m,q$，表示序列长度，位数，操作数。

第二行 $n$ 个非负整数，表示原始序列 $a_i$。

接下来 $q$ 行，每行若干个非负整数表示一个操作。

outputFormat: 对于每个 $2$ 操作输出一行，一个非负整数表示答案。

hint:
【数据范围】
本题共 $10$ 个测试点。

对于测试点 $1 \sim 3$，$1\le n,q \le 1000$；
对于测试点 $4,5$，$1 \le m \le 5$；
对于测试点 $6 \sim 10$，设 $k$ 为测试点编号，有 $m=k$。

对于 $100\%$ 的数据，$1 \le n,q \le 10^5$，$1\le m \le 10$，$0\le a_i,x < 2^m$。

**请注意常数优化。**


title: 密码解锁

background: 在开锁公司劳动

description:
这天，WD发现了一个很奇怪的密码锁，他记得CX让他解开这个密码锁之前告诉过他一些数字，可惜由于WD菜的真实，早就忘了那些数字是啥，只记得把他们从1到$n$编号后，对于任意的正整数$d(1\le d\le n)$，编号为$d$的倍数的数字之和恰好等于$\mu(d)$（即$d$的莫比乌斯函数值）。

现在，由于要打开这个密码锁，他必须知道第$m$个位置上的数字。由于他什么都不会，当然要请你来帮忙啦……

inputFormat: 第一行一个数$T$，表示数据组数。接下来$T$行每行两个数，分别为$n,m$。

outputFormat: 共$T$行，每行一个数字，表示第$m$个数字的值。显然可以证明解是唯一的。


title: 幂

background: 来到数学院劳动

description:
$$\text{求}\ \sum_{n=0}^{\infty}f(n)\ r^n\ ,\ f(n)\text{为一个多项式},\ r\text{是一个}(0,1)\text{内的有理数}$$

若答案的最简分数为$\frac{p}{q}$，你只需要输出$p\times q^{-1}\  \mathrm{mod} \ 998244353\ $的值即可。

inputFormat:
第一行两个整数$m,r$。$m$为多项式的次数。

第二行$m+1$个整数，第$i$个为$x^{i-1}$的系数$a_{i-1}$。

outputFormat: 仅一行一个数字，为答案。


title: 【模板】多项式开根（加强版）

background: 模板题，无背景

description:
给定一个 $n-1$ 次多项式 $A(x)$ ，求一个在 $\bmod\ {x^n}$ 意义下的多项式 $B(x)$ ，使得 $B^2(x)\equiv A(x)\pmod {x^n}$。

多项式的系数在 $\bmod\ 998244353$ 的意义下进行运算。

inputFormat:
第一行一个正整数$n$。

接下来$n$个整数，依次表示多项式的系数$a_0,a_1,\cdots ,a_{n-1}$

**不保证$a_0=1$，但保证$a_0$是$\bmod\ 998244353$下的二次剩余。**

outputFormat: 输出 $n$ 个非负整数，表示答案多项式的系数$b_0,b_1\cdots ,b_{n-1}$。如有多解，输出**系数序列**（而非字符序列）字典序最小的。


title: 序列

background: 搬运序列

description:
有一个序列$a_n$和若干操作。

- $\mathrm{1\  l \  r \ }$ 求$a_l$到$a_r$的和
- $\mathrm{2\  l \  r \ val \ }$ 将$a_l$到$a_r$赋值为$\mathrm{val}$
- $\mathrm{3\  l \  r \ val\ }$将$a_l$到$a_r$加上$\mathrm{val}$
- $\mathrm{4\  l_1 \  r_1 \  l_2 \  r_2 }$将$a_{l_1}$到$a_{r_1}$复制到$a_{l_2}$到$a_{r_2}$处
- $\mathrm{5\  l_1 \  r_1 \  l_2 \  r_2 }$将$a_{l_1}$到$a_{r_1}$与$a_{l_2}$到$a_{r_2}$交换
- $\mathrm{6\  l \  r \ }$将$a_l$到$a_r$翻转

inputFormat:
第一行两个数$n$和$m$，为序列长度和操作个数。

第二行$n$个数，为$a_i$。

下面$m$行，每行为操作种类和相应的若干整数。

outputFormat:
若干行，对于每个$1$操作，输出答案。

由于答案可能过大，对$10^9+7$取模。

最后一行输出序列$a_n$。当然也要取模。

hint:
**请注意常数优化**

若是$\mathrm{copy}$和$\mathrm{swap}$操作，保证$r_1-l_1=r_2-l_2$且区间不重叠。

保证数据随机。

对于$30\%$的数据，保证$\ n,m\le 10^3\ $。

对于$50\%$的数据，保证$\ n,m\le 5\times 10^4\ $。

对于$70\%$的数据，保证$\ n,m\le 1.5\times 10^5\ $。

对于$100\%$的数据，保证$\ n,m\le 3\times 10^5\ ,\ 0\le a_i,\mathrm{val}\lt Mod\ $。


title: Ruri Loves Maschera

background: 琉璃最近沉迷于《Maschera》的二次创作。

description:
琉璃小说中的世界有 $n$ 座城市，其中有 $n-1$ 条道路，不包含重边、自环。这 $n-1$ 条道路中，第 $i$ 条道路的魔力值为 $w_i$。

琉璃作为夜魔女王，她决定要观光整个黑暗世界 。她每次会随机选一个城市为起点，经过不少于 $L$ 条且不多于 $R$ 条道路后在一个城市为终点结束。**她在观光的时候是不走回头路的。**若琉璃每次观光中经过道路的魔力值依次为 $v_1,v_2,...,v_k(L\leq k\leq R)$，那么她会获得 $\max(v_1,v_2,...,v_k)$ 的魔力值。

现在琉璃想知道，她尝试了所有合法的观光路线后，她所获得的魔力值总和为多少。

**注意，$x$ 到 $y$ 的路径和 $y$ 到 $x$ 的路径视为两条路径。**

inputFormat:
第一行三个数 $n,L,R$

接下来 $n-1$ 行，每行三个数 $x,y,w$，表示 $x$ 结点和 $y$ 结点之间有一条魔力值为 $w$ 的道路。

outputFormat: 输出她所获得的魔力值总和。


title: Terrible Homework

background: “像糟糕的作业一样糟糕。”

description:
$ben$同学最讨厌做作业了。

现在，老师布置给了$ben$同学$n$份作业，每份作业有一个难度值$A_i$。

一开始，每份作业都是独立的。有一些操作，每次在两份作业$x,y$间加一条边或删除一条边。

由于老师喜怒无常，因此还有一些操作，是将两份作业$x,y$之间路径上的所有作业的难度值都$xor$上一个值。

同时，为了满足$ben$同学的好奇心，你需要回答两份作业$x,y$之间的所有作业的难度$and$和、难度$or$和、难度$xor$和以及难度和。

inputFormat:
第一行两个正整数$n,q$，分别表示作业份数和操作个数。

接下来一行，$n$个自然数$A_1,...,A_n$，表示每份作业的难度值。

接下来$q$行，每行一个操作：

- $L\ x\ y$：在$x,y$两份作业之间连一条边。（保证不会形成环，即任何时候这张图都是一个森林）
- $C\ x\ y$：删除$x,y$两份作业之间的边。（保证这条边存在且不会被删除多次）
- $U\ x\ y\ v$：将$x,y$两份作业之间路径上的所有作业的难度值都$xor$上$v$。（包括这两份作业，且保证联通，下同）
- $A\ x\ y$：询问$x,y$两份作业之间的所有作业的难度$and$和。
- $O\ x\ y$：询问$x,y$两份作业之间的所有作业的难度$or$和。
- $X\ x\ y$：询问$x,y$两份作业之间的所有作业的难度$xor$和。
- $S\ x\ y$：询问$x,y$两份作业之间的所有作业的难度和。

outputFormat: 对于每一个$A,O,X,S$操作，输出答案。


title: [Ynoi2013] 文化课

background:
Chimuzu 省选一轮爆了两个大零蛋，于是滚回去学文化课了。

他翻出一道基础四则运算练习题……然后发现自己不会。

于是他需要你的帮助，作为回报，他会给你 $100$ 分。

前排打广告，有人来看看我写的[融合树](https://www.luogu.org/blog/user3296/rong-ge-shu-fusion-tree)吗

（其实还写了 Brodal queue）

description:
Chimuzu 手上有一个数字序列 $\{a_{1},a_{2},\ldots,a_{n}\}$ 和一个运算符序列 $\{p_{1},p_{2},\ldots,p_{n-1}\}$。其中 $p_{i}$ 只能为 $+$ 或 $\times$。

我们定义一个区间 $[l,r]$ 的权值 $w(l,r)$ 为将字符串

$$
a_{l}~p_{l}~a_{l+1}~p_{l+1} \cdots a_{r-1}~p_{r-1}~a_{r}
$$

写下来之后，按照运算符的优先级计算出的结果。

下面给出一个运算的例子：

若 $a=\{1,3,5,7,9,11\}$，$p=\{+,\times,\times,+,\times\}$，那么有：

$$
w(1,6)=1+3\times 5\times 7+9\times 11=205
$$

$$
w(3,6)=5\times 7+9\times 11=134
$$

Chimuzu 需要你对这两个序列进行修改，同时查询某个给定区间的权值。

你需要维护这 $3$ 个操作：

操作一：给定 $l,r,x$，将 $a_{l},a_{l+1},\ldots,a_{r}$ 全部修改成 $x$。

操作二：给定 $l,r,y$：将 $p_{l},p_{l+1},\ldots,p_{r}$ 全部修改成 $y$，$0$ 表示 $+$，$1$ 表示 $\times$。

操作三：给定 $l,r$：查询 $w(l,r) \bmod 1000000007$ 的值。

inputFormat:
第一行包含两个整数 $n,m$。

第二行包含 $n$ 个整数 $a_{1},a_{2},\ldots,a_{n}$。

第三行包含 $n-1$ 个整数 $p_{1},p_{2},\cdots,p_{n-1}$，$0$ 表示 $+$， $1$
 表示 $\times$。

接下来 $m$ 行，每行有一个操作。

一开始输入一个标识符 $op$，表示操作类型，接着按照题目描述输入各操作的参数。

$op=1$ 时，输入 $3$ 个整数 $l,r,x$，表示将 $a_{l},a_{l+1},\ldots,a_{r}$ 全部修改成 $x$。

$op=2$ 时，输入 $3$ 个整数 $l,r,y$，表示将 $p_{l},p_{l+1},\ldots,p_{r}$ 全部修改成 $y$，$0$ 表示 $+$，$1$ 表示 $\times$。

$op=3$ 时，输入 $2$ 个整数 $l,r$，表示查询 $w(l,r) \bmod 1000000007$ 的值。

outputFormat: 对于每一次操作 $3$，输出 $1$ 行 $1$ 个整数表示所求答案。

hint:
#### 样例解释 1

初始的两个序列和前两次操作是题目描述中的例子。第四次操作结束后，两个序列变成了如下形态

$a=\{13,13,5,7,9,11\}$，$p=\{+,\times,\times,\times,\times\}$

$$
w(1,6)=13+13\times 5\times 7\times 9\times 11=45058
$$

$$
w(3,6)=5\times 7\times 9\times 11=3465
$$

### 数据范围与约定

对于其中 $1\%$ 的数据，为样例 1，时限为 1.5s

对于另外 $14\%$的数据，$n,m\leq 1000$ ，时限为 1.5s

对于另外 $5\%$ 的数据，没有修改操作，时限为 1.5s

对于另外 $14\%$ 的数据，数据保证随机，时限为 1.5s

对于另外 $19\%$ 的数据，没有 1 操作，时限为 1.5s

对于另外 $19\%$ 的数据，没有 2 操作，时限为 1.5s

对于另外 $8\%$ 的数据，时限为 5s

对于另外 $10\%$ 的数据，时限为 3s

对于 $100\%$ 的数据，$n,m\leq 100000$，$1\leq a_{i},x\lt 2^{32}$，$a_{i},x$ 均为奇数，$p_{i},y\in\{0,1\}$，$1\leq l\leq r\leq n$，所有操作 $2$ 还满足 $r\lt n$。时限为 1.5s

Idea：Juan_feng。

Solution：nzhtl1477，ccz181078。

Code：Juan_feng，nzhtl1477，rehtorbegnaro，ccz181078。

Data：Juan_feng，nzhtl1477，rehtorbegnaro。


title: 算术天才⑨与等差数列

description:
算术天才⑨非常喜欢和等差数列玩耍。
有一天，他给了你一个长度为 $n$ 的序列，其中第 $i$ 个数为 $a_i$。
他想考考你，每次他会给出询问 $l,r,k$，问区间 $[l,r]$ 内的数从小到大排序后能否形成公差为 $k$ 的等差数列。
当然，他还会不断修改其中的某一项。
为了不被他鄙视，你必须要快速并正确地回答完所有问题。
注意：只有一个数的数列也是等差数列。

inputFormat:
第一行包含两个正整数 $n,m$，分别表示序列的长度和操作的次数。
第二行包含 $n$ 个整数，依次表示序列中的每个数 $a_i$。
接下来 $m$ 行，每行一开始为一个数 $\text{op}$，
若 $\text{op}=1$，则接下来两个整数 $x,y$，表示把 $a_x$ 修改为 $y$，
若 $\text{op}=2$，则接下来三个整数 $l,r,k$，表示一个询问。
在本题中，$x,y,l,r,k$ 都是经过加密的，都需要异或你之前输出的 `Yes` 的个数来进行解密。

outputFormat: 输出若干行，对于每个询问，如果可以形成等差数列，那么输出 `Yes`，否则输出 `No`。

hint:
【数据范围】
对于 $100\%$ 的数据， $1\le n,m \le 3\times 10^5$，$0\le a_i,y,k \le 10^9$。


title: [ZJOI2019] 麻将

description:
九条可怜是一个热爱打麻将的女孩子。因此她出了一道和麻将相关的题目，希望这题不会让你对麻将的热爱消失殆尽。

![](https://cdn.luogu.com.cn/upload/pic/55642.png)

今天，可怜想要打麻将，但是她的朋友们都去下自走棋了，因此可怜只能自己一个人打。可怜找了一套特殊的麻将，它有 $n(n\ge 5)$ 种不同的牌，大小分别为 $1$ 到 $n$，每种牌都有 $4$ 张。

定义面子为三张大小相同或者大小相邻的麻将牌，即大小形如 $i,i,i(1 \le i \le n)$ 或者$i,i+1,i+2(1\le i\le n-2)$。定义对子为两张大小相同的麻将牌，即大小形如 $i,i(1 \le i \le n)$。

定义一个麻将牌集合 $S$ 是胡的当且仅当它的大小为 $14$ 且满足下面两个条件中的至少一个：

-  $S$ 可以被划分成五个集合 $S_1$ 至 $S_5$ 。其中 $S_1$ 为对子，$S_2$ 至 $S_5$ 为面子。
-  $S$ 可以被划分成七个集合 $S_1$ 至 $S_7$ ，它们都是对子，且对应的大小**两两不同**。

举例来说，下列集合都是胡的（这儿只标记了大小）：

-  $\{1,1,1,1,2,3,4,5,6,7,8,9,9,9\}$
-  $\{1,1,2,2,4,4,5,5,6,6,7,7,8,8\}$
-  $\{1,1,2,2,3,3,4,4,5,5,6,6,7,7\}$

而下列集合都不是胡的：

-  $\{1,1,1,2,3,4,5,6,7,8,9,9,9\}$
-  $\{1,1,1,1,4,4,5,5,6,6,7,7,8,8\}$
-  $\{1,1,1,2,3,4,5,6,7,8,9,9,9,11\}$

可怜先摸出了 $13$ 张牌，并把剩下的$4n-13$张牌随机打乱。打乱是等概率随机的，即所有$(4n-13)!$种排列都等概率出现。

对于一个排列 $P$，可怜定义 $S_i$ 为可怜事先摸出的 $13$ 张牌加上 $P$ 中的前 $i$ 张牌构成的集合，定义 $P$ 的权值为**最小的 $i$  满足 $S_i$ 存在一个子集是胡的**。如果你对麻将比较熟悉，不难发现 $P$ 的权值就是理论上的最早胡牌巡目数。注意到 $n\ge 5$ 的时候，$S_{4n-13}$总是存在胡的子集的，因此 $P$ 的权值是良定义的。

现在可怜想要训练自己的牌效，因此她希望你能先计算出 $P$ 的权值的期望是多少。

inputFormat:
第一行输入一个整数 $n$，表示这副特殊的麻将牌中的大小种类数。

接下来输入 $13$ 行每行两个整数$w,t(1 ≤ w ≤ n,1 ≤ t ≤ 4)$，表示可怜最开始摸出的第 $i$ 张牌是大小为 $w$ 的第 $t$ 张牌，保证 $(w,t)$ 二元组两两不同。

outputFormat: 输出一行一个整数，表示答案对 $998244353$ 取模后的值。即如果答案的最简分数表示为$\frac{x}{y}(x ≥ 0,y ≥ 1,gcd(x,y) = 1)$，你需要输出$x\times y^{-1}\ \mathrm{mod}\: 998244353$。

hint:
上述牌型叫做纯正九莲宝灯，不难发现不管再加一张什么牌它都是胡的。所以对于所有排列 $P$，权值都是 $1$，因此权值的期望就是 $1$。

对于 $20\%$ 的数据，$n = 5$。

对于 $50\%$ 的数据，$n\le 13$。

对于另外 $20\%$ 的数据，$n \le 100,w_i = i,t_i = 1$。

对于另外 $20\%$ 的数据，$n \le 100,w_i = \lceil \frac{i}{4} \rceil ,t_i= i\ \mathrm{mod}\ 4 + 1$。

对于 $100\%$ 的数据，$5 \le n \le 100$。


title: [ZJOI2019] 线段树

description:
九条可怜是一个喜欢数据结构的女孩子，在常见的数据结构中，可怜最喜欢的就是线段树。

线段树的核心是懒标记，下面是一个带懒标记的线段树的伪代码，其中 $tag$ 数组为懒标记：

![](https://cdn.luogu.com.cn/upload/pic/55648.png)

其中函数 $\operatorname{Lson}(Node)$ 表示 $Node$ 的左儿子，$\operatorname{Rson}(Node)$ 表示 $Node$ 的右儿子。

现在可怜手上有一棵 $[1,n]$ 上的线段树，编号为 $1$。这棵线段树上的所有节点的 $tag$ 均为$0$。接下来可怜进行了 $m$ 次操作，操作有两种：

- $1\ l\ r$，假设可怜当前手上有 $t$ 棵线段树，可怜会把每棵线段树复制两份（$tag$ 数组也一起复制），原先编号为 $i$ 的线段树复制得到的两棵编号为 $2i-1$ 与 $2i$，在复制结束后，可怜手上一共有 $2t$ 棵线段树。接着，可怜会对所有编号为奇数的线段树进行一次 $\operatorname{Modify}(root,1,n,l,r)$。

- $2$，可怜定义一棵线段树的权值为它上面有多少个节点 $tag$ 为 $1$。可怜想要知道她手上所有线段树的权值和是多少。

inputFormat:
第一行输入两个整数 $n,m$ 表示初始区间长度和操作个数。

接下来 $m$ 行每行描述一个操作，输入保证 $1 \le l \le r \le n$。

outputFormat: 对于每次询问，输出一行一个整数表示答案，答案可能很大，对 $998244353$ 取模后输出即可。

hint:
[1,5] 上的线段树如下图所示：

![](https://cdn.luogu.com.cn/upload/pic/55649.png)

在第一次询问时，可怜手上有一棵线段树，它所有点上都没有标记，因此答案为 $0$。

在第二次询问时，可怜手上有两棵线段树，按照编号，它们的标记情况为：

1. 点 $[1,3]$ 上有标记，权值为 $1$。
2. 没有点有标记，权值为 $0$。

因此答案为 $1$。

在第三次询问时，可怜手上有四棵线段树，按照编号，它们的标记情况为：

1. 点 $[1,2],[3,3],[4,5]$ 上有标记，权值为 $3$。
2. 点 $[1,3]$ 上有标记，权值为 $1$。
3. 点 $[3,3],[4,5]$ 上有标记，权值为 $2$。
4. 没有点有标记，权值为 $0$。

因此答案为 $6$。

![](https://cdn.luogu.com.cn/upload/pic/55650.png)


title: [ZJOI2019] Minimax搜索

description:
九条可怜是一个喜欢玩游戏的女孩子。为了增强自己的游戏水平，她想要用理论的武器武装自己。这道题和著名的 Minimax 搜索有关。

可怜有一棵有根树，根节点编号为 $1$。定义根节点的深度为 $1$，其他节点的深度为它的父亲的深度加一。同时在叶子节点权值给定的情况下，可怜用如下方式定义了每一个非节点的权值：
- 对于深度为奇数的非叶子节点，它的权值是它所有子节点的权值最大值。
- 对于深度为偶数的非叶子节点，它的权值是它所有子节点的权值最小值。

最开始，可怜令编号为 $i$ 的叶子节点权值为 i，并计算得到了根节点的权值为 $W$。

现在，邪恶的 Cedyks 想要通过修改某些叶子节点的权值，来让根节点的权值发生改变。Cedyks 设计了一个量子攻击器，在攻击器发动后，Cedyks 会随机获得一个非空的叶子节点集合 $S$ 的控制权，并可以花费一定的能量来修改 $S$ 中的叶子节点的权值。

然而，修改叶子节点的权值也要消耗能量，对于 $S$ 中的叶子节点 $i$，它的初始权值为 $i$，假设 Cedyks 把它的权值修改成了 $w_i$（$w_i$ **可以是任意整数，包括负数**），则 Cedyks 在这次攻击中，需要花费的能量为 $\max_{i\in S} |i − w_i|$。

Cedyks 想要尽可能节约能量，于是他总是会**以最少的能量来完成攻击**，即在花费的能量最小的情况下，让根节点的权值发生改变。令 $w(S)$ 为 Cedyks 在获得了集合 $S$ 的控制权后，会花费的能量。特殊地，对于某些集合 $S$，可能无论如何改变 $S$ 中叶子节点的权值，根节点的权值都不会发生改变，这时，$w(S)$ 的值被定义为 $n$。为了方便，我们称 $w(S)$ 为 $S$ 的稳定度。

当有 $m$ 个叶子节点的时候，一共有 $2^m − 1$ 种不同的叶子节点的非空集合。在发动攻击前，Cedyks 想要先预估一下自己需要花费的能量。于是他给出了一个区间 $[L, R]$，他想要知道对于每一个 $k \in [L, R]$，有多少个集合 $S$ 满足 $w(S) = k$。

inputFormat:
第一行输入三个整数 $n,L,R(n ≥ 2,1 \leq L \leq R \leq n)$。

接下来 $n - 1$ 行每行两个整数 $u,v$，表示树上的一条边。

outputFormat: 输出一行 $R-L+1$ 个整数，第 $i$ 个整数表示 $w(S)$ 为 $L+i-1$ 的集合 $S$ 有多少个。答案可能会很大，请对 $998244353$ 取模后输出。


title: [ICPC2019 WF] Beautiful Bridges

description:
What connects us all? Well, it is often bridges. Since ancient times, people have been building bridges for roads, for trains, for pedestrians, and as aqueducts to transport water. It is humanity's way of not taking inconvenient geography for an answer.

The company Arch Bridges Construction (ABC) specializes in—you guessed it—the construction of arch bridges. This classical style of bridge is supported by pillars that extend from the ground below the bridge. Arches between pillars distribute the bridge's weight onto the adjacent pillars.

The bridges built by ABC often have pillars spaced at irregular intervals. For aesthetic reasons, ABC's bridges always have semicircular arches, as illustrated in Figure B.1. However, while a bridge arch can touch the ground, it cannot extend below the ground. This makes some pillar placements impossible.

![](https://cdn.luogu.com.cn/upload/image_hosting/r95zwobd.png)

Given a ground profile and a desired bridge height $h$, there are usually many ways of building an arch bridge. We model the ground profile as a piecewise-linear function described by $n$ key points $(x_1, y_1),(x_2, y_2), \dots ,(x_n, y_n)$, where the $x-\text{coordinate}$ of a point is the position along the bridge, and the $y-\text{coordinate}$ is the elevation of the ground above sea level at this position along the bridge. The first and last pillars must be built at the first and last key points, and any intermediate pillars can be built only at these key points. The cost of a bridge is the cost of its pillars (which is proportional to their heights) plus the cost of its arches (which is proportional to the amount of material used). So a bridge with $k$ pillars of heights $h_1, \dots , h_k$ that are separated by horizontal distances $d_1, \dots , d_{k - 1}$ has a total cost of
$$\alpha \cdot \sum_{i = 1}^{k} h_i + \beta \cdot \sum_{i = 1}^{k - 1} d_i^2$$
for some given constants $\alpha$ and $\beta$. ABC wants to construct each bridge at the lowest possible cost.

inputFormat: The first line of input contains four integers $n, h, \alpha, and \beta$, where $n$ ($2 \leq n \leq 10^4$) is the number of points describing the ground profile, $h$ ($1 \leq h \leq 10^5$) is the desired height of the bridge above sea level, and $\alpha, \beta$ ($1 \leq \alpha, \beta \leq 10^4$) are the cost factors as described earlier. Then follow $n$ lines, the $i^{\text{th}}$ of which contains two integers $x_i, y_i$ ($0 \leq x_1 < x_2 < . . . < x_n \leq 10^5$ and $0 \leq yi < h$), describing the ground profile.

outputFormat: Output the minimum cost of building a bridge from horizontal position $x_1$ to $x_n$ at height $h$ above sea level. If it is impossible to build any such bridge, output `impossible`.

translation:
给定一个地形剖面图，用 $n$（$n≤10^4$）个点描述，点 $i$ 和点 $i+1$ 之间有直线连接的地面。

你需要建一座拱桥，连接点 $1$ 和点 $n$，桥面的高度为 $h$。

你可以在桥中间建若干个柱子，以分配重量，柱子只能恰好建在给出的 $n$ 个点上（点 $1$ 和点 $n$ 上必须有柱子）。

相邻的两根柱子之间需要建一个半圆形的拱，准确地说，拱的半径为两根柱子之间的距离的一半，并且与两根柱子和桥面相切。

拱可以与地面相切，但不能相交。

同时，桥的花费与柱子高度和拱面积有关，具体地，给出两个参数 $α$ 和 $β$，则花费为：

$$\alpha \cdot \sum_{i = 1}^{k} h_i + \beta \cdot \sum_{i = 1}^{k - 1} d_i^2$$

其中 $k$ 为柱子数量，$h_i$ 为第 $i$ 个柱子的高度，$d_i$ 为第 $i$ 个柱子到第 $i+1$ 个柱子的距离。

问是否可以建出桥，若可以，问最小花费，否则输出
`impossible` 。

hint: Source: ICPC 2019 World Finals.


title: [十二省联考 2019] 异或粽子

description:
小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。

小粽面前有 $n$ 种互不相同的粽子馅儿，小粽将它们摆放为了一排，并从左至右编号为 $1$ 到 $n$。第 $i$ 种馅儿具有一个非负整数的属性值 $a_i$。每种馅儿的数量都足够多，即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 $k$ 个粽子。

小粽的做法是：选两个整数数 $l$,  $r$，满足 $1 \leqslant l \leqslant r \leqslant n$，将编号在 $[l, r]$ 范围内的所有馅儿混合做成一个粽子，所得的粽子的美味度为这些粽子的属性值的**异或和**。（异或就是我们常说的 xor 运算，即 C/C++ 中的 `ˆ` 运算符或 Pascal 中的 `xor` 运算符）

小粽想品尝不同口味的粽子，因此它不希望用同样的馅儿的集合做出一个以上的
粽子。

小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧！

inputFormat:
第一行两个正整数 $n$, $k$，表示馅儿的数量，以及小粽打算做出的粽子的数量。

接下来一行为 $n$ 个非负整数，第 $i$ 个数为 $a_i$，表示第 $i$ 个粽子的属性值。
对于所有的输入数据都满足：$1 \leqslant n \leqslant 5 \times 10^5$,  $1 \leqslant k \leqslant \min\left\{\frac{n(n-1)}{2},2 \times 10^{5}\right\}$,  $0 \leqslant a_i \leqslant 4 294 967 295$。

outputFormat: 输出一行一个整数，表示小粽可以做出的粽子的美味度之和的最大值。


title: [十二省联考 2019] 字符串问题

background:
Yazid 和 Tiffany 喜欢字符串问题。在这里，我们将给你介绍一些关于字符串的基本概念。

对于一个字符串 $S$ ，我们定义 $|S|$ 表示 $S$ 的长度。

接着，我们定义该串的子串 $S(L, R)$ 表示由 $S$ 中从左往右数，第 $L$ 个字符到第 $R$ 个字符依次连接形成的字符串，特别地，如果 $L < 1$ 或 $R > |S|$ 或 $L > R$，则 $S(L, R)$ 表示空串。

我们说两个字符串相等，当且仅当它们的长度相等，且从左至右各位上的字符依次
相同。

我们说一个字符串 $T$ 是 $S$ 的前缀，当且仅当 $S(1, |T|) = T$。

两个字符串 $S$, $T$ 相加 $S + T$ 表示的是在 $S$ 后紧挨着写下 $T$ 得到的长度为 $|S| + |T|$ 的字符串。

description:
现有一个字符串 $S$。

Tiffany 将从中划出 $n_a$ 个子串作为 $A$ 类串，第 $i$ 个（$1 \leqslant i \leqslant n_a$）为 $A_i = S(la_i, ra_i)$。

类似地，Yazid 将划出 $n_b$ 个子串作为 $B$ 类串，第 $i$ 个（$1 \leqslant i \leqslant n_b$）为 $B_i = S(lb_i, rb_i)$。

现额外给定 $m$ 组支配关系，每组支配关系 $(x, y)$ 描述了第 $x$ 个 $A$ 类串**支配** 第 $y$ 个 $B$ 类串。

求一个**长度最大**的目标串 $T$，使得存在一个串 $T$ 的分割 $T = t_1+t_2+· · ·+t_k$（$k \geqslant 0$）满足：
- 分割中的每个串 $t_i$ 均为 $A$ 类串：即存在一个与其相等的 $A$ 类串，不妨假设其为 $t_i = A_{id_i}$。
- 对于分割中所有相邻的串 $t_i, t_{i+1}$（$1 \leqslant i < k$），都有存在一个$A_{id_i}$ 支配的 $B$ 类串，使得该 $B$ 类串为 $t_{i+1}$ 的前缀。

方便起见，你只需要输出这个最大的长度即可。

特别地，如果存在无限长的目标串（即对于任意一个正整数 $n$，都存在一个满足限制的长度超过 $n$ 的串），请输出 $-1$。

inputFormat:
单个测试点中包含多组数据，输入的第一行包含一个非负整数 $T$ 表示数据组数。接下来依次描述每组数据，对于每组数据：
- 第 $1$ 行一个只包含小写字母的字符串 $S$。
- 第 $2$ 行一个非负整数 $n_a$，表示 $A$ 类串的数目。接下来 $n_a$ 行，每行 $2$ 个用空格隔开的整数。
  - 这部分中第 $i$ 行的两个数分别为 $la_i$, $ra_i$，描述第 $i$ 个 $A$ 类串。
  - 保证 $1 \leqslant la_i \leqslant ra_i \leqslant |S|$。
- 接下来一行一个非负整数 $n_b$，表示 $B$ 类串的数目。接下来 $n_b$ 行，每行 $2$ 个用空格隔开的整数。
  - 这部分中第 $i$ 行的两个数分别为 $lb_i$, $rb_i$，描述第 $i$ 个 $B$ 类串。
  - 保证 $1 \leqslant lb_i \leqslant rb_i \leqslant |S|$。
- 接下来一行一个非负整数 $m$，表示支配关系的组数。接下来 $m$ 行，每行 $2$ 个用空格隔开的整数。
  - 这部分中每行的两个整数 $x$,  $y$，描述一对 $(x, y)$ 的支配关系，具体意义见
【题目描述】。
  - 保证 $1 \leqslant x \leqslant n_a$，$1 \leqslant y \leqslant n_b$。保证所有支配关系两两不同，即不存在两组支配关系的 $x, $y **均**相同。

outputFormat:
依次输出每组数据的答案，对于每组数据：
- 一行一个整数表示最大串长。特别地，如果满足限制的串可以是无限长的，则请
输出 $-1$。

hint:
#### 样例一解释
对于第 $1$ 组数据，$A$ 类串有 $\texttt{aaba}$ 与 $\texttt{aba}$，$B$ 类串有 $\texttt{aa}$，且 $A_2$ 支配 $B_1$。我们可以找到串 $\texttt{abaaaba}$，它可以拆分成 $A_2 + A_1$，且 $A_1$ 包含由 $A_2$ 所支配的 $B_1$ 作为前缀。可以证明不存在长度更大的满足限制的串。

对于第 $2$ 组数据，与第 $1$ 组数据唯一不同的是，唯一的 $B$ 类串为 $\texttt{a}$。容易证明存在无限长的满足限制的串。

对于第 $3$ 组数据，容易证明 $\texttt{abbaabbaaaabb}$ 是最长的满足限制的串。

#### 子任务
![img](https://s2.ax1x.com/2019/04/06/AW276I.png)

为了方便你的阅读，我们把**测试点编号**放在了表格的中间，请你注意这一点。

表格中的 $|A_i| > |B_j|$ 指的是**任意** $B$ 类串的长度不超过**任意** $A$ 类串的长度。

对于所有测试点，保证：$T \leqslant 100$，且对于测试点内所有数据，$|S|$, $n_a$, $n_b$, $m$ 的**总和**分别不会超过**该测试点中对应**的**单组数据的限制**的 $10$ 倍。比如，对于第 $1$ 组测试点，就有 $\sum n_a \leqslant 10 \times 100 = 1000$ 等。特别地，我们规定对于测试点 $4$，有 $T \leqslant 10$。

对于所有测试点中的每一组数据，保证：$1 \leqslant |S| \leqslant 2 \times 10^5$，$n_a$, $n_b \leqslant 2 \times 10^5$，$m \leqslant 2 \times 10^5$

#### 提示
十二省联考命题组温馨提醒您：

**数据千万条，清空第一条。**

**多测不清空，爆零两行泪。**


title: [十二省联考 2019] 骗分过样例

background:
这是一道**传统题**。

“我的程序需要完成什么功能呀？. . . . . . ”

“我也不知道. . . . . . ”

“啊？那我怎么写呀. . . . . . ”

“已经有人给你写好测试了，只要你通过这些测试就可以了. . . . . . ”

“啊？. . . . . . ”

“所有的测试数据都在题目目录下，请做好备份，避免误删！”

“这. . . . . . ”

“哦，我还可以把输入格式告诉你. . . . . . 不过都有完整的数据了，知道输入格式可能也没太大用处吧. . . . . . ”

description: 题目数据详见附加文件

inputFormat:
第一行输入一个字符串，表示需要运行的软件功能编号。两个编号越相似，说明对
应的两个功能的算法越接近。

接下来根据功能的不同，可能有任意长度的输入，详见每个功能的文档。

outputFormat: 详见每个功能的文档。

hint:
#### 子任务
“‘每个功能的文档’在哪里呀？”

“我也没有，就像我没有题目描述一样. . . . . . ”

“好吧. . . . . . 那我是不是打表就可以了呀. . . . . . ”

“**代码长度限制是 $\bold{102400}$ 字节** （$100$KB），直接打肯定是不行的！不过，需要的话倒是可以稍微打一些小的表. . . . . . ”

“唔. . . . . . ”

“另外，我们会给你的程序对于每个测试点分别评分，求和后得到总分。按照传统
的规矩，每个测试点正确得满分，错误得 $0$ 分。**每个测试点的分值不全相同，测试点的分值、顺序与难度没有必然联系** 。”

| 测试点 | 功能编号 | 分值 |
| :-------: | :-------: | :-------: |
| $1$ | $\texttt{1\_998244353}$ | $4$ |
| $2$ | $\texttt{1\_998244353}$ | $4$ |
| $3$ | $\texttt{1\_998244353}$ | $4$ |
| $4$ | $\texttt{1?}$ | $7$ |
| $5$ | $\texttt{1?+}$ | $9$ |
| $6$ | $\texttt{1wa\_998244353}$ | $6$ |
| $7$ | $\texttt{1wa\_998244353}$ | $7$ |
| $8$ | $\texttt{2p}$ | $4$ |
| $9$ | $\texttt{2p}$ | $6$ |
| $10$ | $\texttt{2p}$ | $8$ |
| $11$ | $\texttt{2u}$ | $5$ |
| $12$ | $\texttt{2u}$ | $6$ |
| $13$ | $\texttt{2u}$ | $9$ |
| $14$ | $\texttt{2g}$ | $5$ |
| $15$ | $\texttt{2g}$ | $7$ |
| $16$ | $\texttt{2g?}$ | $9$ |

#### 提示
在你使用 C/C++ 的 `int` 类型时，如果发生了溢出，比较可能的情况是按照模 $2^{32}$ 同余的前提下，在 `int` 范围内取一个合理的值。例如在计算 $2147483647 + 2$ 时，较有可能会得到 -$2147483647$。

然而，C/C++ 标准将这种情况归类为“未定义行为”。当你的程序试图计算会溢
出的 `int` 运算时，除了上述结果外，编译器还可能会让你的程序在此时计算出错误结果、死循环、运行错误等，这也是符合 C/C++ 标准的。

如果你的程序希望利用 `int` 的自然溢出的特性，请转换为 `unsigned` 类型运算。例如将 `a + b` 改写为 `(int) ((unsigned) a + (unsigned) b)`，以避免出现不预期的错误。


title: [HNOI2019] 鱼

background: $\text{\color{white}本题数据听说没问题？}$

description:
在平面坐标系上给定$n$个不同的整点（也即横坐标与纵坐标皆为整数的点）。我们称从这$n$个点中选择6个不同的点所组成的有序六元组$(A,B,C,D,E,F)$是一条“鱼”，当且仅当：$AB=AC,BD=CD,DE=DF$（身形要对称），并且$\angle BAD,\angle BDA$ 与$\angle CAD,\angle CDA$都是锐角（脑袋和屁股显然不能是凹的），$\angle ADE,\angle ADF$ 大于$90^\circ$（也即为钝角或平角，为了使尾巴不至于翘那么别扭）。

下图就是一个合法的鱼的例子：

![](https://cdn.luogu.com.cn/upload/pic/56001.png)

其中点的组成相同，但顺序不同的鱼视为不同的鱼，即$(A,B,C,D,E,F)$和$(A,C,B,D,E,F)$视为不同的两条鱼（毕竟鱼也有背和肚子的两面），同理$(A,B,C,D,E,F)$和$(A,B,C,D,F,E)$也可以视为不同的两条鱼（假设鱼尾巴可以打结）。

问给定的$n$个点可以构成多少条鱼。特别的，数据保证$n$个点互不重复。

inputFormat:
第一行一个正整数$n$，代表平面上点的个数。

接下来$n$行每行两个整数$x,y$，代表点的横纵坐标。

outputFormat: 输出一行一个非负整数，代表鱼的个数。

hint:
对于前 20%的数据，保证$n \leq 10,|x|,|y| \leq 5$

对于前 40%的数据，保证$n \leq 300$，$0 \leq |x|,|y| \leq 10^5$。

对于另外 20%的数据，保证$|x|,|y| \leq 20$。

对于所有数据，保证$6 \leq n \leq 1000$，$0 \leq |x|, |y| \leq 10^9$，$n$个点互不重复。


title: [HNOI2019] JOJO

background: JOJO 的奇幻冒险是一部非常火的漫画。漫画中的男主角经常喜欢连续喊很多的 “欧拉” 或者 “木大”。

description:
为了防止字太多挡住漫画内容，现在打算在新的漫画中用 $x$ 欧拉或者 $x$ 木大表示有 $x$ 个欧拉或者木大。

为了简化内容我们现在用字母表示喊出的话。

我们用数字和字母来表示一个串，例如 `2 a 3 b` 表示的串就是 $aabbb$。

一开始漫画中什么话都没有，接下来你需要依次实现 $n$ 个操作，总共只有 $2$ 种操作：

- 第一种：`1 x c` 在当前漫画中加入 $x$ 个 $c$，表示在当前串末尾加入 $x$ 个 $c$ 字符。保证当前串是空串或者串尾字符不是 $c$。
- 第二种：`2 x` 觉得漫画没画好将漫画还原到第 $x$ 次操作以后的样子，表示将串复原到第 $x$ 次操作后的样子，如果 $x=0$ 则是将串变成空串。

如果当前串是 $bbaabbb$，第 $4$ 次操作后串是 $bb$，则 `2 4` 会使 $bbaabbb$ 变成 $bb$，保证 $x$ 小于当前操作数。

众所周知空条承太郎十分聪明，现在迪奥已经被打败了，他开始考虑自己的漫画中的一些问题：

对于一个串的每个前缀 $A$，都有一个最长的比它短的前缀 $B$ 与前缀 $A$ 的一个后缀匹配，设这个最长的前缀 $B$ 的长度为 $L$。$L$ 为 $0$ 时意味着 $B$ 是一个空串。

每一次操作后，你都需要将当前的串的所有前缀的 $L$ 求和并对 $998244353$ 取模输出告诉空条承太郎，好和他的白金之星算出的答案对比。

比如 $bbaaabba$ 的 $L$ 分别是 $0, 1, 0, 0, 0, 1, 2, 3$，所以对于这个串的答案就是 $7$。

inputFormat:
第一行包括一个正整数 $n$，表示操作数量。

接下来 $n$ 行每行包含一个操作，操作格式如题面所示，例如

- `1 x c`
- `2 x`

保证数据合法。

outputFormat: 输出文件仅包含 $n$ 行，第 $i$ 行一个整数，表示 $i$ 个操作之后串的答案。


title: [HNOI2019] 多边形

description:
小 R 与小 W 在玩游戏。

他们有一个边数为$n$的凸多边形，其顶点沿逆时针方向标号依次为$1,2,3,\cdots , n$。最开始凸多边形中有$n$条线段，即多边形的$n$条边。这里我们用一个有序数对$(a, b)$（其中$a < b$）来表示一条端点分别为顶点$a,b$的线段。

在游戏开始之前，小 W 会进行一些操作。每次操作时，他会选中多边形的两个互异顶点，给它们之间连一条线段，并且所连的线段不会与已存的线段重合、相交（只拥有一个公共端点不算作相交）。

他会不断重复这个过程，直到无法继续连线，这样得到了状态$s_0$。$s_0$包含的线段为凸多边形的边与小W 连上的线段，容易发现这些线段将多边形划分为一个个三角形区域。对于其中任意一个三角形，其三个顶点为$i,j,k(i < j < k)$，我们可以给这个三角形一个标号$j$，这样一来每个三角形都被标上了$2,3, \cdots , n - 1$中的一个，且没有标号相同的两个三角形。

小 W 定义了一种“旋转”操作：对于当前状态，选定$4$个顶点$a,b,c,d$，使其满足$1 \leq a < b < c <d \leq n$且它们两两之间共有$5$条线段——$(a,b), (b,c), (c,d), (a,d), (a,c)$，然后删去线段$(a,c)$，并连上线段$(b,d)$。那么用有序数对$(a,c)$即可唯一表示该次“旋转”。我们称这次旋转为$(a,c)$ “旋转”。显然每次进行完“旋转”操作后多边形中依然不存在相交的线段。

当小 W 将一个状态作为游戏初始状态展示给小 R 后，游戏开始。游戏过程中，小 R 每次可以对当前的状态进行“旋转”。在进行有限次“旋转”之后，小 R 一定会得到一个状态，此时无法继续进行“旋转”操作，游戏结束。那么将每一次“旋转”所对应的有序数对按操作顺序写下，得到的序列即为该轮游戏的操作方案。

为了加大难度，小 W 以$s_0$为基础，产生了$m$个新状态。其中第$i$个状态$s_i$为对$s_0$进行一次“旋转”操作后得到的状态。你需要帮助小 R 求出分别以$s_0,s_1\cdots s_n$作为游戏初始状态时，小 R 完成游戏所用的最少“旋转”次数，并根据小 W 的心情，有时还需求出“旋转”次数最少的不同操作方案数。由于方案数可能很大，输出时请对$1e9+7$取模。

inputFormat:
第一行一个整数$W$，表示小W的心情。若$W$为$0$则只需求出最少的“旋转”次数，若$W$为$1$则还需求出“旋转”次数最少时的不同操作方案数。

第二行一个正整数$n$，表示凸多边形的边数。

接下来$n-3$行，每行两个正整数$x,y$，表示小W在$s_0$中连的一条线段，端点分别为$x,y$。保证该线段不与已存的线段重合或相交。

接下来一行一个整数$m$，表示小W以$s_0$为基础产生的新状态个数。

接下来$m$行，每行两个整数。假设其中第$i$行为$a,b$，表示对$s_0$进行$(a,b)$“旋转”后得到$s_i$。

outputFormat:
输出共$m+1$行。

若$W$为$0$则每一行输出一个整数，第$i(i = 1,2, \cdots , m, m + 1)$行输出的整数表示$S_{i-1}$作为初始局面的最少“旋转”次数。

若$W$为$1$则每一行输出两个整数，第$i(i = 1,2, \cdots , m, m + 1)$行输出的两个整数依次表示$S_{i-1}$作为初始局面的最少“旋转”次数、“旋转”次数最少的不同操作方案数对$1e9+7$取模的结果。


title: 下降幂多项式转普通多项式

background: 这是一道模板题

description:
已知下降幂多项式 $F(x)=\displaystyle\sum_{i=0}^{n-1}a_ix^{\underline{i}}$。

求一个普通多项式 $G(x)=\displaystyle\sum_{i=0}^{n-1}b_ix^i$。

使得 $G(x)=F(x)$。

所有运算均在 $\bmod\ 998244353$ 意义下进行。

inputFormat:
第一行一个正整数 $n$，如题所述。

第二行 $n$ 个数，第 $i$ 个数表示 $a_{i-1}$。

outputFormat: 一行 $n$ 个数，第 $i$ 个数为 $b_{i-1}$。


title: 普通多项式转下降幂多项式

background: 这是一道模板题

description:
已知普通多项式 $F(x)=\displaystyle\sum_{i=0}^{n-1}a_ix^{i}$。

求下降幂多项式 $G(x)=\displaystyle\sum_{i=0}^{n-1}b_ix^{\underline{i}}$。

使得 $G(x)=F(x)$。

所有运算均在 $\bmod\ 998244353$ 意义下进行。


title: [十二省联考 2019] 皮配

background:
一年一度的综艺节目《中国好码农》又开始了。本季度，好码农由 Yazid、Zayid、小 R、大 R 四位梦想导师坐镇，他们都将组建自己的梦想战队，并率领队员向梦想发起冲击。

四位导师的**派系**不尽相同，节目组为了营造看点，又将导师分成了不同的**阵营**，与此同时对不同阵营、不同派系都作出了战队总人数限制：
- 四位导师分成两个**阵营**：
  - Yazid、小 R 两位导师组成**蓝阵营**，他们两位的战队人数**总和**不得超过 $C_0$。
  - Zayid、大 R 两位导师组成**红阵营**，他们两位的战队人数**总和**不得超过 $C_1$。
- 四位导师分成两个**派系**：
  - Yazid、Zayid 两位导师属于**鸭派系**，他们两位的战队人数**总和**不得超过 $D_0$。
  - 小 R、大 R 两位导师属于 **R 派系**，他们两位的战队人数**总和**不得超过 $D_1$。

description:
本季好码农邀请到了全国各路学生精英参赛。他们来自全国 $c$ 个城市的 $n$ 所不同学校（城市的编号从 $1$ 至 $c$，学校的编号从 $1$ 至 $n$）。其中，第 $i$ 所学校所属的城市编号为 $b_i$，且共有 $s_i$ 名选手参赛。

在【题目背景】中提到的各总人数限制之外，本季度《中国好码农》的导师选择阶
段有额外规则如下：
- 来自同**城市**的所有选手必须加入相同的**阵营**。
- 来自同**学校**的所有选手必须选择相同的**导师**。

对于导师，大部分学校的学生对导师没有**偏好**。但是有 $k$ 所学校，其中每所学校的学生有且仅有一位他们不喜欢的导师。同一所学校的学生不喜欢的导师相同，他们**不会加入他们不喜欢的导师的战队**。

面对琳琅满目的规则和选手的偏好，作为好码农忠实观众的你想计算出，在所有选
手都进行了战队选择后，战队组成共有多少种可能的局面？
- 两种战队组成的局面被认为是不同的，当且仅当在存在一所学校，使得在这两种
局面中这所学校的选手加入了不同导师的战队。
- 由于答案可能很大，你只需输出可能局面数对 $998244353$ 取模的结果即可。

inputFormat:
单个测试点中包含多组数据，输入的第一行包含一个非负整数 $T$ 表示数据组数。接下来依次描述每组数据，对于每组数据：
- 第 $1$ 行 $2$ 个正整数 $n$, $c$，分别表示学校数目、城市数目。
- 第 $2$ 行 $4$ 个正整数 $C_0$, $C_1$, $D_0$, $D_1$，分别表示题目中所描述的四个限制。
- 接下来 $n$ 行每行 $2$ 个正整数：
  - 这部分中第 $i$ 行的两个数依次为 $b_i$, $s_i$，分别表示第 $i$ 所学校的所属城市以及选手数目。
  - 保证 $b_i \leqslant c$，$s_i \leqslant\min\left\{M, 10\right\}$。其中 $M = \max \left\{C_0, C_1, D_0, D_1\right\}$。
- 接下来 $1$ 行一个非负整数 $k$，表示选手有偏好的学校数目。
- 接下来 $k$ 行，每行 $2$ 个整数 $i$, $p$，描述编号为 $i$ 的学校选手有偏好：
  - 其中，$p$ 为一个 $0$ 至 $3$ 之间的整数，描述该校选手不喜欢的导师：$0$ 代表 Yazid，$1$ 代表小 R，$2$ 代表 Zayid，$3$ 代表大 R。
  - 保证 $1 \leqslant i \leqslant n$，且各行的 $i$ 互不相同。

对于输入的每一行，如果其包含多个数，则用单个空格将它们隔开。

outputFormat:
依次输出每组数据的答案，对于每组数据：
- 一行一个整数，表示可能局面数对 $998244353$ 取模的结果。

hint:
### 样例 1 解释
对于第 $1$ 组数据：
- 唯一的城市 $1$ 包含共 $3$ 名选手，但红阵营的总人数限制为 $2$，无法容纳这些选手，因此他们被迫只能选择蓝阵营。
- 在此基础上，由于 $1$ 号学校的选手不喜欢 Yazid 老师，因此他们就必须加入 R
派系的小 R 老师麾下。
- 由于 R 派系总人数限制为 $2$，因此小 R 老师战队无法容纳 $2$ 号学校的选手，所以他们只能被迫加入Yazid 老师战队。
- 综上所述，可能的局面仅有这一种。

对于第 $2$ 组数据：
- 一个显然的事实是，$1$ 号城市的所有选手都无法加入蓝阵营，这是因为 $1$ 号城市的选手总人数超过了蓝阵营的总人数限制，因此他们被迫全部加入红阵营。
- 对于 $2$ 号城市选手加入蓝阵营的情况，稍加计算可得出共有 $15$ 种可能的局面。
- 对于 $2$ 号城市选手加入红阵营的情况，稍加计算可得出共有 $7$ 种可能的局面。
- 综上所述，可能的局面数为 $15 + 7 = 22$ 种。

### 数据规模与约定
![img](https://s2.ax1x.com/2019/04/07/AfzWPe.png)

其中，$M = \max\left\{C_0, C_1, D_0, D_1\right\}$。

对于所有测试点，保证 $T \leqslant5$。

对于所有测试点中的每一组数据， 保证 $c \leqslant n \leqslant 1000$，$k \leqslant 30$，$M \leqslant 2500$，$1 \leqslant s_i \leqslant \min\left\{M, 10\right\}$。

**另外，请你注意，数据并不保证所有的 $c$ 个城市都有参赛学校。**

### 提示
另外还有两组附加样例文件，请在附件中下载。

十二省联考命题组温馨提醒您：

**数据千万条，清空第一条。**
**多测不清空，爆零两行泪。**


title: [十二省联考 2019] 春节十二响

background:
“清明时节雨纷纷，路上行人欲断魂。”

$2075$ 年的清明没有春雨。在漫天飞雪的笼罩下，穿行在冰原间的，只有载着人类微薄希望的雪地车。

遥遥 $4.22$ 光年的征途，对于地球这孤独的旅人而言，恐怕也是无比寂寞吧。

description:
距离苏拉威西只有一百公里了，车内的空气比窗外更加冰冷。四双眼睛紧盯着艾莉
芬面前的屏幕，那是控制行星发动机的关键程序：春节十二响。他需要将其部署到电力控制系统的一个芯片中。

“春节十二响”由 $n$ 个子程序构成，第 $i$ 个子程序所需的内存空间是 $M_i$。这 $n$ 个子程序之间的调用关系构成了一棵以第 $1$ 个子程序为根的树，其中第 $i$ 个子程序在调用树上的父亲是第 $f_i$ 个子程序。

由于内存紧张，电力控制芯片上提供了一种内存分段机制。你可以将内存分为若干
个段 $S_1$, $S_2$, ..., $S_k$，并将每个程序预先分配到一个固定的段。如果两个子程序没有直接或间接的调用关系，则他们可以被分配到同一个段中，反之则不能。换言之，当且仅当 $a$ 和 $b$ 在调用树上**不是祖先—后代关系**，$a$ 和 $b$ 可以被分配到同一个段中。

一个段的大小应当是所有分配到这个段的子程序所需内存大小的最大值，所有段
大小的和不能超过系统的内存大小。

现在艾莉芬想要知道，电力控制芯片至少要有多少内存，才能保证春节十二响的正
确运行。即：最少需要多大的内存，才能通过先**将内存分成若干个段**，再**把每个子程序分配到一个段中，使得每个段中分配的所有子程序之间不存在祖先—后代关系**。

inputFormat:
第一行包含一个正整数 $n$ 表示子程序的个数，其中 $n \leqslant 2 \times 10^5$。

第二行有 $n$ 个用空格隔开的正整数 $M_1$, $M_2$, ..., $M_n$，$M_i$ 表示第 $i$ 个子程序所需的内存空间。

第三行有 $n - 1$ 个用空格隔开的正整数 $f_2$, $f_3$, ..., $f_n$，满足 $f_i < i$，表示第 $i$ 个子程序在调用树上的父亲是第 $f_i$ 个子程序。

outputFormat: 仅一个整数，表示最小的内存需求。

hint:
#### 样例 $1$ 解释
在最优方案中，内存被划分为大小为 $10$，$20$，$30$ 的三个段，其中第 $1$ 个子程序被分配在第 $1$ 个段中，第 $2$、$3$ 个子程序被分配在第 $2$ 个段中，第 $4$、$5$ 个子程序被分配在第 $3$ 个段中。可以证明，不存在更优的方案。

#### 子任务
![img](https://s2.ax1x.com/2019/04/07/AhSGzd.png)

注意：在第 $10$、$11$、$12$ 号测试点中，$1$ 号子程序**不一定**是链的一个端点。

其中 $M$ 是所有子内存需求的最大值，即 $\max\left\{M_i\right\}$。

对于全部数据，$1 \leqslant n \leqslant2 \times 10^5$，$1 \leqslant M \leqslant 10^9$。

艾莉芬经过仔细阅读题面、认真分析数据范围后，开始编写程序求解这个问题。

$\texttt{\$ login Elephant}$

$\texttt{password: ********}$

艾莉芬，高级程序员。豫阳市第三工程组提醒您：

- 做题千万条，读题第一条；

- 编程不规范，爆零两行泪。

$\texttt{\$ cd spring}$

$\texttt{\$ ac spring}$

$\texttt{Spring Accepted. Score: 100/100.}$


title: [十二省联考 2019] 希望

background:
我们所可以自慰的，想来想去，也还是所谓对于将来的希望。

希望是附丽于存在的，有存在，便有希望，有希望，便是光明。

description:
苏拉威西。距离地球进入木星洛希极限还有 $L$ 单位时间。

蔡德仁收到了来自艾莉芬的“点燃木星计划”。计划要求他将附近所有救援队召集到同一台转向发动机处，清除障碍，并用“春节十二响”程序操纵发动机点燃木星。

转向发动机共有 $n$ 个，它们由 $n - 1$ 条道路相连。任意两个转向发动机都可以通过道路互相到达，二者的距离为其间最短路径的**边数**。

附近一共部署有 $k$ 支救援队 $s_1$, $s_2$, ..., $s_k$，每一支救援队有一个救援范围。救援范围是转向发动机集合的一个连通子集，其中任意两个发动机之间道路上的所有发动机都在救援范围中。

我们称一个发动机 $u$ 可被救援范围为 $S$ 的救援队**到达**，当且仅当 $u$ 在 $S$ 中，且 $S$ 中任意一个发动机 $v$ 到 $u$ 的距离都**不大于** $L$。这样，无论救援队身在岗位的何处，他们都能在时间耗尽前抵达发动机 $u$。

蔡德仁要指挥 $k$ 支救援队集中到同一台发动机处。但由于通讯中断，蔡德仁不知
道每支救援队的救援范围。他想计算出可行的调度方案数，于是将问题输入电脑。

在这台电脑的另一面——你，需要帮他统计出，在多少种可能的部署方案中存在一
台能被所有救援队到达的发动机。一个**方案**指一组救援范围 $\left\{S_1, S_2, ..., S_k\right\}$；两个方案不同，当且仅当某个救援队 $s_i$ 在二者中的救援范围 $S_i$ 不同。在这次联合政府规划的饱和式救援中，两支队伍的救援范围可能**相交**甚至**相同**。

你知道，答案非常大。雪地车在成千上万个地标间穿梭，可能的救援范围浩如烟海，集合所有队伍的方案却寥若晨星。但你没时间绝望，甚至没时间算出那个数字。

你只能算出答案对 $998244353$ 取模的结果。

那就是希望。

即便需要取模，也是光明。

inputFormat:
第一行包含三个数 $n$，$L$，$k$，依次表示转向发动机的个数，拯救地球剩余的时间，和救援队的个数。

接下来 $n - 1$ 行，每行两个整数 $u$，$v$，表示第 $u$ 个和第 $v$ 个转向发动机之间有一条道路相连。

outputFormat: 仅一个整数，表示方案数对 $998244353$ 取模的结果。

hint:
#### 样例 $1$ 解释
一共有以下几个可行的方案：

| 1 号救援队 | 2 号救援队 |
| :---------- | :---------- |
| $\texttt{\{1\}}$ | $\texttt{\{1\}}$ |
| $\texttt{\{1\}}$ | $\texttt{\{1,2\}}$ |
| $\texttt{\{2\}}$ | $\texttt{\{2\}}$ |
| $\texttt{\{2\}}$ | $\texttt{\{1,2\}}$ |
| $\texttt{\{1,2\}}$ | $\texttt{\{1\}}$ |
| $\texttt{\{1,2\}}$ | $\texttt{\{2\}}$ |
| $\texttt{\{1,2\}}$ | $\texttt{\{1,2\}}$ |

#### 样例 $2$ 解释
只有一个救援队，除了这个救援队的救援范围是全集 $\texttt{\{1,2,3,4\}}$ 之外的所有方案都可行。

#### 样例 $4$ 解释

这个测试点的图如下图所示：

![](https://cdn.luogu.com.cn/upload/image_hosting/yownegrq.png)

#### 子任务

![](https://cdn.luogu.com.cn/upload/image_hosting/h64qjcoa.png)

对于所有数据，有 $1 \leqslant n \leqslant 10^6$，$0 \leqslant L \leqslant n$，$1 \leqslant k \leqslant 10$。

~~**请确认程序使用了文件输入输出、没有输出多余调试信息。**~~

蔡德仁抬起头。那是他从未见过的景象——木星占据了大半个天空，绚丽的色彩透过稀薄的大气，变得格外刺眼。

无边的海洋里漂流的小船，不知何时就会被狂风所倾覆；而小船上平凡的我们，也只能怀着渺茫的希望，跟随着舵手指引的航向前行吧。

他走上前按下了 $\texttt{Enter}$。

\$ sudo ./spring12biubiu

指令已经发出。


title: [HNOI2019] 校园旅行

background: HNOI2019 Day2T1

description:
某学校的每个建筑都有一个独特的编号。一天你在校园里无聊，决定在校园内随意地漫步。

你已经在校园里呆过一段时间，对校园内每个建筑的编号非常熟悉，于是你情不自禁的把周围每个建筑的编号都记了下来——但其实你没有真的记下来，而是把每个建筑的编号除以 2 取余数得到 0 或 1，作为该建筑的标记，多个建筑物的标记连在一起形成一个 01 串。

你对这个串很感兴趣，尤其是对于这个串是回文串的情况，于是你决定研究这个问题。

学校可以看成一张图，建筑是图中的顶点，而某些顶点之间存在无向边。对于每个顶点我们有一个标记（0 或者 1）。每次你会选择图中两个顶点，你想知道这两个顶点之间是否存在一条路径使得路上经过的点的标记形成一个回文串。

一个回文串是一个字符串使得它逆序之后形成的字符串和它自己相同，比如 “010”，“1001” 都是回文串，而 “01”，“110” 不是。注意长度为 1 的串总是回文串，因此如果询问的两个顶点相同，这样的路径总是存在。此外注意，经过的路径不一定为简单路径，也就是说每条边每个顶点都可以经过任意多次。

inputFormat:
输入文件名为 tour.in。

第一行三个整数 $n, m, q$，表示图中的顶点数和边数，以及询问数。

第二行为一个长度为 $n$ 的 01 串，其中第 $i$ 个字符表示第 $i$ 个顶点（即顶点 $i$）的标记，点从 1 开始编号。

接下来 $m$ 行，每一行是两个整数 $u_i, v_i$，表示顶点 $u_i$ 和顶点 $v_i$ 之间有一条无向边，不存在自环或者重边。

接下来 $q$ 行，每一行存在两个整数 $x_i, y_i$，表示询问顶点 $x_i$ 和顶点 $y_i$ 的点之间是否有一条满足条件的路径。

outputFormat:
输出文件名为 tour.out。

输出 $q$ 行，每行一个字符串 “YES”，或者 “NO”（引号不输出）。输出 “YES” 表示满足条件的路径存在，输出 “NO” 表示不存在。

hint:
【样例解释 1】

对于第一个询问，3 号点和 2 号点不连通，因此答案为 “NO”。

对于第二个询问，一条合法的路径是 1→3，路径上的标号形成的字符串为 “00”。注意合法路径不唯一。

【数据范围】

对于 $30\%$ 的数据，$1 \leq m \leq 10 ^ 4$；

对于 $70\%$ 的数据，$1 \leq n \leq 3000$，$1 \leq m \leq 5\times 10 ^ 4$；

对于 $100\%$ 的数据，$1 \leq n \leq 5000$，$1 \leq m \leq 5\times 10 ^ 5$，$1 \leq q \leq 10 ^ 5$。

【编译命令】

对于 c++ 语言：g++ -o tour tour.cpp –lm -O2

对于 c 语言：gcc -o tour tour.c –lm -O2

对于 pascal 语言：fpc tour.pas -O2


title: [HNOI2019] 白兔之舞

background: HNOI2019 day2t2

description:
有一张顶点数为 $(L+1)\times n$ 的有向图。这张图的每个顶点由一个二元组$(u,v)$表示$(0\le u\le L,1\le v\le n)$。
这张图不是简单图，对于任意两个顶点 $(u_1,v_1)(u_2,v_2)$，如果 $u_1<u_2$，则从 $(u_1,v_1)$ 到 $(u_2,v_2)$ 一共有 $w[v_1][v_2]$ 条不同的边，如果 $u_1\ge u_2$ 则没有边。

白兔将在这张图上上演一支舞曲。白兔初始时位于该有向图的顶点 $(0,x)$。

白兔将会跳若干步。每一步，白兔会从当前顶点沿任意一条出边跳到下一个顶点。白兔可以在任意时候停止跳舞（也可以没有跳就直接结束）。当到达第一维为 $L$ 的顶点就不得不停止，因为该顶点没有出边。

假设白兔停止时，跳了 $m$ 步，白兔会把这只舞曲给记录下来成为一个序列。序列的第 $i$ 个元素为它第 $i$ 步经过的边。

问题来了：给定正整数 $k$ 和 $y$（$1\le y\le n$），对于每个 $t$（$0\le t<k$），求有多少种舞曲（假设其长度为 $m$）满足 $m \bmod k=t$，且白兔最后停在了坐标第二维为 $y$ 的顶点？

两支舞曲不同定义为它们的长度（$m$）不同或者存在某一步它们所走的边不同。

输出的结果对 $p$ 取模。

inputFormat:
输入文件名为 dance.in。

第一行五个用空格隔开的整数 $n,k,L,x,y,p$。

接下来 $n$ 行，每行有 $n$ 个用空格隔开的整数，第 $i$ 行的第 $j$ 个数表示 $w[i][j]$。

outputFormat:
输出文件名为 dance.out。

依次输出 $k$ 行，每行一个数表示答案对 $p$ 取模的结果。


title: [HNOI2019] 序列

background: HNOI2019 day2t3

description:
给定一个长度为$n$的序列$A_1, … , A_n$，以及$m$个操作，每个操作将一个$A_i$修改为$k$。第一次修改之前及每次修改之后，都要求你找到一个同样长度为$n$的单调不降序列$B_1,… ,B_n$，使得$\sum_{i=1}^n(A_i-B_i)^2$最小，并输出最小值。

需要注意的是每次操作的影响都是独立的，也即每次操作只会对当前询问造成影响。为了避免精度问题，我们保证这个最小值是个分数，也即能表示为两个非负整
数相除的形式：$x/y$。那么你将要输出$(x\times y^{p-2}\mod p)$的值，表示模意义下$x/y$的值。其中$P =
998244353$是一个大质数。

inputFormat:
输入文件名为sequence.in。

第一行两个非负整数$n,m$，代表序列长度和操作数。

第二行有$n$个由空格隔开的正整数，代表序列$A_1, … , A_n$ 。

接下来$m$行每行两个正整数$i$, $k$，代表将$A_i$修改为$k$。

outputFormat:
输出文件名为sequence.out。

输出$m+1$行每行一个整数，第$i$行输出第$i-1$次修改后的答案。特别的，第1行应为初始局面的答案。

hint:
【样例解释】

第一个询问的最优B序列为：{5 5 5 5 5}。

第二个询问的最优B序列为：{1 2 4 5 5}。

第三个询问的最优B序列为：{3 3 4 5 5}。

第四个询问的最优B序列为：{5 5 5 6 6}。

样例是存在最优方案使$B_i$皆为整数的特殊情况。

【数据范围】

对于前 10%的数据，保证$n,m\le 10$，$k,A_i\le 1000$  ，且存在一种最优方案，使得$B_i$皆为整数。

对于前 30%的数据，保证 $n,m\le 100$。

对于另外 20%的数据，保证 $m = 0$ 。

对于另外 20%的数据，保证 $n,m \le 3 \times  10^4$。

对于所有数据，保证 $3 \le n \le 10^5,0 \le m \le 10^5,1 \le k, A_i \le 10^9$。

【编译命令】

对于 c++语言： g++ -o sequence sequence.cpp –lm –O2

对于 c 语言： gcc -o sequence sequence.c –lm –O2

对于 pascal 语言： fpc sequence.pas –O2


title: [北京省选集训2019] 完美塔防

background: 小N最近喜欢玩一款塔防游戏。

description:
这款游戏的棋盘是一个 $n \times m$ 的网格，每个格子上会有以下类型物件：

1. A 型炮台：会向上下两个方向同时发射激光，符号为 `|`;
2. B 型炮台：会向左右两个方向同时发射激光，符号为 `-`;
3. 空地：激光穿过该物件会保持方向前进，符号为 `.`;
4. 障碍：激光到达该物件会消失，符号为 `#`;
5. 正反射镜：激光到达该物件后，会依物理定律改变方向，但仍继续前进，符号为 `\`;
6. 副反射镜：激光到达该物件后，会依物理定律改变方向，但仍继续前进，符号为 `/`;

注意激光之间可以互相穿过，但如果激光射出网格边界，也会消失。
小 N 是一个强迫症玩家，他想让每一处空地都会被至少一束激光打到，但不能让激光攻击到自己的炮台以致损坏。
小 N 可以将任意多的 A 型炮台改造成 B 型炮台，也可以把任意多的 B 型炮台改造成 A 型炮台。
你可以告诉他能否通过这些改造实现他的目标吗?

inputFormat:
第一行一个正整数 $T$，表示数据组数。
每组数据第一行有两个正整数 $n,m$。
接下来 $n $ 行，每行一个长度为 $m$ 的字符串，表示棋盘。

outputFormat:
对于每组数据，若无解则输出一行 `IMPOSSIBLE`，否则输出一行 `POSSIBLE`，再输出改造后的棋盘。
如果有多组解，输出任意一个即可。

samples:
IMPOSSIBLE
POSSIBLE
#.##
#||#
####
POSSIBLE
.-.
|//
.-.
#\/

hint:
### 数据范围：

对于$100\%$的数据：

- $1\le T \le 200$；
- $1\le n,m \le 50$。

Special Judge provided by @tiger2005.


title: [北京省选集训2019] 生成树计数

description:
小S 刚刚学习了生成树的知识，聪明的他想出了一个问题：
给定一个 $n$ 个点的带权无向完全图，求其所有生成树权值的 $k$ 次方之和。
定义一个树的权值，为其所有边权值和。

因为他不会，所以你要来做这题。
由于答案可能很大，请输出答案对 $998244353$ 取模的结果。

inputFormat:
第一行两个非负整数 $n,k$，意义如题目描述。
接下来 $n$ 行，每行 $n$ 个整数，为这个带权无向完全图的邻接矩阵表示。
设 $w_{i,j}$ 表示矩阵的第 $i$ 行第 $j$ 列，保证：
$w_{i,i}=0$，且 $w_{i,j}=w_{j,i}$

outputFormat: 输出一行一个整数表示答案对 $998244353$ 取模的结果。


title: [北京省选集训2019] 图的难题

background: 标题是假的。

description:
小D 在图论习题书上遇到了一个问题：
书上画出了一张无向图，要求把边染成黑白两色，要求所有白色边构成的子图没有环，且所有黑色边构成的子图没有环。
小D 无论怎样尝试都觉得书上的问题没有解，她想请你帮她确认一下。
由于这道题有很多小问，小D 每次会给你图的点数 $n$、边数 $m$ 与所有边集，你只需要告诉小D 有没有解即可。

inputFormat:
第一行一个正整数 $T$，表示数据组数。
对于每组数据，第一行两个正整数 $n,m$，意义如题目描述。
接下来 $m$ 行，每行两个正整数 $u,v$ ,表示一条 $u$ 到 $v$ 的无向边

outputFormat: 输出$T$行，对于每组数据，若有解输出`Yes`，否则输出`No`。


title: 恋恋的数学题

background: 恋恋是个可爱的女孩子，最近她沉迷了做数学题。

description:
现在恋恋正在处理的题目十分简单：现在有$k \space (2\leq k\leq 4)$个数，恋恋不知道它们分别是几，只知道它们**两两**最大公约数及最小公倍数。

按照套路，恋恋非常想复原出那$k$个数，但是现在她需要假装不会做，于是她就把题目交给了你，如果你顺利解决了这个问题，恋恋就会在你背后疯狂打call……

inputFormat:
第一行，两个整数$T$和$k$

接下来$2T$行包含$T$组数据，每组数据包含两行，

第一行，$\frac{k(k-1)}2$个整数，表示$k$个未知数的两两最大公约数，乱序

第二行，$\frac{k(k-1)}2$个整数，表示$k$个未知数的两两最小公倍数，乱序

outputFormat: 输出$T$行，每行$k$个用空格分隔的数，表示**任意一组**符合对应数据的答案。


title: [PKUWC2018] Minimax

description:
小 $C$ 有一棵 $n$ 个结点的有根树，根是 $1$ 号结点，且每个结点最多有两个子结点。

定义结点 $x$ 的权值为：

1.若 $x$ 没有子结点，那么它的权值会在输入里给出，**保证这类点中每个结点的权值互不相同**。

2.若 $x$ 有子结点，那么它的权值有 $p_x$ 的概率是它的子结点的权值的最大值，有 $1-p_x$ 的概率是它的子结点的权值的最小值。

现在小 $C$ 想知道，假设 $1$ 号结点的权值有 $m$ 种可能性，**权值第 $i$ 小**的可能性的权值是 $V_i$，它的概率为 $D_i(D_i>0)$，求：

$$\sum_{i=1}^{m}i\cdot V_i\cdot D_i^2$$

你需要输出答案对 $998244353$ 取模的值。

inputFormat:
第一行一个正整数 $n$；

第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个结点的父亲的编号，其中第 $1$ 个结点的父亲为 $0$；

第三行 $n$ 个整数，若第 $i$ 个结点没有子结点，则第 $i$ 个数为它的权值，否则第 $i$ 个数为 $p_i\cdot 10000$，保证 $p_i\cdot 10000$ 是个正整数。

outputFormat: 输出答案。

hint:
#### 样例解释
1号结点的权值有 $\frac{1}{2}$ 的概率是 $1$，有 $\frac{1}{2}$ 的概率是 $2$，所以答案是 $\frac{5}{4}$。

#### 数据范围

- 对于 $10\%$ 的数据，有 $1\leq n\leq 20$；
- 对于 $20\%$ 的数据，有 $1\leq n\leq 400$；
- 对于 $40\%$ 的数据，有 $1\leq n\leq 5000$；
- 对于 $60\%$ 的数据，有 $1\leq n\leq 10^5$；
- 另有 $10\%$ 的数据保证树的形态随机；
- 对于 $100\%$ 的数据，有 $1\leq n\leq 3\times 10^5$，$1\leq w_i\leq 10^9$。

对于所有数据，满足 $0 < p_i \cdot 10000 < 10000$，所以易证明所有叶子的权值都有概率被根取到。


title: [PKUWC2018] Slay the Spire

description:
九条可怜在玩一个很好玩的策略游戏：Slay the Spire，一开始九条可怜的卡组里有 $2n$ 张牌，每张牌上都写着一个数字$w_i$，一共有两种类型的牌，每种类型各 $n$ 张：

1. 攻击牌：打出后对对方造成等于牌上的数字的伤害。

2. 强化牌：打出后，假设该强化牌上的数字为 $x$，则其他剩下的**攻击牌**的数字都会乘上 $x$。**保证强化牌上的数字都大于 1**。

现在九条可怜会等概率随机从卡组中抽出 $m$ 张牌，由于费用限制，九条可怜最多打出 $k$ 张牌，假设九条可怜永远都会采取能造成最多伤害的策略，求她期望造成多少伤害。

假设答案为 $\text{ans}$ ，你只需要输出

$$\left (\text{ans}\times \frac{(2n)!}{m!(2n-m)!}\right) ~\bmod 998244353$$

即可。其中 $x!$ 表示 $\prod_{i=1}^{x}i$，特别地，$0!=1$ 。

inputFormat:
第一行一个正整数 $T$ 表示数据组数

接下来对于每组数据：

第一行三个正整数 $n,m,k$

第二行 $n$ 个正整数 $w_i$，表示每张强化牌上的数值。

第三行 $n$ 个正整数 $w_i$，表示每张攻击牌上的数值。

outputFormat: 输出 $T$ 行，每行一个非负整数表示每组数据的答案。

hint:
#### 样例解释
例如九条可怜抽到了攻击牌 $\{1,2\}$ 和强化牌 $\{3\}$，那最优策略是先用掉强化牌 $3$，此时攻击牌的数值变成 $\{3,6\}$，然后打出 $6$。

#### 数据范围

对于所有数据，有 $1\leq k\leq m\leq 2n\leq 3000$，且$1\leq w_i\leq 10^8$。

**保证强化牌上的数字都大于 1**。

以下 $(\sum 2n)$ 表示对于输入中所有数据的$2n$的和。

对于 $10\%$ 的数据，有 $1\leq \sum 2n\leq 10$

对于 $20\%$ 的数据，有 $1\leq \sum 2n\leq 100$

对于 $30\%$ 的数据，有 $1\leq \sum 2n\leq 500$

另有 $20\%$ 的数据，满足所有攻击牌的数值相同。

另有 $20\%$ 的数据，满足 $m=k$。

对于 $100\%$ 的数据，有 $1\leq \sum 2n\leq 30000$


title: [加油武汉] 居家隔离

background: 为了防止感染，大家要自觉做到居家隔离，少外出少与外人接触。

description:
居家久了，你需要给自己找点娱乐。于是你看到这么一个游戏：
给定一个 $n$ 元集合 $ \{a_1,a_2,a_3....a_n \}$，元素各不相同。

游戏总共会进行 $n$ 轮，每轮系统会从集合中随机挑出一个元素，记作 $x$。你可以有如下两种选择：

1. 取走 $x$，那么 $x$ 将会是你的最终得分。
2. 舍弃 $x$，此时 $x$ 将会永久的从这个集合中删去，并且进入下一轮。

请注意，若是集合中仅剩唯一一个元素时，该元素无法被舍弃。

由于你很懒，所以你指定了一个很咸鱼的策略：

对于前 $k$ 轮，将得到的数全部舍弃，并且记录下得到的数中的最大值，记作 $y$。

在第 $k$ 轮之后，执行如下策略：

若是取得的 $x > y$，则直接取走 $x$。反之不断舍弃，直到找到了一个满足要求的 $x$ 或是仅剩一个元素。

现在你希望知道，对于 $1$ 到 $n-1$ 的每一个 $k$，你期望下的得分是多少。

所有数请对 $998244353$ 取模。

inputFormat:
第一行一个整数 $n$，表示集合中元素个数。

第二行共 $n$ 个整数，描述集合中的每一个元素。

outputFormat:
一行，总共 $n-1$ 个数，第 $i$ 个数表示当 $k=i$ 时，期望得分。

设答案化为最简分式后的形式为 $\frac{a}{b}$，其中 $a$ 和 $b$ 互质。输出整数 $x$ 使得 $bx\equiv a \pmod{998244353}$ 且 $0\leq x < 998244353$。可以证明这样的整数 $x$ 是唯一的。

hint:
**样例解释**

答案输出的四个数应该分别是 $\frac{39}{10}, \frac{19}{5} ,\frac{69}{20}, 3$，但在模意义下除以一个数相当于乘这个数在模意义下的逆元，因此输出为这些数。举例来说 $\frac{39}{10}\equiv 39\cdot 10^{-1}\equiv 39\cdot 299473306\equiv 698771051\pmod{998244353}$。

提示：如果你不知道如何对一个分数取余，请点这里：<https://www.luogu.com.cn/problem/P2613>

 - 对于 $40\%$ 的数据，满足 $2 \leq n \leq 10$；
 - 对于 $60\%$ 的数据，满足集合为 $[1,n]$ 中所有正整数；
 - 对于 $100\%$ 的数据，满足 $2 \leq n \leq 1000$，集合中所有数字不超过 $10000$。


title: 简单模拟

description:
考虑这样一款游戏，游戏地图可以视为一个平面直角坐标系的第一、四象限。

第一象限内会出现$n$个物体，一个物体可以是一个点，或者一条平行于y轴的线段。一个物体出现时，物体上离x轴最近的点和最远的点，分别称为物体的最低点和最高点。若物体是点，则最低点和最高点相同。

第$i$个物体会在时刻$t_i$出现，最低点为$(x_i,l_i)$，最高点为$(x_i,r_i)$，以速度$v_i$沿y轴负半轴方向匀速移动。

玩家可以标记x轴正半轴上的任何整点（若这个位置已经被标记，则这次的标记和之前的标记互不影响），称为**标记操作**；也可以取消某个标记，称为**取消标记操作**。同一时间可以做任意次操作。已知玩家做了$m$对操作，第$i$对操作的位置为$p_i$，其中标记操作和取消标记操作发生的时刻分别为$a_i$和$b_i$。

每个物体最初会处于**正常状态**。

若在某一时刻，距离一个物体的最低点不大于$d_0$的位置发生标记操作，且这个物体处于正常状态，则会发生**得分事件**，且事件的参数$d$为操作位置与物体最低点的距离。若有多个符合条件的标记操作，事件只发生一次，且认为是使得$d$最小的操作中位置离原点最近的操作引起了这次事件。随后，对于这个物体，若是一个点，则会消失，否则会*被这个操作标记*，且变成**被标记状态**。注意，一个操作可以影响多个物体。

若在某一时刻，距离一个物体的最高点不大于$d_0$位置发生取消标记操作，且这个物体被相应的标记操作标记，则也会发生**得分事件**，且事件的参数$d$为操作位置与物体最高点的距离。随后，这个物体会消失。

若在某一时刻，一个处于正常状态的物体的最低点到达了第四象限（注意，坐标轴上的点不属于任何一个象限），或一个处于被标记状态的物体对应的标记被取消，且没有发生得分事件，则会发生**miss事件**。随后，这个物体会消失。

一个参数为$d$的得分事件发生时，玩家会得到$(d_0^2-d^2)s_1$的基本得分。若包括这次事件在内，连续发生了$k$次得分事件，且没有连续发生$k+1$次得分事件，则玩家会得到$ks_2$的额外得分。

另外，游戏中的一切结算均发生在距离游戏开始经过整数个单位时间的时刻，且游戏开始于0时刻。已经出现的物体会在相邻两个时刻之间进行移动，某一时刻开始时移动已经完成。在某一时刻内，所有物体均视为静止。具体来说，对于包括0时刻在内的任一时刻：首先，这一时刻开始。随后，所有由移动造成的miss事件以某个顺序依次发生。随后，在这一时刻出现的物体同时出现。随后，所有操作同时发生，且在这一时刻的标记不会在同一时刻被取消。随后，所有得分事件以某个顺序依次发生（总得分与顺序无关）。随后，所有由操作造成的miss事件以某个顺序依次发生。随后，所有物体的状态同时改变（消失也视为状态改变）。最后，这一时刻结束。

若所有物体均经历了出现和消失，或miss事件发生了严格大于$w$次，游戏立即结束，此后的操作均可以忽略。

inputFormat:
第一行$n,m$，分别表示物体的个数和操作的对数。

之后$n$行，每行$x_i,l_i,r_i,t_i,v_i$。

之后$m$行，每行$p_i,a_i,b_i$。

之后一行，$d_0,s_1,s_2,w$。

outputFormat: 输出两行，第一行为得分，第二行为游戏结束时刻。

hint:
**样例说明**
在时刻0发生了两次得分事件，共得到了28分；在时刻5发生了一次得分事件和一次miss事件，得到了18分；在时刻7发生了一次得分事件，得到了16分；在时刻8发生了一次miss事件，至此，所有物体都经历了出现和消失，游戏结束。

**数据范围**
所有输入均为整数。

$1\le n,m\le 2000$；

$0\le t_i,a_i,b_i\le 10^9$；

$1\le x_i,p_i,l_i,r_i\le 10^9$；

$a_i<b_i$，$l_i\le r_i$；

$1\le v_i,v_i\cdot\max\{t_j,a_j,b_j\}\le 10^9$；

$0\le d_0,s_1,s_2\le 10^4$；

$0\le w\le n$。

对于30%的数据：$n,m\le 10$。


title: 【模板】Min_25 筛

background: 模板题，无背景。

description:
定义积性函数 $f(x)$，且 $f(p ^ k) = p ^ k(p ^ k - 1)$（$p$ 是一个质数），求

$$\sum_{i = 1} ^ n f(i)$$

对 $10 ^ 9 + 7$ 取模。

inputFormat: 一行一个整数 $n$。

outputFormat: 一个整数表示答案。


title: 头像上传

description:
有一天无聊的你在注册一个无聊的网站，注册完的第一步自然是上传头像。

你发现这个网站总共可以上传 $n$ 个头像，每个头像必须是正方形，并且长宽至少为 $L \times L$

在图片上传前，系统会对图片进行如下处理：如果图片的任何一边长度超过了 $G$ ，那么系统会不断地对图片的长宽同时减半（向下取整），直至两边长度 $\leq G$ 为止。

你现在找到了 $n$ 张可供上传的图片，第 $i$ 张的尺寸是 $W_i \times H_i$。

如果图片有任何一边小于 $L$，请输出 "Too Young"

如果图片满足大小条件但不为正方形，请输出"Too Simple"

如果图片满足大小条件并且是正方形，请输出"Sometimes Naive"

以上所有字符串输出时均不包含引号。

inputFormat:
一行三个整数 $n,L,G$，意义如题目所述。

接下来每行两个整数 $W_i,H_i$，表示图片长宽。

outputFormat: 共 $n$ 行，每行一个字符串，意义如题目所述。


title: [GXOI/GZOI2019] 与或和

description:
Freda 学习了位运算和矩阵以后，决定对这种简洁而优美的运算，以及蕴含深邃空间的结构进行更加深入的研究。

对于一个由非负整数构成的矩阵，她定义矩阵的 $\texttt{AND}$ 值为矩阵中所有数二进制 $\texttt{AND(\&)}$ 的运算结果；定义矩阵的 $\texttt{OR}$ 值为矩阵中所有数二进制 $\texttt{OR(|)}$ 的运算结果。

给定一个 $N \times N$ 的矩阵，她希望求出：
1. 该矩阵的所有子矩阵的 $\texttt{AND}$ 值之和（所有子矩阵 $\texttt{AND}$ 值相加的结果）。
2. 该矩阵的所有子矩阵的 $\texttt{OR}$ 值之和（所有子矩阵 $\texttt{OR}$ 值相加的结果）。

接下来的剧情你应该已经猜到——Freda 并不想花费时间解决如此简单的问题，所以这个问题就交给你了。

由于答案可能非常的大，你只需要输出答案对 $1,000,000,007 (10^9 + 7)$ 取模后的结果。

inputFormat:
输入文件的第一行是一个正整数 $N$，表示矩阵的尺寸。

接下来 $N$ 行，每行 $N$ 个自然数，代表矩阵的一行。相邻两个自然数之间由一个或多个空格隔开。

outputFormat: 输出只有一行，包含两个用空格隔开的整数，第一个应为所有子矩阵 $\texttt{AND}$ 值之和除以 $10^9 + 7$ 的余数，第二个应为所有子矩阵 $\texttt{OR}$ 值之和除以 $10^9 + 7$ 的余数。


title: [GXOI/GZOI2019] 宝牌一大堆

description:
麻将是一种传统的博弈游戏，由 $4$ 名玩家参与，轮流摸牌、打牌。在竞技比赛中主要有国标麻将（中国）和立直麻将（日本）两大规则。本题采用一种特别的规则——「宝牌一大堆」规则。

#### 牌型
一副麻将由 $136$ 张牌组成，其中包含 $34$ 种不同的牌，每种各有 $4$ 张。这 $34$ 种牌分别是：
一万到九万、一索到九索、一筒到九筒、东、南、西、北、中、白、发。

![doraippai1.png](https://cdn.luogu.com.cn/upload/pic/56677.png)

它们可以组合成不同的牌型：
- 顺子：$3$ 张数字连续的万，或 $3$ 张数字连续的索，或 $3$ 张数字连续的筒。
- 刻子：$3$ 张完全一样的牌。
- 杠子：$4$ 张完全一样的牌。
- 雀头：$2$ 张完全一样的牌。

其中顺子和刻子统称为面子。

#### 和牌
手牌（一名玩家持有的牌）宣告胜利的状况称为「和牌」。
- 当玩家持有 $14$ 张牌，并且满足以下三个条件之一时，判定为「和牌」：
  1. 存在一种方案，使得这 $14$ 张牌可以分成 $4$ 组面子、$1$ 组雀头，简记为「$3 \times 4 + 2$」。
  2. 存在一种方案，使得这 $14$ 张牌可以分成 $7$ 组**不同的**雀头，称为「七对子」。
  3. 这 $14$ 张牌**仅由**一万、九万、一索、九索、一筒、九筒、东、南、西、北、中、白、发这 $13$ 种牌组成，并且这 $13$ 种牌**每种至少有 $1$ 张**，称为「国士无双」。
- 当玩家持有 $15$ 张牌，并且存在一种方案，使得这 $15$ 张牌可以分成 $1$ 组杠子、$3$ 组面子、$1$ 组雀头，判定为和牌。
- 当玩家持有 $16$ 张牌，并且存在一种方案，使得这 $16$ 张牌可以分成 $2$ 组杠子、$2$ 组面子、$1$ 组雀头，判定为和牌。
- 当玩家持有 $17$ 张牌，并且存在一种方案，使得这 $17$ 张牌可以分成 $3$ 组杠子、$1$ 组面子、$1$ 组雀头，判定为和牌。
- 当玩家持有 $18$ 张牌，并且存在一种方案，使得这 $18$ 张牌可以分成 $4$ 组杠子、$1$ 组雀头，判定为和牌。

#### 宝牌
每局游戏还会指定若干张「宝牌」，和牌时，手牌中的每张宝牌会使收益翻一番（会在接下来详细介绍）。

#### 达成分数
由于可以「和牌」的手牌很多，可以给每种判定为「和牌」的手牌定义一个「达成分数」，这个分数等于从所有尚未打出的牌中选出若干张，能够组成该手牌的方法数，再乘上手牌中 $2$ 的「宝牌数」次方。
该分数综合考虑了和牌几率与和牌收益，理论上以分数较高的手牌为目标较好。

例如下图手牌显然是可以「和牌」的，如果目前场上还剩 $3$ 张一万、$4$ 张九万，以及二到八万各 $2$ 张没有打出，宝牌为九万，那么下图手牌的「达成分数」就是 $C_3^3 C_4^3 C_2^2 (C_2^1)^6 2^3 = 2048$，其中 $C$ 表示组合数。

![doraippai2.png](https://cdn.luogu.com.cn/upload/pic/56678.png)

特别地，「七对子」和牌的手牌，达成分数额外乘 $7$。「国士无双」和牌的手牌，达成分数额外乘 $13$。

有一天，小 L，小 Y，小 I 和小 W 正在打麻将，路过的雪野和看到了所有已经打出的牌，但不知道任何一名玩家的手牌。也许你已经猜到了下面的剧情—
—雪野和想知道在所有尚未打出的牌中，「达成分数」最高的可以「和牌」的手牌有多少分，但是她还要观看麻将比赛，所以这个问题就交给你了。

inputFormat:
每个测试点包含多组数据，第一行是一个整数 $T$，表示数据组数。注意各组数据之间是互相独立的。

每组数据包含两行，第一行给出场上已经打出的牌，第二行给出该局的所有宝牌。

规定用 $\texttt{1m},\texttt{2m},\dots,\texttt{9m}$ 代表万，$\texttt{1p},\texttt{2p},\dots,\texttt{9p}$ 代表筒，$\texttt{1s},\texttt{2s},\dots,\texttt{9s}$ 代表索，$\texttt E,\texttt S,\texttt W,\texttt N$ 代表东、南、西、北，$\texttt Z,\texttt B,\texttt F$ 代表中、白、发，相邻两张牌之间用一个空格隔开，每行的末尾有一个单独的 $0$ 代表结束。

outputFormat: 输出文件应包含 $T$ 行，对于每组数据，输出一个整数表示最高分数。

samples:
2
0
0
7m 4p 2s 7s 6p 8s 7p 5s 9s 9s 1p 5m 9m 5s 4p 5s E 1p 6s 5p B 4m 6m W 6p 6s E 9s 5p 2s 8s 8p 4m 3s 9m 5p 3s 2s 6s 8s 8p 6p 5m 4s 3m 4s 5s 4s 6m 9s 6p N 5m 7s 4m 2m 2s 6s 3m 7p B B N 1m 3m B 8p F 7p 0
W 4p N 3m 2m B 9m 3p 1p 6p S 4s 5p 8s 4m 5s 2s 3s 0


title: [GXOI/GZOI2019] 特技飞行

description:
公元 $9012$ 年，Z 市的航空基地计划举行一场特技飞行表演。表演的场地可以看作一个二维平面直角坐标系，其中横坐标代表着水平位置，纵坐标代表着飞行高度。

在最初的计划中，这 $n$ 架飞机首先会飞行到起点 $x = x_{st}$ 处，其中第 $i$ 架飞机在起点处的高度为 $y_{i,0}$。它们的目标是终点 $x = x_{ed}$ 处，其中第 $i$ 架飞机在终点处的高度应为 $y_{i,1}$。因此，每架飞机可以看作坐标系中的一个点，它的航线是从 $(x_{st},y_{i,0})$ 出发、到 $(x_{ed},y_{i,1})$ 结束的一条线段，如下图所示。

![aerobatics1.png](https://cdn.luogu.com.cn/upload/pic/56679.png)

这 $n$ 架飞机同时出发且始终保持一定的对地速度。因此，对于任意两条交叉的航线（线段），对应的两架飞机必然会同时到达交点处——这就是它们进行特技表演的时刻。它们将会偏转机翼，展现以极近的距离「擦身而过」特技，然后**继续保持各自的航线**。

航空基地最近还研究了一种新的特技「对向交换」。当两架飞机到达交点处时，之前正在下降的那架立即转为执行抬升动作，之前正在上升的那架则执行一次空翻，两架飞机一上一下、机腹对机腹，同样以极近的距离经过交点，然后**互相交换接下来的航线**。

我们不必关心特技动作在物理上究竟是如何实现的，飞机仍然看作一个点，在两种特技动作下，航线的变化如下图所示（$y_{i,1}'$ 表示交换航线后第 $i$ 架飞机在终点的新高度）。容易发现，「对向交换」会使它们的航线变为折线，并**保持它们在纵坐标上的相对顺序**；而「擦身而过」会**改变它们在纵坐标上的相对顺序**。

![aerobatics2.png](https://cdn.luogu.com.cn/upload/pic/56680.png)

现在，观看表演的嘉宾团提出了一个苛刻的要求——在终点 $x = x_{ed}$ 处，按照高度排序，$n$ 架飞机的相对顺序必须与 $x = x_{st}$ 处的相对顺序一致。嘉宾团还给「对向交换」特技和「擦身而过」特技分别评定了难度系数 $a$ 和 $b$，每次「对向交换」特技可以获得 $a$ 的分数，每次「擦身而过」特技可以获得 $b$ 的分数。

除此以外，嘉宾团共有 $k$ 名成员，第 $i$ 名成员会乘热气球停留在位置 $(p_i,q_i)$ 处，具有 $r_i$ 的观测距离，可以观测到区域 $|x - p_i| + |y - p_i| \le r_i$ 里的所有特技。
若某个交点处的特技被**一名或多名**嘉宾观测到，则可以获得 $c$ 的额外加分。
注意：**特技无论是否被观测到，均可以获得 $a$ 或者 $b$ 的得分**。

下图是对本题第一幅图 $4$ 条航线 $4$ 个交点的一种满足要求的安排，包括 $2$ 次「对向交换」、$2$ 次「擦身而过」，$3$ 项特技被观测到，得分 $2a + 2b + 3c$。为了方便观察，图中展现「对向交换」特技的交点稍稍有些分离。

![aerobatics3.png](https://cdn.luogu.com.cn/upload/pic/56681.png)

在这次的剧情里，你成为了 Z 市航空基地的规划员，你可以决定在每个交点处是执行「对向交换」还是「擦身而过」。你被要求在保证嘉宾团要求的前提下，计算整个特技表演的可能得到的最低和最高分数。

inputFormat:
第一行包含六个非负整数 $n,a,b,c,x_{st},x_{ed}$，分别表示航线（线段）总数、「对向交换」特技的得分、「擦身而过」特技的得分、观测对表演的额外分、飞行起点的横坐标、飞行终点的横坐标。

第二行包含 $n$ 个非负整数 $y_{i,0}$，其中第 $i$ 个数表示第 $i$ 条航线起点的纵坐标，保证按照从低到高的顺序给出，即 $y_{i,0} < y_{i + 1,0}$。

第三行包含 $n$ 个非负整数 $y_{i,1}$，其中第 $i$ 个数表示第 $i$ 条航线终点的纵坐标。

第四行包含一个非负整数 $k$，表示嘉宾的数量。

接下来 $k$ 行每行三个非负整数 $p_i,q_i,r_i$，分别表示第 $i$ 名嘉宾所在位置的横、纵坐标与观测距离。

输入数据对于所有航线（线段）在直线 $x = x_{st}$ 和 $x = x_{ed}$ 之间的交点总数也有一些限制，详见「数据范围与提示」。

outputFormat: 输出只有一行，包含两个整数，表示整个特技飞行表演的可能得到的最低和最高分数，中间用一个空格隔开。


title: [GXOI/GZOI2019] 逼死强迫症

description:
ITX351 要铺一条 $2 \times N$ 的路，为此他购买了 $N$ 块 $2 \times 1$ 的方砖。可是其中一块砖在运送的过程中从中间裂开了，变成了两块 $1 \times 1$ 的砖块！
ITX351 由此产生了一个邪恶的想法：他想要在这条路上故意把两块 $1 \times 1$ 的砖块分开铺，**不让两块砖有相邻的边**，其他砖块可以随意铺，直到整条路铺满。这样一定可以逼死自身强迫症 sea5！

也许下面的剧情你已经猜到了——他为此兴奋不已，以至于无法敲键盘。于是，他请你帮忙计算一下，有多少种方案可以让自己的阴谋得逞。

inputFormat:
每个测试点包含多组数据，输入文件的第一行是一个正整数 $T$，表示数据的组数。注意各组数据之间是独立无关的。

接下来 $T$ 行，每行包含一个正整数 $N$，代表一组数据中路的长度。

outputFormat:
输出应包含 $T$ 行，对于每组数据，输出一个正整数，表示满足条件的方案数。

由于答案可能非常的大，你只需要输出答案对 $1000000007 (10^9 + 7)$ 取模后的结果。


title: [GXOI/GZOI2019] 旅行者

description:
J 国有 $n$ 座城市，这些城市之间通过 $m$ 条单向道路相连，已知每条道路的长度。

一次，居住在 J 国的 Rainbow 邀请 Vani 来作客。不过，作为一名资深的旅行者，Vani 只对 J 国的 $k$ 座历史悠久、自然风景独特的城市感兴趣。
为了提升旅行的体验，Vani 想要知道他感兴趣的城市之间「两两最短路」的最小值（即在他感兴趣的城市中，最近的一对的最短距离）。

也许下面的剧情你已经猜到了—— Vani 这几天还要忙着去其他地方游山玩水，就请你帮他解决这个问题吧。

inputFormat:
每个测试点包含多组数据，第一行是一个整数 $T$，表示数据组数。注意各组数据之间是互相独立的。

对于每组数据，第一行包含三个正整数 $n,m,k$，表示 J 国的 $n$ 座城市（从 $1 \sim n$ 编号），$m$ 条道路，Vani 感兴趣的城市的个数 $k$。

接下来 $m$ 行，每行包括 $3$ 个正整数 $x,y,z$，表示从第 $x$ 号城市到第 $y$ 号城市有一条长度为 $z$ 的单向道路。注意 $x,y$ 可能相等，一对 $x,y$ 也可能重复出现。

接下来一行包括 $k$ 个正整数，表示 Vani 感兴趣的城市的编号。

outputFormat: 输出文件应包含 $T$ 行，对于每组数据，输出一个整数表示 $k$ 座城市之间两两最短路的最小值。


title: [GXOI/GZOI2019] 旧词

description:
> 浮生有梦三千场
> 穷尽千里诗酒荒
> 徒把理想倾倒
> 不如早还乡
>
> 温一壶风尘的酒
> 独饮往事迢迢
> 举杯轻思量
> 泪如潮青丝留他方
>
> ——乌糟兽/愚青《旧词》

你已经解决了五个问题，不妨在这大树之下，吟唱旧词一首抒怀。最后的问题就是关于这棵树的，它的描述很简单。

给定一棵 $n$ 个点的有根树，节点标号 $1 \sim n$，$1$ 号节点为根。
给定常数 $k$。
给定 $Q$ 个询问，每次询问给定 $x,y$。
求：

$$\sum\limits_{i \le x} \text{depth}(\text{lca}(i,y))^k$$

$\text{lca}(x,y)$ 表示节点 $x$ 与节点 $y$ 在有根树上的最近公共祖先。
$\text{depth}(x)$ 表示节点 $x$ 的深度，根节点的深度为 $1$。
由于答案可能很大，你只需要输出答案模 $998244353$ 的结果。

inputFormat:
输入包含 $n+Q$ 行。

第 $1$ 行，三个正整数 $n,Q,k$。

第 $i = 2 \sim n$ 行，每行有一个正整数 $f_i(1 \le f_i \le n)$，表示编号为 $i$ 的节点的父亲节点的编号。

接下来 $Q$ 行，每行两个正整数 $x,y(1 \le x,y \le n)$，表示一次询问。

outputFormat: 输出包含 $Q$ 行，每行一个整数，表示答案模 $998244353$ 的结果。


title: [COCI2018-2019#5] Transport

description:
 一个国家有 $n$ 个城市，每个城市中都有一个加油站，燃料储量为 $a_i$。
有 $n-1$ 条路径，将这些城市连接成一个树形结构。

一个货车能从城市 $u$ 到达城市 $v$ ，货车的燃料量必须不小于 $u,v$ 之间的距离。
每当货车抵达一个城市，就可以补充不超过加油站储量的燃料。

假设货车的油箱是无限大的，请你算出有多少个有序数对 $(u,v)$ 满足：
一个油箱燃料量初始为 $0$ 的货车，可以从城市 $u$ 出发，抵达城市 $v$。

请注意，货车只能走简单路径，也就是说不能走回头路。

inputFormat:
第一行一个正整数 $n$。
第二行有 $n$ 个正整数 $a_i$ ，表示每个加油站的燃料储量。
接下来 $n-1$ 行，每行三个正整数 $u,v,w$，表示城市 $u,v$ 之间有一条长为 $w$ 的路径。

outputFormat: 一行一个整数表示答案。

hint:
### 样例1解释：
唯一可行的是 $(1,2)$，即只有 $1\rightarrow 2$ 是可行的。

### 数据范围：
对于 $20\%$ 的数据：
$1\le n \le 5000$
对于 $40\%$ 的数据：
树是一条链
对于 $100\%$ 的数据：
$1\le n \le 10^5$
$1\le u,v \le n$
$1\le w,a_i \le 10^9$


title: [COCI2018-2019#6] Mobitel

background:
`Nikola`小朋友最近在学乘法口诀。
为了记得更牢，他决定做一个游戏进行练习。

description:
他画了一个 $r$ 行 $s$ 列的矩阵，每个格子里都有一个正整数。
他想知道，如果从左上角走到右下角，且每次只能向右或向下走到相邻格子，那么使得路径上所有数的乘积不小于 $n$ 的路径有多少条？

由于答案可能很大，所以请输出答案对 $10^9 + 7$ 取模的结果。

inputFormat:
第一行三个正整数 $r,s,n$
接下来 $r$ 行，每行 $s$ 个正整数，依次表示矩阵每一行的数。

outputFormat: 输出一行一个整数表示答案。

hint:
### 样例 $1$ 解释：
共有 $3$ 条路径，其中有 $2$ 条满足条件：
$2 \rightarrow 3 \rightarrow 6 \rightarrow 7$，乘积为$252$
$2 \rightarrow 5 \rightarrow 6 \rightarrow 7$，乘积为$420$

### 数据范围：
对于$20\%$的数据：
矩阵中的数不超过$10$
对于$50\%$的数据：
$1\le r,s \le 100$
对于$100\%$的数据：
$1\le r,s \le 300$
$1\le n \le 10^6$
矩阵中的数不超过$10^6$


title: [COCI2018-2019#4] Akvizna

description:
你面临 $n$ 名参赛者的挑战，最终要将他们全部战胜。
每一轮中，都会淘汰一些选手；你会得到这一轮奖金池中 被淘汰者 除以 这一轮对手总数 比例的奖金。

例如某一轮有 $10$ 个对手，淘汰了 $3$ 个，那么你将获得奖金池中 $3/10$ 的奖金。

假设每一轮的奖金池均为一元，`Mirko` 希望通过恰好 $k$ 轮赢得比赛，那么他最多可能获得多少奖金呢？

你只需要输出答案保留 $9$ 位小数即可。

inputFormat: 一行两个正整数 $n,k$。

outputFormat: 输出一行一个实数表示答案。

hint:
### 样例1解释：

最优的情况为：
第一轮淘汰 $3$ 人，剩下两轮各淘汰 $1$ 人。
获得奖金为 $\frac{3}{5}+\frac{1}{2}+\frac{1}{1}=2.1$ 元。

### 数据范围：

对于$20\%$的数据，$1\le n\le 100$。

对于$40\%$的数据，$1\le n \le 3000$。

对于$100\%$的数据，$1\le k \le n \le 10^5$。

本题较卡精度，请留意。


title: [Ynoi2012] 梦断 SCOI2017

description:
有 $n$ 个学生构成了一棵有根树，每个学生有一个 $\text{gpa}$。

定义一个学生所在的**专业**为仅保留两端学生 $\text{gpa}$ 相同的边时，这个学生所在的连通分量。

定义一个专业的**怨气值**是 $max(dep[a]-dep[b]+1)$ $s.t$. $a,b$是专业中的学生，$dep_{根}=0$，$dep_{w}=dep_{w的父亲}+1$。

操作 1 ：给出 $x$ 和 $y$，把学生 $x$ 的 $\text{gpa}$ 改成 $y$。

操作 2 ：给出 $x$ 和 $y$，把学生 $x$ 所在的专业中所有点 $\text{gpa}$ 改为 $y$。

操作 3 ：给出 $x$，问学生 $x$ 的 $\text{gpa}$，$x$ 所在专业的人数，$x$所在专业的怨气值。

inputFormat:
第一行一个数 $n$。

第二行 $n$ 个数表示每个节点的父亲，其中第 $i$ 个数 $<i$，且 $1$ 节点的父亲为 $0$。

第三行 $n$ 个数表示每个学生的 $\text{gpa}$。

第四行一个数 $m$。

之后 $m$ 行，每行一个两或三个数表示一次操作，类型如上述。

outputFormat: 对于每个 $3$ 操作，输出一行三个数，中间用空格隔开，依次表示：学生 $x$ 的 $\text{gpa}$，$x$ 所在专业的人数，$x$ 所在专业的怨气值。

hint:
Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

定义 $\text{gpa}$ 共有 $c$ 种。

对于 $40\%$ 的数据，$n,m \le 1000$。

对于另外 $40\%$ 的数据，$n,m \le 10^{5}$，$c=2$，$\text{gpa}$ 的范围在 $[1,2]$ 中。

对于 $100\%$ 的数据，$n,m \le 10^5$，$c=30$，$\text{gpa}$ 的范围在 $[1,30]$ 中。

我都懒得喷 THU 了。


title: [Ynoi2011] 竞赛实验班

background:
中考的时候好像是没什么实感的，随随便便就考上了cdqz，考前几天晚上还在偷偷用itouch看修仙小说。

考上cdqz之后，我就天天去听OI课了，虽然不太听得懂，但反正也没事干。

当时听于神介绍数据结构，他大概是这么写的：

初级：树状数组，线段树

中级：平衡树，可并堆，莫队

高级：主席树，动态树

前沿：动态仙人掌

感觉有好多听起来就好厉害的树，还有“仙人掌”?数据结构真的是太厉害了（伏笔）！

那一年cdqz突然决定搞一个竞赛实验班，专门搞竞赛，由于挺不喜欢文化课的，所以我决定去参加。

想去竞赛班要经过一个学科夏令营的选拔，当时有个朋友f321dd觉得很毒瘤就跑路了，我还不太能理解，现在一定程度上能理解了。

这个学科夏令营大概就是每天请不同学科的竞赛老师来讲课，数学，物理都不太感兴趣，所以上课就很无聊，无所事事的，经常偷偷跑去机房写点代码。

仔细想想，我当时也对未来没什么打算，也谈不上有多热爱竞赛，也谈不上有多讨厌文化课，只是听说这个实验班好，可以上好大学，就去了，感觉和听到“学计算机挣钱多”而选择去计算机系的人差不多。

不过大家不都是这样的吗。

我最后进入了竞赛实验班，也认识了将要一起学习两年oi的大家，同时还进行了一次摸底考试，当时好像zms拿了350第一，我拿了310第二，记得我还用“动态spfa”水了个最短路题，看到AC的时候开心地叫了出来。

当时的竞赛组：

zms：初中同学，之前有提到，大家都叫他“小白”，感觉是一个挺稳重的人，是公认的我们那届OI最强选手，和yjq关系很好，被当时的我视为目标。

f321dd：初中同学，朋友，初中经常一起逃课打牌（自己搞了个叫化学杀的东西），感觉是个有趣的人。

grh：四中来的，高高瘦瘦的，喜欢看本子和动画片。

ziliuziliu：四中来的，瘦瘦的，喜欢玩坦克世界，练了KV3这条线，天天AP打不穿WZ111，水平不错。

cyz：喜欢玩坦克世界，印象中第一次看到他玩是在玩四号防空车，然后我觉得好玩也入坑了，水平挺高的，感觉经常无法理解他在想什么。

Flaze：女oier，感觉挺可爱的。

zyx：外地生，没学过oi。

cx：胖胖的，会写oj。

zqq：和Flaze一个初中的，感觉挺踏实的（最开始是这样的），什么知识点都会去学。

学长：

yjq：特别强，天天比赛早早做完AK。

Karl_duan：感觉一直在学习，很踏实努力。

zcy：特别会乱搞，平时也经常乱搞过题，NOIP暴力拿了600。

mhy：集训队学长，瘦瘦的。

写下这个回忆录的时候我还是挺有感触的，回忆起当时的事情让我很开心~

学oi的那一阵子虽然我很菜，天天被吊打，但无疑还是快乐的。

【记得配图，内容oj7】

由于这是Ynoi，不是出题人拿来写怀旧的文字的地方，所以你需要做一个数据结构题：

description:
有一个长度为 $n$ 的数组 $A$。下标从 $1$ 开始标号。有 $m$ 个操作需要处理，操作有如下四种：
1. 在数组 $A$ 的末尾添加一个数 $x$。
2. 输出 $\sum_{i=l}^{r}A_i$。
3. 将数组 $A$ 中的每个数 $A_i$ 都改为 $A_i\oplus x$。（$\oplus$ 表示异或操作）。
4. 将数组 $A$ 从小到大排序。

inputFormat:
第一行一个数 $n$ 表示 $A$ 的初始大小。
接下来一行 $n$ 个非负整数 $A_i$，表示 $A$ 的中的每个元素。
接下来一行一个数 表示询问的数量。
接下来 $m$ 行，每行表示一个操作：

- `1 x`： 表示第一种操作，在末尾插入数 $x$。
- `2 l r`：表示第二种操作，询问 $\sum_{i=l}^{r}A_i$。保证有 $1\le l\le r\le n'$，其中 $n'$ 为操作时刻序列的长度。
- `3 x`：表示第三种操作，给每个数 $\oplus$ 上 $x$。
-  `4`：表示第四种操作，将数组 $A$ 排序。

outputFormat: 对于每个第二种操作，输出答案。

hint:
Idea：WJMZBMR，Solution：WJMZBMR，Code：WJMZBMR，Data：WJMZBMR

$1\le n,\,m\le 10^5, 0\le x,A_i\le 10^9$


title: [MtOI2019] 幻想乡数学竞赛

background:
一年一度的幻想乡数学竞赛 (thMO) 又要开始了。

幻想乡中学习数学的少 (lao) 女 (tai) 们 (po) 和冰之妖精 baka 一起准备着 thMO。

但是在那一刻，幻想乡日复一日的宁静被打破了。

广播里，播放起了死亡的歌曲！

在那一刻，人们又回想起了被算数支配的恐惧。

就剩下 baka，baka，baka，baka 的声音在幻想乡里回荡。

---

河城 荷取 (Kawashiro Nitori) 正坐在 thMO2019 的考场上！
因为荷取有着她的[超级计算机](https://www.luogu.org/problemnew/show/P4911)，在成功地用光学迷彩覆盖了计算机之后，荷取在 thMO2019 的考场上所向披靡。

* 荷取用她的超级计算机 $0 \,\mathrm{ms}$ 跑出了这么一道题：

  * $\exists \{ a_n\} (n=0,1,\cdots ,10^{18})$，已知 $a_0=2,a_1=5,a_{n+2}=3a_{n+1}-2a_n$，求 $a_n\bmod 10^{9}+7$

* 荷取：显然，这个题可以用矩阵乘法 + 快速幂，可以 $O(\log n)$ 水过去，差不多就这样：

$$
\begin{bmatrix} a_n & a_{n+1} \end{bmatrix}=\begin{bmatrix} a_0 & a_1 \end{bmatrix} \times \begin{bmatrix} 3 & 1 \\ -2 & 0 \end{bmatrix}^n
$$

但是荷取遇到了一道她不会的题，她正在寻求你的帮助呢！

description:
存在一个数列 $\{ a_n\} (n\in \{ 0,1,2,\cdots ,2^{64}-1\} )$。
已知 $a_0=-3,a_1=-6,a_2=-12,a_n=3a_{n-1}+a_{n-2}-3a_{n-3}+3^n$。

* 现在给你一个非负整数 $n$ ，令 $p=10^{9}+7$，请你求出 $a_n \bmod p$。

* **注：若 $a_n<0$ ，请输出 $(a_n \bmod p+p)\bmod p$。**

为了更充分地考验你的水平，荷取设置了 $T$ 组询问。

* 为了在某种程度上减少你的输入和输出量，我们采用以下的代码来生成询问：

```cpp
namespace Mker
{
//  Powered By Kawashiro_Nitori
//  Made In Gensokyo, Nihon
	#include<climits>
	#define ull unsigned long long
	#define uint unsigned int
	ull sd;int op;
	inline void init() {scanf("%llu %d", &sd, &op);}
	inline ull ull_rand()
	{
		sd ^= sd << 43;
		sd ^= sd >> 29;
		sd ^= sd << 34;
		return sd;
	}
	inline ull rand()
	{
		if (op == 0) return ull_rand() % USHRT_MAX + 1;
		if (op == 1) return ull_rand() % UINT_MAX + 1;
		if (op == 2) return ull_rand();
	}
}
```

在调用 `Mker::init()` 函数之后，你第 $i$ 次调用 `Mker::rand()` 函数时返回的便是第 $i$ 次询问的 $n_i$。

在这里给出 $op$ 的限制：

* 如果 $op=0$，满足 $n_i \leq 2^{16}$。

* 如果 $op=1$，满足 $n_i \leq 2^{32}$。

* 如果 $op=2$，满足 $n_i \leq 2^{64}-1$。

为了减少你的输出量，你只需要输出所有询问答案的**异或和**。

inputFormat: 第一行三个整数，输入 $T$ ， $seed$ 和 $op$。

outputFormat: 第一行一个整数，输出 $T$ 组询问的答案的**异或和**。

hint:
### 子任务

![png](https://i.loli.net/2019/04/19/5cb9bb2c6c1d6.png)

### 题目来源

[迷途之家 2019 联赛](https://www.luogu.org/contest/20135)(MtOI2019) T4

出题人：disangan233

验题人：suwakow


title: [BJOI2019] 奥术神杖

description:
Bezorath 大陆抵抗地灾军团入侵的战争进入了僵持的阶段，世世代代生活在 Bezorath 这片大陆的精灵们开始寻找远古时代诸神遗留的神器，试图借助神器的神秘力量帮助她们战胜地灾军团。

在付出了惨痛的代价后，精灵们从步步凶险的远古战场取回了一件保存尚完好的神杖。但在经历过那场所有史书都视为禁忌的“诸神黄昏之战”后，神杖上镶嵌的奥术宝石已经残缺，神力也几乎消耗殆尽。精灵高层在至高会议中决定以举国之力收集残存至今的奥术宝石，并重金悬赏天下能工巧匠修复这件神杖。

你作为神术一脉第五百零一位传人，接受了这个艰巨而神圣的使命。
神杖上从左到右镶嵌了 $n$ 颗奥术宝石，奥术宝石一共有 $10$ 种，用数字 "`0123456789`" 表示。有些位置的宝石已经残缺，用 "`.`" 表示，你需要用完好的奥术宝石填补每一处残缺的部分（每种奥术宝石个数不限，且不能够更换未残缺的宝石）。古老的魔法书上记载了 $m$ 种咒语 $(S_i,V_i)$ ，其中 $S_i$ 是一个非空数字串，$V_i$ 是这种组合能够激发的神力。

神杖的初始神力值 $Magic = 1$，每当神杖中出现了连续一段宝石与 $S_i$ 相等时，神力值 $Magic$ 就会乘以 $V_i$。但神杖如果包含了太多咒语就不再纯净导致神力降低：设 $c$ 为神杖包含的咒语个数（若咒语类别相同但出现位置不同视为多次），神杖最终的神力值为 $ \sqrt[c]{Magic}$。（若 $c = 0$ 则神杖最终神力值为 $1$ ）

例如有两种咒语 $(01,3)$ 、$(10,4)$ ，那么神杖 “`0101`” 的神力值为 $\sqrt[3]{ 3 \times 4 \times 3}$

你需要使修复好的神杖的最终的神力值最大，输出任何一个解即可。

inputFormat:
第一行两个正整数 $n$ 、$m$ ，表示宝石数和咒语数。

第二行为一个长度为 $n$ 的字符串 $T$ ，表示初始的神杖。

接下来 $m$ 行每行一个非空数字串 $S_i$ 和一个正整数 $V_i$ ，表示每种咒语。

outputFormat: 输出最终神杖上从左到右镶嵌的宝石，多解时任意输出一个即可。

hint:
样例 1 ：法杖最终神力值为 $2$ 。

样例 2 ：法杖最终神力值为 $\sqrt[3]{2 \times 3 \times 4}$

设 $s = \sum_{i=1}^{m} |S_i|$ ，即所有咒语的串长之和。
![](https://cdn.luogu.com.cn/upload/pic/57052.png)