Problem Description

There are $n$ people, numbered from $1$ to $n$. Person $i \ (2 \le i \le n)$ has a hated person $f_i \ (1 \le f_i < i)$. Person $1$ has no hated person.

On this day, the $n$ people play a voting game. One game consists of $n$ rounds. At the start of the game, no one has been voted out. In each round of the game, the following process is performed:

1. For each person $i$ who has not been voted out, they initially have $a_i$ votes.
2. Then, for each person $i$ who has not been voted out, if they have a hated person and their hated person $f_i$ has not been voted out, then they cast $b_i$ votes for $f_i$.
3. Finally, vote out the person (among those not yet voted out) with the highest number of votes. If there are multiple people with the highest number of votes, vote out the one with the largest index.

The votes in the $n$ rounds of one game are counted independently.

Before the game starts, $q$ events happen. There are two types of events:

1. Given $p, x, y$, modify $(a_p, b_p)$ to $(x, y)$.
2. Xiaoming wants to know: given two people $c, d$, if a game is played at this moment, which one of the two will be voted out first.

As Xiaoming’s friend, can you help him?

Input Format

Read input from standard input.

The first line contains two positive integers $n, q$, representing the number of people and the number of events.

The second line contains $(n-1)$ integers $f_2, f_3, \cdots, f_n$.

The third line contains $n$ integers $a_1, a_2, \cdots, a_n$.

The fourth line contains $n$ integers $b_1, b_2, \cdots, b_n$.

The next $q$ lines each contain three or four integers describing an event. The first positive integer $op$ indicates the type of the event.

• If $op = 1$, then the next three integers are $p, x, y$, meaning modifying $(a_p, b_p)$ to $(x, y)$.
• If $op = 2$, then the next two positive integers are $c, d$. You need to determine, if a game is played now, which of $c$ and $d$ will be voted out first.

Output Format

Write output to standard output.

For each event with $op = 2$, output one line containing one character in 01. If $c$ is voted out first, output 0, otherwise output 1.

5 8
1 2 3 2
1 3 2 1 0
0 4 1 0 0
2 1 3
1 1 0 3
2 2 5
1 1 2 2
2 4 3
2 5 4
2 5 1
2 2 1

0
0
1
1
1
1

Hint

For all testdata:

• $1 \le n, q \le 2 \times 10^5$.
• $\forall \ 2 \le i \le n, \ 1 \le f_i < i$.
• $0 \le a_i, b_i, x, y \le 10^8$.
• $1 \le c, d, p \le n$.
• $c \ne d$.

Translated by ChatGPT 5