在一些扑克游戏里，如德州扑克，发牌是有讲究的。一般称呼专业的发牌手为荷官。荷官在发牌前，先要销牌。所谓销牌，就是把当前在牌库顶的那一张牌移动到牌库底，它用来防止玩家猜牌而影响游戏。

假设一开始，荷官拿出了一副新牌，这副牌有 $N$ 张不同的牌，编号依次为 $1$ 到 $N$ 。由于是新牌，所以牌是按照顺序排好的，从牌库顶开始，依次为 $1, 2, \dots$ 直到$N$ ，$N$ 号牌在牌库底。为了发完所有的牌，荷官会进行$N$ 次发牌操作，在第 $i$ 次发牌之前，他会连续进行 $R_i$ 次销牌操作， $R_i$ 由输入给定。请问最后玩家拿到这副牌的顺序是什么样的？

给定一个 $n$ 个点，以 $1$ 为根的有根树，砍断第 $i$ 条边的代价为 $c_i$。有 $m$ 次询问，每次给出 $k_i$ 个关键点（保证关键点不含 $1$ 号节点），询问能够使 $1$ 号节点不能到达任何关键点，所要砍断边的代价和最小是多少。

数据范围：$n,m \leq 250000,\sum {k_i} \leq 5 \times 10^5$

有一个 $n$ 行 $m$ 列的棋盘，棋盘上可以放很多特殊的棋子，每个棋子的攻击范围是 $3$ 行 $p$ 列。输入数据用一个 $3 \times p$ 的矩阵给出了棋子攻击范围的模板，棋子被默认在模板中的第 [二] 行，第 [$k+1$] 列，模板中棋子能攻击到的位置标记为 1，不能攻击到的位置是 0 $(1 \leq p \leq m, 0 \leq k < p)$。输入数据保证模板中的第 [二] 行第 [$k+1$] 列是 1。

打开门的密码是这样的：在要求棋子互相不能攻击到的前提下，摆放棋子的方案数。注意什么棋子都不摆也算作一种可行方案。请求出方案对 $2^{32}$ 取余的结果即可。

方伯伯正在做他的 OJ 。现在他在处理 OJ 上的用户排名问题。 OJ 上注册了 $n$ 个用户，编号为 $1$ ～ $n$ ，一开始他们按照编号排名。

方伯伯会按照心情对这些用户做以下四种操作，修改用户的排名和编号 ，共有 $m$ 次操作：

1. 操作格式为 1 x y ，意味着将编号为 $x$ 的用户编号改为 $y$ ，而排名不变，执行完该操作后需要输出该用户在队列中的位置，数据保证 $x$ 必然出现在队列中，同时， $y$ 是一个当前不在排名中的编号。

2. 操作格式为 2 x ，意味着将编号为 $x$ 的用户的排名提升到第一位，执行完该操作后需要输出执行该操作前编号为 $x$ 用户的排名。

3. 操作格式为 3 x ，意味着将编号为 $x$ 的用户的排名降到最后一位，执行完该操作后需要输出执行该操作前编号为 $x$ 用户的排名。

4. 操作格式为 4 k，意味着查询当前排名为 $k$ 的用户编号，执行完该操作后需要输出当前操作用户的编号。

对于 $100%$ 的数据， $1 \leq n \leq 10^8,1 \leq m \leq 10^5$。

强制在线。

给定一个无向连通图，其节点编号为 $1$ 到 $N$，其边的权值为非负整数。试求出一条从 $1$ 号节点到 $N$ 号节点的路径，使得该路径上经过的边的权值的 “ $\text{XOR}$ 和” 最大。该路径可以重复经过某些节点或边，当一条边在路径中出现多次时，其权值在计算 “$\text{XOR}$ 和” 时也要被重复计算相应多的次数。

直接求解上述问题比较困难，于是你决定使用非完美算法。具体来说，从 $1$ 号节点开始，以相等的概率，随机选择与当前节点相关联的某条边，并沿这条边走到下一个节点，重复这个过程，直到走到 $N$ 号节点为止，便得到一条从 $1$ 号节点到 $N$ 号节点的路径。显然得到每条这样的路径的概率是不同的，并且每条这样的路径的 “ $\text{XOR}$ 和” 也不一样。现在请你求出该算法得到的路径的 “ $\text{XOR}$ 和” 的期望值。

给定一个 $n$ 个点， $m$ 条边的无向图。聪聪开始的时候在 S，可可在节点 T 处。以后的每个时间单位，可可都会选择去相邻的景点(可能有多个)中的一个或停留在原景点不动。而去这些地方所发生的概率是相等的。假设有 $P$ 个景点与景点 M 相邻，它们分别是景点 R、 景点 S，……，景点 Q，在时刻 $i$ 可可处在景点 M，则在 $i+1$ 时刻，可可有 $\frac{1}{1+P}$ 的可能在景点 R，有 $\frac{1}{1+P}$ 的可能在景点 S，……，有 $\frac{1}{1+P}$ 的可能在景点 Q，还有 $\frac{1}{1+P}$ 的可能停在景点 M。

当聪聪在景点 C 时，她会选一个更靠近可可的景点，如果这样的景点有多个，她会选一个标号最小的景点。如果走完第一次移动以后仍然没吃到可可，她还可以在本段时间内再向可可进行一次移动。

在每个时间单位，假设聪聪先走，可可后走。在某一时刻，若聪聪和可可位于同一个景点，则可怜的可可就被吃掉了。

请求出平均情况下，聪聪用几个时间单位就可能吃到可可。

给一个数字串 $s$ 和正整数 $d$ , 统计 $s$ 有多少种不同的排列能被 $d$ 整除（可以有前导 $0$ ）。

给定一个 $n$ 个节点的有根树，开始时每个节点的权值都为 $0$ 。一共有 $q$ 个时刻，每个时刻可能有如下两个操作之一：

1. 给定一个节点 $x$ ，从下一个时刻起每个时刻都给该节点的权值 $+1$（每个节点只会有一次该操作）；

2. 给定两个节点 $x,y$ 以及一个数 $C$ ，求这两个节点的简单路径上权值大于 $C$ 的节点个数，以及简单路径上的所有节点个数。

有 $n$ 家洗车店从左往右排成一排，每家店都有一个正整数价格 $p_i$ 。有 $m$ 个人要来消费，第 $i$ 个人会驶过第 $a_i$ 个开始一直到第 $b_i$ 个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于 $c_i$，那么这个人就不洗车了。

请给每家店指定一个价格，使得所有人花的钱的总和最大。

佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。

现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你，能否选出一个子序列，使得在任意一种变化中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可 。

注意：每种变化最多只有一个值发生变化。

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹，但是以后每一发炮弹都不能高于前一发的高度，其拦截的导弹的飞行速度也不能大于前一发。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

在不能拦截所有的导弹的情况下，我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个，如果有多个最优方案，那么我们会随机选取一个作为最终的拦截导弹行动蓝图。

我方间谍已经获取了所有敌军导弹的高度和速度，你的任务是计算出在执行上述决策时，每枚导弹被拦截掉的概率。

在定位系统中，世界被认为是一个 $W \times W$ 的正方形区域，由 $1 \times 1$ 的方格组成。每个方格都有一个坐标 $(x,y)$ ， $1 \leq x,y \leq W$。

有三种命令，意义如下：

• 0 W 初始化一个全零矩阵。本命令仅开始时出现一次。
• 1 x y A 向方格 $(x,y)$ 中添加A个用户。A是正整数。
• 2 X1 Y1 X2 Y2 查询 $X1 \leq x \leq X_2$ ， $Y_1 \leq y \leq Y_2$ 所规定的矩形中的用户数量
• 3 无参数 结束程序。本命令仅结束时出现一次。

给定了一个长度为 $n$ 的数列和 $m$ 个询问。

每个询问给定数列的一个区间 $[l,r]$ ，你要回答两个问题：

• 该区间内大于等于 $a$ ，小于等于 $b$ 的数的个数，
• 所有大于等于 $a$ ，小于等于 $b$ 的，且在该区间中出现过的数值的个数。

给出正整数 $n$ 和 $k$ ，计算
$$
\sum _ {i=1}^{n} k \bmod i
$$

简单题意：

给定一个质数 $P$ 和其原根 $g$，给定 $X$ 求 $g^x \equiv X \pmod p$ 的非负整数解 $x$。