Description

学校举办了一场长期训练赛，共产生了 (n) 条成绩记录。

每条记录包含：

• 一名学生的名字；
• 该学生本次训练获得的分数。

同一名学生可能参加多次，因此可能有多条成绩记录。

现在有 q 次查询。每次查询给出一个学生名字 name 和两个整数 (L,R)，你需要找出该学生所有满足

L <= score <= R 的成绩。

对于每次查询，请输出：

1. 满足条件的成绩数量；
2. 满足条件的最小成绩；
3. 满足条件的最大成绩。 如果该学生不存在，或者没有成绩落在区间 ([L,R]) 中，则输出：0 -1 -1

Format

Input

第一行输入两个整数：n、q分别表示成绩记录数量和查询数量。 接下来 n 行，每行输入： name score

其中：

• name 是只包含小写英文字母的字符串；
• score 是该次训练的分数。 接下来 q 行，每行输入： name L R

表示一次查询。

Output

对于每次查询，输出一行三个整数： cnt min_score max_score

其中：

• cnt 表示落在 [L,R] 中的成绩数量；
• min_score 表示其中最小成绩；
• max_score 表示其中最大成绩。 如果没有符合条件的成绩，输出： 0 -1 -1

Samples

8 5
alice 80
bob 50
alice 95
cindy 70
bob 90
alice 80
david 60
bob 75
alice 80 90
bob 60 100
cindy 1 69
eve 0 100
alice 0 100

2 80 80
2 75 90
0 -1 -1
0 -1 -1
3 80 95

Limitation

1s, 1024KiB for each test case.