Tree Queries with Parent Updates

You are given a tree with n nodes. The tree nodes are numbered from 1 to n. Each node x has a parent fa(x) and an edge weight from x to fa(x). The root rt is defined by the property fa(rt)=rt and its depth is 0. For any other node x, its depth is defined as:

[ dep(x)=\sum_{y \in path(x,rt)} w(y, fa(y)) ]

You are also given a sequence a of length n, where each element of a is a node in the tree.

There are m operations. Each operation is one of the following types:

• 1 l r: For every index i with l \le i \le r, update a_i to fa(a_i).
• 2 l r: Query the minimum depth among all nodes a_i with l \le i \le r.

Precompute the depth for each node based on the given tree, then simulate the operations on the sequence a and answer the queries.

inputFormat

The input begins with two integers n and m (the number of nodes and the number of operations).

Then follow n lines, each containing two integers fa_i and w_i. For the root node, it is guaranteed that fa(rt)=rt and w(rt)=0. For any other node i, fa_i denotes its parent's index and w_i the weight of the edge from i to fa_i.

The next line contains n integers representing the sequence a.

After that, there are m lines. Each line represents an operation in one of the following formats:

• 1 l r
• 2 l r

outputFormat

For each operation of type 2 l r, output the result of the query – the minimum depth among all nodes a_i for indices l \le i \le r. Each result should be printed on a new line.

sample

3 3
1 0
1 1
1 2
1 2 3
2 1 3
1 2 3
2 1 3

0
0