Description

给定函数 $f(x) = a\cdot x$，$g(x) = x + b$。

将这两个函数任意嵌套 $m$ 次将得到 $2^m$ 种不同的函数。

如 $m = 3$ 时将得到函数：

• $h_1 = f \cdot f \cdot f$
• $h_2 = f \cdot f \cdot g$
• $h_3 = f \cdot g \cdot f$
• $h_4 = f \cdot g \cdot g$
• $h_5 = g \cdot f \cdot f$
• $h_6 = g \cdot f \cdot g$
• $h_7 = g \cdot g \cdot f$
• $h_8 = g \cdot g \cdot g$

现在给出一个数字 $x$，lyc 想知道随机从这 $2^m$ 个函数中等概率抽取一个函数 $h$，$\mathbb{E}(h(x))$ 是多少。

lyc 不满足只求出一个整数的答案，他有 $n$ 个数字 $x_1, x_2,\cdots,x_n$，对每个数字他想知道从 $2^m$ 个函数中抽取一个函数得到 $h(x_i)$ 的期望大小是多少。

Input

第一行包含两个实数 $a,b\ (0 < a,b \leq 10^9)$，含义见题面。

第二行包含两个整数 $n,m\ (0\leq n,m \leq 10^5)$，含义见题面。

第三行包含 $n$ 个整数 $x_1,x_2,\cdots,x_n\ (0\leq x_i\leq 10^9)$，含义见题面。

保证 $a^m \leq 10^{20}$。

Output

输出一行 $n$ 个实数，第 $i$ 个数表示 $\mathbb{E}(h(x_i))$。

你的输出结果与标准答案的相对误差或绝对误差应小于 $10^{-6}$。即如果标准答案是 $b$，那你的输入答案 $a$ 应该满足条件 $\frac{\lvert b-a \rvert }{\max(1,b)}\leq {10^{-6}}$。

Samples

2 1
2 2
1 2

3.500000000 5.750000000

Note

第一个样例中函数有 $4$ 个函数 $h_1(x) = f(f(x)) = 4x$，$h_2(x)=f(g(x))=2x + 2$，$h_3(x)=g(f(x))=2x + 1$，$h_4(x)=g(g(x))=x+2$。

第一个样例中第二个数字 $2$ 得到的 $h(x)$ 分别为 $8,6,5,4$，大小期望为 $5.75$。

Resources

电子科技大学第十五届 ACM 趣味程序设计竞赛