#213393. [NOI2025] 序列变换

给定两个长度为 的整数序列 ，。对于长度为 的非负整数序列 ，设 为所有满足 的下标 的集合，定义 ，。特别地，若 为空，则 ，。

小 L 有一个长度为 的 正整数序列 。小 L 可以对序列 做如下修改：

• 选择序列 的两个 相邻 的下标 （即 且 ），若 ，则将 改为 ，同时将 改为 。

小 L 可以进行任意多次修改操作，也可以不进行任何修改。对于所有序列 通过以上修改操作可以得到的序列 ，小 L 想求出 的最大值以及 之和，请你帮助他求出这两个值。形式化地，记 为序列 通过以上修改操作可以得到的 所有序列的集合，你需要求出 以及 。其中，由于 可能较大，你只需要求出其对 取模后的结果。

本题包含多组测试数据。

输入的第一行包含两个非负整数 ，分别表示测试点编号与测试数据组数。 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含一个正整数 ，表示序列长度。
• 第二行包含 个正整数 ，表示序列 。
• 第三行包含 个整数 ，表示序列 。
• 第四行包含 个正整数 ，表示序列 。

对于每组测试数据，仅输出一行，其中包含两个整数，分别表示 以及 对 取模后的结果。注意： 不需要对 取模。

本题包含两个小问，正确回答其中任意一个小问均可获得部分分数。具体评分规则请参见【评分方式】。

样例输入 1

0 3
3
5 6 6
3 6 9
1 2 3
6
1 1 4 5 1 4
-1 1 -1 1 -2 2
1 1 1 1 1 1
8
4 2 4 2 2 2 4 4
-2 4 9 -3 4 8 7 8
1 1 1 1 1 1 1 1

样例输出 1

15 10
1 18
37 48

样例 1 解释

该样例共包含三组测试数据。

对于第一组测试数据，可以得到以下 4 个序列：

• ，，；
• ，，；
• ，，；
• ，，。

故 ，。

样例 2

见选手目录下的 sequence/sequence2.in 与 sequence/sequence2.ans。

该样例满足测试点 3、4 的约束条件。

样例 3

见选手目录下的 sequence/sequence3.in 与 sequence/sequence3.ans。

该样例满足测试点 5、6 的约束条件。

样例 4

见选手目录下的 sequence/sequence4.in 与 sequence/sequence4.ans。

该样例满足测试点 7 的约束条件。

样例 5

见选手目录下的 sequence/sequence5.in 与 sequence/sequence5.ans。

该样例满足测试点 11、12 的约束条件。

样例 6

见选手目录下的 sequence/sequence6.in 与 sequence/sequence6.ans。

该样例满足测试点 的约束条件。

设 为单个测试点内所有测试数据的 的和。对于所有测试数据，保证：

• ；
• ，；
• 对于所有 ，均有 ；
• 对于所有 ，均有 ；
• 对于所有 ，均有 。

::cute-table{tuack}

• 特殊性质 A：保证 。
• 特殊性质 B：保证对于所有 ， 均在 中 独立均匀随机 生成。

评分方式

对于每个测试点：

• 正确回答所有测试数据的 ，可获得该测试点 的分数；
• 正确回答所有测试数据的 对 取模后的结果，可获得该测试点 的分数。

注意：即使选手仅回答了其中一个问题，也需要按照输出格式输出两个整数，分别对应两个问题的答案。

附加文件来自于 QOJ。