# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Tahsin and Tree

Tahsin loves graph theory very much. He is specialy fond of trees. For his upcoming birthday his friends decided to gift him a tree, lets call it birthday tree. Birthday tree consists of **n** node numbered **1** to **n**, having a light in every node. Initialy some of the light is turned on and some are turned off. Root of the tree is **1**.

The tree has a special property, when a node is toggled, all the children of the node is also toggled. So if you toggle the node **i**, you also toggle the children of **i** and so on.

In order to help Tahsin understand the tree better, you are going help him process **q** queries.

## Input

Input starts with **T** ( **1 <= T <= 5** ).

The first line of every test contains two integers **n** and **q**. ( **1 <= n < q <= 10 ^{5}** ). The second line contains

**n**integer

**a**,

_{1}**a**, …,

_{2}**a**, where

_{n}**a**is the initial state of the node

_{i}**i**. Each of the next

**n-1**lines contains two integer

**u**,

_{i}**v**, (

_{i}**1 <= u**), meaning there is an edge between

_{i}, v_{i}<= n**u**and

_{i}**v**.

_{i}Each of the next **q** line contains an integer **x** ( **1 <= x <= n** ), the node to be toggled.

**Constraints**

**n**, **q** ( **1 <= n < q <= 100000** ).

## Output

For each case, after processing all the queries, print **n** integer **b _{1}**,

**b**, …,

_{2}**b**, denoting the status of the node.

_{n}See the sample test case for input output format.

## Samples

Input | Output |
---|---|

1 4 1 0 1 1 0 1 4 2 1 3 1 1 | Case 1: 1 0 0 1 |

#### CLown1331

→

Login to submit