题目描述

你有一个长度为 $n$ 的序列 $x$ 和一个数 $a=p$。

序列 $x$ 的第 $i$ 个数具有一个花费序列 $w_{i,1},w_{i,2},\dots,w_{i,k}$。

你可以将 $a$ 变换成 $i$（$1\le i\le n$，$a$ 可以等于 $i$），当前是你的第 $j$ 次操作，则花费为 $w_{i,j} + 2\times(L-(x_a \mathbin{\&} x_i))$，其中 $\mathbin{\&}$ 是按位与，即 C++ 中的 &。

$L$ 是序列 $x$ 中所有数的最大值，即 $\max\limits_{1\le i\le n}x_i$。

你需要对所有 $1\le i\le n$ 求出在第 $k$ 步操作结束时将 $a$ 变成 $i$ 的最小花费。询问之间互相独立，每次询问不会影响其他次询问的答案。

输入格式

由于直接输入数据量过大，请使用以下方式读入数据：

第一行输入 $5$ 个整数 $n,p,k,c,seed$，其中 $c,seed$ 的意义在下文给出。

第二行输入 $c$ 个整数 $y_0,y_1,\dots,y_{c-1}$，其中 $y_i$ 的意义在下文给出。

读入后使用以下函数获得输入：

int c, y[65536]; unsigned long long seed;
int get_rand(int mod)
{
    seed ^= seed << 14;
    seed ^= seed >> 7;
    seed ^= seed << 19;
    seed ^= seed << 23;
    return seed % mod;
}
void get_input()
{
    for (int i = 1; i <= n; i++) x[i] = y[get_rand(c)];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= k; j++) w[i][j] = get_rand(1000000);
}

你需要调用的是 get_input 函数。

注意：此输入方式仅为减小输入量，标准解法并不依赖此输入方式。

输出格式

共一行输出 $n$ 个正整数，第 $i$ 个表示将 $a$ 变成 $i$ 的最小花费。

3 1 2 3 1025032617
1 2 3

730965 742898 1038257

提示

【样例解释】

$x = \{3, 1, 3\},w_1 = \{834731, 259456\},w_2 = \{471501, 271389\} ,w_3 = \{902700, 566748\},a=1,L=3$。

将 $a$ 变为 $2$ 的最优操作是第一次 $a\to 2$ 花费 $w_{2,1} + 2\times(3-3\& 1)= 471505$，第二次 $a\to 2$ 花费 $w_{2,2} + 2\times(3-1\& 1)= 271393$，总花费为 $742898$。

【数据范围】

• Subtask #1（$15\text{ pts}$）：$k = 1$，$x_i < 2^{12}$。
• Subtask #2（$25\text{ pts}$）：$c\le 10^3$（最多只有 $10^3$ 种不同的 $x_i$），$x_i < 2^{12}$。
• Subtask #3（$25\text{ pts}$）：$\max\{\text{popcount}(x_i)\} \le 5$。其中 $\text{popcount}(x_i)$ 表示 $x_i$ 在二进制下 $1$ 的个数。
• Subtask #4（$35\text{ pts}$）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$1 \le k \le 10$，$0\le x_i<2^{16}$，$1 \le p \le n$，$0\le w_{i,j}<10^6$。$1\le seed \le 2\times 10^9$，$1\le c \le 2^{16}$，$0 \le y_i < 2^{16}$。