这是一个交互式问题。

交互式证明的概念由 Goldwasser、Micali 和 Rackoff 在 1985 年引入计算复杂性理论。该系统涉及两方：证明者（Prover）和验证者（Verifier），它们都能访问一个公共字 $x$。验证者想要确定 $x$ 是否属于某个集合 $L$，而证明者想要说服验证者确实如此。验证者是一个必须在多项式时间内运行的随机化程序，而证明者的时间和内存不受限制。证明者和验证者通过互相发送消息进行交互，最后由验证者决定接受或拒绝。

验证者的目标是仅在 $x$ 确实属于 $L$ 时才接受。证明者的目标是强制验证者接受。该证明系统通常必须满足以下条件：如果 $x \in L$，证明者可以以高概率使验证者接受；如果 $x \notin L$，无论证明者如何努力，验证者接受的概率都可忽略不计。

在本题中，我们研究 #SAT 问题的一种重要交互式证明协议的性质。

令 $\varphi$ 为一个包含 $n$ 个布尔变量 $x_1, \dots, x_n$ 的布尔公式。允许的操作包括逻辑或（记作 |）、逻辑与（记作 &）和逻辑非（记作 !）。操作符按优先级从低到高排列，括号可用于改变运算优先级。例如，考虑公式 $\varphi(x_1, x_2) = x_1 \& x_2 | !x_1 \& !x_2$。

我们用 $0$ 表示假（false），$1$ 表示真（true）。如果布尔向量 $(a_1, \dots, a_n)$ 在设置 $x_i = a_i$ 后使得 $\varphi$ 的值为 $1$，则称该向量满足 $\varphi$。例如，向量 $(0, 0)$ 和 $(1, 1)$ 满足上述公式 $\varphi$，而 $(1, 0)$ 和 $(0, 1)$ 不满足。满足条件的向量个数称为 $\varphi$ 的权重，记作 $w(\varphi)$，因此 $w(\varphi) = 2$。

我们现在考虑证明 $w(\varphi) = k$ 的正确交互协议。从形式上定义语言 $\#SAT = \{(\varphi, k) \mid w(\varphi) = k\}$，并证明 $(\varphi, k) \in \#SAT$。

首先，证明者和验证者选择一个足够大的素数 $p$。所有后续计算均在模 $p$ 意义下进行。对于布尔公式 $\varphi$，其算术化 $A(\varphi)$ 递归定义如下：

• 如果 $y$ 是变量，则 $A(y) = y$。
• 如果 $\varepsilon$ 是公式且 $\varphi = !\varepsilon$，则 $A(\varphi) = 1 - A(\varepsilon)$。
• 如果 $\vartheta$ 和 $\varepsilon$ 是公式且 $\varphi = \vartheta \& \varepsilon$，则 $A(\varphi) = A(\vartheta) \cdot A(\varepsilon)$。
• 如果 $\vartheta$ 和 $\varepsilon$ 是公式且 $\varphi = \vartheta | \varepsilon$，则 $A(\varphi) = 1 - (1 - A(\vartheta)) \cdot (1 - A(\varepsilon))$。

例如，$A(\varphi) = 1 - (1 - x_1 x_2)(1 - (1 - x_1)(1 - x_2))$。 容易看出，如果 $(a_1, \dots, a_n)$ 是 $\varphi$ 的一个满足赋值，则 $A(\varphi)(a_1, \dots, a_n) = 1$，否则 $A(\varphi)(a_1, \dots, a_n) = 0$。因此： $$w(\varphi) = \sum_{x_1=0}^{1} \dots \sum_{x_n=0}^{1} A(\varphi)(x_1, \dots, x_n)$$

证明 $w(\varphi) = k$ 的过程分为 $n$ 个步骤。 在第一步中，考虑函数： $$P_1(x_1) = \sum_{x_2=0}^{1} \dots \sum_{x_n=0}^{1} A(\varphi)(x_1, \dots, x_n)$$ 该函数是关于 $x_1$ 的多项式：$P_1(x_1) = c_{1, d_1} x_1^{d_1} + c_{1, d_1-1} x_1^{d_1-1} + \dots + c_{1, 1} x_1 + c_{1, 0}$。显然，$P_1(0) + P_1(1) = k$。证明者通过发送 $d_1$ 以及系数 $c_{1, d_1}, \dots, c_{1, 0}$ 将 $P_1$ 发送给验证者。验证者检查 $P_1(0) + P_1(1) = k$，并随机选择一个 $0$ 到 $p-1$ 之间的整数 $r_1$ 发送给证明者。

现在开始第二步。考虑函数： $$P_2(x_2) = \sum_{x_3=0}^{1} \dots \sum_{x_n=0}^{1} A(\varphi)(r_1, x_2, \dots, x_n)$$ 注意 $x_1$ 已被替换为参数 $r_1$。该函数又是关于 $x_2$ 的多项式，因此证明者将此多项式发送给验证者。验证者检查 $P_2(0) + P_2(1) = P_1(r_1)$，并随机选择一个 $0$ 到 $p-1$ 之间的整数 $r_2$ 发送给证明者。

一般地，对于 $i$ 从 $2$ 到 $n-1$ 的第 $i$ 步，考虑函数： $$P_i(x_i) = \sum_{x_{i+1}=0}^{1} \dots \sum_{x_n=0}^{1} A(\varphi)(r_1, \dots, r_{i-1}, x_i, x_{i+1}, \dots, x_n)$$ 该函数是关于 $x_i$ 的多项式，证明者将其发送给验证者。验证者检查 $P_i(0) + P_i(1) = P_{i-1}(r_{i-1})$，随机选择 $r_i \in {0, \dots, p-1}$ 并发送给证明者。

最后一步略有不同。函数： $$P_n(x_n) = A(\varphi)(r_1, \dots, r_{n-1}, x_n)$$ 被发送给验证者。验证者检查 $P_n(0) + P_n(1) = P_{n-1}(r_{n-1})$，选择随机数 $r_n \in {0, \dots, p-1}$ 并检查 $A(\varphi)(r_1, \dots, r_n) = P_n(r_n)$ 是否成立。

请再次注意，所有计算均在模 $p$ 意义下进行。

如果验证者的所有测试均成功，则证明被接受。如果至少有一个测试失败，则证明被拒绝。可以证明，如果 $A(\varphi)$ 的次数为 $d$，则证明被接受但 $w(\varphi) \neq k$ 的概率最多为 $1 - (1 - d/p)^n$，因此通过选择足够大的 $p$，该值可以变得微不足道。

该证明协议的核心思想是，通过在 $\varphi$ 的算术化中代入模 $p$ 的随机整数，而不是仅仅代入 $0$ 和 $1$，来降低证明者强制验证者接受错误陈述的概率。如果验证者只选择 $0$ 或 $1$ 作为 $r_i$，证明者可以轻易欺骗验证者，即使在 $w(\varphi) \neq k$ 时也能以高概率强制其接受。这正是你在本题中需要做的。

你的程序将扮演证明者，试图强制评审团的验证者接受错误的陈述 $w(\varphi) = k$。验证者将遵循上述协议，但有一个例外：它将选择 $r_i \in \{0, 1\}$。我们将使用 $p = 239$。

交互

你的程序在每次运行中必须进行多次证明。如果你的程序成功在至少 $1/2$ 的案例中强制验证者接受，则会被接受。

每个证明开始时，你的程序从标准输入读取 $n$（$\varphi$ 中的变量个数，$2 \le n \le 7$）。如果 $n=0$，则表示测试运行结束，你的程序必须终止。如果 $n > 0$，则证明开始。

下一行包含 $\varphi$ 的公式。公式使用以下字符：&、|、!、(、) 以及 x 后面紧跟其从 $1$ 到 $n$ 的索引。空格可以自由分隔公式部分，但 x 与其索引之间不会被分隔。公式长度最多为 $100$ 个字符。

下一行包含 $k$，你的程序必须尝试证明 $w(\varphi) = k$，即使事实并非如此（$0 \le k \le 2^n$）。

读取 $n$、$\varphi$ 和 $k$ 后，你的程序必须通过向验证者发送 $P_1$ 来开始协议。 它必须向标准输出打印次数 $d_1$，随后打印 $c_{1, d_1}, \dots, c_{1, 0}$。数字之间用空格或换行符分隔，在最后一个数字后打印换行符并刷新标准输出。

所有多项式的次数不得超过 $20$。所有系数必须在 $0$ 到 $238$ 之间。对于本题，常数零多项式的次数为 $0$。

验证者检查条件 $P_1(0) + P_1(1) = k$，并打印 $r_1$，你必须从标准输入读取它，$r_1$ 将为 $0$ 或 $1$。 之后，你必须以相同的格式发送 $P_2$，读取 $r_2$，依此类推。 发送 $P_n$ 后，你无需再为该测试用例等待任何输入，并继续处理下一个测试用例。

即使验证者执行的测试之一失败，验证者也不会终止协议。因此，即使你的程序发现无法欺骗验证者，也必须运行协议的所有 $n$ 轮。但是，不允许打印不正确的多项式（次数错误或系数错误）。

对于每个测试，你的程序将被要求进行至少 $64$ 次且最多 $128$ 次证明，如果在此测试用例中至少在 $1/2$ 的案例中欺骗了验证者，则会被接受。唯一的例外是样例测试，其中只有 $1$ 次运行，只要程序遵循交互协议，无论如何都会被接受。

保证验证者的回答不依赖于证明者发送的多项式。

样例

输入 1

2
x1 & x2 | !x1 & !x2
3
0
0

输出 1

1
1 1
1
238 1

在上面的例子中，协议进行如下。正确的 $P_1(x_1)$ 是 $P_1(x_1) = 1$。然而，证明者不能将其发送给验证者，因为 $P_1(0) + P_1(1) = 2$，但它需要证明 $w(\varphi) = 3$（当然这是错误的）。因此，证明者发送了不正确的多项式 $P_1(x_1) = x_1 + 1$，它满足 $P_1(0) + P_1(1) = 3$。验证者检查这一点并选择 $r_1 = 0$。

现在证明者发送 $P_2(x_2) = -x_2 + 1$，或者由于所有计算均在模 $239$ 下进行，$P_2(x_2) = 238x_2 + 1$。验证者检查 $P_2(0) + P_2(1) = P_1(0) = 1$。现在它选择 $r_2$ 为 $0$ 或 $1$，并检查 $A_\varphi(0, r_2) = P_2(r_2)$ 是否成立。幸运的是，对于证明者来说，$r_2 = 0$ 和 $r_2 = 1$ 时均成立，因此无论验证者最后如何选择，它都会接受。目标达成，验证者被欺骗了。

标准输入的最后一个 $0$ 表示测试运行结束，因此证明者终止。