There are $n$ people, numbered from $1$ to $n$. Each person $i$ ($2 \le i \le n$) has a person they dislike, $f_i$ ($1 \le f_i < i$), while person $1$ does not dislike anyone.

One day, the $n$ people play a voting game. A single 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 occurs:

1. For every person $i$ who has not been voted out, they initially have $a_i$ votes.
2. Then, for every person $i$ who has not been voted out, if they have a person they dislike and that person $f_i$ has not been voted out, they cast $b_i$ votes for $f_i$.
3. Finally, the person who has not been voted out with the highest number of votes is voted out. If there are multiple people with the same highest number of votes, the one with the largest index is voted out.

The votes are counted independently across the $n$ rounds of a game.

Before the game begins, $q$ events occur. The events are of two types:

1. Given $p, x, y$, update $(a_p, b_p)$ to $(x, y)$.
2. Xiao Ming wants to know, given two people $c$ and $d$, if a game were to be played at this moment, which of the two would be voted out first.

As a friend of Xiao Ming, can you help him?

Input

Read the data from standard input.

The first line contains two positive integers $n$ and $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 event.

• If $op=1$, it is followed by three integers $p, x, y$, meaning to update $(a_p, b_p)$ to $(x, y)$.
• If $op=2$, it is followed by two positive integers $c, d$, and you need to determine which of $c$ and $d$ would be voted out first if a game were played at this moment.

Output

Output to standard output.

For each $op=2$ event, output a single 01 character on a new line. If $c$ is voted out first, output 0; otherwise, output 1.

Examples

Examples 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

Subtasks

For all test data:

• $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$