시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 39 13 13 37.143%

문제

연세대는 코로나 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 ≤ Nui ≠ vi. (1 ≤ i ≤ M)
  • 0 ≤ si ≤ ei ≤ 10,000,000. (1 ≤ i ≤ M)

예제 입력 1

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

예제 출력 1

1
3
5
3
5
3
5

예제 입력 2

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

예제 출력 2

-1

예제 입력 3

1 0
0

예제 출력 3

1

예제 입력 4

1 0
1

예제 출력 4

-1

예제 입력 5

5 5
0 0 0 0 0
1 2 0 0
2 3 0 0
3 4 0 0
4 5 0 0
5 1 0 0

예제 출력 5

1
0
0
0
0
0