题目描述

33DAI 最近在玩泰拉瑞亚，他收集到了 $n$ 把武器。每个武器有两个属性：类型与攻击力。

• 类型最多有三种：近战武器、射手武器与法师武器，分别用 A, B, C 表示。
• 攻击力比较简单，就是一个正整数。

作为一道练习备赛题，33DAI 想要你有序地帮他展示这些武器，以及应对有可能的查询。具体来说你需要做两件比较模版的事：

• 请先把这 $n$ 把武器进行排序：
  • 近战武器排在前面，射手武器放在中间，法师武器排在后面。
  • 近战武器按照攻击力从小到大排序。
  • 射手武器按照攻击力从大到小排序。
  • 法师武器按照攻击力从小到大排序。
• 在排序完成后，你要进行 $Q$ 次查询，第 $i$ 次查询用 $type_i, x_i$ 描述。
  • $type_i$ 为需要查询的武器类型，$x_i$ 为攻击力的要求。
  • 当 $x_i\ge 0$ 时，请你找到第一个攻击力大于等于 $x_i$ 的 $type_i$ 类型的武器。
  • 当 $x_i\lt 0$ 时，请你找到第一个攻击力小于等于 $-x_i$ 的 $type_i$ 类型的武器。
  • 你需要输出找到的武器排在 $1\sim n$ 的第几个，如果找不到，输出 $0$。

输入格式

第一行为正整数 $n$。

接下来 $n$ 行，每行为空格隔开的一个字符和一个正整数，即每把武器的类型与攻击力。

接下一行为一个正整数 $Q$。

接下来 $Q$ 行，第 $i$ 行为第 $i$ 次查询的内容 $type_i,x_i$

输出格式

输出 $Q$ 行，第 $i$ 行为第 $i$ 次查询的答案。

10 
B 45
C 6
A 10
C 8
B 30
A 15
C 1
B 35
A 7
A 79
5
B 35
B -35
C 7
A -15
A 15

5
6
10
1
3

样例 1 提示

排完序后的内容如下，三行内容分别为类型、攻击力、排完序之后的位置：

A  A  A  A  B  B  B  C  C  C
7  10 15 79 45 35 30 1  6  8  
1  2  3  4  5  6  7  8  9  10

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,Q \le 10^5$，保证武器类型和查询类型都是 A, B, C 中的一种，武器攻击率为不超过 $10^9$ 的正整数，$1\le |x_i| \le 10^9$。

• 子任务 1（30 分）：保证武器类型和查询类型只有 A。
• 子任务 2（30 分）：保证 $x_i\ge 1$。
• 子任务 3（40 分）：没有特殊情况。