Mafia

A mafia has infiltrated the city <insert name here>. This has made the police force of <insert name here> very confused, with accusations of corruption being made in every direction. The city’s $N$ cops (which are numbered between $0$ and $N - 1$) has made a number of accusations about other policemen. Each accusation is either:

1. Police number $i$ is an honest cop.

2. Police number $i$ is a corrupt cop.

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

The chief of police is now trying to fix the situation, starting with determining how many of her police men 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 (where all the remaining cops are honest), given that all accusations are consistent.

Example

Let there be $N = 3$ cops, and two accusations. The first cop accused the second cop of being corrupt, and the second cop accused the third cop of being corrupt. There are two cases: either the second cop is corrupt or not.

If the second cop is corrupt, then he lies (so the third cop is honest), and the first cop did not lie (meaning he too is honest).

If the second cop is honest, then the third cop must certainly be corrupt (since the second cop’s accusation is now true), and the first cop must be corrupt (since his accusation was a lie).

There are thus two possible subsets of corrupt cops: $\{ 1, 3\} $ and $\{ 2\} $, meaning there is one subset of size 1 and one of size 2.

Task

Your task is to compute, for each of the police chief’s guesses $C$, in how many ways there can be exactly $C$ corrupt cops. You should implement the functions cops(N, M, A, B, T) and guess(C).

• cops(N, M, A, B, T) - this function will be called exactly once by the judge at the start of the execution.

  • N: the number of cops.

  • M: the number of accusations.

  • A: an array with $M$ elements. A[i] ($0 \le i < N$) contains the number of the cop who made the $i$:th accusation.

  • B: an array with $M$ elements. B[i] ($0 \le i < N$) contains the number of the cop who is the target of the $i$:th accusation.

  • T: an array with $M$ elements. T[i] ($0 \le i < N$) contains 1 or 2 if the $i$:th accusation is of type 1 or 2, respectively.

  • The function has no return value.

• guess(C) - this function will be called once for every guess.

  • C: a number between $0$ and $N$; the guess of the police chief.

  • The return value of the function will never exceed $10^{18}$.

  • The function should return the number of possible sets of corrupt cops of size $C$, where the remaining cops are honest.

A code skeleton containing the functions to be implemented, together with a sample grader, can be found at http://progolymp.se/uploads/kattis-attachments/mafia.zip.

Subtasks

The problem consists of a number of subtasks. Each subtask gives some amount of points, and to pass the subtask you must pass all the test cases in the subtask.

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

Input format

The sample 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 format

The sample judge will write $G$ lines with the return values of guess(C).

3 2
1 2
0 1
2 2
4
0 1 2 3

0 1 1 0