题目描述

Ingrid is a head of a big railway station and, among other duties, is responsible for routing trains to the right platforms. The station has one entrance, and there are many switches that direct trains to other switches and platforms.

Each switch has one inbound track and two outbound tracks, platforms have one inbound track, and station entrance has one outbound track. Each outbound track is connected to one inbound track and vice versa. Every switch and platform is reachable from station entrance.

Platforms have a rail dead ends and you may assume that trains disappear from the platform immediately after arriving to it.

Each morning Ingrid looks at the timetable and writes switch toggling instruction: when and which switch to toggle. She would like to automate this process to save a lot of time.

输入格式

The first line of the input file contains a single integer $n$ — the total number of switches and platforms on the station $(3 \le n \le 51)$ .

The i-th of the following $n$ lines describes a switch or a platform with an index $i$ . Description starts with a character p for a platform or s for a switch. Next number $q_{i}$ indicates the number of the switch the inbound track is connected to or $0$ if it is connected to station entrance $(0 \le q_{i} < i)$ . Description of the platform also contains a unique lowercase English letter — the platform identifier.

Trains spend exactly one minute to move between two connected switches or a switch and a platform. In the morning, each switch is toggled in a way that a train would pass to the one of the two outbound tracks connected to the switch/platform with the lower number.

Next line of the input file contains a single integer $m (1 \le m \le 1000)$ — the number of trains in timetable.

Each of the following $m$ lines contains integer $a_{i} (0 \le a_{i} \le 10 000$ ; $a_{i} > a_{i−1})$ — the time in minutes when a train arrives to the station entrance, and the letter $p_{i}$ — identifier of the destination platform for this train.

输出格式

In the first line output integer $c$ — the number of commands in the switch toggling instruction. For each command, output two integers $s_{i}$ and $t_{i} (1 \le s_{i} \le n$ ; $0 \le t_{i} \le 10^{9})$ — the number of the switch and the time to toggle it. Assume that the switch is toggled between minutes $t_{i} − 1$ and $t_{i}.$

Output commands in order of non-decreasing time. The number of commands should not exceed $100 000$ .

题目大意

题目描述

英格丽德是一家大型火车站的站长，除其他职责外，还负责将火车开到正确的站台。车站有一个入口，有许多道岔将列车引导至其他道岔和站台。

每个道岔有一条入站轨道和两条出站轨道，站台有一条入站轨道，车站入口有一条出站轨道。每个出站磁道连接到一个入站磁道，反之亦然。每个道岔和站台都可以从车站入口到达。

月台有一个铁路死胡同，你可以假设火车到达月台后立即从月台上消失。

每天早上，英格丽德都会查看时间表，并编写切换指令：何时以及切换哪个开关。她希望将此过程自动化以节省大量时间。

输入格式

输入文件的第一行包含一个整数n—站点上交换机和平台的总数

以下n行的第i行描述了具有索引i的交换机或平台。说明以字符p开头表示平台，以字符s开头表示交换机。下一个数字qi表示入站轨道连接到的道岔的编号，如果连接到车站入口，则表示0(0≤q$i$≤i)平台说明还包含一个唯一的小写英文字母 -- 平台标识符。

列车在两个相连的道岔或道岔与站台之间移动只需一分钟。早上，每一个道岔都会以一种方式进行切换，列车将通过连接到道岔/站台的两条出站轨道中编号较低的一条。 输入文件的下一行包含一个整数m(0≤m≤1000) -- 时刻表上的列车数量。

以下m行中的每一行都包含整数ai (0≤a$i$ ≤10000;a$i$>a$i-1$) -- 列车到达车站入口的时间（以分钟为单位），以及字母pi -- 列车目的站台的标识符。

输出格式

在第一行输出整数c中，开关切换指令中的命令数。对于每个命令，输出两个整数 si和 t$i$ (1≤s$i$ ≤n;0≤ t$i$ ≤10^9) -- 开关的编号和切换开关的时间。假设开关在分钟之间切换 t$i$-1 和 t。

按非递减时间顺序输出命令。命令的数量不应超过100000。

7
s 0
s 1
s 1
p 2 a
p 2 b
p 3 c
p 3 d
5
0 a
1 c
3 b
4 a
5 d

6
1 2
1 4
2 4
2 6
1 6
3 7

5
s 0
p 1 y
s 1
p 3 z
p 3 x
3
7 y
8 y
15 y

0

3
s 0
p 1 y
p 1 z
3
7 y
8 y
10 y

5
1 1
1 2
1 2
1 3
1 200

提示

Below is the time trace for the first example.

Time limit: 2 s, Memory limit: 256 MB.