6196. 「美团 CodeM 复赛」通信

题目描述

有 $N$ 个信号塔，第 $i$ 个塔的位置是 $i$，信号强度 $X_i$（$X_i$ 保证互不相同）。

有 $N$ 个人，第 $i$ 个人的位置是 $i$，一个人往左走一格要 $A$ 秒，往右走一格要 $B$ 秒。

这些人之间要传递信息，具体地，如果 $i$ 有信息，那么 $i$ 会依次做以下操作：

1. 选择一个 $j$ 满足 $1 \leq j \leq i$，并找到一个 $k$ 使得 $j \leq k \leq i$ 并且 $X_k$ 最大来保证通信。
2. $i, j$ 同时向 $k$ 移动，先到的会等另一个人直到两个人都到达。
3. 等到 $i,j$ 都到达 $k$ 时，信息的传递瞬间完成，并且 $i,j$ 瞬间回到原来的位置。
4. 之后 $i$ 会失去信息，$j$ 会获得信息。

请对每个 $i$ 计算，如果初始 $i$ 有信息，那么最少多少时间以后信息可以传递到 $1$，并输出最少时间的方案数，方案数对 $2^{32}$ 取模。

一个方案可以被描述成 $P_1=i, P_2, P_3, \dots, P_t=1$，表示信息的传递是

$$P_1 \rightarrow P_2 \rightarrow P_3 \rightarrow \dots \rightarrow P_t. $$

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

特殊地，对于 $1$，我们认为最少时间是 $0$，方案数为 $1$。

---

输入格式

第一行三个数 $N, A, B$。
接下来一行 $N$ 个数表示 $X_i$。

---

输出格式

令 $f_i$ 表示从 $i$ 出发的最小时间，$g_i$ 表示最小时间的方案数。
输出两行：
第一行 $f_1 \oplus f_2 \oplus \dots \oplus f_n$（$f_n$ 为 long long 计算异或）。
第二行 $g_1 \oplus g_2 \oplus \dots \oplus g_n$（$g_n$ 为 unsigned int 计算异或）。

---

样例

输入

6 13 3
2 4 3 5 6 1

输出

6
6

数据对应：

$$\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} $$

---

数据范围与提示

$1 \le N \le 10^6$，$1 \le A,B \le 10^9$，$1 \le X_i \le 10^9$。