Whitewater rafting and canoeing are fun activities, especially on hot summer days. Splashing water cools you off in the rapids, then the current carries you to another part of the river. There are many different rivers to choose from, each with its own set of rapids. Which river is the most fun, and which section of that river?

From each rapid ~i~, the current flows to some unique other rapid ~i'~, except when ~i~ is the last rapid on a given river. It is possible for one river to flow into another; in this case, the current flows from two or more different rapids ~i_1, i_2, \ldots~ to the same downriver rapid ~i'~. Since water always flows downhill, it is not possible for the current to start at some rapid ~i~ and eventually return to the original rapid ~i~.

To make fun precise, we will assign each rapid ~i~ a score ~-1000 \le s_i \le 1000~. You can choose to start your trip at some rapid, then flow with the current to successive rapids until you either get tired and decide to stop, or until you reach the last rapid of a river. The overall score of a trip is the sum of the scores of the rapids that you passed through. You are at some starting rapid and wondering where you should stop to maximize the overall score of your trip.

Sadly, as summer turns to fall, water levels get lower and some sections of the river are no longer navigable. In other words, where previously the current flowed from rapid ~i~ to rapid ~i'~, it now no longer does. It is still possible to start a trip at rapid ~i'~, but any trip that goes to rapid ~i~ must stop there; it can no longer continue to rapid ~i'~.

Input Specification

The first line contains two integers - ~N~ and ~Q~, with ~1 \le N, Q \le 300\, 000~.

This is followed by ~N~ lines that describe the initial state of the rivers. The ~i~'th such line contains two integers ~p_i\ (0 \le p_i \le N)~ and ~s_i\ (-1000 \le s_i \le 1000)~. If ~p_i~ is ~0~, then rapid ~i~ is at the end of a river. Otherwise, ~p_i~ indicates the next downriver rapid that rapid ~i~ flows into. ~s_i~ is the fun score of the ~i~'th rapid.

This is followed by ~Q~ lines that describe changes to the water levels over time and queries. Each of these ~Q~ lines contains two integers ~c\ (1 \le c \le 2)~, ~x\ (1 \le x \le N)~. If ~c~ is ~1~, then this line indicates that rapid ~x~ now becomes the end of a river (i.e. it no longer flows to any other rapid). In this case, it is guaranteed that rapid x was not already the end of a river. If ~c~ is ~2~, then this query asks you to output the maximum amount of fun that can be obtained by starting your trip at rapid ~x~.

Output Specification

Output one line for each query with ~c = 2~, indicating the maximum fun you can have for that query. Output should be in the same order as the queries appear in the input.

Sample Input 1

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

Sample Output 1

10
5

Sample Input 2

5 5
0 5
1 -1
2 5
0 3
2 0
2 3
1 2
2 3
2 4
2 2

Sample Output 2

9
5
3
-1