연세 마스크 공장

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

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

각 공간별로 정수 pi가 할당되어 있는데, pi가 양수면 만큼 지하 공간으로부터 마스크를 매 초마다 pi 개를 받고, 음수면 매 초마다 -pi개 만큼 지하 공간으로 보내야 한다. 또한, 각 통로별로 매 초마다 최소 보내야 하는 마스크의 개수 si, 보낼 수 있는 마스크의 최대 개수 ei가 주어진다.

마스크를 생산하는 공간과 지하 공간은 매 초마다 마스크를 보낼 때 해당 공간의 마스크의 개수에 변동 사항이 없어야 한다.

이렇게 했을 때, 각각의 통로별로 몇 개의 마스크를 보내야 하는지 구하여라.

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

N M
p1 . . . pN
u1 v1 s1 e1
. . . . . .
uM vM sM eM

첫 번째 줄에 답이 있는 경우에는 1, 답이 없는 경우에는 -1을 출력한다.

답이 있는 경우, M개의 줄에 걸쳐 통로별로 매 초마다 보내야 하는 마스크의 개수를 번호 순서대로 출력하시오. 만약에 답이 여러 개인 경우 가능한 아무 경우나 출력하면 된다.

• 1 ≤ N ≤ 200.
• 0 ≤ M ≤ $\min(\frac{N(N-1)}{2},1000)$
• -10,000,000 × max(min(N-1, M), 1) ≤ pi ≤ 10,000,000 × max(min(N-1, M), 1)
• 1 ≤ ui, vi ≤ N, ui ≠ vi. (1 ≤ i ≤ M)
• 0 ≤ si ≤ ei ≤ 10,000,000. (1 ≤ i ≤ M)