Ingrid 是一位大型火车站的站长，她的职责之一是引导火车前往正确的站台。车站有一个入口，并有许多道岔将火车导向其他道岔或站台。

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

站台是铁轨的尽头，你可以假设火车在到达站台后会立即消失。

每天早上，Ingrid 都会查看时刻表并编写道岔切换指令：何时切换哪个道岔。她希望将此过程自动化以节省大量时间。

输入格式

输入文件的第一行包含一个整数 $n$ —— 车站中道岔和站台的总数 ($3 \le n \le 51$)。

接下来的 $n$ 行，第 $i$ 行描述了索引为 $i$ 的道岔或站台。描述以字符 ‘p’（表示站台）或 ‘s’（表示道岔）开头。接下来的数字 $q_i$ 表示该入轨连接的道岔编号，如果连接到车站入口则为 0 ($0 \le q_i < i$)。站台的描述还包含一个唯一的英文小写字母 —— 站台标识符。

火车在两个相连的道岔之间或道岔与站台之间移动恰好需要一分钟。

在早上，每个道岔的初始状态使得火车会驶向连接到该道岔/站台的两个出轨中编号较小的那一个。

输入文件的下一行包含一个整数 $m$ ($1 \le m \le 1000$) —— 时刻表中的火车数量。

接下来的 $m$ 行，每行包含一个整数 $a_i$ ($0 \le a_i \le 10\,000$; $a_i > a_{i-1}$) —— 火车到达车站入口的时间（分钟），以及字母 $p_i$ —— 该火车的目的地站台标识符。

输出格式

第一行输出整数 $c$ —— 道岔切换指令的数量。对于每条指令，输出两个整数 $s_i$ 和 $t_i$ ($1 \le s_i \le n$; $0 \le t_i \le 10^9$) —— 道岔编号和切换时间。假设道岔在 $t_i - 1$ 到 $t_i$ 分钟之间被切换。

按时间非递减的顺序输出指令。指令数量不应超过 $100\,000$。

样例

样例 1

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

样例 2

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

0

样例 3

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

说明

下方是第一个样例的时间轨迹图。