题目描述

有一段使用游程编码保存的暗号。暗号由 n 个片段组成，每个片段包含一个大写字母 c 和一个正整数 cnt，表示字母 c 连续出现 cnt 次。

例如，片段 A 3、B 2、C 1 表示原暗号 AAABBC。

完整暗号可能非常长，无法直接展开。现在有 q 次查询，每次给出一个位置 k，请输出原暗号中第 k 个字符。若 k 超过暗号总长度，输出问号 ?。

输入格式

第一行输入一个整数 n。

接下来 n 行，每行输入一个大写字母 c 和一个正整数 cnt。

下一行输入一个整数 q。

接下来 q 行，每行输入一个正整数 k。

输出格式

对每次查询输出一行，包含查询到的字符或 ?。

样例

3
A 3
B 2
C 1
5
1
4
6
7
2

A
B
C
?
A

数据范围与限制

• 1 <= n, q <= 200000；
• 1 <= cnt <= 10^12；
• 暗号总长度不超过 10^18；
• 1 <= k <= 10^18；
• 时间限制：1 秒；
• 空间限制：64 MiB。