#4867. [Ynoi2017]舌尖上的由乃

题目描述

由乃为了吃到最传统最纯净的美食，决定亲自开垦一片菜园。现有一片空地，由乃已经规划n个地点准备种上蔬菜

。最新鲜的蔬菜需有最甘甜井水的灌溉，因此由乃将要打出两口井，分别记为井A、井B。现在问题来了，由乃可是

一周目的神，为何要打井？是谁想出来的这些题面？由乃不善于搞事情，于是提出以下几个方法，再根据这些方法

找出题人。方法如下：

1. 做完这个出题人出的所有题

2. 做完所有数据结构题

3. 出一道奇怪的数据结构题，而且卡常卡死所有做题的

至于为什么这样能找到出题人呢。。。我也不信她能找到我。。。（能找到岂不是更好？）

因为由乃是神，所有她有很多秒时间，她终于做完了世界上左右的数据结构题

于是该她出题了，她左思右想，出了一个简单数据结构题：

给你一个n个点的有根树，1为根，带边权，有m次操作。

1、求x的子树中第k小的深度的值，如果子树中没有k个点则输出-1；

2、将x与x父亲的边权加上k。

保证每次操作2的k以及原树的边权小于等于一个数len。

如果操作2中x为1，那么视为将x的基础深度加上了k。

由乃能不能找到出题人呢？

输入格式

第一行三个数n,m,len。

之后n - 1行每行两个数表示2~n每个点的父亲编号，以及他们到父亲的边权。。。

之后m行每行三个数 opt,x,k，opt表示操作种类，x,k意义如题所述。

n,m <= 100000

输出格式

对于每个操作1，输出一个数表示答案

样例

样例输入

3 5 3  

1 3  

2 3  

1 1 3  

2 3 3  

1 1 3  

2 1 2  

1 1 3

样例输出

6  

9  

11

数据范围与提示

对于所有数据，n,m <= 100000，len <= 10

因为出题人是sb，len <= 10，其实没有这个限制也可以解决这个问题