题目描述

题目译自 XXII Olimpiada Informatyczna — II etap Trzy Wieże

Bajtocja 正饱受通货膨胀困扰，忧心忡忡的 Bajtazar 苦思如何保值资产。不幸的是，他被一则博彩广告吸引，决定投身赌注，押注足球比赛。

即将举行 $n$ 场足球比赛，每场必有胜负（无平局）。单个赌注需预测全部 $n$ 场比赛结果。若正确预测第 $i$ 场比赛，胜方为第一队则获利 $a_i$ 拜托拉，第二队则获利 $b_i$ 拜托拉。错误预测无收益。赌注总收益为所有正确预测的收益之和。

Bajtazar 需从 $z$ 个赌注中选择一个。第 $i$ 个赌注包含预测序列 $p_i$（长度 $n$）和价格 $k_i$ 拜托拉，其中 $p_{i,j}$ 为 $0$ 表示第 $j$ 场比赛预测第一队胜，为 $1$ 表示第二队胜。赌注净收益为总收益减去价格。

Bajtazar 向你提供了所有赌注信息，并提出 $q$ 个问题。第 $i$ 个问题给出一个比赛结果序列 $w_i$，其中 $w_{i,j}$ 为 $0$ 表示第 $j$ 场比赛第一队胜，为 $1$ 表示第二队胜。你的任务是计算在 $w_i$ 结果下，选择任一赌注可获得的最大净收益，以及达成此收益的赌注数量。

输入格式

第一行包含一个整数 $n$ ($1 \leq n \leq 20$)，表示比赛场数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$)，表示第一队胜的收益。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$ ($0 \leq b_i \leq 10^9$)，表示第二队胜的收益。

第四行包含一个整数 $z$ ($1 \leq z \leq 10^6$)，表示赌注数量。

接下来的 $z$ 行，每行描述第 $i$ 个赌注：一个长度 $n$ 的 $01$ 序列 $p_i$（无空格），后跟整数 $k_i$ ($0 \leq k_i \leq 10^9$)。

下一行包含一个整数 $q$ ($1 \leq q \leq 10^6$)，表示问题数量。

接下来的 $q$ 行，每行包含一个长度 $n$ 的 $0$ 或 $1$ 序列 $w_i$（无空格），描述第 $i$ 个问题的比赛结果。

输出格式

输出 $q$ 行，第 $i$ 行包含两个整数：第一个为在 $w_i$ 结果下任一赌注可获得的最大净收益，第二个为达成此收益的赌注数量。

样例

输入：

3
1 3 5
4 2 5
5
000 5
010 2
101 1
000 8
011 3
3
000
011
100

输出：

4 2
5 1
6 1

解释： 给定 $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$。

• 问题 1：$w_1=000$，各赌注净收益：

  • 赌注 1：$a_1 + a_2 + a_3 - k_1 = 4$
  • 赌注 2：$a_1 + a_3 - k_2 = 4$
  • 赌注 3：$a_2 - k_3 = 2$
  • 赌注 4：$a_1 + a_2 + a_3 - k_4 = 1$
  • 赌注 5：$a_1 - k_5 = -2$ 最大净收益 $4$，由赌注 1 和 2 达成，数量为 $2$。

• 问题 2：$w_2=011$，赌注 5 净收益 $a_1 + b_2 + b_3 - k_5 = 5$ 为最大，数量为 $1$。

• 问题 3：$w_3=100$，赌注 3 净收益 $b_1 + a_2 - k_3 = 6$ 为最大，数量为 $1$。

附加样例

• $n=20$, $a_i=1$, $b_i=2$, $z=q=1000$, $k_i=i$，$p_i$ 和 $w_i$ 为从 $00\ldots0$ 开始的字典序序列。
• $n=10$, $a_i=b_i=i$, $z=q=10^6$, $k_i=23$，$p_i$ 和 $w_i$ 为从 $00\ldots0$ 开始的循环字典序序列。
• $n=17$, $a_i=b_i=10^9$, $z=q=10^5$, $k_i=0$，$p_i$ 和 $w_i$ 为从 $11\ldots1$ 开始的递减字典序序列。
• $n=20$, $a_i=b_i=i-1$, $z=q=10^6$, $k_i=10^9-i$，$p_i$ 和 $w_i$ 为从 $00\ldots0$ 开始的字典序序列。

数据范围与提示

详细子任务附加限制及分值如下表所示。

若程序仅正确输出每对结果的第一个值（最大净收益），且第二个值在 $32$ 位有符号整数范围内（int），可获测试 $50\%$ 分数。