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

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

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

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

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

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

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

有三种命令，意义如下：

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

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

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

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

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

简单题意：

给定一个质数 $P$ 和其原根 $g$，给定 $X$ 求 $g^x\equiv X(\mathrm{mod}p)$ 的非负整数解 $x$。

已知一个长度为 $n$ 的整数数列 $a_1,a_2,\dots ,a_n$ ，给定查询参数 $l$ 、 $r$ ，问在 $a_l,a_{l+1},\dots ,a_r$ ​区间内，有多少子序列满足异或和等于 $k$ 。也就是说，对于所有的 $x,y$ $(l\le x\le y\le r)$ ，能够满足 $a_x⨁a_{x+1}⨁\dots ⨁a_y=k$ 的 $x,y$ 有多少组。

喜欢钻研问题的 $JS$ 同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。

例如 JSOI07 ，可以读作： JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 ，把它们按照字符串的大小排序：

• 07JSOI
• 7JSOI0
• I07JSO
• JSOI07
• OI07JS
• SOI07J

读出最后一列字符：I0O7SJ，就是加密后的字符串。 但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？

你被要求设计一个计算器完成以下三项任务：

1. 给定 $y,z,p$ ，计算 $y^{z}modp$ 的值；

2. 给定 $y,z,p$ ，计算满足 $xy\equiv z(\mathrm{mod}p)$ 的最小非负整数 $x$；

3. 给定 $y,z,p$ ，计算满足 $y^x\equiv z(\mathrm{mod}p)$ 的最小非负整数 $x$。

保证 $p$ 为质数。

小 $W$ 喜欢读书，尤其喜欢读《约翰克里斯朵夫》。最近小W准备读一本新书，这本书一共有 $P$ 页，页码范围为 $0\dots P-1$。

小 $W$ 很忙，所以每天只能读一页书。为了使事情有趣一些，他打算使用 $\text{NOI2012}$ 上学习的线性同余法生成一个序列，来决定每天具体读哪一页。

我们用 $X_i$ 来表示通过这种方法生成出来的第 $i$ 个数，也即小 $W$ 第 $i$ 天会读哪一页。这个方法需要设置 $3$ 个参数 $a,b,X_1$ ，满足 $0\le a,b,X_1\le p-1$ ，且 $a,b,X_1$ 都是整数。按照下面的公式生成出来一系列的整数：$X_{i+1}=(a{X}_i+b)modp$ 其中 $mod$ 表示取余操作。

但是这种方法可能导致某两天读的页码一样。

小 $W$ 要读这本书的第 $t$ 页，所以他想知道最早在哪一天能读到第 $t$ 页，或者指出他永远不会读到第 $t$ 页。

作为体育委员， $C$ 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 $N\times N$ 的方阵，为了保证队伍在行进中整齐划一， $C$ 君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。

现在， $C$ 君希望你告诉他队伍整齐时能看到的学生人数。

一段文章 $T$ 是由若干小写字母构成。一个单词 $W$ 也是由若干小写字母构成。一个字典 $D$ 是若干个单词的集合。我们称一段文章 $T$ 在某个字典 $D$ 下是可以被理解的，是指如果文章 $T$ 可以被分成若干部分，且每一个部分都是字典 $D$ 中的单词。

给定一个字典 $D$ ，你的程序需要判断若干段文章在字典 $D$ 下是否能够被理解。并给出其在字典 $D$ 下能够被理解的最长前缀的位置。

给定一个长度为 $N$ 的数列，每次一个操作或询问：

• 把闭区间 $[L,R]$ 内的数全部加上一个整数 $W$
• 问闭区间 $[L,R]$ 内有多少英雄身高大于等于 $C$

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

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

小 $Y$ 最近在一家金券交易所工作。该金券交易所只发行交易两种金券：$A$ 纪念券（以下简称 $A$ 券）和 $B$ 纪念券（以下简称 $B$ 券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 $K$ 天中 $A$ 券 和 $B$ 券的价值分别为 $A_K$ 和 $B_K$（元/单位金券）。为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。比例交易法分为两个方面：

（a）卖出金券：顾客提供一个 $[0,100]$ 内的实数 $OP$ 作为卖出比例，其意义为：将 $OP$ 的 $A$ 券和 $OP$ 的 $B$ 券以当时的价值兑换为人民币；

（b）买入金券：顾客支付 $IP$ 元人民币，交易所将会兑换给用户总价值为 $IP$ 的金券，并且，满足提供给顾客的 $A$ 券和 $B$ 券的比例在第 $K$ 天恰好为 $Rat{e}_K$ ；

注意到，同一天内可以进行多次操作。小 $Y$ 是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来 $N$ 天内的 $A$ 券和 $B$ 券的价值以及 $Rate$ 。他还希望能够计算出来，如果开始时拥有 $S$ 元钱，那么 $N$ 天后最多能够获得多少元钱。