#6196. 「美团 CodeM 复赛」通信

内存限制:2048 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

NN 个信号塔,第 ii 个塔的位置是 ii,信号强度 XiX_iXiX_i 保证互不相同)。

NN 个人,第 ii 个人的位置是 ii,一个人往左走一格要 AA 秒,往右走一格要 BB 秒。

这些人之间要传递信息,具体地,如果 ii 有信息,那么 ii 会依次做以下操作:

  • 选择一个 jj 满足 1ji1\leq j\leq i,并找到一个 kk 使得 jkij\leq k\leq i 并且 XkX_k 最大来保证通信。
  • i,ji, j 同时向 kk 移动,先到的会等另一个人直到两个人都到达。
  • 等到 i,ji,j 都到达 kk 时,信息的传递瞬间完成,并且 i,ji,j 瞬间回到原来的位置
  • 之后 ii 会失去信息jj 会获得信息。

请对每个 ii 计算,如果初始 ii 有信息,那么最少多少时间以后信息可以传递到 11,并输出最少时间的方案数,方案数对 2322^{32} 取模

一个方案可以被描述成 P1=i,P2,P3,,Pt=1P_1=i,P_2,P_3,\dots,P_t=1,表示信息的传递是 P1P2P3PtP_1\rightarrow P_2\rightarrow P_3 \rightarrow \dots \rightarrow P_t

两个方案被认为是不同的当且仅当 tt 不同或者存在一个 1it1\leq i\leq t 使得 PiP_i 不同。

特殊地,对于 11,我们认为最少时间是 00,方案数为 11

输入格式

第一行三个数 N,A,BN,A,B

接下来一行 NN 个数表示 XiX_i

输出格式

fif_i 表示从 ii 出发的最小时间,gig_i 表示最小时间的方案数。

输出两行,第一行 f1f2f3fnf_1 \oplus f_2 \oplus f_3 \oplus \cdots \oplus f_n

第二行 g1g2g3g4gng_1 \oplus g_2 \oplus g_3 \oplus g_4 \oplus \cdots \oplus g_n

fnf_n 请转成 64 位有符号整形(C++ long long计算 \oplus

gng_n 请转成 32 位无符号整形(C++ unsigned int计算 \oplus

样例

样例输入

6 13 3
2 4 3 5 6 1

样例输出

6
6

样例解释

{f1=0g1=1f2=3g2=1f3=13g3=1f4=9g4=2f5=12g5=4f6=13g6=1 \begin{cases} f_1 = 0 & g_1 = 1 \\ f_2 = 3 & g_2 = 1 \\ f_3 = 13 & g_3 = 1 \\ f_4 = 9 & g_4 = 2 \\ f_5 = 12 & g_5 = 4 \\ f_6 = 13 & g_6 = 1 \end{cases}

数据范围与提示

1N8×105,1A,B1041\leq N\leq 8\times 10^5,1\leq A,B\leq 10^4