在 $2016$ 年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个 $1$ 到 $n$ 的全排列，现在对这个全排列序列进行 $m$ 次局部排序，排序分为两种：

• $(0,l,r)$表示将区间 $[l,r]$ 的数字升序排序
• $(1,l,r)$表示将区间 $[l,r]$ 的数字降序排序
  最后询问第 $q$ 位置上的数字。

你的面前有 $n$ 个数排成一行，分别为 $a_1,a_2,...,a_n$ 。你打算在每相邻的两个 $a_i$c和 $a _ {i+1}$ 间都插入一个加号、减号或者乘号。那么一共有 $3^{n-1}$ 种可能的表达式。

你对所有可能的表达式的值的和非常感兴趣。但这毕竟太简单了，所以你还打算支持一个修改操作，可以修改某个 $a_i$ 的值。

你能够编写一个程序对每个修改都输出修改完之后所有可能表达式的和吗？注意，修改是永久的，也就是说每次修改都是在上一次修改的基础上进行，而不是在最初的表达式上进行。

简单版题意：

给定一个 $R \times C$ 的矩形，在其中 $N$ 个位置有随机生成的资源点。现在请你求出在所有的子矩形中，至少包含一个资源点的矩形数量。

可读版题意：

给定 $n$ 个仅包含大写字母的模板串，求所有的长度为 $M$ 且仅包含大写字母的不同字符串中，有多少个包含至少一个模板串。答案对 $10007$ 取模。

可读版题意：

给定 $n$ 个字符串，第 $i$ 个字符串的长度为 $M_i$ ，求每个字符串在所有字符串中出现的次数。

数据范围：$n \leq 100,\ M = \sum M_i \leq 10^6$.

阿申准备报名参加 $GT$ 考试，准考证号为 $n$ 位数 $X_1X_2\cdots X_n(0\le X_i\le 9)$，他不希望准考证号上出现不吉利的数字。

他的不吉利数字 $A_1A_2\cdots A_m(0\le A_i\le 9)$ 有 $m$ 位，不出现是指 $X_1X_2\cdots X_n$ 中没有恰好一段等于 $A_1A_2\cdots A_m$，$A_1$​ 和 $X_1$ 可以为 $0$。

阿申想知道不出现不吉利数字的号码有多少种，输出模 $K$ 取余的结果。

HH 是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为 HH 是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。

现在给你学校的地图（假设每条路的长度都是一样的都是 $1$ ），问长度为 $t$ ，从给定地点 $A$ 走到给定地点 $B$ 共有多少条符合上述条件的路径。

有一个无向图 $G$ ，每个点有个权值，每条边有一个颜色。这个无向图满足以下两个条件：

• 对于任意节点连出去的边中，相同颜色的边不超过两条。
• 图中不存在同色的环，同色的环指相同颜色的边构成的环。

在这个图上，你要支持以下三种操作：

• 修改一个节点的权值。
• 修改一条边的颜色。
• 查询由颜色 $c$ 的边构成的图中， $u$ 到节点 $v$ 之间的简单路径上的节点的权值的最大值。

对于 100% 的数据，保证颜色不多于 $10$ 种。

系统将依次随机抛出 $k$ 次宝物，每次你都可以选择吃或者不吃。宝物一共有 $n$ 种，系统每次抛出这 $n$ 种宝物的概率都相同且相互独立。

吃一次第 $i$ 种宝物将得到 $P_i$ 分，但并不是每种宝物都是可以随意获取的。第 $i$ 种宝物有一个前提宝物集合 $S_i$ 。只有当 $S_i$ 中所有宝物都至少吃过一次，才能吃第 $i$ 种宝物。注意，$P_i$ 可以是负数。

假设你采取最优策略，平均情况你一共能在奖励关得到多少分值？

有 $m$ 个骑士攻占 $n$ 个城池。除 $1$ 号城池外，城池 $i$ 会受到另一座城池 $f_i$ 的管辖，其中 $f_i < i$。也就是说，所有城池构成了一棵有根树。第 $i$ 个骑士的初始战斗力为 $s_i$，第一个攻击的城池为 $c_i$。

每个城池有一个防御值 $h_i$，如果一个骑士的战斗力大于等于城池的生命值，那么骑士就可以占领这座城池；否则占领失败，骑士将在这座城池牺牲。占领一个城池以后，骑士的战斗力将发生变化，然后继续攻击管辖这座城池的城池，直到占领 $1$ 号城池，或牺牲为止。

除 $1$ 号城池外，每个城池 $i$ 会给出一个战斗力变化参数 $a_i$;$v_i$。若 $a_i = 0$，攻占城池 $i$ 以后骑士战斗力会增加 $v_i$；若 $a_i = 1$，攻占城池 $i$ 以后，战斗力会乘以 $v_i$。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池，不管结果如何，均不会影响其他骑士攻击这座城池的结果。

对于每个城池，输出有多少个骑士在这里牺牲；对于每个骑士，输出他攻占的城池数量。