长期以来，中央市的供水系统一直运行良好。城市的污水系统呈有根树状结构：中央水库位于根节点，房屋位于叶子节点。水通过沿树边铺设的管道从中央水库流向各房屋。每间房屋都能获得供水。

突然，歹徒占领了一些房屋。作为市长，你对此非常担忧，并希望将歹徒驱逐出去。因此，你想要切断通往被歹徒占领房屋的水流。为此，你可以堵塞污水系统中的一些管道。如果从水库到某间房屋的路径上至少包含一条被堵塞的管道，那么该房屋就无法获得供水。

你非常害怕歹徒，因此决定堵塞最少数量的管道，使其看起来像是一场意外。同时，你关心市民，因此在确定的堵塞管道数量下，你希望最小化那些没有被歹徒占领但同时也无法获得供水的房屋数量。

不幸的是，歹徒可能会在某些房屋中出现或消失。因此，你需要询问科学家在歹徒位置发生每次变动后，所需的最小堵塞管道数量，以及在选择该数量的堵塞管道时，没有被歹徒占领但无法获得供水的房屋的最小数量。

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示代表污水系统的树的顶点数和歹徒位置的变动次数（$2 \le n \le 100\,000$；$1 \le q \le 100\,000$）。

第二行包含污水系统的描述：一个包含 $n - 1$ 个整数的序列 $p_2, p_3, \dots, p_n$，其中 $p_i$ 是顶点 $i$ 的父节点（$1 \le p_i < i$）。中央水库位于顶点 $1$。

接下来的 $q$ 行表示歹徒位置的变动。每次变动有两种类型：“$+ v$”表示歹徒占领了顶点 $v$ 处的房屋；“$- v$”表示歹徒离开了顶点 $v$ 处的房屋。

初始时，所有房屋都没有歹徒。所有的变动均构成合法的序列：如果房屋已被占领，歹徒无法再次占领；如果房屋未被占领，歹徒无法离开。

输出格式

输出应包含 $2q$ 个整数，每行两个：$c_i$ 表示最小堵塞管道数量，$h_i$ 表示在选择 $c_i$ 个堵塞管道的情况下，没有被歹徒占领但无法获得供水的房屋的最小数量。

样例

输入 1

7 6
1 2 1 3 3 3
+ 4
+ 5
+ 6
+ 7
- 6
- 5

输出 1

1 0
2 0
2 1
2 0
2 1
2 0