Colored Constraints

Input

The first line contains three integers $n$, $m$, and $k$ (1 \leq n \leq 2 \cdot 10^5, 0 \leq m \leq 2 \cdot 10^5, 1 \leq k \leq 2 \cdot 10^5) — the number of vertices, edges, and colors.

The second line contains a binary string $a$ of length $n$, where a_i is the initial bit of vertex $i$.

The third line contains $n$ integers w_1,w_2,\ldots,w_n (0 \leq w_i \leq 10^9) — the costs of changing the bits.

Each of the next $m$ lines contains four integers $u$, $v$, $b$, and $c$ (1 \leq u,v \leq n, b \in \{0,1\}, 1 \leq c \leq k). This describes an edge of color $c$ between vertices $u$ and $v$ imposing the constraint x_u \oplus x_v=b.

The graph may contain parallel edges and self-loops. Some colors may not occur among the edges.

Output

Print $k$ integers.

The integer at position $c$ must be the minimum cost after removing all edges of color $c$, or $-1$ if the remaining constraints cannot all be satisfied.

Examples

Note

In the first example, after removing the edges of colors $1$, $2$, and $3$, you can choose the final bits 100, 110, and 000, respectively. The minimum costs are 5+2=7, $5$, and $2$.

In the second example, removing color $1$ leaves two identical constraints x_1=x_2. It is enough to change the bit of the first vertex at a cost of $4$. Removing color $2$ or color $3$, which is absent from the graph, leaves a self-loop requiring x_1 \oplus x_1=1, which is impossible.

In the third example, there are no edges. For each color, all initial bits can be left unchanged, so both answers are $0$.

Scoring

1. $20$ points — k=1.

2. $40$ points — n \leq 16, m \leq 30, k \leq 10.

3. $60$ points — n,m,k \leq 2000.

4. $80$ points — k \leq 20.

5. $80$ points — b=0 for every edge.

6. $100$ points — w_i=0 for every vertex.

7. $120$ points — no additional constraints.