Mafia

Time limit1sMemory limit1024 MB

Summary

Given accusations of honesty or corruption between cops, count for each queried C the number of size-C corrupt sets consistent with all accusations.

Level: Hard8 of 10
Topics: Graph, Union-find, Combinatorics, Dynamic programming
Solved: No attempts yet

Problem

A mafia has infiltrated the city <insert name here>. This has left the police force of <insert name here> in deep confusion, with accusations of corruption coming from every direction. The city's $N$ cops (numbered from $0$ to $N - 1$ ) have made a number of accusations about other policemen. Each accusation is one of the following:

Police officer $i$ is an honest cop.
Police officer $i$ is a corrupt cop.

An honest cop always tells the truth, while a corrupt cop always lies. In total there have been $M$ accusations.

The chief of police is now trying to fix the situation, starting by determining how many of her police officers are corrupt. She has $G$ different guesses about the number of corrupt cops, and for each such number $C$ she wants to know how many different sets of size $C$ can be corrupt (with all remaining cops honest), given that all accusations are consistent.

Input

The judge reads input in the following format:

line $1$ : N M
line $2$ : A[0] ... A[M - 1]
line $3$ : B[0] ... B[M - 1]
line $4$ : T[0] ... T[M - 1]
line $5$ : G, the number of calls made to guess(C).
line $6$ : C1 ... CG, the parameters of the $G$ calls to guess(C).

Output

The judge writes $G$ lines containing the return values of guess(C).

Constraints

Let $G$ be the number of calls to guess(C).

$N \le 2\,000$
$M \le 70\,000$
$G \le 2\,000$

Examples1

Example 1
Input
```
3 2
1 2
0 1
2 2
4
0 1 2 3
```
Expected output
```
0 1 1 0
```