연세 마스크 공장

연세대는 코로나 19에 대비하기 위해 마스크 공장을 만들었다.

공장에는 마스크를 생산하는 $N$개의 공간이 있고, 이들을 잇는 $M$개의 단방향 통로가 있다. 지하 공간도 있어서 각 공간에 마스크를 보내거나 각 공간으로부터 마스크를 받는다. 서로 다른 두 공간 사이에 두 개 이상의 통로가 있는 경우와, 같은 공간을 잇는 통로가 있는 경우는 없다.

각 공간 $i$에는 정수 $p_i$가 할당되어 있다. $p_i$가 양수이면 지하 공간으로부터 매 초 $p_i$개의 마스크를 받는다. 음수이면 매 초 $-p_i$개의 마스크를 지하 공간으로 보낸다. 각 통로 $i$에는 매 초 보내야 하는 마스크의 최소 개수 $s_i$와 보낼 수 있는 최대 개수 $e_i$가 주어진다.

마스크를 생산하는 공간과 지하 공간은 매 초 마스크를 주고받은 뒤에도 보관 중인 마스크의 개수가 변하지 않아야 한다.

이 조건을 만족할 때 각 통로가 매 초 보내야 하는 마스크의 개수를 구하라.

입력은 다음과 같이 주어진다.

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

첫 번째 줄에 답이 있으면 1, 없으면 -1을 출력한다.

답이 있으면 $M$개의 줄에 걸쳐 통로 $i$가 매 초 보내야 하는 마스크의 개수를 번호 순서대로 출력한다. 답이 여러 개이면 그중 아무 것이나 출력해도 된다.

• $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$)