NOIP 编号为 ZJ-267 的小 Z 在 NOIP 中 AK 啦！

小 Z 打算去冲击省选，于是开始学习 trie 。

有一天，他得到了 $N$ 个字符串。

他先建立一个根节点，对于每一个字符串，他都从根节点开始一点点插入。

小 Z 不满足于此。他的大脑里盘旋着 $M$ 个问题：

如果给定一个二元组 $(s,t)$ （ $s$，$t$ 都是 trie 中的节点且 $s$ 是 $t$ 的祖先），存在多少个二元组 $(x,y)$ （ $x$，$y$ 都是 trie 中的节点且 $x$ 是 $y$ 的祖先），满足 $s$ ~ $t$ 路径上的字符串和 $x$ ~ $y$ 路径上的字符串完全一样？

注意 $s$ 可以等于 $t$ ， $x$ 也可以等于 $y$ 。

小 P 非常喜欢玩。他最喜欢玩的一个游戏就是《洞》，这个游戏遵循以下规则：

有 $N$ 个洞呈直线分布，并且从左到右依次编号为 $1$ 到 $N$ 。每个洞都有它自己的能量值（编号为 $i$ 的洞有能量值 $a_i$ ）。如果你把一个球扔到洞 $i$ ，它会迅速调到洞 $i+a_i$ ，以此类推。如果没有编号为 $i+a_i$ 的洞，这个球将会跳到这洞外，结束循环。玩家将会执行 $M$ 次以下两种操作之一：

• 设置洞 $a$ 的能量值为 $b$ 。
• 将球扔到洞 $a$ ，计算球跳到洞外之前跳跃的次数，以及球刚好跳到洞外之前最后经过的洞的编号。

小 P 不擅长数学，所以将由你实现这些计算。

克拉克是一名人格分裂患者。某一天他变成一名数学家，在研究奇怪的东西。

他突然想算这么一个式子，给出 $f(i), 1 \le i \le n$ ，要求算：

$\displaystyle g(i) = \sum_{i_1 \mid i} \sum_{i_2 \mid i_1} \sum_{i_3 \mid i_2} \cdots \sum_{i_k \mid i_{k-1}} f(i_k) \text{ mod } 1000000007 \ \ (1 \le i \le n,i_j \in \mathbb{N}^+)$

$\mid$ 是整除的意思,比如 $i_1 = 5$ , $i_2 = 10$ 则 $i_1 \mid i_2$。

线段树是一种经典的数据结构，一颗 $[1,n]$ 的线段树他的根是 $[1,n]$ ，当一个线段树的结点是 $[l,r]$ 时，设 $mid=(l+r)/2$ ，则这个结点的左儿子右儿子分别是 $[l,mid]$ ， $[mid+1,r]$ 。

当我们在线段树上跑 $[x,y]$ 询问时，一般是从根节点开始计算的，设现在所在结点是 $[l,r]$ ，有以下几种分支：

• 若 $[x,y]$ 包含 $[l,r]$ ，计算结束。
• 否则，若左儿子和 $[x,y]$ 有交，计算左儿子，若右儿子和 $[x,y]$ 有交，计算右儿子。

定义询问 $[x,y]$ 的费用是询问时计算了几个结点。

给定 $Q$ 次询问，每次给定 $l$ , $r$ ，求满足 $l\leq x\leq y\leq r$ 的 $(x,y)$ 的费用之和。

雪之国度有 $N$ 座城市，依次编号为 $1$ 到 $N$，又有 $M$ 条道路连接了其中的城市，每一条道路都连接了不同的 $2$ 个城市，任何两座不同的城市之间可能不止一条道路。

雪之女王赋予了每一座城市不同的能量，其中第 $i$ 座城市被赋予的能量为 $W_i$ 。如果城市 $u$ 和 $v$ 之间有一条道路，那么只要此刻雪之女王的能量不小于 $|W_u-W_v|$ ，这条道路就是安全的。如果城市 $u$ 和 $v$ 之间存在两条没有重复道路的安全路径（其中每一段道路都是安全的），则认为这两座城市之间有着良好的贸易关系。

最近，雪之女王因为情感问题，她的能量产生巨大的波动。为了维持雪之国度的经济贸易，她希望你能帮忙对 $Q$ 对城市进行调查。

对于第 $j$ 对城市 $u_j$ 和 $v_j$ ，她希望知道在保证这两座城市之间有着良好贸易关系的前提之下，自己最少需要保持多少的能量。

我们把所有大于整数 $p$ 的质数称作大质数。

现在我们要统计区间 $[a,b]$ 中有多少数其至少有一个约数是大质数。

Fancy 年青的时候喜欢旅行。据他回忆说，那曾是一段有始有终的旅行。

他来到了一个叫 Fancy 的理想国。那里有许许多多的 FancyCat 。最开始的时候，同一种 FancyCat 会形成一个部落，拥有特定的一块领地。Fancy 第一次来这里的时候还 Too Young ，现在他将故地重游。但由于多年的演变，部落分分合合，现在两个不一样的部落有可能也是由同一种 FancyCat 组成。

Fancy 开始了他的徒步路程。每次他经过某一个部落，他将收到由该部落种类的纪念品一份。Fancy 很喜欢收集纪念品。他是一个性情中人，越喜欢的纪念品他就越想得到，而且要越多越好。Fancy 列出了一张纪念品喜欢程度的排名表。在这个表中越靠前的纪念品表示 Fancy 越喜欢。

由于理想国过于庞大，虽然拥有地图，但 Fancy 也会因为找不到地图上对应的位置而经常迷路。 Fancy 觉得与其在地图中苦苦挣扎不如随机走。而且他坚信一定能走到终点！ Fancy 在旅行开始前，想到可以先计算一下期望得到的每个纪念品的数量，不过由于图中环的存在，给计算带来了很大困难。于是 Fancy 打算只计算一下自己完全随机乱走的情况下最坏能得到的那些纪念品。对于两条旅行线路的比较，他采取了如下的方法：找出在排名表中最靠前的一个纪念品，满足两条线路中获得的该纪念品数量不相等。这时候，该纪念品多的那一条线路更优。

你要做的工作就是计算出最坏情况下的得到纪念品序列。

现在有一个长度为 $n$ 的数组 $A$ ，另外还有一个整数 $k$ 。数组下标从 $1$ 开始。

现在你需要把数组的顺序重新排列一下使得下面这个的式子的值尽可能小。

$\sum_{i=1}^{n-k}{|A[i]-A[i+k]|}$

特别的，你也可以不对数组进行重新排列。

有 $n$ 堆方块，第 $i$ 堆方块由 $h_i$ 个方块堆积而成。

接下来拆方块。一个方块称为内部方块当且仅当他的上下左右都是方块或者是地面。否则方块就是边界方块。每一次操作都要把边界方块拿掉。

问多少次操作之后所有方块会消失。

$N$ 个不同的正整数，找出由这些数组成的最长的等差数列。