Delay the Evil: Maximizing Queries on a Logic Tree

Consider a full binary tree called the logic tree with 2N-1 nodes: there are exactly N leaves and N-1 internal nodes. Each internal node has exactly two children. Each leaf contains a boolean variable (with possible values True or False), and each internal node holds a logical operator, either AND or OR.

The value of an internal node is computed from the values of its two children using the operator at that node. For example, if a node has operator \(\text{AND}\), its value is the logical AND of its two children; if it has operator \(\text{OR}\), its value is the logical OR of its two children.

An evil organization wishes to know the value at the root. They have prepared an inquiry sequence \(\{P_i\}_{i=1}^{N}\) which is a permutation of the N leaves. They query the leaves sequentially according to the sequence. However, if at any point the value at the root can be determined from the already queried leaves (taking into account short‐circuit evaluation—for example, in \(x \text{ AND } y\), if \(x\) is known to be False then the value of \(y\) is not needed), they will skip unnecessary queries.

You have the power to assign a boolean value to each leaf. Your primary objective is to force the evil organization to make as many queries as possible (i.e. maximize the number of leaf inquiries). On this basis, you should also try to make the root's value as True as possible.

One way to force maximum queries is to assign the leaves so that no short‐circuiting happens. Notice that for an AND operator, if both children are True, then neither child can determine the operator's result early; whereas for an OR operator, if both children are False, then evaluating just one child is not enough to determine the result. (For the special case when \(N=1\), the tree has only one node, and you may simply assign it True.)

We assume that the tree is given in heap order. Specifically:

• The first line of input is an integer \(N\) (N \ge 1).
• The tree has \(2N-1\) nodes. The internal nodes are numbered \(1,2,\dots, N-1\) and the leaves are numbered \(N, N+1, \dots, 2N-1\). For an internal node with index \(i\), its left child is at index \(2i\) and its right child is at index \(2i+1\).
• The second line contains \(N-1\) strings: each is either AND or OR, representing the operators at internal nodes \(1\) to \(N-1\) respectively.
• The third line contains a permutation of the integers \(1\) to \(N\) indicating the inquiry order of the leaves (where leaf \(i\) corresponds to the node with index \(i+N-1\) in the tree).

Your task is to output a valid assignment of boolean values for the N leaves (in order from leaf 1 to leaf N). The assignment must force the evil organization to query as many leaves as possible. To achieve this, for every internal node:

• If its operator is \(\text{AND}\), assign both of its children True (so that the gate's result is not determined until both are known).
• If its operator is \(\text{OR}\), assign both of its children False (so that the gate's result is not determined until both are known).

Note that this rule is applied to the leaf whose direct parent is the internal node. In the case \(N=1\) (a single-node tree), simply output True.

Input Format:

N
op[1] op[2] ... op[N-1]
P[1] P[2] ... P[N]

Output Format:

V[1] V[2] ... V[N]

Here, each V[i] is either 1 (for True) or 0 (for False). For leaf i (which corresponds to node index \(i+N-1\)), let its parent's operator be given by op[\(\lfloor (i+N-1)/2 \rfloor\)]. Then:

• If op[\(\lfloor (i+N-1)/2 \rfloor\)] is AND, assign V[i]=1.
• If it is OR, assign V[i]=0.

Your solution must produce valid output for all test cases.

inputFormat

The input consists of three lines:

1. The first line contains an integer \(N\) (\(N \ge 1\)).
2. The second line contains \(N-1\) space‐separated strings. Each string is either AND or OR, representing the operator at internal nodes in heap order (nodes 1 to \(N-1\)).
3. The third line contains a permutation of the integers from 1 to \(N\) (space‐separated), which represents the inquiry order of the leaves. Leaf i corresponds to node index \(i+N-1\) of the tree.

outputFormat

Output a single line containing \(N\) space‐separated integers. The \(i\)th integer represents the boolean value assigned to the \(i\)th leaf (use 1 for True and 0 for False).

sample

1

1

1