라멘 가게 좌석 배정

론은 라멘 가게를 운영한다.

최근 점심시간에 자리가 모자라 손님이 오래 기다린다는 사실을 알게 됐다. 오래 기다린 손님은 만족도가 떨어지고, 기다리다 그냥 돌아가는 손님도 있다. 그래서 좌석을 늘리기로 하고, 몇 자리가 적당한지 판단하려고 손님의 행동을 재현하는 시뮬레이터를 만들어 달라고 부탁했다.

손님은 그룹 단위로 오고, 각 그룹은 네 값으로 정해진다.

• $T_i$: 그룹이 가게에 오는 시각
• $P_i$: 그룹의 인원수
• $W_i$: 그룹이 자리를 기다릴 수 있는 시간
• $E_i$: 그룹이 식사에 쓰는 시간

$i$번 그룹은 시각 $T_i$에 $P_i$명이 함께 온다. 그 시각에 한 카운터에서 연속한 빈 좌석 $P_i$개를 잡을 수 있으면 곧바로 앉는다. 그렇지 않으면 자리가 날 때까지 기다린다. 도착 시각으로부터 $W_i$ 이내(끝값 포함)이면서 폐점 시각보다 앞선 시각에 앉지 못하면, 그 그룹은 기다리기를 포기하고 돌아간다. 또 먼저 온 그룹이 기다리고 있으면, 나중에 온 그룹은 앞선 그룹이 모두 앉거나 돌아갈 때까지 자리를 잡을 수 없다.

가게에는 $1$번부터 $N$번까지 번호가 붙은 카운터가 있고, $i$번 카운터에는 좌석 $C_i$개가 한 줄로 놓여 있다. 그룹은 다른 손님과 멀리 떨어진 자리를 좋아한다. 정확히는 아래 기준으로 자리를 고른다. 그룹이 앉은 뒤 그룹의 왼쪽으로 이어진 빈 좌석 수를 $S_L$, 오른쪽으로 이어진 빈 좌석 수를 $S_R$이라고 하자. 왼쪽에 다른 손님이 하나도 없으면 $S_L$을 무한대로 보고, 오른쪽에 다른 손님이 하나도 없으면 $S_R$을 무한대로 본다.

1. $\min(S_L, S_R)$이 가장 큰 자리를 고른다.
2. 그런 자리가 여럿이면 $\max(S_L, S_R)$이 가장 큰 자리를 고른다.
3. 그래도 여럿이면 번호가 가장 작은 카운터를 고른다.
4. 그래도 여럿이면 가장 왼쪽 자리를 고른다.

여러 그룹이 같은 시각에 식사를 마치고 나가고 그때 기다리는 그룹이 있으면, 나갈 그룹이 모두 나간 뒤에 기다리는 그룹의 자리를 정한다.

손님 한 명의 만족도는 다음과 같다.

• 식사하지 못하고 돌아간 그룹의 손님은 $-1$이다.
• 그 밖에는 $(W_i - t_i)/W_i$이다. 여기서 $t_i$는 $i$번 그룹이 실제로 기다린 시간이고, 이 값은 $0$ 이상 $1$ 이하다.

전체 손님의 만족도 평균을 구하라.

입력은 여러 데이터 집합으로 이루어진다. 데이터 집합 하나의 형식은 다음과 같다.

N M T
C_1 C_2 ... C_N
T_1 P_1 W_1 E_1
T_2 P_2 W_2 E_2
...
T_M P_M W_M E_M

$N$은 카운터 수, $M$은 그룹 수, $T$는 폐점 시각이다. 가게는 항상 시각 $0$에 문을 연다. 입력의 모든 값은 정수다.

$1 \le N \le 100$, $1 \le M \le 10000$, $1 \le T \le 10^9$, $1 \le C_i \le 100$, $0 \le T_1 < T_2 < \dots < T_M < T$, $1 \le P_i \le \max_j C_j$, $1 \le W_i \le 10^9$, $1 \le E_i \le 10^9$이다.

세 수가 모두 $0$인 줄이 나오면 입력이 끝난다. 이 줄은 데이터 집합이 아니다.

데이터 집합마다 전체 손님의 만족도 평균을 한 줄에 출력한다. 소수점 아래 $10$자리로 반올림해 정확히 $10$자리를 출력한다.