T835611 混乱（CHAOS）
题目背景
吾即是吾，吾本真。
f(x)=xf(x) = x f(x)=x
题目描述
鸠有两个序列 aaa 和 bbb。
已知序列 bbb 的构造方法：
* 对于 2≤i≤T2 \le i \le T2≤i≤T 的情况，bi=aixorai−1b_i = a_i \operatorname{xor} a_{i - 1}bi =ai xorai−1 ，其中 xor\operatorname{xor}xor 表示异或；
* b1=a1xoraTb_1 = a_1 \operatorname{xor} a_Tb1 =a1 xoraT 。
鸠给你了序列 bbb 的长度 TTT ，以及序列 bbb，求序列 aaa，保证有解。
输入格式
第一行一个正整数 TTT。
接下来 TTT 行，每行一个自然数 bib_ibi 。
输出格式
共 TTT 行，每行一个整数 aia_iai 。
保证有符合要求的输出，如果有不止一种符合要求的输出，你只需要输出任意一种。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
【样例 1 解释】
* b2=a2xora1=2xor1=3b_2 = a_2 \operatorname{xor} a_1=2\operatorname{xor}1=3b2 =a2 xora1 =2xor1=3
* b3=a3xora2=3xor2=1b_3= a_3 \operatorname{xor} a_2=3\operatorname{xor}2=1b3 =a3 xora2 =3xor2=1
* b1=a1xora3=1xor3=2b_1 = a_1 \operatorname{xor} a_3=1\operatorname{xor}3=2b1 =a1 xora3 =1xor3=2
样例 2
见选手目录下的 chaos2.in/chaos2.out。
该样例满足测试点 11∼2011 \sim 2011∼20 的限制。
数据范围
测试点 $T <>e $ 1∼101 \sim 101∼10 333 11∼2011 \sim 2011∼20 10510^5105
对于 100%100\%100% 的数据，保证 1≤T≤105,0≤bi<2301 \le T \le 10^5, 0 \le b_i < 2^{30}1≤T≤105,0≤bi <230，且保证有解。
T835940 幻景（MIRAGE）
题目背景
赛后更新：本题已经添加了子任务。
题目描述
鸠有 nnn 个集合 a1,a2,…,ana_1,a_2,\dots,a_na1 ,a2 ,…,an ，且对于所有 iii 满足 ai⊆[m]a_i \subseteq [m]ai ⊆[m]。有 kkk 个条件，形如如下三种：
* 1 u v，表示 au⊆ava_u \subseteq a_vau ⊆av 。
* 2 u v，表示 au⊊ava_u \subsetneq a_vau ⊊av 。
* 3 u v，表示 ∣au∣=v|a_u|=v∣au ∣=v。
你需要输出是否存在满足所有 kkk 个条件的 nnn 个集合。
注：[m][m][m] 表示 {1,2,…,m}\{1,2,\dots,m\}{1,2,…,m}。
输入格式
第一行输入一个整数 TTT，表示测试数据的数量。
对于每组数据，第一行输入三个正整数 n,m,kn,m,kn,m,k，后面的 kkk 行中，每行三个正整数 op,u,vop,u,vop,u,v，含义见题目描述。
输出格式
对于每组数据，输出一个字符串 YES 或 NO，表示是否存在满足所有 kkk 个条件的 nnn 个集合。
输入输出样例 #1
输入 #1
输出 #1
T835439 小鸟游六花（KIRINOSAMA）
题目描述
在放学后的活动室里，六花又开始研究新的“不可视境界线”。
“勇太！我发现了，人与人之间其实存在着一种由位置和力量共同决定的距离！”
她在纸上画出了排成一排的 nnn 个点，并给第 iii 个点标上了一个神秘的“魔力值” aia_iai 。
对于两个不同的位置 i,ji,ji,j，六花认为它们之间的“共鸣距离”为 ∣ai−aj∣+∣i−j∣|a_i-a_j|+|i-j|∣ai −aj ∣+∣i−j∣。
然而，并不是任意两个位置之间都能够产生共鸣。
六花又在纸上画出了 mmm 个“不可视境界”，每个境界覆盖一段连续的位置 [lk,rk][l_k,r_k][lk ,rk ]。
如果存在某一道境界，使得两个位置中恰好一个位于境界之内，而另一个位于境界之外，那么六花就认为这两个位置成功地被境界分隔，是一对“合法位置”。
“只要找到被境界分隔，而且共鸣最强的两个点，就能够打开真正的不可视境界线！”
勇太看着已经完全沉浸在设定里的六花，只好帮她计算：
所有合法位置对中，最大的 ∣ai−aj∣+∣i−j∣|a_i-a_j|+|i-j|∣ai −aj ∣+∣i−j∣ 是多少？
如果根本不存在合法的位置对，那么就输出 −1-1−1。
输入格式
第一行输入两个整数 n,mn,mn,m。
第二行输入 nnn 个整数 a1,a2,…,ana_1,a_2,\dots,a_na1 ,a2 ,…,an 。
接下来 mmm 行，每行两个整数 lk,rkl_k,r_klk ,rk ，表示一个区间。
输出格式
输出所有合法位置对的最大代价。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
对于 100%100\%100% 的数据有 2≤n≤2×1052\le n\le 2\times 10^52≤n≤2×105，1≤m≤2×1051\le m\le 2\times 10^51≤m≤2×105，1≤lk≤rk≤n1\le l_k\le r_k\le n1≤lk ≤rk ≤n，∣ai∣≤109|a_i|\le 10^9∣ai ∣≤109。
Subtask 分值 限制 1 15 n,m≤200n,m\le 200n,m≤200 2 20 m≤20m\le 20m≤20 3 15 所有给定区间两两不交 4 50 无特殊限制
T835440 夏洛特（CHARLOTTE）
题目背景
关注 Cute_Wazzy 谢谢喵。
题目描述
星之海学园最近又发现了一批能力者。
为了防止能力之间互相干扰，友利奈绪决定重新安排他们的编号位置。
现在有 nnn 名能力者，他们被编号为 1,2,…,n1,2,\dots,n1,2,…,n。
你需要给他们安排一个新的顺序，记第 iii 个位置上的能力者编号为 pip_ipi 。因此 ppp 必须是一个 1∼n1\sim n1∼n 的排列。
但是由于某些能力之间存在特殊的关系，友利规定：
* 对于任意 1≤i≤n1\le i\le n1≤i≤n，必须满足 pi−i∉{−k,0,k}p_i-i\notin\{-k,0,k\}pi −i∈/{−k,0,k}。
友利想知道，一共有多少种不同的合法安排方案。
由于答案可能很大，你只需要输出答案对 998244353998244353998244353 取模后的结果。
输入格式
第一行输入两个正整数 n,kn,kn,k。
输出格式
输出一行，表示合法排列的数量对 998244353998244353998244353 取模后的结果。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
对于 100%100\%100% 的数据有 1≤n≤20001\le n\le 20001≤n≤2000，1≤k≤n−11\le k\le n-11≤k≤n−1。
Subtask 分值 限制 1 10 n≤9n\le 9n≤9 2 15 n≤18n\le 18n≤18 3 15 k>n2k>\frac n2k>2n 4 20 k=1k=1k=1 5 40 无特殊限制
