题目描述

在寒假初始，小 $C$ 就已经把寒假作业写完了。于是他准备专心出去旅游。

小 $C$ 来到 $P$ 市旅游， $P$ 市一共有 $N$ 个旅游景点，每个旅游景点编号为 $1-N$号。 $P$ 市的旅游快速巴士能带你快速的穿梭在各个旅游景点之间。为了方便大家轻松地进行旅游，对于每一个景点，旅游规划局只设计了一辆快速巴士，每辆巴士需要花费 $X_i$ 元并且只能固定前往 $Y_i$ 号旅游景点。

因为 $P$ 市真的太好玩了，就算有的景点重复玩了几次也不会觉得无聊。小 $C$ 决定从$A$号景点开始，搭乘 $B$ 次的旅游快速巴士后结束旅程，每一次在一个景区 $i$ 下车后只能通过搭乘由 $i$ 出发的旅游快速巴士的方式达到其他景点。

由于小 $C$ 不太会做旅游攻略，他想问问你，搭乘 $B$ 趟旅游快速巴士需要花费多少元钱，路途参观过几个不同的景点（算上做大巴所在的初始景点），以及最后到达哪一个旅游景点。

输入格式

第$1$行输入三个整数 $N$ 、$A$、 $T$，以空格间隔。

接下来$N$行，每行有两个整数 $X_i$ 和 $Y_i$ ，以空格间隔。

接下来$T$行，每行有一个整数 $B$

输出格式

输出 $T$ 行。

每行输出三个整数，以一个空格间隔，对应询问的$B$，输出从 $A$ 号景点出发经过 $B$ 次后的巴士花费、可以参观的不同的景点数量、最后一站到达的景点编号。

样例数据

输入样例#1

5 1 3
1 2
2 3
3 4
4 5
5 1
5
3
10

输出样例#1

15 5 1
6 4 4
30 5 1

输入样例#2

5 1 2
5 3
7 4
2 5
1 1
9 2
1
100

输出样例#2

5 2 3
480 5 1

数据范围

对30%的数据，$1 \le N，T, B \le 100, 1 \le T \le 10$；

对100%的数据，$1 \le N、T 、X_i、B \le 10000， 1 \le A、Y_i \le N$。