In a distant land, there are islands. Each island has a value of accessibility denoted by . You are a bridge building contractor that has been given the task of trying to connect the islands by building bridges. However, because you want to save resources, you have decided to only build bridges such that the **XOR** of the accessibilities of the islands you connect with a bridge, is less than or equal to . That is, you will build a bridge between island and if and only if . Now, your boss has given you queries, each asking if islands and will be connected by the bridges.

#### Constraints

For all subtasks:

##### Subtask 1 [5%]

##### Subtask 2 [5%]

##### Subtask 3 [10%]

for some non-negative integer and

##### Subtask 4 [80%]

No additional constraints.

#### Input Specification

The first line contains three space-separated integers .

The second line contains space-separated integers, , denoting the accessibility of island .

The next lines contain two space-separated integers and , a query asking if islands and are connected by a set of bridges.

#### Output Specification

For each of the queries, print `YES`

if the islands are connected, or `NO`

otherwise.

#### Sample Input

```
4 5 4
1 2 3 10
1 4
2 3
3 4
1 2
```

#### Sample Output

```
NO
YES
NO
YES
```

## Comments

how can I deal with bad_alloc ??

You're using too much memory. You can pass the first two subtasks by making your array sizes smaller, but your approach won't work for subtasks 3 and 4.

Can anyone provide some ideas to approach this problem? Thanks.

An editorial will be released sometime today or tomorrow.