Bajtocji 正经历严重的通货膨胀，忧心忡忡的 Bajtazar 正在考虑如何投资他的钱。不幸的是，他刚刚看了一则博彩广告，并决定投资这类博彩。

不久后将举行 $n$ 场足球比赛，每场比赛都会以其中一方的胜利告终（没有平局）。单次投注包括对 $n$ 场比赛的预期结果进行预测。如果正确预测了第 $i$ 场比赛的结果，若第一支队伍获胜，则获得 $a_i$ Bajtalar 的利润；若第二支队伍获胜，则获得 $b_i$ Bajtalar 的利润。如果对比赛结果的预测错误，则不会获得任何利润。投注的总利润是与所有预测结果相关的利润之和。

Bajtazar 想要购买其中一个投注。第 $i$ 个投注有一个固定的长度为 $n$ 的序列 $p_i$，描述了对每场比赛结果的预期，以及一个价格 $k_i$ Bajtalar；序列 $p_i$ 的第 $j$ 个元素（记为 $p_{i,j}$）为 $0$ 表示预测第 $j$ 场比赛第一支队伍获胜，为 $1$ 则表示第二支队伍获胜。投注的利润定义为总奖金减去其价格。

Bajtazar 已经向你提供了所有可用投注的信息。现在他请求你回答 $q$ 个令他困扰的问题。在第 $i$ 个问题中，你会得到一个序列 $w_i$，描述了 Bajtazar 考虑的 $n$ 场比赛的结果；序列 $w_i$ 的第 $j$ 个元素（记为 $w_{i,j}$）为 $0$ 表示第 $j$ 场比赛第一支队伍获胜，为 $1$ 则表示第二支队伍获胜。你的任务是确定在比赛结果由序列 $w_i$ 描述的情况下，使用所给投注中的某一个所能获得的最大利润。此外，你还应确定达到该最大利润的投注数量。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 20$)，表示比赛场数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)。 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($0 \le b_i \le 10^9$)。 第四行包含一个整数 $z$ ($1 \le z \le 10^6$)，表示投注数量。 接下来的 $z$ 行中，第 $i$ 行描述第 $i$ 个投注。该描述由一个序列 $p_i$（一个长度为 $n$ 的由 $0$ 或 $1$ 组成的字符串，中间无空格）和一个整数 $k_i$ ($0 \le k_i \le 10^9$) 组成。 下一行包含一个整数 $q$ ($1 \le q \le 10^6$)，表示询问次数。 接下来的 $q$ 行中，第 $i$ 行描述第 $i$ 个问题，即一个序列 $w_i$（一个长度为 $n$ 的由 $0$ 或 $1$ 组成的字符串，中间无空格）。

输出格式

输出应包含 $q$ 行。第 $i$ 行应包含两个整数，表示第 $i$ 个问题的答案。第一个整数应等于在比赛结果由序列 $w_i$ 描述时，使用所给投注中的某一个所能获得的最大利润。第二个整数应等于达到该最大利润的投注数量。

说明

示例解释：已知 $a_1 = 1, a_2 = 3, a_3 = 5, b_1 = 4, b_2 = 2, b_3 = 5$。各投注的预期结果序列为： $p_1 = 000, p_2 = 010, p_3 = 101, p_4 = 000, p_5 = 011$， 其价格分别为 $k_1 = 5, k_2 = 2, k_3 = 1, k_4 = 8, k_5 = 3$。在第一个问题中，描述比赛结果的序列为 $w_1 = 000$。在此问题中，各投注可获得的利润如下： 第一个投注：$a_1 + a_2 + a_3 - k_1 = 4$ 第二个投注：$a_1 + a_3 - k_2 = 4$ 第三个投注：$a_2 - k_3 = 2$ 第四个投注：$a_1 + a_2 + a_3 - k_4 = 1$ * 第五个投注：$a_1 - k_5 = -2$

因此，最大利润 (4) 可以通过第一个或第二个投注获得。 第二个问题中描述比赛结果的序列为 $w_2 = 011$。在这种情况下，只有第 5 个投注能获得最大利润，即 $a_1 + b_2 + b_3 - k_5 = 5$。 第三个问题中描述比赛结果的序列为 $w_3 = 100$。在这种情况下，只有第 3 个投注能获得最大利润，即 $b_1 + a_2 - k_3 = 6$。

子任务

如果你的程序仅正确输出了结果对中的第一个值，而第二个值在 32 位有符号整数（int）范围内，则该测试点可获得 50% 的分数。