这天，SJY 显得无聊。在家自己玩。在一个棋盘上，有 $N$ 个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是曼哈顿距离即 $(|x_1-x_2|+|y_1-y_2|)$ 。现在给出 $N$ 个初始棋子和 $M$ 个操作,对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

给定一棵 $n$ 个点的有根树，每个点有一种颜色。对于每个点，统计子树里出现次数最多的颜色（可能有多个）的编号和。

放假了，小 Z 觉得呆在家里特别无聊，于是决定一个人去游乐园玩。进入游乐园后，小 Z 看了看游乐园的地图,发现可以将游乐园抽象成有 $n$ 个景点、 $m$ 条道路的无向连通图，且该图中至多有一个环（即 $m$ 只可能等于 $n$ 或者 $n-1$ ）。

小 Z 现在所在的大门也正好是一个景点。小 Z 不知道什么好玩，于是他决定，从当前位置出发，每次随机去一个和当前景点有道路相连的景点，并且同一个景点不去两次（包括起始景点）。贪玩的小 Z 会一直游玩，直到当前景点的相邻景点都已经访问过为止。

小 Z 所有经过的景点按顺序构成一条非重复路径，他想知道这条路径的期望长度是多少？

小 Z 把游乐园的抽象地图画下来带回了家，可是忘了标哪个点是大门，他只好假设每个景点都可能是大门（即每个景点作为起始点的概率是一样的）。同时，他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点。

小 T 打算在城市 C 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，小 T 希望快餐店的地址选在离最远的顾客距离最近的地方。

快餐店的顾客分布在城市 C 的 $N$ 个建筑中，这 $N$ 个建筑通过恰好 $N$ 条双向道路连接起来，不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小 T 的快餐店可以开设在任一建筑中，也可以开设在任意一条道路的某个位置上（该位置与道路两端的建筑的距离不一定是整数）。

现给定城市 C 的地图（道路分布及其长度），请找出最佳的快餐店选址，输出其与最远的顾客之间的距离。

我们知道一棵有根树可以进行深度优先遍历（DFS）以及广度优先遍历（BFS）来生成这棵树的 DFS 序以及 BFS 序。两棵不同的树的 DFS 序有可能相同，并且它们的 BFS 序也有可能相同。

现给定一个 DFS 序和 BFS 序，我们想要知道，符合条件的有根树中，树的高度的平均值。即，假如共有 $K$ 棵不同的有根树具有这组 DFS 序和 BFS 序，且他们的高度分别是 $h_1, h_2, \ldots, h_K$​ ，那么请你输出：

$\frac{h_1+h_2+\cdots +h_K}{K}$

今年夏天，NOI 在 SZ 市迎来了她 30 周岁的生日。来自全国 $n$ 个城市的 OIer 们都会从各地出发，到 SZ 市参加这次盛会。

全国的城市构成了一棵以 SZ 市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 $n$ 个城市用 $1$ 到 $n$ 的整数编号。其中 SZ 市的编号为 $1$ 。对于除 SZ 市之外的任意一个城市 $v$ ，我们给出了它在这棵树上的父亲城市 $f_v$ 以及到父亲城市道路的长度 $s_v$ 。

从城市 $v$ 前往 SZ 市的方法为：选择城市 $v$ 的一个祖先 $a$，支付购票的费用，乘坐交通工具到达 $a$。再选择城市 $a$ 的一个祖先 $b$ ，支付费用并到达 $b$ 。以此类推，直至到达 SZ 市。

对于任意一个城市 $v$ ，我们会给出一个交通工具的距离限制 $l_v$ 。对于城市 $v$ 的祖先 $a$ ，只有当它们之间所有道路的总长度不超过 $l_v$ 时，从城市 $v$ 才可以通过一次购票到达城市 $a$ ，否则不能通过一次购票到达。对于每个城市 $v$ ，我们还会给出两个非负整数 $p_v,q_v$ 作为票价参数。若城市 $v$ 到城市 $a$ 所有道路的总长度为 $d$ ，那么从城市 $v$ 到城市 $a$ 购买的票价为 $dp_v+q_v$​​ 。

每个城市的 OIer 都希望自己到达 SZ 市时，用于购票的总资金最少。你的任务就是，告诉每个城市的 OIer 他们所花的最少资金是多少。

小 H 有一个 $N$ 行 $M$ 列的棋盘，她首先按照上述过程，通过 $N\times M+Q$ 次交换操作，生成一个 $1 \sim N \times M$ 的随机排列 $\{T_i\}^{N \times M}_{i \geq 1}$ ，然后将这 $N \times M$ 个数逐行逐列依次填入这个棋盘：也就是第 $i$ 行第 $j$ 列的格子上所填入的数应为 $T_{(i-1)M+j}$​​ 。

接着小 H 希望从棋盘的左上角，也就是第一行第一列的格子出发，每次向右走或向下走，在不走出棋盘的前提下，走到棋盘的右下角，也就是第 $N$ 行第 $M$ 列的格子。

小 H 把所经过格子上的数字都记录了下来，并从小到大排序，这样，对于任何一条合法的移动路径，小 H 都可以得到一个长度为 $N+M-1$ 的升序序列，我们称之为路径序列。

小 H 想知道，她可能得到的字典序最小的路径序列应该是怎样的呢？

近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。

下课前，园长提出了一个问题： KMP 算法只能求出 $next$ 数组。我现在希望求出一个更强大 $num$ 数组——对于字符串 $S$ 的前 $i$ 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作 $num_i$ 。

最后，园长给出了奖励条件，第一个做对的同学奖励巧克力一盒。听了这句话，睡了一节课的企鹅立刻就醒过来了！但企鹅并不会做这道题，于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出 $num$ 数组呢？

为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐士。

魔法森林可以被看成一个包含 $N$ 个节点 $M$ 条边的无向图，节点标号为 $1,\ldots,N$ ，边标号为 $1,\ldots,M$ 。初始时小 E 同学在号节点 $1$ ，隐士则住在 $N$ 号节点。小 E 需要通过这一片魔法森林，才能够拜访到隐士。

魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在 $1$ 号节点住着两种守护精灵： $A$ 型守护精灵与 $B$ 型守护精灵。小 E 可以借助它们的力量，达到自己的目的。

只要小 E 带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边 $E_i$ 包含两个权值 $A_i$ 与 $B_i$ 。若身上携带的 A 型守护精灵个数不少于 $A_i$ ，且 $B$ 型守护精灵个数不少于 $B_i$ ，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小 E 发起攻击，他才能成功找到隐士。

由于携带守护精灵是一件非常麻烦的事，小 E 想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为 $A$ 型守护精灵的个数与 $B$ 型守护精灵的个数之和。

21 世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。作为一名青春阳光好少年，atm 一直坚持与起床困难综合症作斗争。通过研究相关文献，他找到了该病的发病原因：在深邃的太平洋海底中，出现了一条名为 drd 的巨龙，它掌握着睡眠之精髓，能随意延长大家的睡眠时间。正是由于 drd 的活动，起床困难综合症愈演愈烈，以惊人的速度在世界上传播。为了彻底消灭这种病，atm 决定前往海底，消灭这条恶龙。

历经千辛万苦，atm 终于来到了 drd 所在的地方，准备与其展开艰苦卓绝的战斗。drd 有着十分特殊的技能，他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来，drd 的防御战线由 $n$ 扇防御门组成。每扇防御门包括一个运算 $op$ 和一个参数 $t$ ，其中运算一定是 OR、XOR、AND 中的一种，参数则一定为非负整数。如果还未通过防御门时攻击力为 $x$ ，则其通过这扇防御门后攻击力将变为 $x$ $op$ $t$ 。最终 drd 受到的伤害为对方初始攻击力 $x$ 依次经过所有 $n$ 扇防御门后转变得到的攻击力。

由于 atm 水平有限，他的初始攻击力只能为 $0$ 到 $m$ 之间的一个整数（即他的初始攻击力只能在 $0,1,\cdots m$ 中任选，但在通过防御门之后的攻击力不受 $m$ 的限制）。为了节省体力，他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害，请你帮他计算一下，他的一次攻击最多能使 drd 受到多少伤害。