U223665 环线

恭喜你成为一条地铁环线上的乘务员，你的任务是给乘客指路。

你所在的环线上共有 $n$ 座车站。现在有 $m$ 名乘客向你问路，第 $i$ 名乘客想要从 $s_i$ 站去 $d_i$ 站，你需要对每名乘客指出它们乘坐的方向和途径的重点车站。 如图，由于我国大部分城市地铁靠右行驶，因此，定义**内环指顺时针方向，外环指逆时针方向。**  由于环线的两个方向都可以到达对应站点，且环线方向指示不明，因此，你需要给乘客指出 $q$ 座车站，以方便乘客辨认方向。规则：(建议结合样例去理解) (1)站点必须在乘客乘坐区间内，并且按乘客到达顺序给出。 (2)优先选择级别较高的站点。 (3)如果大于等于当前级别的车站小于 $q$ 个，则下降级别以输出更多站点。 (4)如果大于等于当前级别的站点刚刚大于等于 $q$ 个，则输出最靠近起点的 $q$ 个。

第一行三个整数 $n$,$m$,$q$，表示车站的数量，询问的数量，需要输出的站数。 接下来的 $n$ 行，每行一个整数 $a_i$ 与一个字符串 $b_i$，表示第 $i$ 座车站的等级与站名。 接下来的 $m$ 行，每行两个字符串 $s_i$ 与 $d_i$，表示每名乘客的出发车站与到达车站。

输出共 $m$ 行。 每行第一个整数 0/1，表示乘坐方向是内环/外环。（如果内环外环乘坐站数相等，则乘坐内环） 每行第二个整数表示乘坐站数。 接下来输出 $q$ 个字符串，表示途经的重要站点。

 **样例说明** 这是北京地铁 2 号线，有 18 站。有 5 组询问，每次询问要求输出 5 个车站。 第一组询问从宣武门站去东直门站，乘坐外环经过八站。级别 $\geq 5$ 的只有东直门站，级别 $\geq 4$ 的有前门、北京站、东直门。级别 $\geq 3$ 的有前门、崇文门、北京站、建国门、朝阳门、东直门，满足条件，按顺序输出前五个。 第二组询问从东四十条去阜成门，乘坐外环经过八站。级别 $\geq 4$ 的有东直门、西直门。级别 $\geq 3$ 的有东直门、雍和宫、西直门、车公庄，仍不符合要求。级别 $\geq 2$ 的除起点终点与安定门都符合条件，按顺序输出。 第三组询问中，内环与外环都是 9 站，输出内环。 ~~其余部分不予解释。~~ ------------ **数据范围** 存在 $10\%$ 的数据，$q=1$ ------------ 对于前 $30\%$ 的数据： (1)$1 \leq n \leq 60$,$1 \leq m \leq 100$,$1 \leq q\leq 15$ (2)保证地铁线路真实存在，且比较接近实际。 ------------ 对于 $100\%$ 的数据： (1)$1 \leq n \leq 10^5$,$1 \leq m \leq 10^5$,$1 \leq q\leq 150$ (2)车站等级为 $1 \leq a_i \leq 30$ 的整数。 (3)站名长度 $\leq 30$,只包含大小写字母，不包含空格。任意两个站名不重复。 (4)车站按内环方向给出。 (5)保证在乘坐范围内有超过 $q$ 座车站。 (6)保证每次询问起点与终点不一致。 数据正在设置中，仅上传样例一组数据，通过不代表算法正确。