#216002. [TOPC 2021] A Hard Problem

You are given a simple undirected graph consisting of nodes and edges. The nodes are numbered from 1 to , and the edges are numbered from 1 to . Node has a non-negative integer value and the weight of edge is defined as where is the exclusive-or operator (equivalent to ^ in C) and is the number of set bits in the binary representation of non-negative integer .

The node values must satisfy constraints. Each of the constraints can be represented as a 5-tuple .

• if , then
• if , then

where the function returns the -th least significant bit of . For examples, is 1 and . In the C programming language, can be computed by ((x >> i) & 1U) if is a 32-bit unsigned integer and is a non-negative integer at most 31.

Unfortunately, some node values are missing now. Your task is to assign new values to them to minimize without violating any given constraint. Please write a program to help yourself to complete this task.

The input consists of five parts. The first part contains one line, and that line contains two positive integers and . is the number of nodes, and is the number of edges. The second part contains lines. Each of them contains two integers and , indicating an edge of the given graph. The third part contains one line. That line consists of space-separated integers . For any , if the node value is missing, will be -1; otherwise, is . The fourth part contains one integer , indicating the number of constraints. The fifth part contains lines, and each of them contains five space-separated integers indicating that is a constraint.

Output an integer which is the minimum value under the constraints. If it is not possible to satisfy all the constraints, output -1.

样例输入 1

4 4
1 3
1 2
3 2
0 3
-1 -1 60091 51514
2
1 2 0 1 5
0 2 6 0 15

样例输出 1

13

样例输入 2

3 2
0 1
1 2
-1 -1 -1
2
1 2 0 1 5
0 1 5 2 0

样例输出 2

-1