Magical Subtrees

In Vétyem Woods there is an ancient beech tree called (\text{\huge Ős Vezér}) which can be modeled as a tree with (N) nodes numbered from (0) to (N-1) and (N-1) edges. For every edge (i) ((1 \le i < N)) the tree has an edge connecting node (i) to node (P[i]) with (0 \le P[i] < i). We define (P[0] = -1) and for convenience we let (C[0] = 0). Each edge (i) has a color denoted by (C[i]) where (C[i]) is an integer in ({1,2,\ldots,M}) for (1 \le i < N) (note that different edges might share the same color).

For any node (r) ((0 \le r < N)) define its subtree (T(r)) as the set of nodes satisfying:

1. (r \in T(r)).
2. If (x \in T(r)), then all children of (x) (i.e. all nodes (y) with (P[y] = x)) are in (T(r)).
3. No other nodes are in (T(r)).

A permutation (i.e. reordering) of (T(r)) is given as (v_0, v_1, \ldots, v_{|T(r)|-1}). For every index (i) with (1 \le i < |T(r)|) define [ f(i) = #{,1 \le j < i : C[v_j] = C[v_i]}]. ] Note that by definition (f(1)=0) since the corresponding sequence is empty. This permutation is said to be a magical permutation if:

• (v_0 = r), and
• For every (1 \le i < |T(r)|) we have [ P[v_i] = v_{f(i)}. ]

We say that the subtree (T(r)) is magical if there exists a magical permutation of its nodes. (Note that every singleton subtree is magical by definition.)

Your task is to determine for every node (r) ((0 \le r < N)) whether (T(r)) is magical.

Remark: You are given several examples in the description. For instance, in one example with (N = 18) and (M = 3) using

[ P = [-1,0,0,0,1,1,1,2,2,3,3,3,4,4,5,10,11,11], \quad C = [0,1,2,3,1,2,3,1,3,3,2,1,1,2,2,1,2,3], ]

it turns out that (T(0)) and (T(3)) are not magical, while (T(1)) and (T(14)) are magical.

A helpful hint for solving this problem is to simulate the construction of a magical permutation. Notice that in any such permutation the following holds:

• The first element is \(r\).
• Whenever a node \(u\) (with \(u \neq r\)) is placed at position \(i\) (i.e. \(v_i = u\)), since \(f(i)\) equals the number of occurrences of \(C[u]\) among \(v_1, \ldots, v_{i-1}\), the condition \(P[u] = v_{f(i)}\) forces a relation between the order in which nodes of a given color appear and the position of the parent of \(u\).

A greedy strategy can be used: starting with (v_0 = r), iteratively choose an available node (u) (i.e. one whose parent is already placed) that satisfies [ \text{number of occurrences of } C[u] \text{ among already placed nodes (excluding }v_0\text{)} = \text{position of } P[u] \text{ in the ordering}. ] If such an ordering exists covering all nodes in (T(r)), then the subtree (T(r)) is magical.

inputFormat

The first line contains two integers (N) and (M) separated by a space. The second line contains (N) integers representing the array (P[0], P[1], \ldots, P[N-1]) (with (P[0] = -1) always). The third line contains (N) integers representing the array (C[0], C[1], \ldots, C[N-1]) (with (C[0] = 0) and for (1 \le i < N), (1 \le C[i] \le M)).

It is guaranteed that for every (1 \le i < N), (0 \le P[i] < i).

outputFormat

Output a single line containing a string of (N) characters. The (r)th character (0-indexed) should be '1' if the subtree (T(r)) is magical, and '0' otherwise.

sample

7 3
-1 0 0 1 1 2 2
0 1 2 1 2 3 1

1111111