Yonsei Mask Factory

Time limit1sMemory limit1024 MB

Summary

Assign each one-way passage a flow between its minimum s_i and maximum e_i so every site's net flow matches p_i, or report that it is impossible.

Level: Medium6 of 10
Topics: Graph, BFS, DFS
Solved: No attempts yet

Problem

Yonsei University built a mask factory to prepare for COVID-19.

The factory has $N$ production sites and $M$ one-way passages connecting them. There is also an underground space that sends masks to each site or receives masks from it. No two distinct sites are connected by more than one passage, and no site is connected to itself.

Each site $i$ has an integer $p_i$ . If $p_i$ is positive, the site receives $p_i$ masks per second from the underground space. If $p_i$ is negative, the site sends $-p_i$ masks per second to the underground space. Each passage $i$ is given a minimum number of masks $s_i$ and a maximum number of masks $e_i$ that may be sent per second.

The production sites and the underground space must keep the number of masks they hold unchanged every second.

Find how many masks each passage must carry per second under these conditions.

Input

The input is given as follows.

N M
p_1 ... p_N
u_1 v_1 s_1 e_1
...
u_M v_M s_M e_M

Output

On the first line, print 1 if a valid answer exists and -1 if it does not.

If a valid answer exists, print $M$ lines. The $i$ -th line contains the number of masks passage $i$ carries per second. If several answers exist, print any one of them.

Constraints

$1 \le N \le 200$ .
$0 \le M \le \min(\frac{N(N-1)}{2},1000)$
$-10{,}000{,}000 \times \max(\min(N-1, M), 1) \le p_i \le 10{,}000{,}000 \times \max(\min(N-1, M), 1)$
$1 \le u_i, v_i \le N$ , $u_i \ne v_i$ ( $1 \le i \le M$ )
$0 \le s_i \le e_i \le 10{,}000{,}000$ ( $1 \le i \le M$ )

Examples5

Example 1

Input

6 6
-2 2 -2 2 -2 2
1 2 2 4
2 3 4 6
3 4 3 5
4 5 5 7
5 6 1 3
6 1 3 5

Expected output

Example 2

Input

6 6
-2 2 -2 2 -2 2
1 2 2 4
2 3 4 6
3 4 3 5
4 5 5 7
5 6 1 2
6 1 3 5

Expected output

-1

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

Example 5

Input

Expected output