Elimination Voting Game

You are given \(n\) people numbered from \(1\) to \(n\). For each person \(i\) where \(2 \le i \le n\), there is a person \(f_i\) such that \(1 \le f_i < i\) whom person \(i\) dislikes; person \(1\) has no such person. Initially, each person \(i\) is associated with two values: an initial vote count \(a_i\) and a bonus vote \(b_i\) (for person \(1\), the bonus value is unused as they have no one they dislike).

A game is played among these \(n\) people in \(n\) rounds. At the beginning of every round, the remaining (i.e. not yet eliminated) persons receive votes as follows:

1. Each remaining person \(i\) is given \(a_i\) votes.
2. Then, for each remaining person \(i\) with \(i \ge 2\), if the person they dislike, i.e. person \(f_i\), is also still in the game, person \(i\) casts an extra \(b_i\) votes to person \(f_i\). (Note that each person can contribute bonus votes only to the one person they dislike.)
3. At the end of the round, the person among those still in the game with the maximum number of votes is eliminated. If there is a tie, the person with the largest index is eliminated.

The rounds are independent in terms of vote counting; that is, votes do not carry over between rounds. After \(n\) rounds, everyone is eliminated, and thus an elimination order is formed.

Before the game starts, \(q\) events occur. There are two types of events:

• Type 1: An update event. Given \(p, x, y\), update \(a_p = x\) and \(b_p = y\).
• Type 2: A query event. Given two persons \(c\) and \(d\), if a game were played immediately using the current \(a_i\) and \(b_i\) values, determine which one of the two persons would be eliminated earlier (i.e. in an earlier round).

Your task is to process these \(q\) events sequentially. For each query event, simulate the game with the current configuration and output the person (\(c\) or \(d\)) who is eliminated earlier.

All formulas are in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n, q \le \text{constraints})\) indicating the number of people and the number of events.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\), denoting the initial votes.

The third line contains \(n\) integers \(b_1, b_2, \dots, b_n\). (Note that for person \(1\), \(b_1\) is given but never used.)

The fourth line contains \(n-1\) integers \(f_2, f_3, \dots, f_n\), where \(f_i\) denotes the person that person \(i\) dislikes.

The following \(q\) lines each describe an event in one of the following formats:

• 1 p x y : Update event. Set \(a_p = x\) and \(b_p = y\).
• 2 c d : Query event. For persons \(c\) and \(d\), determine who is eliminated earlier if a game is played with the current configuration.

outputFormat

For each query event (type 2), output a single line containing the number of the person (either \(c\) or \(d\)) who is eliminated earlier in the game.

sample

5 5
3 1 4 1 5
0 1 1 2 2
1 1 1 3
2 2 3
1 3 10 10
2 1 3
1 5 0 0
2 4 5

3
1
4

</p>