你有一个长度为 \(n (1 \le n \le 2 \times 10^5)\) 的整数序列 \(a\)。
你需要回答 \(q (1 \le q \le 2 \times 10^5)\) 个独立的问题，每次询问如下：
给定 \(l\) 和 \(r\)，你可以对序列做若干次操作（也可以不做），每次操作，你需要选择两个数 \(L\) 与 \(R\)，其中必须满足 \(l\le L\le R\le r\) 且 \(R-L+1\) 为奇数。然后将 \(a_L\sim a_R\) 的所有数改为 \(a_L\sim a_R\) 的异或和，即 \(a_L\oplus a_{L+1}\oplus \sim \oplus a_R\)。
你的目标是将 \(a_l\sim a_r\) 的所有数变为 \(0\)。每次询问完后，序列复原。
询问的答案即为最小操作数。如果总是不能达到目标，则答案为 \(-1\)。
给定 \(s\) 串和 \(t\) 串，其中 \(s\) 串包含小写字母和问号，\(t\) 串只包含小写字母。
假设共有 \(k\) 个问号。
你需要给把每个问号变成一个小写字母，共有 \(26^k\) 种可能。
对于每种可能，设 \(t\) 匹配 \(s\) 的次数为 \(f_i\)，请输出 \(\max(f_i)\) 。
\(1\leq |s|,|t|\leq 10^5,|s|\cdot |t|\leq 10^7\)
一文概括 Splay
长文预警
Splay 是一种平衡树，可以解决很多序列问题。而平衡树是一种二叉搜索树。
二叉搜索树则是一种数据结构，对于每一个节点，权值满足左儿子小于根节点小于右儿子，且整棵树的中序遍历是排序后的序列。这样二叉搜索树就可以解决很多问题，其时间复杂度取决于树的深度。
于是这里可以引出一种调试平衡树的常见方法：输出这棵树的中序遍历，看中序遍历是否为排序后序列。
然而在特殊数据下，二叉搜索树很容易退化成一颗链，于是就有了一种优化版本：平衡树。平衡树可以让二叉搜索树随时变化，以求深度保持相对较小，即“平衡”。而 Splay 就是一种平衡树。
生物学家终于发明了修复 DNA 的技术，能够将包含各种遗传疾病的DNA片段进行修复。
为了简单起见，DNA 看作是一个由
A、G、C、T
构成的字符串。
修复技术就是通过改变字符串中的一些字符，从而消除字符串中包含的致病片段。
例如，我们可以通过改变两个字符，将 DNA 片段 AAGCAG 变为
AGGCAC，从而使得 DNA 片段中不再包含致病片段
AAG、AGC、CAG，以达到修复该DNA片段的目的。
需注意，被修复的 DNA 片段中，仍然只能包含字符
A、G、C、T。
请你帮助生物学家修复给定的 DNA 片段，并且修复过程中改变的字符数量要尽可能的少。
你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包 \(A\) 依赖软件包 \(B\)，那么安装软件包 \(A\) 以前，必须先安装软件包 \(B\)。同时，如果想要卸载软件包 \(B\)，则必须卸载软件包 \(A\)。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除 \(0\) 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而 \(0\) 号软件包不依赖任何一个软件包。依赖关系不存在环（若有 \(m \ (m \geq 2)\) 个软件包\(A_1, A_2, A_3, \ldots ,A_m\)，其中 \(A_1\) 依赖 \(A_2\)，\(A_2\) 依赖 \(A_3\)，\(A_3\) 依赖 \(A_4\)，……，\(A_{m−1}\) 依赖 \(A_m\)，而 \(A_m\) 依赖 \(A_1\)，则称这 \(m\) 个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为 \(0\)。
对于所有数据，\(n \leq 100000, \ q \leq 100000\)。
树链剖分是一个很常见的处理树上问题的算法，但之前一直没学 /kk，现在终于把这个坑补了。
这里只讲了重链剖分，不涉及其他剖分方式。
树链剖分是一种把树上问题转化为序列问题的算法。它可以将树上的一条路径所经过的点用序列中的若干条区间表示。
首先我们需要知道几个概念：重儿子、轻儿子、重边、轻边。我们定义对于一个节点 \(u\) 的儿子为 \(v\)，我们定义以 \(v\) 为根的子树中节点最多的子树所对应的 \(v\) 为重儿子，其余的 \(v\) 为轻儿子。父亲连向重儿子的边为重边，父亲连向轻儿子的边为轻边。如果同时有多个以 \(v\) 为根的子树节点数相同且最大，则选取任意一个 \(v\) 为重儿子，其余为轻儿子。这样对于每个非叶节点，我们都有一个重儿子和一个重边。
在这一轮的星际战争中，我方在宇宙中建立了 \(n\) 个据点，以 \(m\) 个单向虫洞连接。我们把终点为据点 \(u\) 的所有虫洞归为据点 \(u\) 的虫洞。
战火纷飞之中这些虫洞很难长久存在，敌人的打击随时可能到来。这些打击中的有效打击可以分为两类：
注意：摧毁只会导致虫洞不可用，而不会消除它的存在。
为了抗击敌人并维护各部队和各据点之间的联系，我方发展出了两种特种部队负责修复虫洞：
考虑到敌人打击的特点，我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复，处于可用状态，那么这个据点也是可用的。
我方掌握了一种苛刻的空间特性，利用这一特性我方战舰可以沿着虫洞瞬移到敌方阵营，实现精确打击。
为了把握发动反攻的最佳时机，指挥部必须关注战场上的所有变化，为了寻找一个能够进行反攻的时刻。总指挥认为：
总司令为你下达命令，要求你根据战场上实时反馈的信息，迅速告诉他当前的时刻是否能够进行一次反攻。
对于所有数据保证：\(1 \le n \le 5 \times {10}^5\)，\(1 \le m \le 5 \times {10}^5\)，\(1 \le q \le 5 \times {10}^5\)。