Description

给定一个非负整数 $x$，你要经过若干次以下操作将其变成 $y$，求最小代价：

• 选择一个 $0\leq i\leq k$，花费 $a_i$ 代价将 $x$ 加或减 $2^i$。

注意：你在操作时不需要保证 $x$ 为非负整数。

Input Format

本题有多组测试数据。

第一行，一个正整数 $T$，表示测试数据组数。对于每组测试数据：

• 第一行，三个非负整数 $x,y,k$。
• 第二行，$k+1$ 个正整数 $a_0, \ldots, a_k$。

Output Format

对于每组测试数据，一行，一个非负整数，表示最小代价。

5
2 4 1
2 5
2 5 2
2 5 2
3 9 2
1 2 3
4 23 3
1 5 2 4
1 114 5
1 4 1 9 19 8

4
4
5
11
29

Hint

【样例解释】

对于样例的第二组测试数据：经过以下两次操作即可让 $x$ 变为 $y$，且代价最小：

• 取 $i=2$，令 $x\gets x+2^2$，此时 $x=6$，总代价为 $2$；
• 取 $i=0$，令 $x\gets x-2^0$，此时 $x=5$，总代价为 $4$。

【数据范围】

本题使用捆绑测试。

对于所有数据：$1\leq T\leq2\times10^5$，$0\leq x,y<2^{30}$，$1\leq k\leq 30$，$1\leq a_i\leq10^9$。

【提示】

请使用较快的读入方式。