Problem: Ron is a master of a ramen shop.

Recently, he has noticed some customers wait for a long time. This has been caused by lack of seats during lunch time. Customers loses their satisfaction if they waits for a long time, and even some of them will give up waiting and go away. For this reason, he has decided to increase seats in his shop. To determine how many seats are appropriate, he has asked you, an excellent programmer, to write a simulator of customer behavior.

Customers come to his shop in groups, each of which is associated with the following four parameters:

* Ti : when the group comes to the shop
* Pi : number of customers
* Wi : how long the group can wait for their seats
* Ei : how long the group takes for eating



The i-th group comes to the shop with Pi customers together at the time Ti . If Pi successive seats are available at that time, the group takes their seats immediately. Otherwise, they waits for such seats being available. When the group fails to take their seats within the time Wi (inclusive) from their coming and strictly before the closing time, they give up waiting and go away. In addition, if there are other groups waiting, the new group cannot take their seats until the earlier groups are taking seats or going away.

The shop has N counters numbered uniquely from 1 to N. The i-th counter has Ci seats. The group prefers “seats with a greater distance to the nearest group.” Precisely, the group takes their seats according to the criteria listed below. Here, SL denotes the number of successive empty seats on the left side of the group after their seating, and SR the number on the right side. SL and SR are considered to be infinity if there are no other customers on the left side and on the right side respectively.

1. Prefers seats maximizing min{SL, SR}.
2. If there are multiple alternatives meeting the first criterion, prefers seats maximizing max{SL, SR}.
3. If there are still multiple alternatives, prefers the counter of the smallest number.
4. If there are still multiple alternatives, prefers the leftmost seats.



When multiple groups are leaving the shop at the same time and some other group is waiting for available seats, seat assignment for the waiting group should be made after all the finished groups leave the shop.

Your task is to calculate the average satisfaction over customers. The satisfaction of a customer in the i-th group is given as follows:

* If the group goes away without eating, -1.
* Otherwise, (Wi - ti )/Wi where ti is the actual waiting time for the i-th group (the value ranges between 0 to 1 inclusive).



Input

The input consists of multiple datasets.

Each dataset has the following format:


N M T
C1 C2 ... CN
T1 P1 W1 E1
T2 P2 W2 E2
...
TM PM WM EM


N indicates the number of counters, M indicates the number of groups and T indicates the closing time. The shop always opens at the time 0. All input values are integers.

You can assume that 1 ≤ N ≤ 100, 1 ≤ M ≤ 10000, 1 ≤ T ≤ 109, 1 ≤ Ci ≤ 100, 0 ≤ T1 < T2 < ... < TM < T, 1 ≤ Pi ≤ max Ci, 1 ≤ Wi ≤ 109 and 1 ≤ Ei ≤ 109.

The input is terminated by a line with three zeros. This is not part of any datasets.

Output

For each dataset, output the average satisfaction over all customers in a line. Each output value may be printed with an arbitrary number of fractional digits, but may not contain an absolute error greater than 10-9.

Example

Input

1 4 100
7
10 1 50 50
15 2 50 50
25 1 50 50
35 3 50 50
1 2 100
5
30 3 20 50
40 4 40 50
1 2 100
5
49 3 20 50
60 4 50 30
1 2 100
5
50 3 20 50
60 4 50 30
2 3 100
4 2
10 4 20 20
30 2 20 20
40 4 20 20
0 0 0


Output

0.7428571428571429
0.4285714285714285
0.5542857142857143
-0.1428571428571428
0.8000000000000000

Solution (in CPP):

Solution:
#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

class Data
{
public:
    long long time;
    int id;
    int kind; // 0 : 客の来店
              // 1 : 待ち時間が長く帰宅
              // 2 : 食事を終えて帰宅
              // 3 : 閉店
    Data(long long time0, int id0, int kind0){
        time = time0;
        id = id0;
        kind = kind0;
    }
    bool operator< (const Data& d) const{
        return make_pair(time, kind) < make_pair(d.time, d.kind);
    }
};

pair<int, int> findCounter(const vector<vector<bool> >& used, int num)
{
    int n = used.size();

    int sl = -1;
    int sr = -1;
    pair<int, int> ret(-1, -1);
    for(int i=0; i<n; ++i){
        int m = used[i].size();
        int size = 0;
        for(int j=0; j<m; ++j){
            if(used[i][j]){
                size = 0;
                continue;
            }

            ++ size;
            if(size >= num){
                int sl2;
                int sr2;
                int k;
                if(j+1 == size && j == m-1){
                    sl2 = sr2 = INT_MAX;
                    k = 0;
                }else if(j+1 == size){
                    sl2 = INT_MAX;
                    sr2 = size - num;
                    k = 0;
                }else if(j == m-1){
                    sl2 = size - num;
                    sr2 = INT_MAX;
                    k = j - num + 1;
                }else{
                    sl2 = (size - num) / 2;
                    sr2 = (size - num + 1) / 2;
                    k = j - size + (size - num) / 2 + 1;
                }
                if(min(sl2, sr2) > min(sl, sr) || (min(sl2, sr2) == min(sl, sr) && max(sl2, sr2) > max(sl, sr))){
                    sl = sl2;
                    sr = sr2;
                    ret = make_pair(i, k);
                }
            }
        }
    }

    return ret;
}

int main()
{
    for(;;){
        int n, m, closeTime; // カウンター数、グループ数、閉店時間
        cin >> n >> m >> closeTime;
        if(n == 0)
            return 0;

        vector<int> counter(n); // 各カウンターの席の数
        for(int i=0; i<n; ++i)
            cin >> counter[i];
        vector<vector<bool> > used(n); // 使用中のカウンターの席
        for(int i=0; i<n; ++i)
            used[i].assign(counter[i], false);

        vector<int> come(m), num(m), wait(m), eat(m); // 来店時間、各グループの客の人数、最大待ち時間、食事時間
        for(int i=0; i<m; ++i)
            cin >> come[i] >> num[i] >> wait[i] >> eat[i];

        multiset<Data> ms;
        ms.insert(Data(closeTime, -1, 3));
        for(int i=0; i<m; ++i){
            ms.insert(Data(come[i], i, 0));
            ms.insert(Data(come[i] + wait[i], i, 1));
        }

        queue<int> q;                         // 待っているグループ
        vector<pair<int, int> > sit(m);       // 各グループが使っているカウンターの位置
        vector<double> satisfaction(m, -1.0); // 各グループの満足度
        bool isClose = false;                 // 閉店時間を過ぎたかどうか
        while(!ms.empty()){
            long long time = ms.begin()->time;
            while(!ms.empty() && ms.begin()->time == time){
                Data d = *ms.begin();
                ms.erase(ms.begin());

                if(d.kind == 0){
                    q.push(d.id);
                }else if(d.kind == 2){
                    for(int i=0; i<num[d.id]; ++i)
                        used[sit[d.id].first][sit[d.id].second + i] = false;
                }else if(d.kind == 3){
                    isClose = true;
                }
            }
            if(isClose)
                break;

            while(!q.empty()){
                int id = q.front();
                if(time > come[id] + wait[id]){
                    q.pop();
                    continue;
                }

                pair<int, int> pos = findCounter(used, num[id]);
                if(pos.first == -1){
                    if(time == come[id] + wait[id]){
                        q.pop();
                        continue;
                    }
                    break;
                }

                q.pop();
                for(int i=0; i<num[id]; ++i)
                    used[pos.first][pos.second + i] = true;
                sit[id] = pos;
                satisfaction[id] = (wait[id] - (time - come[id])) / (double)wait[id];
                ms.insert(Data(time + eat[id], id, 2));
            }
        }

        double ret = 0.0;
        for(int i=0; i<m; ++i)
            ret += satisfaction[i] * num[i];
        ret /= accumulate(num.begin(), num.end(), 0);
        printf("%.10f\n", ret);
    }
}