After much hard work, you find the North Pole to be more than adequately prepared for the upcoming Christmas. However, when you go to ask Santa about his retirement, he reveals that he had tricked you and only wanted you to do his work for him. Furious, you challenge him to a present-making duel on Christmas Eve, with the winner attaining the title of Santa.

During the duel, you are responsible for making presents for a big city with ~N~ families numbered ~1~ to ~N~. In this city, there is a hierarchy structure that indicates the prestige of each family. The prestigious family ~1~ is the most renowned of these families and has every other family somewhere below it. All the other families each have exactly one family directly above them in prestige. At the start, each family has some amount of kids ~c_i~.

To beat Santa, your toy factory must be able to answer the following queries:

1. 1 x v: Through a Christmas miracle, family ~x~ gains ~v~ kids.
2. 2 x v: The kids in family ~x~ and every family below them on the hierarchy become obsessed with a new toy. However, this new toy can only be manufactured in bundles of ~v~. You must count and output the number of families in this group that have a number of kids divisible by ~v~.

As spectators begin to gather in the distance, you must now find a way to answer these queries quickly in order to finally realize your dream of becoming Santa.

Input Specification

The first line of input contains two space-separated integers, ~N~ and ~Q~.

The next line of input contains ~N~ space-separated integers, ~p_1, p_2, ..., p_N~, where ~p_1 = 0~ and ~p_i~ is the family above family ~i~.

The next line of input contains ~N~ space-separated integers, ~c_1, c_2, ..., c_N~.

The next ~Q~ lines of input each contain three space-separated integers, corresponding to one of the above query types.

Output Specification

For each query of type ~2~, output the answer on a separate line.

Constraints

For this problem, you are not required to pass previous subtasks to earn points for a specific subtask.

In all subtasks,

~1 \le N, Q \le 10^5~

~1 \le p_i, x \le N~

~1 \le c_i, v \le 2\cdot 10^4~

At any point, the number of kids a family has will not exceed ~10^7~.

Subtask 1 [10%]

~1 \le N, Q \le 10^3~

Subtask 2 [30%]

For all type ~2~ queries, ~v = 2~.

Subtask 3 [60%]

No additional constraints.

Sample Input

8 9
0 3 4 7 8 5 1 7
17420 6186 13022 9244 7696 3496 17956 3528
1 1 1
2 7 4
2 1 3
1 5 3
1 8 4
2 5 1
1 1 4
1 7 3
2 5 8

Sample Output

5
3
2
1