We are given a graph. Initially graph is empty. There are three type of operation we can perform on graph.

1. insertType1 value
2. insertType2 value parentNodeId
3. query nodeId maxDistance

Both insertType1 and insertType2 adds node to the graph. Newly added node will have new NodeId which will be auto incremented (starting from 0).

For example, 
first node inserted will have nodeId = 0
second node inserted will have nodeId = 1
third node inserted will have nodeId = 2
and so on.

insertType2 takes parent node id as second argument. So there will be directed edge from parent node to newly generated node.

These insert operations will form graph which contains multiple directed tree graph.

insertType1 and insertType2 operator should print nodeId. query operator should print sum of values of all nodes which are descendent of node with id equals to nodeId and descendents should not be far more than maxDistance.

Sample Input:

insertType1 11
insertType2 12 0
insertType2 13 0
query 0 0
query 0 1
insertType2 14 1
insertType2 15 2
insertType2 16 3
insertType2 17 3
insertType2 18 3
query 3 1
query 0 2
query 1 1

Sample Output:

0
1
2
11
36
3
4
5
6
7
65
65
26

example tree:

          11 
         /  \
        12   13
       /      \
      14       15
    /  |  \ 
  16  17  18

Brute for approach for query operation will require breadth first search for every query.

Any Idea how to answer queries efficiently? Looking for an online algorithm.